[关闭]
@KirinBill 2017-09-18T10:17:07.000000Z 字数 6764 阅读 535

AtCoder Regular Contest 080

题解 套题

目录


C. 4-adjacent

题目大意:给你一个数列,问是否能通过置换(交换某些元素的位置),使得该数列满足

思路

代码

  1. #include <cstdio>
  2. const int MAXN=1e5+5;
  3. int n,cnt_4,cnt_not4;
  4. int a[MAXN];
  5. int main(){
  6. scanf("%d",&n);
  7. for(int i=1;i<=n;++i){
  8. scanf("%d",&a[i]);
  9. if(a[i]%4==0) ++cnt_4;
  10. else if(a[i]%2) ++cnt_not4;
  11. }
  12. if(cnt_4>=cnt_not4 || (cnt_4>=cnt_not4-1 && cnt_4+cnt_not4==n)) printf("Yes");
  13. else printf("No");
  14. return 0;
  15. }

D. Grid Coloring

题目大意:给你种颜色,每种有一个数量要求,你要对一个的四连通矩阵染色,使每种颜色数量为,并且每种颜色的方格必须互相连通,给出一种方案。

思路

代码

  1. #include <cstdio>
  2. #include <queue>
  3. using std::queue;
  4. const int MAXHW=105;
  5. int n,h,w,a;
  6. int sqr[MAXHW][MAXHW];
  7. queue<int> q,ans;
  8. int main(){
  9. scanf("%d%d%d",&h,&w,&n);
  10. for(int i=1;i<=n;++i){
  11. scanf("%d",&a);
  12. q.push(a);
  13. }
  14. int k=0;
  15. while(++k,q.size()){
  16. a=q.front();
  17. q.pop();
  18. for(int i=1;i<=a;++i)
  19. ans.push(k);
  20. }
  21. for(int i=1;i<=h;i+=2){
  22. for(int j=1;j<=w;++j){
  23. sqr[i][j]=ans.front();
  24. ans.pop();
  25. }
  26. for(int j=w;j && ans.size();--j){
  27. sqr[i+1][j]=ans.front();
  28. ans.pop();
  29. }
  30. }
  31. for(int i=1;i<=h;++i){
  32. for(int j=1;j<=w;++j)
  33. printf("%d ",sqr[i][j]);
  34. putchar('\n');
  35. }
  36. return 0;
  37. }

E. Young Maids

题目大意:给你一个数列,每次可以取出相邻的两个数按原数列顺序加到一个新的数列的头部,求字典序最小的新数列。

思路

考试的时候傻掉了。。。

代码

整体不难,但实现起来有些繁琐

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <utility>
  4. #include <queue>
  5. #include <vector>
  6. #include <functional>
  7. #include <climits>
  8. #include <cmath>
  9. using std::min;
  10. using std::pair;
  11. using std::priority_queue;
  12. using std::vector;
  13. using std::greater;
  14. typedef pair<int,int> range;
  15. typedef pair<int,int> number;
  16. typedef pair<number,range> sub_qry;
  17. const int MAXN=2e5+5,MAXLOG=(int)(log(MAXN)/log(2)+0.5);
  18. int p[MAXN];
  19. class SparseTab{
  20. private:
  21. int log_tab[MAXN];
  22. number c[MAXLOG][MAXN];
  23. public:
  24. void build(int n,int a[],bool type){
  25. log_tab[0]=-1;
  26. for(int i=1;i<=n;++i){
  27. c[0][i]=number((i&1)==type ? a[i]:INT_MAX,i);
  28. log_tab[i]= i&(i-1) ? log_tab[i-1]:log_tab[i-1]+1;
  29. }
  30. for(int i=1;i<=log_tab[n];++i){
  31. for(int j=1;j+(1<<i)-1<=n;++j)
  32. c[i][j]=min(c[i-1][j],c[i-1][j+(1<<i-1)]);
  33. }
  34. }
  35. number qry(int l,int r){
  36. int k=log_tab[r-l+1];
  37. return min(c[k][l],c[k][r-(1<<k)+1]);
  38. }
  39. }odd,even;
  40. inline void solve(int n){
  41. static priority_queue<sub_qry,vector<sub_qry>,greater<sub_qry> > hp;
  42. number tmp1=odd.qry(1,n),tmp2=even.qry(tmp1.second,n);
  43. printf("%d %d ",tmp1.first,tmp2.first);
  44. if(1<=tmp1.second-1)
  45. hp.push(sub_qry(odd.qry(1,tmp1.second-1),range(1,tmp1.second-1)));
  46. if(tmp1.second+1<=tmp2.second-1)
  47. hp.push(sub_qry(even.qry(tmp1.second+1,tmp2.second-1),range(tmp1.second+1,tmp2.second-1)));
  48. if(tmp2.second+1<=n)
  49. hp.push(sub_qry(odd.qry(tmp2.second+1,n),range(tmp2.second+1,n)));
  50. sub_qry now;
  51. number that;
  52. SparseTab *st1,*st2;
  53. while(hp.size()){
  54. now=hp.top();
  55. hp.pop();
  56. st1= now.second.first&1 ? &odd:&even;
  57. st2= now.second.first&1 ? &even:&odd;
  58. that=st2->qry(now.first.second,now.second.second);
  59. printf("%d %d ",now.first.first,that.first);
  60. if(now.second.first<now.first.second-1)
  61. hp.push(sub_qry(st1->qry(now.second.first,now.first.second-1),range(now.second.first,now.first.second-1)));
  62. if(now.first.second+1<that.second-1)
  63. hp.push(sub_qry(st2->qry(now.first.second+1,that.second-1),range(now.first.second+1,that.second-1)));
  64. if(that.second+1<now.second.second)
  65. hp.push(sub_qry(st1->qry(that.second+1,now.second.second),range(that.second+1,now.second.second)));
  66. }
  67. }
  68. int main(){
  69. int n;
  70. scanf("%d",&n);
  71. for(int i=1;i<=n;++i)
  72. scanf("%d",&p[i]);
  73. odd.build(n,p,1),even.build(n,p,0);
  74. solve(n);
  75. return 0;
  76. }

F. Prime Flip

题目大意:有一个无限长的卡片序列标号为,给定个数,这些数对应标号的卡片是向上的,其它为向下的,每次只可以连续翻转奇质数长度的卡片,求使得整个卡片序列都向下的最少操作次数。()。

思路

这题太神了,看了半天题解。。。orz

代码

  1. #include <cstdio>
  2. #include <cmath>
  3. #include <climits>
  4. #include <queue>
  5. #include <algorithm>
  6. using std::queue;
  7. using std::min;
  8. const int MAXX=1e7+5,MAXN=205;
  9. int n,cnt_x,cnt_y;
  10. int x_id[MAXN],y_id[MAXN];
  11. bool up[MAXX];
  12. struct node{int he,iter,dis;}d[MAXN];
  13. struct line{int to,nex,cap;}ed[MAXN*MAXN<<1];
  14. inline bool is_odd_prm(int x){
  15. if(x==1) return false;
  16. for(int i=2;i*i<=x;++i){
  17. if(x%i==0) return false;
  18. }
  19. return true;
  20. }
  21. inline void addE(int u,int v,int cap){
  22. static int cnt=1;
  23. ed[++cnt]=(line){v,d[u].he,cap};
  24. d[u].he=cnt;
  25. }
  26. inline int revE(int i){return i^1;}
  27. inline bool BFS(int s,int t,int n){
  28. for(int i=1;i<=n;++i)
  29. d[i].dis=-1;
  30. static queue<int> q;
  31. d[s].dis=0;
  32. q.push(s);
  33. int u;
  34. while(q.size()){
  35. u=q.front();
  36. q.pop();
  37. for(int i=d[u].he,v;i;i=ed[i].nex){
  38. if(ed[i].cap==0) continue;
  39. v=ed[i].to;
  40. if(d[v].dis==-1){
  41. d[v].dis=d[u].dis+1;
  42. q.push(v);
  43. }
  44. }
  45. }
  46. return d[t].dis!=-1;
  47. }
  48. int aug(int u,int rest,const int t){
  49. if(u==t) return rest;
  50. int ret=0;
  51. for(int &i=d[u].iter,v,cap,flow;i;i=ed[i].nex){
  52. v=ed[i].to,cap=ed[i].cap;
  53. if(d[v].dis!=d[u].dis+1 || cap==0)
  54. continue;
  55. flow=aug(v,min(cap,rest),t);
  56. ed[i].cap-=flow,ed[revE(i)].cap+=flow;
  57. ret+=flow,rest-=flow;
  58. if(rest==0) return ret;
  59. }
  60. if(ret==0) d[u].dis=-1;
  61. return ret;
  62. }
  63. inline int Dinic(int s,int t,int n){
  64. int ret=0;
  65. while(BFS(s,t,n)){
  66. for(int i=1;i<=n;++i)
  67. d[i].iter=d[i].he;
  68. ret+=aug(s,INT_MAX,t);
  69. }
  70. return ret;
  71. }
  72. inline void build(){
  73. for(int i=1;i<=cnt_x;++i){
  74. for(int j=1,v;j<=cnt_y;++j){
  75. if(is_odd_prm(abs(x_id[i]-y_id[j]))){
  76. v=j+cnt_x;
  77. addE(i,v,INT_MAX),addE(v,i,0);
  78. }
  79. }
  80. }
  81. for(int i=1,s=cnt_x+cnt_y+1;i<=cnt_x;++i)
  82. addE(s,i,1),addE(i,s,0);
  83. for(int i=1,u,t=cnt_x+cnt_y+2;i<=cnt_y;++i){
  84. u=cnt_x+i;
  85. addE(u,t,1),addE(t,u,0);
  86. }
  87. }
  88. int main(){
  89. scanf("%d",&n);
  90. int x;
  91. for(int i=1;i<=n;++i){
  92. scanf("%d",&x);
  93. up[x]=true;
  94. }
  95. for(int i=1;i<=x+1;++i){
  96. if(up[i]!=up[i-1])
  97. i&1 ? x_id[++cnt_x]=i:y_id[++cnt_y]=i;
  98. }
  99. build();
  100. int k=Dinic(cnt_x+cnt_y+1,cnt_x+cnt_y+2,cnt_x+cnt_y+2);
  101. printf("%d",k+((cnt_x-k)/2+(cnt_y-k)/2)*2+(cnt_x-k)%2*3);
  102. return 0;
  103. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注