「codechef」January Challenge 2015
CHEFSTON
|
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<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #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,m; ll ans; int a[100005],b[100005]; int main() { T=read(); while(T--) { n=read();m=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) b[i]=read(); ans=0; for(int i=1;i<=n;i++) ans=max(ans,(ll)m/a[i]*b[i]); printf("%lld\n",ans); } return 0; } |
GCDQ
gcd满足区间加法TAT，所以维护前缀和后缀和就好了
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #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,q; int a[100005],t1[100005],t2[100005]; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int main() { T=read(); while(T--) { n=read();q=read(); for(int i=1;i<=n;i++)a[i]=read(); t1[1]=a[1];for(int i=2;i<=n;i++)t1[i]=gcd(t1[i-1],a[i]); t2[n]=a[n];for(int i=n-1;i;i--)t2[i]=gcd(t2[i+1],a[i]); while(q--) { int l=read(),r=read(),ans; if(l==1)ans=t2[r+1]; else if(r==n)ans=t1[l-1]; else ans=gcd(t2[r+1],t1[l-1]); printf("%d\n",ans); } } return 0; } |
SEAVOTE
去掉所有0后
若∑bi < tot 或∑bi >= 100+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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #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; int a[10005],tot; bool check() { int sum=0; for(int i=1;i<=n;i++) sum+=a[i]; if(sum<100||sum>=100+n) return 0; return 1; } int main() { T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++)a[i]=read(); tot=0;for(int i=1;i<=n;i++)if(a[i])a[++tot]=a[i]; n=tot; if(check())puts("YES"); else puts("NO"); } return 0; } |
ONEKING
按照右端点排序，选择第一个的右端点，删去覆盖其的线段。。。
剩下的线段同理
|
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<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #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; struct data{ int l,r; }a[100005]; bool operator<(data a,data b) { return a.r<b.r; } int main() { T=read(); while(T--) { n=read(); for(int i=1;i<=n;i++) a[i].l=read(),a[i].r=read(); int last=-1,ans=0; sort(a+1,a+n+1); for(int i=1;i<=n;i++) if(a[i].l>last)ans++,last=a[i].r; printf("%d\n",ans); } return 0; } |
CLPERM
答案根据第一个不能合成的数奇偶性得出
若用一些数字合成1-sum，加入一个数x（x<=sum+1），则能合成sum+x
由于sumK<=5^10^5，若能合成1-500000，依据上面的结论，可以获得所有1-剩余的n-K个数字之和
所以暴力判断1-500000是否能合成（根号级别的运算次数），若能的话根据剩余的n-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<queue> #include<set> #include<map> #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,t,mx; int a[100005]; void solve(int a,int b) { for(int i=a+1;mx<=500000&&i<b;i++) if(i<=mx+1) mx+=i; else break; } int main() { T=read(); while(T--) { n=read();K=read(); mx=0;t=((ll)n*(n+1)/2)&1; for(int i=1;i<=K;i++) a[i]=read(); for(int i=1;i<=K;i++) if(a[i]&1)t^=1; sort(a+1,a+K+1);a[K+1]=n+1; for(int i=0;mx<=500000&&i<=K;i++) solve(a[i],a[i+1]); if(mx>500000) { if(t&1)puts("Mom"); else puts("Chef"); } else if(mx&1)puts("Mom"); else puts("Chef"); } return 0; } |
QSET
如果a,b满足前缀和取模相等，则a+1~b的和取模等于0
显然可以用线段树维护区间 前缀和取模为0，1，2的数量
单点修改区间查询
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #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; } char a[100005]; struct data{ int l,r,sum,v[3]; }t[400005]; int n,K; data merge(data a,data b) { data t;t.l=a.l;t.r=b.r; t.sum=a.sum+b.sum; for(int i=0;i<3;i++) { int tmp=(a.sum+i)%3; t.v[tmp]=a.v[tmp]+b.v[i]; } return t; } void build(int k,int l,int r) { t[k].l=l;t[k].r=r;int mid=(l+r)>>1; if(l==r){t[k].sum=(a[l]-'0')%3;t[k].v[t[k].sum]=1;return;} build(k<<1,l,mid);build(k<<1|1,mid+1,r); t[k]=merge(t[k<<1],t[k<<1|1]); } data query(int k,int x,int y) { int l=t[k].l,r=t[k].r,mid=(l+r)>>1; if(l==x&&y==r)return t[k]; if(y<=mid)return query(k<<1,x,y); else if(x>mid)return query(k<<1|1,x,y); else return merge(query(k<<1,x,mid),query(k<<1|1,mid+1,y)); } void change(int k,int x,int val) { int l=t[k].l,r=t[k].r,mid=(l+r)>>1; if(l==r) { t[k].v[0]=t[k].v[1]=t[k].v[2]=0; t[k].v[val%3]=1; t[k].sum=val%3; return; } if(x<=mid)change(k<<1,x,val); else change(k<<1|1,x,val); t[k]=merge(t[k<<1],t[k<<1|1]); } int main() { n=read();K=read(); scanf("%s",a+1); build(1,1,n); while(K--) { int opt=read(),x=read(),y=read(); if(opt==1)change(1,x,y); else { ll ans=0;data t=query(1,x,y); for(int i=0;i<3;i++)ans+=(ll)t.v[i]*(t.v[i]-1)/2; ans+=t.v[0]; printf("%lld\n",ans); } } return 0; } |
XRQRS
kuribohG说，裸题+傻逼题，作为一个中国人都应该可以A掉
唔可持久化字典树裸题。。。
纯模板没啥难度
|
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 94 95 96 97 98 99 100 101 102 103 104 105 106 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #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 bin[25]; int m,n; int root[500005]; struct trie{ int cnt; int to[10000005][2],sum[10000005]; int insert(int x,int val){ int tmp=++cnt,y=tmp; for(int i=20;i>=0;i--) { int t=val&bin[i];t>>=i; to[y][0]=to[x][0];to[y][1]=to[x][1]; to[y][t]=++cnt; x=to[x][t];y=to[y][t]; sum[y]=sum[x]+1; } return tmp; } int querymx(int l,int r,int x){ int tmp=0; for(int i=20;i>=0;i--) { int t=x&bin[i];t>>=i; if(sum[to[r][t^1]]-sum[to[l][t^1]]) tmp+=bin[i],l=to[l][t^1],r=to[r][t^1]; else l=to[l][t],r=to[r][t]; } return tmp; } int querynum(int l,int r,int x){ int tmp=0; for(int i=20;i>=0;i--) { int t=x&bin[i];t>>=i; if(t==1)tmp+=sum[to[r][0]]-sum[to[l][0]]; if(sum[to[r][t]]-sum[to[l][t]]) { l=to[l][t],r=to[r][t]; } else break; } return tmp; } int queryval(int l,int r,int x){ int tmp=0; for(int i=20;i>=0;i--) { if(sum[to[r][0]]-sum[to[l][0]]<x) { x-=sum[to[r][0]]-sum[to[l][0]]; tmp+=bin[i];l=to[l][1],r=to[r][1]; } else l=to[l][0],r=to[r][0]; } return tmp; } }trie; int main() { bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1; m=read(); int opt,l,r,x; while(m--) { opt=read(); switch(opt) { case 0:x=read(); root[n+1]=trie.insert(root[n],x); n++;break; case 1: l=read(),r=read(),x=read(); printf("%d\n",x^trie.querymx(root[l-1],root[r],x));break; case 2: x=read();n-=x;break; case 3: l=read();r=read();x=read(); printf("%d\n",trie.querynum(root[l-1],root[r],x+1));break; case 4: l=read();r=read();x=read(); printf("%d\n",trie.queryval(root[l-1],root[r],x));break; } } //cout<<trie.cnt<<endl; return 0; } |
SEALCM
举个例子
lcm能被12整除的=m^n-lcm不能被12整除的
lcm不能被12整除的=(M-M/4)^N+(M-M/3)^N-(M-(M/4+M/3-M/12)^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 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 |
#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 mod 1000000007 #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,m,L,R,D,cnt; ll ans; int a[105],b[2005]; int pow(ll a,int b,int p) { ll ans=1; for(int i=b;i;i>>=1,a=a*a%p) if(i&1)ans=ans*a%p; return ans; } void dfs(int now,int k,int top,int sum) { if(now==cnt+1) { if(k!=0) { if(k&1) ans=(ans-pow(sum,n,mod)+mod)%mod; else ans=(ans+pow(sum,n,mod))%mod; } return; } dfs(now+1,k,top,sum); int t=top; for(int i=1;i<=t;i++) b[++top]=-b[i]/a[now]; b[++top]=-m/a[now]; for(int i=t+1;i<=top;i++)sum+=b[i]; dfs(now+1,k+1,top,sum); } void solve() { ans=(ans+pow(m,n,mod))%mod; cnt=0; int tmp=D; for(int i=2;i<=sqrt(D);i++) if(tmp%i==0) { a[++cnt]=1; while(tmp%i==0)a[cnt]*=i,tmp/=i; } if(tmp!=1)a[++cnt]=tmp; dfs(1,0,0,m); } int main() { T=read(); while(T--) { n=read();m=read();L=read();R=read(); ans=0; for(D=L;D<=R;D++) solve(); printf("%lld\n",ans); } return 0; } |
RANKA
写这个我血都要喷了
usedtobe提供了一种简单的做法
——————————————————–
1111->0000->2222->0000
1111 0000 2222 0000
1111 0000 2222 0000
1110 0002 2202 0010
——————————————————–
以下是我用的做法。。。
我没考虑到如果棋盘上只有一个空格，其它均为1，在空格放2会把全部的1都吃掉
我认为吃对方的棋子首先自身棋子要有气T T（主要是自己弱）
设两种棋子分别为1，2
开始的想法是，先填上半2，然后填下半1的时候把上半1吃掉
然后想个办法让每次填的顺序不同
发现每次每半边留一个异色棋子即可,然后每次改变异色棋子的位置
即如下（为了简便缩小了棋盘），还要注意不能出现重复的情况
1000->0222->0222->0000->0100->2022
0000 2222 2222 0000 0000 2222
0000 0000 0000 1111 1111 0000
0000 0000 0002 1112 1111 0000
结果发现这样只有5000步TAT FK！
又拿出两行来，一开始是这样
0000
1111
做完一次在第一行放个1变成
1000
1111
然后重新搞。。。。这样就能把方案乘以9了
但是这样容易有重复的情况。。。在每次的开始和结束局面
只要把异色棋子的枚举范围每次缩小一点即可
以下代码有一行if(bx==T+2&&by<k)continue;
唔我的逗比代码，把注释去掉运行可以看到每一步的运行
单独的提子我没有搞出来
|
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 94 95 |
#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 n,cnt,T; int lastx=-1,lasty; int x[50005],y[50005]; int mp[10][10]; /*void print() { for(int i=1;i<=9;i++) { for(int j=1;j<=9;j++) cout<<mp[i][j]; cout<<endl; } system("pause"); }*/ void move(int a,int b) { x[++cnt]=a;y[cnt]=b; /*if(cnt&1)mp[a][b]=1; else mp[a][b]=2; if(a==T&&b==9) { for(int i=T+1;i<=9;i++) for(int j=1;j<=9;j++) mp[i][j]=0; } else if(a==T+1&&b==1) { for(int i=3;i<=T;i++) for(int j=1;j<=9;j++) mp[i][j]=0; } print();*/ } void solve() { for(int k=1;k<=9;k++) { for(int ax=4,bx=9;ax<T&&bx>T+1;ax++,bx--) for(int ay=1,by=9;ay<=9;ay++,by--) { if(bx==T+2&&by<k)continue; move(ax,ay); if(lastx!=-1) move(0,0),move(lastx,lasty); for(int i=3;i<=T;i++) for(int j=1;j<=9;j++) if(i!=ax||j!=ay) move(i,j),move(0,0); move(bx,by);move(0,0); move(ax,ay); for(int i=9;i>=T+1;i--) for(int j=9;j;j--) if(i!=bx||j!=by) move(i,j),move(0,0); lastx=bx;lasty=by; } move(1,k);move(0,0); } } int main() { n=read(); for(int i=1;i<=9;i++) { move(2,i); move(0,0); } T=6; solve(); for(int i=1;i<=n;i++) printf("%d %d\n",x[i],y[i]); return 0; } |
SEAND2
写了个无脑随机化得分0.755
预处理f[i][j]表示第10^i mod b[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 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 94 95 96 97 98 |
#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,mn,L,S; char ch[1005]; int a[1005],mod[105]; int tmp[1005][105],N[105]; int t[105],now[105],c[1005]; int ans[1005]; void pre() { for(int i=1;i<=L;i++) for(int j=1;j<=n;j++) N[j]=(N[j]+tmp[L-i+1][j]*a[i])%mod[j]; for(int i=1;i<=n;i++) S+=N[i]; } void solve() { int sum=S; for(int i=1;i<=n;i++)now[i]=N[i]; for(int i=1;i<=L;i++)c[i]=a[i]; for(int i=1;i<=300;i++) { int a=rand()%L+1,b=rand()%L+1,tot=0; if(c[a]==c[b])continue; for(int j=1;j<=n;j++) { int u,v; v=(tmp[L-a+1][j]*c[b]+tmp[L-b+1][j]*c[a])%mod[j]; u=(tmp[L-a+1][j]*c[a]+tmp[L-b+1][j]*c[b])%mod[j]; t[j]=(now[j]+v-u+mod[j])%mod[j]; tot+=now[j]-t[j]; } if(tot>0) { swap(c[a],c[b]),sum-=tot; for(int j=1;j<=n;j++) now[j]=t[j]; } } if(sum<mn) { mn=sum; for(int i=1;i<=L;i++)ans[i]=c[i]; } } int main() { srand(1); T=read(); while(T--) { mn=inf;S=0; memset(N,0,sizeof(N)); scanf("%s",ch+1); L=strlen(ch+1); for(int i=1;i<=L;i++) a[i]=ch[i]-'0'; n=read(); for(int i=1;i<=n;i++) mod[i]=read(); for(int i=1;i<=L;i++) { for(int j=1;j<=n;j++) { if(i==1)tmp[i][j]=1%mod[j]; else tmp[i][j]=(tmp[i-1][j]*10)%mod[j]; } } pre(); for(int i=1;i<=130;i++) solve(); for(int i=1;i<=L;i++) putchar(ans[i]+'0'); puts(""); } return 0; } |
Subscribe
计数器 9324511
OI 课件=>
OI 课件=>