2014PKU计算概论入学测试
poj1961 Period
kmp求出fail数组后，前i个的重复子串就是i-fail(i)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,T,l; int fail[1000005]; char ch[1000005]; int main() { while(scanf("%d",&n),n) { T++; printf("Test case #%d\n",T); scanf("%s",ch+1); l=strlen(ch+1); int t=0; for(int i=2;i<=n;i++) { while(ch[t+1]!=ch[i]&&t)t=fail[t]; if(ch[t+1]==ch[i])t++; fail[i]=t; } for(int i=2;i<=n;i++) { if(fail[i]&&i%(i-fail[i])==0) printf("%d %d\n",i,i/(i-fail[i])); } puts(""); } return 0; } |
poj1276 Cash Machine
用f(i,j)表示前i种面值，达到j的面值和，所需要的第i种钞票的最少数量
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int S,n,ans; int a[1005],w[1005]; int f[100005]; int main() { while(scanf("%d%d",&S,&n)!=EOF) { ans=0; for(int i=1;i<=S;i++) f[i]=inf; for(int i=1;i<=n;i++) a[i]=read(),w[i]=read(); f[0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=S;j++) if(f[j]+1<=a[i]&&j+w[i]<=S&&f[j+w[i]]==inf) f[j+w[i]]=f[j]+1; for(int j=0;j<=S;j++) if(f[j]<=a[i]) { f[j]=0; ans=max(ans,j); } } printf("%d\n",ans); } return 0; } |
poj1702 Eva’s Balance
先把n转为3进制，若p位为2，就在左盘放3^p，进位
若p位为1，就在右盘放3^p
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T,n; int bin[25],num[25]; int main() { bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]*3; T=read(); while(T--) { memset(num,0,sizeof(num)); vector<int>a,b; n=read(); for(int i=19;i>=0;i--) { num[i]=n/bin[i]; n%=bin[i]; } for(int i=0;i<20;i++) { num[i+1]+=num[i]/3; num[i]%=3; if(num[i]==2) { a.push_back(bin[i]); num[i+1]++; } if(num[i]==1) b.push_back(bin[i]); } if(!a.size())printf("empty "); else { for(int i=0;i<a.size()-1;i++) printf("%d,",a[i]); printf("%d ",a[a.size()-1]); } for(int i=0;i<b.size()-1;i++) printf("%d,",b[i]); printf("%d ",b[b.size()-1]); puts(""); } return 0; } |
poj1273 Drainage Ditches
大名鼎鼎的草地排水，网络流模板
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define ll long long #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt,flow; int last[205],q[205],h[205]; struct edge{ int to,next,v; }e[405]; void insert(int u,int v,int w) { e[++cnt]=(edge){v,last[u],w};last[u]=cnt; e[++cnt]=(edge){u,last[v],0};last[v]=cnt; } int bfs() { int head=0,tail=1; memset(h,-1,sizeof(h)); q[0]=1;h[1]=0; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[tail++]=e[i].to; } } return h[m]!=-1; } int dfs(int x,int f) { if(x==m)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } void dinic() { while(bfs())flow+=dfs(1,inf); } int main() { while(scanf("%d%d",&n,&m)!=EOF) { flow=0;cnt=1; memset(last,0,sizeof(last)); for(int i=1;i<=n;i++) { int u=read(),v=read(),c=read(); insert(u,v,c); } dinic(); printf("%d\n",flow); } return 0; } |
Milk Patterns
计数器 9355257
OI 课件=>
OI 课件=>
黄学长这是在准备入学测试么？（黄学长报的计算概论？）
我已经准备信科直通车了
黄学长有ACM的意向么？
可能会去打个酱油