1.29 CF edu103

A题：

容斥原理直接除就行；

代码：

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 int main(){
 5     int T;
 6     scanf("%d",&T);
 7     while (T--){
 8         ll n,k;
 9         scanf("%lld%lld",&n,&k);
10         ll cmp=k;
11         while (cmp<n){
12             cmp+=k;
13         }
14         ll res=(cmp+n-1)/n;
15         printf("%lld
",res);
16     }
17 }

View Code

B题：

从后往前推一遍，保证小于k%就行。

代码：

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll a[105],n,k;
 5 int main(){
 6     int T;
 7     scanf("%d",&T);
 8     while (T--){
 9         scanf("%lld%lld",&n,&k);
10         ll sum=0;
11         for (int i=1; i<=n; i++){
12             scanf("%lld",&a[i]);
13             sum+=a[i];
14         }
15         ll ret=0;
16         for (int i=n; i>=2; i--){
17             sum-=a[i];
18             if (100*a[i]>k*sum){
19                 ll add;
20                 if (100*a[i]%k==0)
21                    add=100*a[i]/k-sum;
22                 else add=100*a[i]/k-sum+1;
23                 ret+=add;
24                 sum+=add;
25             }
26         }
27         printf("%lld
",ret);
28     }
29 }

View Code

C题：

DP，从后往前，每次选一下是只要两个还是加上之前做出来的最优解。

代码：

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 ll n,a[100005],b[100005],c[100005],d[100005],sum[100005];
 5 ll dp[100005];
 6 int main(){
 7     int T;
 8     scanf("%d",&T);
 9     while (T--){
10         scanf("%lld",&n);
11         for (int i=1; i<=n; i++)
12             scanf("%lld",&a[i]);
13         for (int i=1; i<=n; i++)
14             scanf("%lld",&b[i]);
15         for (int i=1; i<=n; i++)
16             scanf("%lld",&c[i]);
17         for (int i=1; i<n; i++){
18             d[i]=abs(b[i+1]-c[i+1])+1;
19         }
20         dp[n-1]=d[n-1]+a[n];
21         for (int i=n-2; i>=1; i--){
22             dp[i]=d[i]+a[i+1];
23             if (d[i+1]!=1){
24                 dp[i]=max(d[i]+min(c[i+2],b[i+2])+a[i+1]-max(c[i+2],b[i+2])+1+dp[i+1]-d[i+1],dp[i]);
25             }
26         }
27         ll ret=0;
28         for (int i=1; i<=n-1; i++)
29             ret=max(ret,dp[i]);
30         printf("%lld
",ret);
31     }
32 }

View Code

D题：

打的时候感觉是个记忆化，可惜写挂了，没时间改，之后别人告诉我递推也能过（当然记忆化也行），之后赶紧补一下。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int st[300005],ed[300005],res[300005];
 4 char s[300005];
 5 int n;
 6 int main(){
 7     int T;
 8     scanf("%d",&T);
 9     while (T--){
10         scanf("%d",&n);
11         scanf("%s",s+1);
12         st[0]=0;
13         for (int i=1; i<=n; i++){
14             if (s[i]=='L'){
15                 if (i==1) st[i]=st[i-1]+1;
16                 else if (st[i-1]==0){
17                     st[i]=st[i-2]+2;
18                 }
19                 else st[i]=1;
20             }
21             else {
22                 st[i]=0;
23             }
24         }
25         ed[n]=0;
26         for (int i=n-1; i>=0; i--){
27             if (s[i+1]=='R'){
28                 if (i==n-1) ed[i]=ed[i+1]+1;
29                 else if (ed[i+1]==0){
30                     ed[i]=ed[i+2]+2;
31                 }
32                 else ed[i]=1;
33             }
34             else {
35                 ed[i]=0;
36             }
37         }
38         for (int i=0; i<=n; i++)
39             printf("%d ",ed[i]+1+st[i]);
40         printf("
");
41     }
42     return 0;
43 }

View Code

(连打两场CF状态真的很差，前一天上的分全还回去[叹气]