Codeforces Round #574 (Div. 2)

D2 - Submarine in the Rybinsk Sea (hard edition)

千万注意，是%=，而不是%

(sum+=value[i][len[i]]*g[j])%=mod;
与

(sum+=value[i][len[i]]*g[j])%mod;　　//wrong

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10 
11 const double eps=1e-8;
12 const ll inf=1e9;
13 const ll mod=998244353;
14 const int maxn=1e5+10;
15 
16 ll len[maxn],a[maxn],value[maxn][21],ext[maxn][21],ch[21],g[21];
17 
18 ll cal(ll d)
19 {
20     ll tot=0;
21     while (d)
22     {
23         tot++;
24         d/=10;
25     }
26     return tot;
27 }
28 
29 int main()
30 {
31     ll i,j,k,n,d,sum=0,add;
32     ch[0]=1;
33     for (i=1;i<=20;i++)
34         ch[i]=ch[i-1]*10%mod;///10^i
35 
36     scanf("%lld",&n);
37     for (i=1;i<=n;i++)
38     {
39         scanf("%lld",&a[i]);
40         d=a[i];
41         len[i]=cal(d);
42         g[len[i]]++;
43 
44         j=1;
45         add=0;
46         while (d)
47         {
48             (add+=d%10*ch[j*2-2])%=mod;
49             value[i][j]=add*11%mod;
50             d/=10;
51             ext[i][j]=d*ch[j*2]*2%mod;
52             j++;
53         }
54 //        printf("z");
55     }
56 
57     for (i=1;i<=n;i++)
58     {
59         k=len[i];
60         for (j=1;j<=10;j++)
61             if (k<=j)
62                 (sum+=value[i][len[i]]*g[j])%=mod;
63             else
64             {
65                 (sum+=(value[i][j]+ext[i][j])*g[j])%=mod;
66             }
67     }
68 
69     printf("%lld",sum);///why
70     return 0;
71 }
72 /*
73 5
74 1000000000 1000000000 1000000000 1000000000 1000000000
75 
76 in codeblocks, answer is wrong?
77 ³¢ÊÔÌá½»£¿
78 */

E - OpenStreetMap

套路单调队列题

从上到下记录a*1，然后从左往右记录a*b(若干个a*1)

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <algorithm>
 7 #include <iostream>
 8 using namespace std;
 9 #define ll long long
10  
11 const double eps=1e-8;
12 const ll inf=1e9;
13 const ll mod=1e9+7;
14 const int maxn=3e3+10;
15  
16 ll h[maxn][maxn],pos[maxn];
17 ll col[maxn][maxn];
18  
19 int main()
20 {
21     ll sum=0;
22     ll n,m,a,b,i,j;
23     ll g0,x,y,z;
24     ll head,tail;
25     scanf("%lld%lld%lld%lld",&n,&m,&a,&b);
26     scanf("%lld%lld%lld%lld",&g0,&x,&y,&z);
27     for (i=1;i<=n;i++)
28         for (j=1;j<=m;j++)
29         {
30             h[i][j]=g0;
31             g0=(1ll*g0*x+y)%z;
32         }
33  
34  
35     for (j=1;j<=m;j++)
36     {
37         head=1,tail=0;
38         for (i=1;i<=n;i++)
39         {
40             while (head<=tail && pos[head]<=i-a)
41                 head++;
42             while (head<=tail && h[pos[tail]][j]>=h[i][j])
43                 tail--;
44             tail++;
45             pos[tail]=i;
46             col[i][j]=h[pos[head]][j];
47         }
48     }
49  
50     for (i=a;i<=n;i++)
51     {
52         head=1,tail=0;
53         for (j=1;j<=m;j++)
54         {
55             while (head<=tail && pos[head]<=j-b)
56                 head++;
57             while (head<=tail && col[i][pos[tail]]>=col[i][j])
58                 tail--;
59             tail++;
60             pos[tail]=j;
61             if (j>=b)
62                 sum+=col[i][pos[head]];
63         }
64     }
65     printf("%lld",sum);
66     return 0;
67 }
68 /*
69 3 4 2 1
70 1000000000 1000000000 1 234142
71 */