「CF526X」ZeptoLab Code Rush 2015
懒得开多篇了，深夜口胡TAT 现在是凌晨4点。。。
A：King of Thieves
枚举起始点模拟
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define mod 1000000007 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 n; char ch[105]; bool solve(int x,int y) { for(int i=0;i<=4;i++) if(ch[x+y*i]=='.')return 0; return 1; } int main() { n=read(); scanf("%s",ch+1); bool flag=0; for(int i=1;i<=n;i++) for(int j=1;j*4+i<=n;j++) if(solve(i,j))flag=1; if(flag)puts("yes"); else puts("no"); return 0; } |
B：Om Nom and Dark Park
算出最大值，从最高层开始贪心，能加尽量加
|
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<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define mod 1000000007 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 ans; int n,m,mx; int a[5005],b[5005]; void add(int x,int y,int val) { for(int i=x;i<=y;i++) b[i]+=val; } void solve(int x,int y) { int mn=inf; for(int i=x;i<=y;i++) mn=min(mx-b[i],mn); for(int i=x;i<=y;i++) b[i]+=mn; ans+=mn; } int main() { n=read();m=(1<<(n+1))-2; for(int i=1;i<=m;i++)a[i]=read(); int id=0; for(int i=1<<(n-1);i;i>>=1) for(int j=1<<n;j<=m+1;j+=i) add(j,i+j-1,a[++id]); for(int i=1;i<=m+1;i++)mx=max(mx,b[i]); for(int i=1<<(n-1);i;i>>=1) for(int j=1<<n;j<=m+1;j+=i) solve(j,i+j-1); printf("%d\n",ans); return 0; } |
C：Om Nom and Candies
设hb/wb为小于ha/wa即a的单位质量价值高
分类讨论
若wb很大，则可以枚举b取了多少个
否则a取的数量一定与c/wa相差不超过wb
分类暴力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<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 #define pa pair<int,int> #define ll long long #define mod 1000000007 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; } ll c,hr,hb,wr,wb,ans; void solve1() { for(int i=0;i*wb<=c;i++) ans=max(ans,(c-i*wb)/wr*hr+i*hb); } void solve2() { ll t=c/wr; for(int i=t;i>=t-wb&&i>=0;i--) ans=max(ans,(c-i*wr)/wb*hb+i*hr); } int main() { c=read();hr=read();hb=read();wr=read();wb=read(); if((double)hr/wr<(double)hb/wb)swap(hr,hb),swap(wr,wb); if(wb>=100) solve1(); else solve2(); printf("%lld",ans); return 0; } |
D： Om Nom and Necklace
我的做法是枚举A+B的长度，hash暴力
最后二分出A的最长长度T T，至于区间修改用差分前缀和就能完成
复杂度nlogn。。。FST
擦赛后加了个if(K*x>n)return;就卡过了T T。。。
正解kmpTAT详情请看官方题解。。。
|
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<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #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; } int M[3]={1000000007,1000000009,515347067}; ll mul[1000005],s[1000005]; int n,K,mod; char ch[1000005]; int mark[1000005]; int gethash(int l,int r) { int t=(s[r]-s[l-1]*mul[r-l+1])%mod; return t<0?t+mod:t; } void solve(int x) { int H=gethash(1,x),ans=0,tot=0; if(K*x>n)return; for(int i=1;i<=n&&tot<K;i+=x) if(gethash(i,i+x-1)!=H)break; else ans=i+x-1,tot++; if(tot!=K)return; int l=1,r=x,t=0; while(l<=r) { int mid=(l+r)>>1; if(gethash(1,mid)==gethash(ans+1,ans+mid))t=mid,l=mid+1; else r=mid-1; } mark[ans]++; mark[ans+t+1]--; } int main() { srand(time(0)); n=read();K=read(); mod=M[rand()%3]; scanf("%s",ch+1); mul[0]=1;for(int i=1;i<=n;i++)mul[i]=mul[i-1]*149%mod; for(int i=1;i<=n;i++) { s[i]=s[i-1]*149+ch[i]-'a'; s[i]%=mod; } for(int i=1;i<=n;i++) solve(i); int tot=0; for(int i=1;i<=n;i++) { tot+=mark[i]; printf("%d",tot>0); } return 0; } |
E：Transmitting Levels
我的做法比较乱搞
先任意找个起始点划分一下。。。找最少个数的那段
最优解必然有一个断点在这一段中
枚举这一段的每个点作为起始点划分，根据该段的数量决定是每次二分下个断点还是暴力找
最后2.4s卡过
实际上只要预处理一下每个位置，最多能包含到向后什么地方，复杂度就可以变成On辣
|
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 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #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; } ll S; int n,m,mn,L,ans; ll a[2000005],s[2000005]; void solve(int x) { ll tot=0; int num=0; for(int i=x;i<=x+n-1;i++) { tot+=a[i]; if(tot>S)tot=a[i],num++; } num++; ans=min(ans,num); } void solve2(int x) { int l,r,mid,nxt,num=0; for(int i=x;i<=x+n-1;i=nxt+1,num++) { l=i,r=x+n-1,nxt=i; while(l<=r) { mid=(l+r)>>1; if(s[mid]-s[i-1]<=S) nxt=mid,l=mid+1; else r=mid-1; } } ans=min(ans,num); } void query() { ll tot=0,nowl=1; for(int i=1;i<=n;i++) { tot+=a[i]; if(tot>S) { tot=a[i]; if(i-nowl<mn) mn=i-nowl,L=nowl; nowl=i; } } for(int i=L;i<=L+mn;i++) if(mn<=12)solve(i); else solve2(i); } int main() { n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++)a[i+n]=a[i]; for(int i=1;i<=2*n;i++)s[i]=s[i-1]+a[i]; while(m--) { S=read(); mn=ans=n; query(); printf("%d\n",ans); } return 0; } |
计数器 9528102
OI 课件=>
OI 课件=>
C：否则a取的数量一定与c/wa相差不超过wb 这是为啥啊……我随便定了一个相差的值结果fst了……
因为取wb个wa和wa个wb的质量一样，但是显然前者优
啊 好神奇