题解 Educational Codeforces Round 80 [Rated for Div. 2](CF1288)

前言:11点的时候某天下第一可爱的萌神问我怎么不打CF,跑去开题,11:30终于开了C和D,秒了一下,考后萌神轻松上分并告诉我E的tag于是我赛后补题。

A:n/x上取整是(n-1)/x+1,式子变形成x+1+(n-1)/(x+1)<=d。根据a+b>=2√ab随便化简一下。(20s秒了??)

 1 #include
 2 #include
 3 using namespace std;
 4 int T,n,d,x,y;
 5 int main(){ 
 6     scanf("%d",&T);
 7     while(T--)
 8         scanf("%d%d",&d,&n),x=sqrt(n-1),y=x-1,((n<=d)||(x+1+(n-1)/(x+1)<=d)||(y+1+(n-1)/(y+1)<=d))?puts("YES"):puts("NO");
 9     return 0;
10 }
View Code

B:a*b+a+b=a*10b的位数+b。化简得知b+1=10b的位数。所以只有9,99,999……这样是可行的。那么统计B是几位数啥的随便算算再乘个A输出,还有要判相等。(1min不到秒了??)

 1 #include
 2 const int x[]={0,0,9,99,999,9999,99999,999999,9999999,99999999,999999999,1000000001};
 3 const int y[]={0,0,1,2,3,4,5,6,7,8,9};
 4 int T,a,b,i;
 5 int main(){  
 6     scanf("%d",&T);
 7     while(T--){
 8         scanf("%d%d",&a,&b);
 9         for(i=1;i<=10&&x[i+1]<=b;++i);
10         printf("%lld\n",1ll*a*y[i]);
11     }
12     return 0;
13 }
View Code

C:做过构造解的原题呢。会两种dp的写法。

一眼秒的O(n2m)做法:设f[i][j]=到i,选择的元素为j的方案。由于A不降B不升,所以并起来看。那么f[i][j]+=f[i-1][k](k<=j)。ans=Σf[2*m][i],1<=i<=n

再想想的O(nm)做法:f[i][j]+=f[i-1][j]+f[i][j-1]。就是把枚举k的那一维省去,直接把j的贡献用j-1的贡献计算,因为这1~n个元素是连续的。 ans=Σf[n][i],1<=i<=2*m;

困死了明早去机房补代码。

(越做越后悔没打上分场.jpg)

D:开始就想了个二分+枚举子集。萌神说只要枚举子集看是A还是B的贡献就行。所以为什么我要多个log?人间迷惑.jpg

仍然把代码咕咕咕到明天。

E:萌神说是莫队,我:??我打不开E。

F:??打不开告辞,明早去机房补。

你可能感兴趣的