Educational Codeforces Round 90 (Rated for Div. 2)(D 思维 E 打表)ccsudeer-educational codeforces round 90 (rated for div. 2)

题目链接

D. Maximum Sum on Even Positions

题意：给你n长度的数组a  要求翻转 子区间  使得  偶数上的数之和尽量最大。

做法:用偶数位置减去奇数位置的值  就相当于求子序列最大值，随便dp一下就好了，这类题  主要思路就是化简为以前遇到过的经典题。同理奇数位置减去偶数也跑一遍即可。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e6+10; int n; ll a[N],res,ans; int main() {     int _=read();while(_--)     {         n=read();         ans=0;         rep(i,1,n) {             a[i]=read();             if(i%2==1) ans+=a[i];         }          ll mx=0,res=0,sum=0;         for(int i=2;i<=n;i+=2)         {             sum=max(0ll,a[i]-a[i-1]+sum);             mx=max(mx,sum);             //mx=max(mx,max(a[i]-a[i-1]+mx,0ll));         }          sum=0;         for(int i=3;i<=n;i+=2){             sum=max(0ll,a[i-1]-a[i]+sum);             mx=max(mx,sum);         }           printf("%lldn",ans+mx);     } } /* 4 5 1 2 3 4 5  5 5 4 3 2 1  4 10 7 8 4 5 7 6 8 9 7 3  */ 

E. Sum of Digits

题意：给你 n 和 k  求最小的x  使得 x 、 x+1 、x+2  的各位数上的和等于n

做法：这题提供打表的做法，这类n不是很大的情况，而且自己一时半会也想不到什么好的思路，就可以用这种方法搞一发。

1、当k>=2的时候是可以暴力跑的

2、k=0  直接构造 最低位尽量填9就可以了。

3、至于k=1 怎么弄呢？暴力跑又很大，超时。

其实很简单，当n是奇数  n/2+1  按照k=0 的构造就好了， 然后构造出的答案减1 才是最小值

当n是偶数

就是第一个数 的第一位尽量是9  第二位尽量是8 （如果够的话。）只进位一次。

那么设 x  x+1   f(x) =y  f(x+1)=y+1-9    n=2*y-8   计算出y  然后  第一位尽量是9  第二位尽量是8 构造就可以了。

暴力打表程序：

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } int f(int x) {     int ans=0;     while(x) ans+=x%10,x=x/10;     return ans; } unordered_map <int,int>mp; string run(int x) {     string ans="";     if(x%9!=0) ans+=x%9+'0';     for(int i=1;i<=x/9;++i) ans+='9';     return ans; } string run1(int x) {     string ans="";     if(x>=9) ans+='9',x-=9;     if(x>=8) ans+='8',x-=8;     for(int i=1;i<=x/9;++i) ans+='9';     if(x%9!=0) ans+=x%9+'0';     reverse(ans.begin(),ans.end());     return ans; } int main() {     //cout<<run1(28)<<endl;     freopen("output.txt", "w", stdout);      for(int i=0;i<=1000000;++i) mp[i]=f(i);      for(int i=0;i<=150;++i){         printf("{");         for(int k=0;k<=9;++k){             int flag=0;             if(i==0){                 printf("-1");continue;                 if(k!=9) printf(",");             }               if(k==0){                 string ans=run(i);                 cout<<ans;                 if(k!=9) printf(",");                 continue;             }             else if(k==1){                 string ans;                 if(i<10){                     if(i==1) printf("0");                     else if(i==2) printf("-1");                     else if(i==3) printf("1");                     else if(i==4) printf("-1");                     else if(i==5) printf("2");                     else if(i==6) printf("-1");                     else if(i==7) printf("3");                     else if(i==8) printf("-1");                     else if(i==9) printf("4");                     if(k!=9) printf(",");                     continue;                 }                 if(i%2==0){                     int d=(i+8)/2;                     ans=run1(d);                 }                 else{                     int d=i/2+1;                     ans=run(d);                     int flag=1;                     for(int i=ans.size()-1;i>=0;--i){                         if(ans[i]=='0'){                             ans[i]='9';                         }                         else{                             ans[i]=ans[i]-1;break;                         }                     }                     //这里应该是模拟减1                  }                 cout<<ans;                 if(k!=9) printf(",");                 continue;             }              int res=0;             for(int j=0;j<=k;++j) res+=mp[j];              //printf("i:%d k:%d res:%dn",i,k,res);              if(res==i){                 printf("%d",0);                 if(k!=9) printf(",");                 continue;             }              for(int j=k+1;j<=1000000&&!flag;++j){                 res+=mp[j]-mp[j-k-1];                 if(res==i){                     printf("%d",j-k);                     if(k!=9) printf(",");                     flag=1;                     break;                 }             }             if(!flag) printf("%d,",-1);         }         puts("},");     }    } 

AC 代码

 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll ans[151][12]={{-1-1-1-1-1-1-1-1-1-1}, {1,0,-1,-1,-1,-1,-1,-1,-1,-1,}, {2,-1,-1,-1,-1,-1,-1,-1,-1,-1,}, {3,1,0,-1,-1,-1,-1,-1,-1,-1,}, {4,-1,-1,-1,-1,-1,-1,-1,-1,-1,}, {5,2,-1,-1,-1,-1,-1,-1,-1,-1,}, {6,-1,1,0,-1,-1,-1,-1,-1,-1,}, {7,3,-1,-1,-1,-1,-1,-1,-1,-1,}, {8,-1,-1,-1,-1,-1,-1,-1,-1,-1,}, {9,4,2,-1,-1,-1,-1,-1,-1,-1,}, {19,9,-1,1,0,-1,-1,-1,-1,-1,}, {29,5,-1,-1,-1,-1,-1,-1,-1,-1,}, {39,19,3,-1,-1,-1,-1,-1,-1,-1,}, {49,6,-1,-1,-1,-1,-1,-1,-1,-1,}, {59,29,-1,2,-1,-1,-1,-1,-1,-1,}, {69,7,4,9,1,0,-1,-1,-1,-1,}, {79,39,-1,-1,-1,-1,-1,-1,-1,-1,}, {89,8,-1,-1,-1,-1,-1,-1,-1,-1,}, {99,49,5,3,-1,-1,-1,-1,-1,-1,}, {199,18,-1,19,9,-1,-1,-1,-1,-1,}, {299,59,-1,8,2,-1,-1,-1,-1,-1,}, {399,28,6,-1,-1,1,0,-1,-1,-1,}, {499,69,-1,4,-1,-1,-1,-1,-1,-1,}, {599,38,-1,29,8,-1,-1,-1,-1,-1,}, {699,79,7,18,19,9,-1,-1,-1,-1,}, {799,48,-1,7,3,-1,-1,-1,-1,-1,}, {899,89,-1,5,-1,-1,-1,-1,-1,-1,}, {999,58,17,39,7,2,-1,-1,-1,-1,}, {1999,189,-1,28,18,-1,1,0,-1,-1,}, {2999,68,-1,17,29,-1,-1,-1,-1,-1,}, {3999,289,27,6,4,7,9,-1,-1,-1,}, {4999,78,-1,49,6,-1,-1,-1,-1,-1,}, {5999,389,-1,38,17,-1,8,-1,-1,-1,}, {6999,88,37,27,28,3,-1,-1,-1,-1,}, {7999,489,-1,16,39,-1,7,-1,-1,-1,}, {8999,98,-1,59,5,-1,2,-1,-1,-1,}, {9999,589,47,48,16,5,6,1,0,-1,}, {19999,198,-1,37,27,-1,19,9,-1,-1,}, {29999,689,-1,26,38,-1,5,8,-1,-1,}, {39999,298,57,69,49,4,18,7,-1,-1,}, {49999,789,-1,58,15,-1,4,6,-1,-1,}, {59999,398,-1,47,26,-1,17,5,-1,-1,}, {69999,889,67,36,37,15,3,4,-1,-1,}, {79999,498,-1,79,48,-1,16,3,-1,-1,}, {89999,989,-1,68,59,-1,29,2,-1,-1,}, {99999,598,77,57,25,14,15,19,1,0}, {199999,1989,-1,46,36,-1,28,18,-1,1}, {299999,698,-1,89,47,-1,14,17,-1,2}, {399999,2989,87,78,58,25,27,16,-1,3}, {499999,798,-1,67,69,-1,13,15,-1,4}, {599999,3989,-1,56,35,-1,26,14,-1,5}, {699999,898,97,189,46,24,39,13,-1,6}, {799999,4989,-1,88,57,-1,25,12,-1,7}, {899999,998,-1,77,68,-1,38,29,-1,8}, {999999,5989,197,66,79,35,24,28,11,9}, {1999999,1998,-1,289,45,-1,37,27,-1,10}, {2999999,6989,-1,188,56,-1,23,26,-1,11}, {3999999,2998,297,87,67,34,36,25,-1,12}, {4999999,7989,-1,76,78,-1,49,24,-1,13}, {5999999,3998,-1,389,89,-1,35,23,-1,14}, {6999999,8989,397,288,55,45,48,22,-1,15}, {7999999,4998,-1,187,66,-1,34,39,-1,16}, {8999999,9989,-1,86,77,-1,47,38,-1,17}, {9999999,5998,497,489,88,44,33,37,21,18}, {19999999,19989,-1,388,189,-1,46,36,-1,19}, {29999999,6998,-1,287,65,-1,59,35,-1,20}, {39999999,29989,597,96,76,55,45,34,-1,21}, {49999999,7998,-1,589,87,-1,58,33,-1,22}, {59999999,39989,-1,488,188,-1,44,32,-1,23}, {69999999,8998,697,387,289,54,57,49,-1,24}, {79999999,49989,-1,196,75,-1,43,48,-1,25}, {89999999,9998,-1,689,86,-1,56,47,-1,26}, {99999999,59989,797,588,187,65,69,46,31,27}, {199999999,19998,-1,487,288,-1,55,45,-1,28}, {299999999,69989,-1,296,389,-1,68,44,-1,29}, {399999999,29998,897,789,85,64,54,43,-1,30}, {499999999,79989,-1,688,186,-1,67,42,-1,31}, {599999999,39998,-1,587,287,-1,53,59,-1,32}, {699999999,89989,997,396,388,75,66,58,-1,33}, {799999999,49998,-1,889,489,-1,79,57,-1,34}, {899999999,99989,-1,788,95,-1,65,56,-1,35}, {999999999,59998,1997,687,286,74,78,55,41,36}, {1999999999,199989,-1,496,387,-1,64,54,-1,37}, {2999999999,69998,-1,989,488,-1,77,53,-1,38}, {3999999999,299989,2997,888,589,85,63,52,-1,39}, {4999999999,79998,-1,787,195,-1,76,69,-1,40}, {5999999999,399989,-1,596,386,-1,89,68,-1,41}, {6999999999,89998,3997,1989,487,84,75,67,-1,42}, {7999999999,499989,-1,988,588,-1,88,66,-1,43}, {8999999999,99998,-1,887,689,-1,74,65,-1,44}, {9999999999,599989,4997,696,295,185,87,64,51,45}, {19999999999,199998,-1,2989,486,-1,73,63,-1,46}, {29999999999,699989,-1,1988,587,-1,86,62,-1,47}, {39999999999,299998,5997,987,688,94,189,79,-1,48}, {49999999999,799989,-1,796,789,-1,85,78,-1,49}, {59999999999,399998,-1,3989,395,-1,188,77,-1,50}, {69999999999,899989,6997,2988,586,285,84,76,-1,51}, {79999999999,499998,-1,1987,687,-1,187,75,-1,52}, {89999999999,999989,-1,896,788,-1,83,74,-1,53}, {99999999999,599998,7997,4989,889,194,186,73,61,54}, {199999999999,1999989,-1,3988,495,-1,289,72,-1,55}, {299999999999,699998,-1,2987,686,-1,185,89,-1,56}, {399999999999,2999989,8997,996,787,385,288,88,-1,57}, {499999999999,799998,-1,5989,888,-1,184,87,-1,58}, {599999999999,3999989,-1,4988,989,-1,287,86,-1,59}, {699999999999,899998,9997,3987,595,294,93,85,-1,60}, {799999999999,4999989,-1,1996,786,-1,286,84,-1,61}, {899999999999,999998,-1,6989,887,-1,389,83,-1,62}, {999999999999,5999989,19997,5988,988,485,285,82,71,63}, {1999999999999,1999998,-1,4987,1989,-1,388,189,-1,64}, {2999999999999,6999989,-1,2996,695,-1,284,188,-1,65}, {3999999999999,2999998,29997,7989,886,394,387,187,-1,66}, {4999999999999,7999989,-1,6988,987,-1,193,186,-1,67}, {5999999999999,3999998,-1,5987,1988,-1,386,185,-1,68}, {6999999999999,8999989,39997,3996,2989,585,489,184,-1,69}, {7999999999999,4999998,-1,8989,795,-1,385,183,-1,70}, {8999999999999,9999989,-1,7988,986,-1,488,92,-1,71}, {9999999999999,5999998,49997,6987,1987,494,384,289,81,72}, {19999999999999,19999989,-1,4996,2988,-1,487,288,-1,73}, {29999999999999,6999998,-1,9989,3989,-1,293,287,-1,74}, {39999999999999,29999989,59997,8988,895,685,486,286,-1,75}, {49999999999999,7999998,-1,7987,1986,-1,589,285,-1,76}, {59999999999999,39999989,-1,5996,2987,-1,485,284,-1,77}, {69999999999999,8999998,69997,19989,3988,594,588,283,-1,78}, {79999999999999,49999989,-1,9988,4989,-1,484,192,-1,79}, {89999999999999,9999998,-1,8987,995,-1,587,389,-1,80}, {99999999999999,59999989,79997,6996,2986,785,393,388,91,81}, {199999999999999,19999998,-1,29989,3987,-1,586,387,-1,82}, {299999999999999,69999989,-1,19988,4988,-1,689,386,-1,83}, {399999999999999,29999998,89997,9987,5989,694,585,385,-1,84}, {499999999999999,79999989,-1,7996,1995,-1,688,384,-1,85}, {599999999999999,39999998,-1,39989,3986,-1,584,383,-1,86}, {699999999999999,89999989,99997,29988,4987,885,687,292,-1,87}, {799999999999999,49999998,-1,19987,5988,-1,493,489,-1,88}, {899999999999999,99999989,-1,8996,6989,-1,686,488,-1,89}, {999999999999999,59999998,199997,49989,2995,794,789,487,191,90}, {1999999999999999,199999989,-1,39988,4986,-1,685,486,-1,181}, {2999999999999999,69999998,-1,29987,5987,-1,788,485,-1,182}, {3999999999999999,299999989,299997,9996,6988,985,684,484,-1,183}, {4999999999999999,79999998,-1,59989,7989,-1,787,483,-1,184}, {5999999999999999,399999989,-1,49988,3995,-1,593,392,-1,185}, {6999999999999999,89999998,399997,39987,5986,894,786,589,-1,186}, {7999999999999999,499999989,-1,19996,6987,-1,889,588,-1,187}, {8999999999999999,99999998,-1,69989,7988,-1,785,587,-1,188}, {9999999999999999,599999989,499997,59988,8989,1985,888,586,291,189}, {19999999999999999,199999998,-1,49987,4995,-1,784,585,-1,190}, {29999999999999999,699999989,-1,29996,6986,-1,887,584,-1,281}, {39999999999999999,299999998,599997,79989,7987,994,693,583,-1,282}, {49999999999999999,799999989,-1,69988,8988,-1,886,492,-1,283}, {59999999999999999,399999998,-1,59987,9989,-1,989,689,-1,284}, {69999999999999999,899999989,699997,39996,5995,2985,885,688,-1,285}}; int main() {     int _;scanf("%d",&_);while(_--)     {         int n,k;         scanf("%d%d",&n,&k);         printf("%lldn",ans[n][k]);     } }