usaco 刷水。。。
2017: [Usaco2009 Nov]硬币游戏
f(i,j)表示考虑最后i枚，前一次对手取j枚，自己的最大获益
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #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 n; int c[2005],sum[2005]; int f[2005][2005]; int main() { n=read(); for(int i=n;i;i--)c[i]=read(); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+c[i]; for(int i=1;i<=n;i++) { int mn=inf; for(int j=1;j<=n;j++) { int t=2*j; if(t<=i)mn=min(mn,f[i-t][t]); t=2*j-1; if(t<=i)mn=min(mn,f[i-t][t]); f[i][j]=sum[i]-mn; } } printf("%d\n",f[n][1]); return 0; } |
[Usaco2005 Feb]Rigging the Bovine Election 竞选划区
爱怎么暴力怎么暴力
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #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]={0,0,1,-1},yy[4]={1,-1,0,0}; int n,ans; char mp[15][15]; bool mark[15][15],b[15][15]; void dfs(int x,int y) { b[x][y]=0; for(int k=0;k<4;k++) { int nx=x+xx[k],ny=y+yy[k]; if(b[nx][ny])dfs(nx,ny); } } bool cal() { for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) b[i][j]=mark[i][j]; bool flag=0; for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) if(b[i][j]&&!flag) { dfs(i,j); flag=1; } for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) if(b[i][j])return 0; return 1; } void dfs(int x,int y,int a,int b) { if(a+b==7) { if(a>b)ans+=cal(); return; } if(y==6)x++,y=1; if(x==6)return; mark[x][y]=1; if(mp[x][y]=='J') dfs(x,y+1,a+1,b); else dfs(x,y+1,a,b+1); mark[x][y]=0; dfs(x,y+1,a,b); } int main() { for(int i=1;i<=5;i++)scanf("%s",mp[i]+1); dfs(1,1,0,0); printf("%d\n",ans); return 0; } |
1661: [Usaco2006 Nov]Big Square 巨大正方形
狗眼瞎了wa了n发。。。
枚举一条边暴力即可
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #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 n,ans; char mp[105][105]; int a[105][105]; void solve(int x1,int y1,int x2,int y2) { int tx=x2-x1,ty=y2-y1; if(ty>=x1||y2+tx>n)return; if(a[x2-ty][y2+tx]==0)return; if(a[x1-ty][y1+tx]==0)return; int t=a[x2-ty][y2+tx]+a[x1-ty][y1+tx]+a[x1][y1]+a[x2][y2]; if(t>=7) ans=max(ans,tx*tx+ty*ty); } int main() { n=read(); for(int i=1;i<=n;i++)scanf("%s",mp[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(mp[i][j]=='J')a[i][j]=2; else if(mp[i][j]=='*')a[i][j]=1; } for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) if(a[x][y]) for(int i=x;i<=n;i++) for(int j=y;j<=n;j++) if(mp[i][j]&&(x!=i||y!=j)) solve(x,y,i,j); printf("%d\n",ans); return 0; } |
1654: [Usaco2006 Jan]The Cow Prom 奶牛舞会
有向图强连通分量。。。
|
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 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #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 n,m,ind,scc,ans,cnt,top; int last[10005],dfn[10005],low[10005],sum[10005],q[10005]; bool inq[10005]; struct edge{ int to,next; }e[50005]; void insert(int u,int v) { e[++cnt]=(edge){v,last[u]};last[u]=cnt; } void tarjan(int x) { dfn[x]=low[x]=++ind; q[++top]=x;inq[x]=1; for(int i=last[x];i;i=e[i].next) if(!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]); else if(inq[e[i].to]) low[x]=min(low[x],dfn[e[i].to]); if(low[x]==dfn[x]) { int now=-1;scc++; while(now!=x) { now=q[top--];inq[now]=0; sum[scc]++; } } } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,v); } for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int i=1;i<=scc;i++) if(sum[i]!=1)ans++; printf("%d\n",ans); return 0; } |
Subscribe