%今天“AK”的陈文卓大爷（蒯就蒯嘛还全蒯了讲题又讲不出多尴尬）
1.开灯
我很生气为什么大家写的暴力都可以跑过
亏我还写的正解
把所有操作的灯都异或起来就可以了 因为开的又关异或和为1 暴力搞数组开不了那么大
|
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 |
// <light.cpp> - 06/09/16 08:01:16 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } lol gl(){ lol res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } int main(){ freopen("light.in","r",stdin); freopen("light.out","w",stdout); int n=gi();double a;lol ans=0; for(int i=1;i<=n;i++){ scanf("%lf",&a); lol t=gl(); for(lol i=1;i<=t;i++)ans^=lol(a*i); } printf("%lld",ans); return 0; } |
2.打砖块
这题好显然的背包啊
然而没有考虑到没子弹的时候送子弹的方块不能打
所以dp就要加一维
首先预处理每一列打i个的得分和花费
然后背包一下，加一维表示是否存在一列最后打的一个不是送子弹方块
然后就是std是个萎的
|
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 |
// <game.cpp> - 06/09/16 08:01:16 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=205; const int INF=1e9; int a[MAXN][MAXN],c[MAXN][MAXN],v[MAXN][MAXN]; bool b[MAXN][MAXN]; int dp[MAXN][MAXN][2]; int main(){ freopen("game.in","r",stdin); freopen("game.out","w",stdout); int n=gi(),m=gi(),k=gi(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ a[i][j]=gi(); b[i][j]=getchar()!='Y'; } for(int i=n;i;i--) for(int j=1;j<=m;j++){ c[i][j]=c[i+1][j]+b[i][j]; v[i][j]=v[i+1][j]+a[i][j]; } for(int j=1;j<=m;j++){ memcpy(dp[j],dp[j-1],sizeof(dp[j])); for(int i=1;i<=n;i++) for(int o=c[i][j];o<=k;o++){ int l=o-c[i][j]; dp[j][o][b[i][j]]=max(dp[j][o][b[i][j]],dp[j-1][l][0]+v[i][j]); if(dp[j-1][l][1])dp[j][o][1]=max(dp[j][o][1],dp[j-1][l][1]+v[i][j]); } } int ans=dp[m][k][1]; for(int o=k-1;o>=0;o--)ans=max(ans,max(dp[m][o][0],dp[m][o][1])); printf("%d",ans); return 0; } |
3.长方形
好像看错了什么东西爆零了。。再改吧
4.收费站
显然二分答案跑最短路
然而这题居然有一个点卡SPFA（虽然早料到了）
不打算改了。。反正在自己机子上能过
|
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 |
// <cost.cpp> - 06/09/16 08:01:16 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=5010,MAXM=40010; const int INF=1e9; int n,m,u,v,s; int f[MAXN]; int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM]; inline void add(int x,int y,int c){next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=c;} queue <int> q; lol dis[MAXN]; bool in[MAXN]; inline bool check(int k){ if(f[u]>k)return 0; for(int i=1;i<=n;i++)dis[i]=0; dis[u]=1; q.push(u);in[u]=1; while(!q.empty()){ int now=q.front();q.pop();in[now]=0; for(int i=b[now];i;i=next[i]){ if(f[to[i]]>k)continue; if(dis[to[i]]&&dis[now]+val[i]>=dis[to[i]])continue; dis[to[i]]=dis[now]+val[i]; if(in[to[i]])continue; in[to[i]]=1; q.push(to[i]); } } return dis[v]&&dis[v]-1<=s; } int main(){ freopen("cost.in","r",stdin); freopen("cost.out","w",stdout); n=gi(),m=gi(),u=gi(),v=gi(),s=gi(); for(int i=1;i<=n;i++)f[i]=gi(); for(int i=1;i<=m;i++){ int a=gi(),b=gi(),c=gi(); add(a,b,c);add(b,a,c); } int l=0,r=INF+1; while(l<r){ int m=(l+r)>>1; if(check(m))r=m; else l=m+1; } if(l==INF+1)printf("-1"); else printf("%d",l); return 0; } |
说点什么