huyifan951124
- 浏览: 83607 次
-
最新评论
-
coralsea：
试试log4jdbc
SpringMVC+MyBatis+Log4j输出sql语句 -
hellotieye：
题目是什么意思？？？
NYOJ118 求次小生成树
文章列表
题目大意：让你求1-n里面有几个素数(1<=n&&n<=1e11)。
算法思路：这里的n非常大，因此我们用Meisell-Lehmer算法求1-n的个数，该算法的复杂度为n^(2/3)
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
const int N = 5e6 + 2;
bool np[N];
int prime[N], pi[N];
int getprime()
{
int cnt = 0;
...
hdu5444 模拟
- 博客分类：
- 算法
题目大意：给你一棵树的先序遍历和中序遍历，让你求给定点的位置。
算法思路：根据中序遍历和先序遍历的特点，模拟即可（这模拟模了我快三小时，我也是醉了）。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
#define MAXN 1005
string str[MAXN];
int t,n,q;
int a[MAXN],b[MAXN];
bool visited[MAXN];
int mai ...
hdu5446 中国剩余定理+lucas定理
- 博客分类：
- 算法
题目大意：让你求出C(n,m)%M的值。
算法思路：此题的 n和m非常大，因此不能用快速幂取模，这里我们只能用lucas定理，但lucas定理有一个条件，要求C(n,m)%M的M必须要为素数，因此，我们又要用到中国剩余定理。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
int t,k;
LL nn,mm;
LL p[15],fac[100050],inv[100050];
LL pow_ ...
hdu5443 线段树求区间最大
- 博客分类：
- 算法
题目大意：给你一些水源，让你求给定区间当中的最大值。
算法思想：线段树求区间最大。
#include<iostream>
#include<cstdio>
using namespace std;
typedef struct Node
{
int value;
int l;
int r;
};
Node tree[1050*4];
int a[10050];
void build_tree(int v,int l,int r)
{
tree[v].l=l;
tree[v].r=r;
...
csu1120 最长上升公共子序列
- 博客分类：
- 算法
题目大意：中文题。
算法思路：最长上升公共子序列。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1050
int a[MAXN],b[MAXN];
int n,m;
int dp[MAXN];
int main()
{
int t,k;
scanf("%d",&t);
while(t--)
{
memset(dp,0, ...
2016年湖南省第十二届大学生程序设计竞赛总结
- 博客分类：
- 总结
过题数:1
排名：52
奖项：三等奖。
今年的题可谓是把我们都吓傻了，比赛开始前我们匆匆的浏览一下题目，发现都不好解决，于是我的两个队友先去做A题，而我则看到地铁这题应该可以做，感觉跑一遍spfa就可以过(事实证明这样做是肯定会超时，需要用优先队列优化，赛后看了一下别人的题解，发现大多数的人都是用dijkstra+优先队列做的)，于是一直卡在这两题，后来队友做了大概一个多小时发现A题不好做，于是我让其中一个队友去做一道计算几何，因为这道题感觉很像之前训练的一道题目，而且也准备了模板。之后我们看了一下榜单，发现G题有很多人过，于是我和剩下的一名队友转去做G题。2小时之后，计算几何的 ...
题目大意：给你一张图，一个人走过之后路径的费用会增加，问有2个人走，最小的总费用是多少。
算法思路：一开始准备跑2遍dijkstra，每次求最小的费用，不知道为什么这样一直WA，最后问了一下别人，发现是用最小费用最大流，每个点之间连接2条边，一条是走之前正常的路，另一条是走完这条路后增加了费用的路，因为有2个人，因此超级源点与起点的容量为2，超级汇点与终点的容量为2，跑一遍最小费用最大流的模板就可以。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue&g ...
POJ3660 floyd求传递闭包
- 博客分类：
- 算法
题目大意：一群牛比胜负，然后balabala，然后给你一堆关系，让你求出能够判断出名次的牛的个数。
算法思路：这道题主要的用的是传递闭包，然后只要判断该牛的入度和出度之和等于n-1，就说明该牛能判断出名次。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 105
int n,m,a,b,res;
int p[MAXN][MAXN],in[MAXN],out[MAXN], ...
NYOJ239 月老的难题 二分图匹配
- 博客分类：
- 算法
题目大意：中文题。
算法思路：匈牙利算法的模板题，一开始用邻接矩阵做，结果超时了，后来一看，有10000的边数，难怪超时，因为要判定两点是否有边的话，就得遍历一行，每次递归都这样做的话时间花费是很大的，就改为了邻接表，过了。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f3f
#define MAXN 505
int t,n,k,a,b,e;
i ...
NYOJ 哭泣天使 sap求最大流
- 博客分类：
- 算法
题目大意：中文题。
算法思路：因为他是网格，所以我们把将每一行看成点，将每一列看成点，将行与超级源点连接，行再与列相连接，列再与超级会点相连，求最大流即可。
#include<bits/stdc++.h>
using namespace std;
#define INF 0xfffffff
#define MAXN 600
int t;
int m,n,sum1,sum2,src,sink;
int a[MAXN],b[MAXN];
int maps[MAXN][MAXN],pre[MAXN],level[MAXN];
int gap[MAXN];
int ...
NYOJ118 求次小生成树
- 博客分类：
- 算法
题目大意：中文题。
算法思路：求次小生成树。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 505
int t,n,m,a,b,c,sum,e,MAX,pr;
int maps[MAXN][MAXN],dist[MAXN],p[MAXN][MAXN],pre[MAXN];
bool visited[MAXN],used[MAXN][MAXN];
void p ...
Poj3177 tarjan算法求双连通分量
- 博客分类：
- 算法
题目大意：给定一个无向连通图，问天几条边可以使它变成一个双连通图。
算法思路：tarjan算法模板。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
#define MAXN 10005
int n,m;
typedef struct Edge
{
int u;
int v;
int c;
};
Edge edges[MAXN*20];
int head[M ...
NYOJ677 EK算法求解最大流
- 博客分类：
- 算法
题目大意：中文题。。。
算法思路：这里明显是求最小割的。那么什么是最小割呢？最小割就是所有割的权值之和的最小值，那么什么是割呢？割就是如果把图中的一条边或几条边去掉之后使得图变得不连通。这里可以用一个叫做最大流最小割的定理：在任意一个只有一个源和一个汇的图来说，最小割就等于最大流。因此可以把问题转化为求最大流的问题。这里用ek算法求解最大流。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#def ...
题目大意：有一个国王他开着一辆最大只能行驶d距离的车子(因为行驶完d距离后车子就没油了)环游世界，他想从1点出发环游到n点再回来，由于车子的原因，他必须在某几个点上建加油站，来保证它能够顺利的环游世界，但是在第i个点建立加油站的费用为2^i，因此问你如何建站能使所需要的费用最小，如果怎么建站也不行的话就输出-1。
算法思想：假设我们再每个点都建站，如果这样都不能完成的话，那么肯定输出-1，否则，我们就从第n个点开始，判断第n个点是否需要建加油站，如果少了这个加油站不能完成的话，那么这个点必须要建站，然后在判断第n-1个点，n-2个点，一直到第2个点（因为第一个点根据题目要求必须要建站）。
...
Poj1523 无向连通图求割点
- 博客分类：
- 算法
题目大意：也是给你一个无向连通图，让你求出该无向图的割点，并求出如果去掉这个割点，该无向图会变成几个连通分量。
算法思路：赤裸裸的tarjan求割点算法，但cnt数组记录的是去掉该点，连通图的连通分量的变化量，因此，如果数组在该点的值不为1，那么说明这个点为割点，但要注意，分成的连通分量数为cnt数组在该点的值+1。但特别要注意的一点，如果根节点是割点的话，那么说明根的度>=2，则这个度就是分成的连通分量数，不必再+1。
#include<iostream>
#include<cstdio>
#include<cstring>
#inclu ...