「CF335X」MemSQL start[c] up Round 2 – online version
A. Banana
枚举sheet数，找到第一个不能用已有sticker凑出的
|
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 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 100000000 #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 n,L,cnt[26],p[26]; char s[1005]; bool check(int x) { int ans=0; for(int i=0;i<26;i++) { p[i]=cnt[i]/x+(cnt[i]%x!=0); ans+=p[i]; } p[0]+=n-ans; return ans<=n; } int main() { scanf("%s",s+1);n=read();L=strlen(s+1); for(int i=1;i<=L;i++)cnt[s[i]-'a']++; for(int i=1;i<=2000;i++) if(check(i)) { printf("%d\n",i); for(int j=0;j<26;j++) while(p[j]--)putchar('a'+j); return 0; } puts("-1"); return 0; } |
B. Palindrome
f(i,j)表示末尾在i之前，长度为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 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 100000000 #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; } char c[50005]; int n,K,f[50005][105],p[50005][26]; string a; int main() { scanf("%s",c+1); n=strlen(c+1);K=100; for(int i=1;i<=n;i++) { for(int j=0;j<26;j++)p[i][j]=p[i-1][j]; p[i][c[i]-'a']=i; } for(int i=1;i<=n;i++) f[i][0]=i+1,f[i][1]=i; for(int i=2;i<=n;i++) for(int j=2;j<=K;j++) { f[i][j]=f[i-1][j]; if(f[i-1][j-2]) f[i][j]=max(f[i-1][j],p[f[i-1][j-2]-1][c[i]-'a']); } int len=K,t=n; while(!f[n][len])len--; while(len>1) { a.push_back(c[f[t][len]]); t=p[t][c[f[t][len]]-'a']-1; len-=2; } cout<<a; if(len)cout<<c[f[t][len]]; reverse(a.begin(),a.end()); cout<<a; return 0; } |
C. More Reclamation
用(len,x,y)表示一个游戏状态，2*len的完整格子，左端的状态为x，右端的状态为y
x，y = 0/1/2 分别表示（完整），（左侧/右侧第一行第一格不可删），（左侧/右侧第二行第一格不可删）
边界情况：
len=0时sg值为0
len=1时sg(1,2,1)=sg(1,1,2)=0
其余sg(1,x,y)=1
枚举删除一个中间格子+记忆化搜索求sg值
把初始状态分成若干个子游戏，将它们的sg值异或起来，结果为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 |
#include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 100000000 #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 n,m; int f[105][3][3]; struct data{ int p,val; }a[105]; bool operator<(data a,data b) { return a.p<b.p; } int sg(int len,int x,int y) { if(f[len][x][y]!=-1)return f[len][x][y]; if(len==0)return 0; if(x>y)swap(x,y); if(len==1) { if(x==1&&y==2)return 0; else return 1; } bool t[105]={}; for(int l1=0;l1<len;l1++) { int l2=len-l1-1; if(!l1) { if(!x)t[sg(l2,1,y)]=t[sg(l2,2,y)]=1; else t[sg(l2,x,y)]=1; } else if(!l2) { if(!y)t[sg(l1,x,1)]=t[sg(l1,x,2)]=1; else t[sg(l1,x,y)]=1; } else { t[sg(l1,x,1)^sg(l2,1,y)]=1; t[sg(l1,x,2)^sg(l2,2,y)]=1; } } for(int i=0;i<n;i++)if(!t[i])return f[len][x][y]=i; return 0; } int main() { memset(f,-1,sizeof(f)); n=read();m=read(); for(int i=1;i<=m;i++) a[i].p=read(),a[i].val=read(); a[0].p=0;a[m+1].p=n+1; sort(a,a+m+2); int ans=0; for(int i=1;i<=m+1;i++) ans^=sg(a[i].p-a[i-1].p-1,a[i-1].val,a[i].val); if(ans)puts("WIN"); else puts("LOSE"); return 0; } |
D. Rectangles and Square
给出的矩形不重合是此题的关键
预处理s(i,j)表示(1,1)(i,j)这个矩形范围内被覆盖的格子数
l(i,j)表示(i,1)(i,j)这一列被矩形左边界覆盖的格子数
r(i,j) u(i,j) d(i,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 |
#include<map> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 100000000 #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 n; int x1[100005],y1[100005],x2[100005],y2[100005]; int s[3005][3005],l[3005][3005],r[3005][3005],d[3005][3005],u[3005][3005]; vector<int>ans; int main() { n=read(); for(int i=1;i<=n;i++) { x1[i]=read()+1,y1[i]=read()+1,x2[i]=read(),y2[i]=read(); for(int j=x1[i];j<=x2[i];j++) for(int k=y1[i];k<=y2[i];k++) s[j][k]=1; for(int j=x1[i];j<=x2[i];j++) d[j][y1[i]]++,u[j][y2[i]]++; for(int j=y1[i];j<=y2[i];j++) l[x1[i]][j]++,r[x2[i]][j]++; } for(int i=1;i<=3000;i++) for(int j=1;j<=3000;j++) { s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; d[i][j]+=d[i-1][j];u[i][j]+=u[i-1][j]; l[i][j]+=l[i][j-1];r[i][j]+=r[i][j-1]; } for(int i=1;i<=n;i++) for(int len=1;;len++) { int x=x1[i],y=y1[i]; if(l[x][y+len-1]-l[x][y-1]!=len)break; if(d[x+len-1][y]-d[x-1][y]!=len)break; if(s[x+len-1][y+len-1]+s[x-1][y-1]-s[x+len-1][y-1]-s[x-1][y+len-1]!=len*len)break; if(r[x+len-1][y+len-1]-r[x+len-1][y-1]!=len)continue; if(u[x+len-1][y+len-1]-u[x-1][y+len-1]!=len)continue; for(int j=1;j<=n;j++) if(x1[j]>=x&&y1[j]>=y&&x1[j]<x+len&&y1[j]<y+len)ans.push_back(j); printf("YES %d\n",(int)ans.size()); for(int j=0;j<ans.size();j++) printf("%d ",ans[j]); return 0; } puts("NO"); return 0; } |
E. Counting Skyscrapers
题解说的很清楚
戳这里有中文题解/题面，orz wmd
http://blog.csdn.net/wmdcstdio/article/details/44646631
|
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 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 100000000 #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 n,h; double ans; string s; int main() { cin>>s; n=read();h=read(); if(s=="Bob")printf("%d\n",n); else { for(int i=1;i<=h;i++) for(int j=1;j<=n;j++) ans+=(n-j)*(1/pow(2,2*i))*pow(1-1/pow(2,i),j-1)*(pow(2,i)-pow(2,i-1)*(1+(j-1)/(pow(2,i)-1))); printf("%.9lf",n+ans); } return 0; } |
F. Buy One, Get One Free
神题
问题转换为求最大收益
从大到小dp到一个价格为A的商品时
1.A跟之前未配对的商品配对，收益为A
2.拆开之前一个收益为P的配对(x,y)，使之与两个A配对(x,A)(y,A)，收益为2A-P
这样的意义是，如果我需要一个比较优的配对，从堆中取出(x,y)，需要两个从堆中取出(x,A)(y,A)
显然我们一定优先拆收益最小的配对，所以用一个小根堆维护
若P<A，则P是不优的，所以删除它，往堆中放两个A
这样的意义是，如果我需要一个比较优的配对，从堆中取出(x,A)，需要两个从堆中取出(x,A)(y,A)
复杂度nlogn
|
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 |
#include<map> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 100000000 #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 sum; int n,tmp; map<int,int>m; priority_queue<int,vector<int>,greater<int> >q,q2; int main() { n=read(); for(int i=1;i<=n;i++) { int x=read(); sum+=x;m[x]++; } for(map<int,int>::reverse_iterator i=m.rbegin();i!=m.rend();i++) { int A=i->first,num=i->second; while(tmp&&num) { tmp--;num--;q2.push(A); } while(num>=2&&(!q.empty()&&q.top()<2*A)) { if(q.top()<A)q2.push(A),q2.push(A); else q2.push(2*A-q.top()),q2.push(q.top()); num-=2; q.pop(); } if(num&&!q.empty()&&q.top()<A) q.pop(),q.push(A); while(!q2.empty()) q.push(q2.top()),q2.pop(); tmp+=num; } while(!q.empty()) { sum-=q.top();q.pop(); } cout<<sum<<endl; return 0; } |
计数器 9775010
OI 课件=>
OI 课件=>
黄学长虐题无数！太神啦！