[关闭]
@KirinBill 2017-12-25T06:27:13.000000Z 字数 4853 阅读 1133

AtCoder Regular Contest 088

题解

目录


C. Multiple Gift

题目大意:构造一个序列,使,求

思路

代码

  1. #include <cstdio>
  2. int main(){
  3. unsigned long long x,y;
  4. scanf("%llu%llu",&x,&y);
  5. int ans=0;
  6. while(x<=y) x<<=1,++ans;
  7. printf("%d",ans);
  8. return 0;
  9. }

D. Wide Flip

题目大意:给你一个01串,每次可以选一段长度不小于的区间~取反。求使能够变为全0串的

思路

代码

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using std::max;
  5. using std::min;
  6. const int MAXN=1e5+5;
  7. char s[MAXN];
  8. int main(){
  9. scanf("%s",s);
  10. int n=strlen(s),ans=n;
  11. for(int i=1;i<n;++i){
  12. if(s[i]!=s[i-1])
  13. ans=min(ans,max(i,n-i));
  14. }
  15. printf("%d",ans);
  16. return 0;
  17. }

E. Papple Sort

题目大意:给你一个字符串,每次可以交换相邻两个字符,求使变为回文串的最小交换次数(无解则输出)。

思路

代码

  1. #include <cstdio>
  2. #include <cstring>
  3. const int MAXN=2e5+5,INF=0x7f7f7f7f;
  4. int n;
  5. int a[MAXN];
  6. char s[MAXN];
  7. inline int chr_idx(char c){return c-'a';}
  8. template<class T>
  9. long long mge_sort(T a[],int l,int r){
  10. static T tmp[MAXN];
  11. if(l==r) return 0;
  12. int mid=l+r>>1;
  13. long long ret=mge_sort(a,l,mid)+mge_sort(a,mid+1,r);
  14. int lp=l,rp=mid+1,cur=l-1;
  15. while(lp<=mid && rp<=r){
  16. if(a[lp]<=a[rp]) tmp[++cur]=a[lp++];
  17. else{
  18. ret+=mid-lp+1;
  19. tmp[++cur]=a[rp++];
  20. }
  21. }
  22. while(lp<=mid) tmp[++cur]=a[lp++];
  23. while(rp<=r) tmp[++cur]=a[rp++];
  24. memcpy(a+l,tmp+l,(r-l+1)*sizeof(T));
  25. return ret;
  26. }
  27. inline void deal(){
  28. static int fir_pos[26],last_pos[26],pre[MAXN],nex[MAXN];
  29. static bool use[MAXN];
  30. for(int i=n;i;--i){
  31. nex[i]=fir_pos[chr_idx(s[i])];
  32. fir_pos[chr_idx(s[i])]=i;
  33. }
  34. for(int i=1;i<=n;++i){
  35. pre[i]=last_pos[chr_idx(s[i])];
  36. last_pos[chr_idx(s[i])]=i;
  37. }
  38. for(int i=0;i<26;++i){
  39. if(!fir_pos[i]) continue;
  40. for(int l=fir_pos[i],r=last_pos[i];r;l=nex[l],r=pre[r])
  41. a[n-l+1]=r;
  42. }
  43. }
  44. inline bool spj(){
  45. static int cnt[26];
  46. for(int i=1;i<=n;++i)
  47. ++cnt[chr_idx(s[i])];
  48. int tot=0;
  49. for(int i=0;i<26;++i){
  50. if(cnt[i]&1) ++tot;
  51. }
  52. return tot==(n&1);
  53. }
  54. int main(){
  55. scanf("%s",s+1);
  56. n=strlen(s+1);
  57. if(!spj()){
  58. printf("-1");
  59. return 0;
  60. }
  61. deal();
  62. printf("%lld",mge_sort(a,1,n)>>1);
  63. return 0;
  64. }

F. Christmas Tree

题目大意:你有个长度最多为的路径。每次可以选在不同连通块中的两个点,将它们合成一个点。最后要求合并成一个与所给的树同构的树。求的最小值及此时的最小值。

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. using std::sort;
  5. using std::vector;
  6. const int MAXN=1e5+5;
  7. int rt,n,A,B;
  8. int he[MAXN],deg[MAXN];
  9. int dp[MAXN];
  10. struct line{int to,nex;}ed[MAXN<<1];
  11. inline void addE(int u,int v){
  12. static int cnt;
  13. ed[++cnt]=(line){v,he[u]};
  14. he[u]=cnt;
  15. }
  16. inline bool cmp_dp(int a,int b){return dp[a]<dp[b];}
  17. inline bool check(vector<int> &vec,int son){
  18. for(int l=0,r=vec.size()-1;l<r;++l,--r){
  19. if(l==son) ++l;
  20. if(r==son) --r;
  21. if(dp[vec[l]]+dp[vec[r]]>B)
  22. return false;
  23. }
  24. return true;
  25. }
  26. inline int bin_chop_son(vector<int> &vec){
  27. int l=0,r=vec.size()-1,mid;
  28. while(l<=r){
  29. mid=l+r>>1;
  30. if(check(vec,mid)) r=mid-1;
  31. else l=mid+1;
  32. }
  33. return l;
  34. }
  35. bool treeDP(int u,int fa){
  36. vector<int> vec;
  37. for(int i=he[u],v;i;i=ed[i].nex){
  38. v=ed[i].to;
  39. if(v!=fa){
  40. if(!treeDP(v,u)) return false;
  41. vec.push_back(v);
  42. }
  43. }
  44. if(vec.size()==0){
  45. dp[u]=1;
  46. return true;
  47. }
  48. //度数为奇数,则儿子为偶数个
  49. if(deg[u]&1) vec.push_back(0);
  50. sort(vec.begin(),vec.end(),cmp_dp);
  51. int v=bin_chop_son(vec);
  52. if(v==vec.size()) return false;
  53. dp[u]=dp[vec[v]]+1;
  54. return dp[u]<=B+1;
  55. }
  56. inline void bin_chop_B(){
  57. int l=0,r=n;
  58. while(l<=r){
  59. B=l+r>>1;
  60. if(treeDP(rt,0)) r=B-1;
  61. else l=B+1;
  62. }
  63. B=l;
  64. }
  65. inline void cal_A(){
  66. int cnt=0;
  67. for(int i=1;i<=n;++i)
  68. cnt+=deg[i]&1;
  69. A=cnt>>1;
  70. }
  71. int main(){
  72. scanf("%d",&n);
  73. for(int i=1,u,v;i<n;++i){
  74. scanf("%d%d",&u,&v);
  75. ++deg[u],++deg[v];
  76. addE(u,v),addE(v,u);
  77. }
  78. cal_A();
  79. for(int i=1;i<=n;++i){
  80. if(deg[i]==1){
  81. rt=i;
  82. break;
  83. }
  84. }
  85. bin_chop_B();
  86. printf("%d %d",A,B);
  87. return 0;
  88. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注