[POJ 3461]Oulipo

字符串搜索提……同时是KMP模板提……

注意啊变量别重名,结果会很壮观的(大吐核)。

代码:

#include <cstdio>
#include <cstring>
const int maxn=1000005,maxm=10005;
char P[maxm],T[maxn];
int f[maxm];
int n,m;
inline void MakeFail(){
    register int i,j;
    f[0]=f[1]=0;
    for(i=1;i<m;i++){
        j=f[i];
        while(j && P[j]!=P[i])
            j=f[j];
        f[i+1]=(P[j]==P[i]?j+1:0);
    }
}
inline int KMP(){
    register int i,j,ans=0;
    n=strlen(T);
    m=strlen(P);
    MakeFail();
    j=0;
    for(i=0;i<n;i++){
        while(j && P[j]!=T[i])
            j=f[j];
        if(P[j]==T[i])
            j++;
        if(j==m)
            ans++;
    }
    return ans;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%s%s",P,T);
        printf("%d\n",KMP());
    }
    return 0;
}

[POJ 1274]The Perfect Stall

很裸的二分图匹配辣~

不过这是我第一次写匈牙利算法……囧

还有时隔多年再次写了一次邻接矩阵QwQ

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=201,maxm=40001;
bool G[maxn][maxn];

// Hungray
int n,m;
bool vis[maxn];
int GirlFriend[maxn];
bool DFS(int x){
    int i;
    for(i=1;i<=m;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!GirlFriend[i] || DFS(GirlFriend[i])){
                GirlFriend[i]=x;
                return true;
            }
        }
    return false;
}
inline int Hungray(){
    register int i,ans=0;
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}

int main(){
    register int i,j;
    int k,temp;
    while(scanf("%d%d",&n,&m)!=EOF){
        memset(G,0,sizeof(G));
        memset(GirlFriend,0,sizeof(GirlFriend));
        for(i=1;i<=n;i++){
            scanf("%d",&k);
            for(j=1;j<=k;j++){
                scanf("%d",&temp);
                G[i][temp]=true;
            }
        }
        printf("%d\n",Hungray());
    }
    return 0;
}

[POJ 3159]Candies

差分约束系统处女作QwQ这个题就是个裸的差分约束系统

但是粗题银啊,你粗来我们需要谈谈。

卡SPFA是怎么回事?(好像据说stack版可过)

还有,不滋磁pb_ds,又是怎么回事?

代码:

#include <cstdio>
#include <bitset>
#include <cstring>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;
const int maxn=30001,maxm=150001;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int graph_cnt=0;
void Add_Edge(int u,int v,int d){
	graph_cnt++;
	next[graph_cnt]=first[u];
	first[u]=graph_cnt;
	to[graph_cnt]=v;
	dist[graph_cnt]=d;
}

int n;
int d[maxn];
bitset<maxn> vis;
typedef pair<int,int> my_pair;
typedef priority_queue<my_pair,vector<my_pair>,greater<my_pair> > Heap;
Heap Q;
int dij(){
    register int i,u;
    memset(d,0x7f,sizeof(d));
    d[1]=0;
    Q.push(make_pair(0,1));
	while(!Q.empty()){
		u=Q.top().second;
		Q.pop();
		if(vis[u])
			continue;
		vis[u]=true;
		for(i=first[u];i;i=next[i]){
			if(d[to[i]]>d[u]+dist[i]){
				d[to[i]]=d[u]+dist[i];
				Q.push(make_pair(d[to[i]],to[i]));
			}
		}
	}
    return d[n];
}
int main(){
	int m;
	int u,v,d;
	register int i;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&d);
		Add_Edge(u,v,d);
	}
	printf("%d\n",dij());
	return 0;
}

[POJ 2388]Who's in the Middle

这题题面长得挺吓人的(英文……),不过就是让你求中位数……

我怀疑会有卡快排的数据,不过我用的是STL的sort(sort好像用的不是普通的快排)

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=10000;
int A[maxn];
int main(){
	register int i;
	int n;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&A[i]);
	sort(A,A+n);
	printf("%d\n",A[n>>1]);
	return 0;
}

[POJ 2104]K-th Number

我擦终于A了这题了!

主席树坑点多……

最好不要写指针主席树,不然容易TLE……(自带常数?

并且注意,一定要把数组开大,开大,再开大,重要的事情说三遍

代码:

继续阅读