「codechef」March Challenge 2015
只做了前6题弃疗了
感觉codechef写题解也没啥人看……
「codechefCNOTE」Chef and Notebooks
纯模拟
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline 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,x,y,k,n; int p[100005],c[100005]; void solve() { for(int i=1;i<=n;i++) if(p[i]>=x-y&&c[i]<=k) { puts("LuckyChef"); return; } puts("UnluckyChef"); } int main() { T=read(); while(T--) { x=read(),y=read(),k=read(),n=read(); for(int i=1;i<=n;i++) p[i]=read(),c[i]=read(); solve(); } return 0; } |
「codechefSIGNWAVE」 Sign Wave
听说此题打表可以找规律。。
引用zld神犇的话吧。。。
就是若干个余弦函数的零点均不同。。
然后sin函数的分布就十分奇怪了。。
比如s=3的时候就是312131213，忽略两端的情况。。
就变成非常规则的1213121
然后我们再考虑余弦函数当c=2的时候分布就是011101110
k=1的时候那么我们就求总共有多少个交点就行了。。
否则，k>s的时候一定无解。。
否则我们枚举i，表示有i个sin函数交在同一点。。
考虑一下它加上余弦函数的交点之后能不能>=k
如果能的话就把i这一类加入答案。。
|
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<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> #define pa pair<int,int> #define inf 1000000000 #define ll long long #define p(i,j) (i-1)*m+j using namespace std; inline 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; } ll T,s,c,K,ans; void solve() { if(K==1) { ll tmp=(1LL<<(c+1))-2; if(s==0)printf("%lld\n",tmp); else printf("%lld\n",max((1LL<<s)-2,tmp)+3); } else { if(K>s) puts("0"); else { ans=2; for(int i=s;i>=1;i--) if(i+(s-i<=c)>=K) ans+=1LL<<(s-i); printf("%lld\n",ans); } } } int main() { T=read(); while(T--) { s=read();c=read();K=read(); solve(); } return 0; } |
「codechefDEVCLASS」Devu and his Class
type为0易得。。
否则将男女编号求逆序对啥的。。。略
|
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 91 92 93 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> #define pa pair<int,int> #define inf 1000000000 #define eps 1e-8 #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; ll ans; int val[100005],t[200005]; char ch[100005]; void add(int x,int val) { for(int i=x;i<=2*n;i+=i&-i) t[i]+=val; } int query(int x) { int ans=0; for(int i=x;i;i-=i&-i) ans+=t[i]; return ans; } void solve(int t1,int t2) { ll tot=0; for(int i=1;i<=n;i++) if(ch[i]=='B')val[i]=t1,t1+=2; else val[i]=t2,t2+=2; if(abs(t1-t2)!=1)return; for(int i=1;i<=n;i++) { tot+=i-query(val[i])-1; add(val[i],1); } ans=min(ans,tot); } int main() { T=read(); while(T--) { int k=read(); scanf("%s",ch+1); n=strlen(ch+1); int t1=0,t2=0; for(int i=1;i<=n;i++) if(ch[i]=='B')t1++; else t2++; if(abs(t1-t2)>1) { puts("-1"); continue; } ans=10000000000LL; if(k==0) { ll tmp=0; if(t1>=t2) { for(int i=1;i<=n;i++) if((i&1)&&ch[i]=='G')tmp++; ans=min(ans,tmp); } if(t1<=t2) { tmp=0; for(int i=1;i<=n;i++) if((i&1)&&ch[i]=='B')tmp++; ans=min(ans,tmp); } } else { solve(2,1);for(int i=1;i<=2*n;i++)t[i]=0; solve(1,2);for(int i=1;i<=2*n;i++)t[i]=0; } printf("%lld\n",ans); } return 0; } |
「codechefSTRSUB」Count Substrings
预处理每个位置向左不超过k的最左点。。。
求其前缀和，每次询问分段统计一下
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline 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,q; char s[100005]; ll sum[2],f[100005],g[100005]; void pre() { int now=1; for(int i=1;i<=n;i++) { sum[s[i]-'0']++; while(sum[s[i]-'0']>k) { sum[s[now]-'0']--; now++; } f[i]=now;g[i]=g[i-1]+i-f[i]+1; } } int main() { T=read(); while(T--) { sum[0]=sum[1]=0; n=read();k=read();q=read(); scanf("%s",s+1); pre(); while(q--) { int x=read(),y=read(); int t=lower_bound(f+x,f+y+1,x)-f-1; printf("%lld\n",(ll)(t-x+2)*(t-x+1)/2+g[y]-g[t]); } } return 0; } |
「codechefSEAPROAR」Sereja and Random Array
x和x+130172在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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<set> #include<map> #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #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,L; char ch[200005]; int A[200005]; unsigned X; void srand1(unsigned S){ X = S; } unsigned nextInteger1(void){ X = X * 1103515245 + 12345; return (X / 65536) % 32768; } bool generator1(int N, unsigned S, int A[]){ srand1(S); for(int i=1;i<=N;i++){ A[i] = nextInteger1() % 2; if(ch[i]-'0'!=A[i])return 0; } return 1; } bool solve() { L=strlen(ch+1); for(int i=1;i<=131072;i++) if(generator1(L,i,A))return 1; return 0; } int main() { T=read(); while(T--) { scanf("%s",ch+1); if(solve())puts("LCG"); else puts("Xorshift"); } return 0; } |
「codechefMTRWY」Matrix
离线+并查集水过
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> #define pa pair<int,int> #define inf 1000000000 #define ll long long #define p(i,j) (i-1)*m+j using namespace std; inline 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; } ll ans; int T; int n,m,q,mx; int vis[3][1005][1005]; int fa[1000005],size[1000005]; struct data{ int f,x,y,x1,x2,y1,y2; }a[1000005]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } void un(int x,int y) { int p=find(x),q=find(y); if(p!=q)size[q]+=size[p]; mx=max(mx,size[q]); fa[p]=q; } int main() { T=read(); while(T--) { n=read();m=read();q=read(); for(int i=1;i<=n*m;i++)fa[i]=i,size[i]=1; mx=1;ans=0; for(int i=1;i<=q;i++) { a[i].f=read(); if(a[i].f==1||a[i].f==2) { a[i].x=read(),a[i].y=read(); vis[a[i].f][a[i].x][a[i].y]++; } else if(a[i].f==3) { a[i].x1=read(),a[i].y1=read(); a[i].x2=read(),a[i].y2=read(); } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(j<m&&!vis[1][i][j]) un(p(i,j),p(i,j+1)); if(i<n&&!vis[2][i][j]) un(p(i,j),p(i+1,j)); } for(int i=q;i>=1;i--) { int x=a[i].x,y=a[i].y,f=a[i].f; if(f==1||f==2) { vis[f][x][y]--; if(!vis[f][x][y]) { if(f==1)un(p(x,y),p(x,y+1)); if(f==2)un(p(x,y),p(x+1,y)); } } if(f==3)ans+=(find(p(a[i].x1,a[i].y1))==find(p(a[i].x2,a[i].y2))); if(f==4)ans+=mx; } printf("%lld\n",ans); } return 0; } |
Subscribe
计数器 9786994
OI 课件=>
OI 课件=>