Educational Codeforces Round 53 (Rated for Div. 2)

http://codeforces.com/contest/1073

A. Diverse Substring

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define minv 1e-6
 5 #define inf 1e9
 6 #define pi 3.1415926536
 7 #define nl 2.7182818284
 8 const ll mod=1e9+7;//998244353
 9 const int maxn=1e3+10;
10 
11 char s[maxn];
12 
13 int main()
14 {
15     int n,i;
16     scanf("%d",&n);
17     scanf("%s",s);
18     for (i=0;i<=n-2;i++)
19         if (s[i]!=s[i+1])
20             break;
21     if (i==n-1)
22         printf("NO");
23     else
24     {
25         printf("YES
");
26         printf("%c%c",s[i],s[i+1]);
27     }
28     return 0;
29 }

B. Vasya and Books

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int maxn=2e5+10;
 5 
 6 int f[maxn];
 7 
 8 int main()
 9 {
10     int n,a,v=0,i;
11     scanf("%d",&n);
12     for (i=1;i<=n;i++)
13     {
14         scanf("%d",&a);
15         f[a]=i;
16     }
17     for (i=1;i<=n;i++)
18     {
19         scanf("%d",&a);
20         if (i!=1)
21             printf(" ");
22         if (f[a]<v)
23             printf("0");
24         else
25             printf("%d",f[a]-v);
26         v=max(f[a],v);
27     }
28     return 0;
29 }

C. Vasya and Robot

奇偶，负数取模

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=2e5+10;
 5 const ll inf=1e9;
 6 
 7 int px[maxn],py[maxn];
 8 
 9 int main()
10 {
11     char c;
12     int n,x,y,ax,ay,i,l,r,m,re;
13     scanf("%d
",&n);
14     for (i=1;i<=n;i++)
15     {
16         scanf("%c",&c);
17         if (c=='U')
18             x=0,y=1;
19         else if (c=='D')
20             x=0,y=-1;
21         else if (c=='L')
22             x=-1,y=0;
23         else
24             x=1,y=0;
25         px[i]=px[i-1]+x;
26         py[i]=py[i-1]+y;
27     }
28     scanf("%d%d",&ax,&ay);
29     if (px[n]==ax && py[n]==ay)
30     {
31         printf("0");
32         return 0;
33     }
34     if (abs(ax+ay+n)%2==1)
35     {
36         printf("-1");
37         return 0;
38     }
39     re=inf;
40     for (i=1;i<=n;i++)
41     {
42         l=i;
43         r=n;
44         while (l<=r)
45         {
46             m=(l+r)>>1;
47             ///change [i,m] ; use [1,i-1] [m+1,n]
48             if (m-i+1>=abs(px[i-1]+px[n]-px[m]-ax)+abs(py[i-1]+py[n]-py[m]-ay))
49                 r=m-1;
50             else
51                 l=m+1;
52         }
53         if (l!=n+1)
54             re=min(re,l-i+1);
55     }
56     if (re==inf)
57         re=-1;
58     printf("%d",re);
59     return 0;
60 }

D. Berland Fair

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int maxn=2e5+10;
 5 
 6 int nex[maxn],a[maxn];
 7 
 8 int main()
 9 {
10     int n,i,j,g;
11     ll m,tot=0,num=0;
12     scanf("%d%lld",&n,&m);
13 
14     for (i=0;i<n;i++)
15         scanf("%d",&a[i]),tot+=a[i];
16     for (i=0;i<n;i++)
17         nex[i]=(i+1)%n;
18     g=n;
19     i=0;
20     j=n-1;
21     while (nex[i]!=i)
22     {
23         num+=m/tot*g;
24         m%=tot;
25         while (nex[i]!=i)
26         {
27             if (a[i]<=m)
28             {
29                 m-=a[i];
30                 num++;
31                 j=i;
32             }
33             else
34             {
35                 nex[j]=nex[i];
36                 tot-=a[i];
37                 g--;
38             }
39             i=nex[i];
40             if (m>=tot)
41                 break;
42         }
43     }
44     num+=m/a[i];
45     cout<<num;
46     return 0;
47 }
48 /*
49 1 100
50 1
51 
52 3 1000
53 1 2 100
54 */

E. Segment Sum

代码是错的，以待后续埋坑

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const ll mod=998244353;
 5 const double minv=1e-10;
 6 
 7 ll sum=0,shi[20],k,f[20][20];
 8 
 9 void work(ll a,int w,int g,int hav,ll num,int ori,int cond)
10 {
11     int s,gg,i,j,c;
12     if (a==0)
13         return;
14     s=a/shi[w];
15     for (i=0;i<=s;i++)
16     {
17         gg=g-(!((hav>>i) & 1) && (!(i==0 && ori==1)));
18         if (gg>=0)
19         {
20             if (i<s)
21             {
22                 /**
23                 这一位选的是i，
24                 除去这一位，还有w位，
25                 从gg个数中选j个数作为需要添加的数(之前没出现过的)，
26                 每一位都有k-gg+j种选择
27                 **/
28                 f[0][0]=1;
29                 for (j=1;j<=w;j++)
30                 {
31                     f[j][0]=f[j-1][0]*(k-gg)%mod;
32                     ///already k-gg numbers
33                     sum=(sum+f[j-1][0]* sum of k-gg numbers )%mod;
34 
35 
36                     for (c=1;c<=min(gg,j);c++)
37 
38                             sum=(sum+f[j-1][c]* k-gg+c numbers + f[j-1][c-1]* any number(random average of gg numbers))
39 
40 
41                         f[j][c]=(f[j-1][c]*(k-gg+c)+f[j-1][c-1]*(10-(k-gg+c-1)))%mod;
42                 }
43                 for (c=0;c<=min(gg,w);c++)
44                     sum=(sum+f[w][c]*cond)%mod;
45 
46 
47                 ///geshu
48 //                f[0][0]=1;
49 //                for (j=1;j<=w;j++)
50 //                {
51 //                    f[j][0]=f[j-1][0]*(k-gg)%mod;
52 //                    for (c=1;c<=min(gg,j);c++)
53 //                        f[j][c]=(f[j-1][c]*(k-gg+c)+f[j-1][c-1]*(10-(k-gg+c-1)))%mod;
54 //                }
55 //                for (c=0;c<=min(gg,w);c++)
56 //                    sum=(sum+f[w][c]*cond)%mod;
57             }
58             else
59                 work(a%shi[w],w-1,gg,hav|(1<<i),ori&(i==0),cond);
60         }
61     }
62 }
63 
64 int main()
65 {
66     ll l,r;
67     int i,w;
68     scanf("%lld%lld%d",&l,&r,&k);
69     shi[0]=1;
70     for (i=1;i<=18;i++)
71         shi[i]=shi[i-1]*10;
72 
73     w=log(r+minv)/log(10);
74     work(r,w,k,0,0,1,1);
75     if (l!=1)
76     {
77         w=log(l-1+minv)/log(10);///l=1???
78         work(l-1,w,k,0,0,1,-1);
79     }
80     printf("%lld",(sum+mod)%mod);
81     return 0;
82 }