PKUSC 2013 #2
A:The Settlers of Catan
枚举起点dfs
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll 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,ans,cnt; int last[30]; bool mark[105]; struct edge{ int to,next; }e[105]; void dfs(int x,int tot) { ans=max(ans,tot); for(int i=last[x];i;i=e[i].next) if(!mark[i]&&!mark[i^1]) { mark[i]=1; dfs(e[i].to,tot+1); mark[i]=0; } } void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; e[++cnt]=(edge){u,last[v]};last[v]=cnt; } int main() { while(scanf("%d%d",&n,&m)) { if(!n)return 0; cnt=1;ans=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,v); } for(int i=1;i<=n;i++)dfs(i,0); printf("%d\n",ans); } return 0; } |
B:Nim
傻逼记忆化搜索我竟然清空错数组QAQ
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll 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,S,m[25]; int f[25][10005]; int dp(int x,int y) { if(x>2*n)x=1; if(y==0)return 1; int &t=f[x][y]; if(t!=-1)return t; for(int i=1;i<=m[x];i++) if(y-i>=0) if(!dp(x+1,y-i))return t=1; return t=0; } int main() { while(1) { n=read();if(!n)return 0; S=read();for(int i=1;i<=2*n;i++)m[i]=read(); for(int i=1;i<=2*n;i++) for(int j=1;j<=S;j++) f[i][j]=-1; printf("%d\n",dp(1,S)); } return 0; } |
C:Traditional BINGO
纯阅读题
|
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 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll 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; int a[10][10],b[100]; bool mark[10][10]; bool add(int x) { bool flag=0; for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) if(a[i][j]==x){mark[i][j]=1;flag=1;} if(!flag)mark[3][3]=1; for(int i=1;i<=5;i++) { flag=0; for(int j=1;j<=5;j++)if(!mark[i][j])flag=1; if(!flag)return 1; } for(int i=1;i<=5;i++) { flag=0; for(int j=1;j<=5;j++)if(!mark[j][i])flag=1; if(!flag)return 1; } flag=0;for(int i=1;i<=5;i++)if(!mark[i][i])flag=1; if(!flag)return 1; flag=0;for(int i=1;i<=5;i++)if(!mark[i][5-i+1])flag=1; if(!flag)return 1; return 0; } int main() { T=read(); while(T--) { memset(mark,0,sizeof(mark)); for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) if(i!=3||j!=3) a[i][j]=read(); for(int i=1;i<=75;i++)b[i]=read(); for(int i=1;i<=75;i++) if(add(b[i])) { printf("BINGO after %d numbers announced\n",i); break; } } return 0; } |
D:Traditional BINGO
排序后广搜
更新每个点能到达的最高点。。。一通乱搞
感觉并查集也可以就是很麻烦？
|
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 83 84 85 86 87 88 89 90 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll read() { ll 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 xx[4]={1,-1,0,0},yy[4]={0,0,1,-1}; int T,n,m,d,tot,ans,head,tail; int a[505][505],p[505][505]; int qx[250005],qy[250005],mx[505][505]; bool mark[505][505]; struct data{ int x,y,val; }b[250005]; bool operator<(data a,data b) { return a.val>b.val; } int bfs(int p,int q) { int tmp; head=0,tail=1; qx[0]=p;qy[0]=q; mark[p][q]=1; tmp=mx[p][q]=a[p][q]; while(head!=tail) { int x=qx[head],y=qy[head];head++; for(int k=0;k<4;k++) { int tx=x+xx[k],ty=y+yy[k]; if(ty<1||tx<1||tx>n||ty>m)continue; if(mx[tx][ty]!=-1)tmp=max(tmp,mx[tx][ty]); else if(a[tx][ty]>a[p][q]-d&&!mark[tx][ty]) { qx[tail]=tx;qy[tail]=ty; mark[tx][ty]=1; tail++; } } } return tmp; } int main() { T=read(); while(T--) { n=read();m=read();d=read(); tot=ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mx[i][j]=-1,mark[i][j]=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { a[i][j]=read(); b[++tot]=(data){i,j,a[i][j]}; } sort(b+1,b+tot+1); for(int i=1;i<=tot;i++) { if(!mark[b[i].x][b[i].y]) { int tmp=bfs(b[i].x,b[i].y); if(tmp==a[b[i].x][b[i].y])ans++; for(int j=0;j<head;j++) mx[qx[j]][qy[j]]=tmp; } else if(mx[b[i].x][b[i].y]==a[b[i].x][b[i].y])ans++; } printf("%d\n",ans); } return 0; } |
Subscribe
计数器 9320819
OI 课件=>
OI 课件=>