「codechef」December Challenge 2014
「codechefCAPPLE」Chef and Apple Trees
其实我想练习打字，点开codechef随便做。。。后来发现这是在challenge，后来补了俩题
|
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 |
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ans; int T,n; int a[100005]; int main() { T=read(); while(T--) { ans=0; memset(a,0,sizeof(a)); n=read(); for(int i=1;i<=n;i++) { int x=read(); a[x]++; if(a[x]==1)ans++; } printf("%d\n",ans); } return 0; } |
「codechefXORSUB」XOR with Subset
求线性基，裸题
|
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<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define pa pair<int,int> #define ll long long 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,K,now; int a[1005]; int bin[15]; void gauss() { now=0; for(int i=10;i>=0;i--) { int j=now+1; while((bin[i]&a[j])==0&&j<=n)j++; if(j==n+1)continue; now++;swap(a[j],a[now]); for(int k=1;k<=n;k++) if((a[k]&bin[i])&&k!=now)a[k]^=a[now]; } } int main() { bin[0]=1;for(int i=1;i<=10;i++)bin[i]=bin[i-1]<<1; T=read(); while(T--) { n=read();K=read(); for(int i=1;i<=n;i++) a[i]=read(); gauss(); for(int i=1;i<=now;i++) if((K^a[i])>K)K^=a[i]; printf("%d\n",K); } return 0; } |
「codechefSANSKAR」Alok-nath and His Sanskars
从大到小排序后优先用大的合成
随便搜索一下TAT
这样过了codechef
但是似乎会被构造卡掉
14 4
15 10 17 16 12 1 10 20 17 19 4 5 9 5
正确应为yes,每段长度为40,一种可能解为 (20 15 5 ),(19 17 4 ),( 17 12 10 1 ), ( 16 10 9 5 )
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define pa pair<int,int> #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; } bool flag; int T,n,K; ll a[25],sum; bool mark[25],sel[25]; bool dfs(int x,ll tot) { tot+=a[x]; if(tot>sum)return 0; if(tot==sum) { for(int i=1;i<=n;i++) if(sel[i])mark[i]=1; return 1; } for(int i=x+1;i<=n;i++) if(!mark[i]) { sel[i]=1; if(dfs(i,tot))return 1; sel[i]=0; } return 0; } int main() { T=read(); while(T--) { memset(mark,0,sizeof(mark)); n=read();K=read(); for(int i=1;i<=n;i++)a[i]=read(); if(K>n){puts("no");continue;} sort(a+1,a+n+1,greater<int>()); sum=0; while(n&&a[n]==0)n--; for(int i=1;i<=n;i++)sum+=a[i]; if(sum%K!=0){puts("no");continue;} sum=sum/K; flag=1; for(int i=1;i<=n;i++) if(!mark[i]) { sel[i]=1; memset(sel,0,sizeof(sel)); if(!dfs(i,0)){flag=0;puts("no");break;} } if(flag)puts("yes"); } return 0; } |
Subscribe
计数器 9787166
OI 课件=>
OI 课件=>