CERC 2012 填坑计划(4 / 11)
A – Kingdoms
把所有破产状态状压dp
|
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 |
#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,n; int a[25][25],f[1048576],val[25]; void dp() { for(int i=0;i<=(1<<n)-1;i++)f[i]=0; f[0]=1; for(int i=0;i<=(1<<n)-1;i++) if(f[i]) { memset(val,0,sizeof(val)); for(int j=1;j<=n;j++) if(!((1<<(j-1))&i)) for(int k=1;k<=n;k++)val[k]+=a[j][k]; for(int j=1;j<=n;j++) if(val[j]<0) f[i|(1<<(j-1))]=1; } } int main() { T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=read(); dp(); bool flag=0; for(int i=1;i<=n;i++) { if(f[(1<<n)-1-(1<<(i-1))]) { printf("%d ",i); flag=1; } } if(!flag)puts("0"); else puts(""); } return 0; } |
C – Chemist’s vows
无聊的抄表题。。。
|
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 |
#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; } string a[]={"h","he","li","be","b","c","n","o","f","ne","na","mg","al","si","p","s","cl","ar","k","ca", "sc","ti","v","cr","mn","fe","co","ni","cu","zn","ga","ge","as","se","br","kr","rb","sr","y", "zr","nb","mo","tc","ru","rh","pd","ag","cd","in","sn","sb","te","i","xe","cs","ba","la","ce", "pr","nd","pm","sm","eu","gd","tb","dy","ho","er","tm","yb","lu","hf","ta","w","re","os","ir", "pt","au","hg","tl","pb","bi","po","at","rn","fr","ra","ac","th","pa","u","np","pu","am","cm","bk", "cf","es","fm","md","no","lr","rf","db","sg","bh","hs","mt","ds","rg","cn","fl","lv"}; int n; string b,t; map<string,int>mp; bool f[50005]; int main() { for(int i=0;i<114;i++)mp[a[i]]=1; n=read(); while(n--) { cin>>b; int len=b.length();b=" "+b; for(int i=0;i<=len;i++)f[i]=0; f[0]=1; for(int i=0;i<len;i++) if(f[i]) { t=b[i+1]; if(mp[t]==1)f[i+1]=1; t=t+b[i+2]; if(mp[t]==1)f[i+2]=1; } if(f[len])puts("YES"); else puts("NO"); } return 0; } |
H – Darts
模拟题
|
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 |
#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,n,score; int main() { T=read(); while(T--) { score=0; n=read(); for(int i=1;i<=n;i++) { int x=read(),y=read(); for(int j=10;j;j--) { int d=20*(11-j); if(d*d>=x*x+y*y){score+=j;break;} } } printf("%d\n",score); } return 0; } |
J – Conservation
怀疑数据是不是有问题。。。贪心+拓扑排序
|
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<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 T,n,m,ans,mn; int tmp[100005],d[100005],a[100005]; bool mark[100005]; vector<int>e[100005],t[2]; void solve(int x) { if(!t[x].size()&&!t[x^1].size())return; ans++; while(!t[x].empty()) { int u=t[x].back();t[x].pop_back(); mark[u]=1; for(int j=0;j<e[u].size();j++) { int v=e[u][j]; d[v]--; if(!d[v]) t[a[v]].push_back(v); } } solve(x^1); } bool check() { for(int i=1;i<=n;i++)if(!mark[i])return 0; return 1; } int main() { T=read(); while(T--) { mn=inf; n=read();m=read(); for(int i=1;i<=n;i++)e[i].clear(),d[i]=tmp[i]=mark[i]=0; for(int i=1;i<=n;i++)a[i]=read()-1; for(int i=1;i<=m;i++) { int u=read(),v=read(); e[u].push_back(v); d[v]++;tmp[v]++; } for(int i=1;i<=n;i++) if(!d[i])t[a[i]].push_back(i); ans=0;solve(0); if(check())mn=min(mn,ans); for(int i=1;i<=n;i++)d[i]=tmp[i],mark[i]=0; for(int i=1;i<=n;i++) if(!d[i])t[a[i]].push_back(i); ans=0;solve(1); if(check())mn=min(mn,ans); printf("%d\n",mn-1); } return 0; } |
Subscribe
计数器 9850840
OI 课件=>
OI 课件=>