暑假集训日记——7.18（codeforce）

C. Basketball Exercise 题解： 我也是醉了，我说我咋连一道简单dp的题都写不对…题意理解错了… 写成了：单调递减子序列的最大和：

#include<bits/stdc++.h> #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef long double ld; const int N=1e5+10; const int MAXN=20010; const int INF=0x3f3f3f3f; const double eps=0.0000001; const ll mod=1e9+7; int n,m,x,y,t; ll a[2][N]; ll d[2][N]; int main() { scanf("%d",&n); //scanf("%d",&n); for(int i=1;i<=n;i++) { cin>>a[0][i]; } for(int i=1;i<=n;i++) { cin>>a[1][i]; } int cnt=0; d[0][1]=a[0][1]; d[1][1]=a[1][1]; ll mx=max(a[1][1],a[0][1]); for(int i=2;i<=n;i++) { for(int k=0;k<2;k++) { for(int j=1;j<i;j++) { for(int p=0;p<2;p++) { if(a[p][j]>a[k][i]&&d[p][j]+a[k][i]>d[k][i]) d[k][i]=d[p][j]+a[k][i]; else d[k][i]=max(a[k][i],d[k][i]); } } if(d[k][i]>mx) mx=d[k][i]; } } cout<<mx<<endl; }

正确的写法：对于最新的状态，要么不选任何数字，要么选与自己不同行的前一个状态进行转移

#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair const int N=100050; ll dp[2][N],h[2][N]; int main() { int n; scanf("%i",&n); for(int i=1;i<=n;i++) scanf("%lld",&h[0][i]); for(int i=1;i<=n;i++) scanf("%lld",&h[1][i]); for(int i=1;i<=n;i++) { dp[0][i]=max(dp[0][i-1],dp[1][i-1]+h[0][i]); dp[1][i]=max(dp[1][i-1],dp[0][i-1]+h[1][i]); } printf("%lld\n",max(dp[0][n],dp[1][n])); return 0; }

D1. Submarine in the Rybinsk Sea (easy edition) 题意： 让我们用一个函数$f(a_1{a}_2\dots a_{p-1}{a}_p,b_1{b}_2\dots b_{p-1}{b}_p)$来交替两个数字的各位数码，其中$a_1,a_2,\dots ,和b_1,b_2,\dots ,$是以十进制表示的两个整数的数码，不含前导零。 换句话说，函数$f(x,y)$通过将数字$x$和$y$的各位数码从最低位数写到较高位数字，从数字$y$开始，交替地插入数字$x$和$y$。该函数的结果也是从右到左构建的（即从较低的数字到较旧的数字）。如果其中一个参数（不妨设为$x$）的数字已写完，则写下另一个参数（即$y$）的剩余数字，下面我们来看几个例子熟悉一下。

$f(1111,2222)=12121212$

$f(7777,888)=7787878$

$f(33,44444)=4443434$

$f(555,6)=5556$

$f(111,2222)=2121212$

一般的，如果$p\ge q$，那么$f(a_1\dots a_p,b_1\dots b_q)=(a_1{a}_2\dots a_{p-q+1}{b}_1{a}_{p-q+2}{b}_2\dots a_{p-1}{b}_{q-1}{a}_p{b}_q{)}_{(10)}$ $MishanyaMishanya$为您提供一个由$n$个整数组成的数组$\left\{a_i\right\}$。此数组中的所有数字长度相等（即每个数字的位数相等）。你的任务是帮助学生们计算$\sum _{i=1}^n\sum _{j=1}^{n}f(a_i,a_j)\mathrm{m}\mathrm{o}\mathrm{d}998,244,353$

题解： 例如 $3$个数 $12$ $33$ $45$ 根据题意得 $sum=1122+3333+4455+1323+3132+3435+4353+1425+4152$ 因此等价于 $sum=1122\ast 3+3333\ast 3+4455\ast 3$

#include<bits/stdc++.h> #define mp make_pair using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef long double ld; const int N=1e5+10; const int MAXN=20010; const int INF=0x3f3f3f3f; const double eps=0.0000001; const ll mod=1e9+7; int n,m,x,y,t; int a[100005]; int main() { int n; scanf("%d",&n); LL ans=0; for(int i = 0;i<n;i++){ scanf("%d",&a[i]); int tmp=a[i]; vector<int> v; while(tmp){ v.pb(tmp%10); tmp/=10; } reverse(v.begin(),v.end()); LL value=0; for(auto it:v){ value*=100; value+=it; value%=mod; } ans+=value%mod*n%mod; ans%=mod; ans+=value*10%mod*n%mod; ans%=mod; } printf("%lld\n",ans); } }

D2. Submarine in the Rybinsk Sea (hard edition) 题解：模拟 一个数字 s1 中一个字母出现的次数等于 2*n 次

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<string> a(n); int c[11] = {}; for (string&s : a) { cin >> s; reverse(s.begin(), s.end()); c[s.size()]++; } ll mod = 998244353; ll pow10[30] = {1}; for (int i = 1; i < 30; i++)//初始化权值 pow10[i] = pow10[i-1]*10%mod; ll ans = 0; for (string&s : a) { for (int i = 0; i < s.size(); i++) { for (int j = 1; j <= 10; j++) { (ans += pow10[min(i*2,i+j)]*c[j]*(s[i]-'0')) %= mod;//仅考虑一个位置上的数字会出现在哪里 (ans += pow10[min(i*2+1,i+j)]*c[j]*(s[i]-'0')) %= mod; } } } cout << ans << endl; }

E. OpenStreetMap 题解：建一下矩阵，然后套一下二维单调队列就好了

C. Ehab and a 2-operation task 题意： n个数，最多n+1操作，要么前i个数加x,要么前i个数对x取余，最后使得严格递增 题解：在n+1步内一定可以变成单调序列，而且数字不受限制 所以可以考虑把所有的数字变为0 1 2 3 4 …这样的序列

#include<bits/stdc++.h> using namespace std; int main() { int n,i; cin>>n; int a[n]; for(i=0;i<n;i++) cin>>a[i]; for(i=0;i<n;i++) a[i]+=100000; cout<<n+1<<"\n"; cout<<"1 "<<n<<" 100000\n"; for(i=0;i<n;i++){ cout<<"2 "<<i+1<<" "<<a[i]-i<<"\n"; } return 0; }

C. Prefix Sum Primes 题解：质数一定为奇数

#include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int c1=0,c2=0; for (int i=1;i<=n;i++){ int x; cin>>x; if (x==1) c1++; else c2++; } if (c1==0){ while (c2--) cout<<2<<' '; }else if (c2==0){ while (c1--) cout<<1<<' '; }else{ c1--,c2--; cout<<2<<' '<<1<<' '; while (c2--) cout<<2<<' '; while (c1--) cout<<1<<' '; } return 0; }