A: Suppose a three digit number is x1y1z1, with cal(x1y1z1) + cal(x2y2z2) = cal((x1 + x2)(y1 + y2) (z1 + z2))
prove:
We don't carry and treat each bit as a multi - base number (actually the same as decimal)
cal(x1y1z1) = cal(x1 + y1 + z1). cal(x2y2z2) = cal(x2 + y2 + z2)
cal((x1 + x2)(y1 + y2) (z1 + z2)) = cal(x1 + x2 + y1 + y2 + z1 + z2).
Assuming that the current level is at the lowest level, there is cal(x1 + y1 + z1) + cal(x2 + y2 + z2) = x1 + y1 + z1 + x2 + y2 + z2;
cal(x1 + x2 + y1 + y2 + z1 + z2) = x1 + y1 + z1 + x2 + y2 + z2;
cal(x1y1z1) + cal(x2y2z2) = cal((x1 + x2)(y1 + y2) (z1 + z2))
Then with this step, just forget it. Here dp's a note.
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 1e7 + 5; const LL Mod = 998244353; #define INF 1e14 #define dbg(ax) cout << "now this num is " << ax << endl; inline long long ADD(long long x,long long y) { if(x + y < 0) return ((x + y) % Mod + Mod) % Mod; return (x + y) % Mod; } inline long long MUL(long long x,long long y) { if(x * y < 0) return ((x * y) % Mod + Mod) % Mod; return x * y % Mod; } inline long long DEC(long long x,long long y) { if(x - y < 0) return (x - y + Mod) % Mod; return (x - y) % Mod; } int n,a[N]; LL dp[10],f[10];//Hewei j Number of schemes. int cal(int x) { if(x < 10) return x; else { int ff = 0; while(x) { ff += x % 10; x /= 10; } return cal(ff); } } void solve() { scanf("%d",&n); for(int i = 1;i <= n;++i) scanf("%d",&a[i]); for(int i = 1;i <= n;++i) { int now = cal(a[i]); for(int j = 1;j <= 9;++j) f[j] = dp[j]; for(int j = 1;j <= 9;++j) { int tmp = cal(now + j); f[tmp] = ADD(f[tmp],dp[j]); } f[now] = ADD(f[now],1); for(int j = 1;j <= 9;++j) dp[j] = f[j]; } for(int i = 1;i <= 9;++i) printf("%lld%c",dp[i],i == 9 ? '\n' : ' '); } int main() { // int _; // for(scanf("%d",&_);_;_--) { solve(); //} // system("pause"); return 0; }
B: The st table is preprocessed to take the value that can be increased at the beginning of each mode 3 (0,1,2).
Then double the interval each time.
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 2e5 + 5; const int M = 1e7 + 5; const LL Mod = 998244353; #define INF 1e14 #define dbg(ax) cout << "now this num is " << ax << endl; inline long long ADD(long long x,long long y) { if(x + y < 0) return ((x + y) % Mod + Mod) % Mod; return (x + y) % Mod; } inline long long MUL(long long x,long long y) { if(x * y < 0) return ((x * y) % Mod + Mod) % Mod; return x * y % Mod; } inline long long DEC(long long x,long long y) { if(x - y < 0) return (x - y + Mod) % Mod; return (x - y) % Mod; } int n,q,dp[N][20][3];//from i with k Start scoring string str; void init() { for(int i = 1;i <= n;++i) { for(int j = 0;j < 3;++j) { if(str[i - 1] == 'D') dp[i][0][j] = 0; else if(str[i - 1] == 'W') dp[i][0][j] = 1; else dp[i][0][j] = (j == 0) ? 0 : -1; } } for(int i = 1;i < 20;++i) { for(int j = 1;j <= n;++j) { int mx = j + (1 << i) - 1; if(mx > n) break; for(int k = 0;k < 3;++k) { int st = k + dp[j][i - 1][k]; dp[j][i][k] = st + dp[j + (1 << (i - 1))][i - 1][st % 3] - k; //printf("dp[%d][%d][%d] is %d\n",j,i,k,dp[j][i][k]); } } } } int query(int L,int r,int s) { int len = (r - L + 1); int k = log2(len); // printf("L is %d r is %d s is %d k is %d\n",L,r,s,k); if((1 << k) == len) return dp[L][k][s]; else { return dp[L][k][s] + query(L + (1 << k),r,(s + dp[L][k][s]) % 3); } } void solve() { scanf("%d %d",&n,&q); cin >> str; init(); while(q--) { int L,r,s;scanf("%d %d %d",&L,&r,&s); printf("%d\n",s + query(L,r,s % 3)); } } int main() { // int _; // for(scanf("%d",&_);_;_--) { solve(); //} // system("pause"); return 0; }
C: Push back as far as you can.
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 2e5 + 5; const int M = 1e7 + 5; const LL Mod = 998244353; #define INF 1e14 #define dbg(ax) cout << "now this num is " << ax << endl; inline long long ADD(long long x,long long y) { if(x + y < 0) return ((x + y) % Mod + Mod) % Mod; return (x + y) % Mod; } inline long long MUL(long long x,long long y) { if(x * y < 0) return ((x * y) % Mod + Mod) % Mod; return x * y % Mod; } inline long long DEC(long long x,long long y) { if(x - y < 0) return (x - y + Mod) % Mod; return (x - y) % Mod; } int n,a[105][5],now[105]; int ad[105]; int get(int L,int r) { int sum = ad[L]; for(int i = L + 1;i < r;++i) { sum++; sum += ad[i]; } return sum; } void solve() { scanf("%d",&n); for(int i = 1;i <= n;++i) for(int j = 1;j <= 3;++j) scanf("%d",&a[i][j]); int ans = 0; for(int i = 1;i <= n;++i) { for(int j = 1;j <= 3;++j) { int pos = i - j; if(pos <= 0 || a[i][j] == 0) continue; int len = get(pos,i); if(len < 3) { ad[i - 1] += 3 - len; ans += 3 - len; } // printf("%d %d ans is %d\n",pos,i,ans); } } printf("%d\n",ans); } int main() { // int _; // for(scanf("%d",&_);_;_--) { solve(); //} // system("pause"); return 0; } /* 4 0 0 0 0 0 0 0 1 0 0 1 1 */
D: This question feels pretty good.
Obviously, the largest is the largest prime number in the interval.
Then for the first part, we will look at the Euler function.
Because $\ varphi (x) = x \prod_{i = 1}^{k} (1 - \frac{1}{pi})$
It can be seen that the more prime factors, the smaller.
Then try to multiply it by a small quality factor.
There may be a situation where there are as many minimum prime factors in the interval, because we have always multiplied the smallest non multiplied prime factors.
So it must be the x smallest of these.
Most of them just look for primes by violence (the interval between primes is up to a few hundred)
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<double,int> pii; const int N = 1e5 + 5; const int M = 1e7 + 5; #define rep(at,am,as) for(int at = am;at <= as;++at) const LL Mod = 10000; #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline long long ADD(long long x,long long y) { if(x + y < 0) return ((x + y) % Mod + Mod) % Mod; return (x + y) % Mod; } inline long long MUL(long long x,long long y) { if(x * y < 0) return ((x * y) % Mod + Mod) % Mod; return x * y % Mod; } inline long long DEC(long long x,long long y) { if(x - y < 0) return (x - y + Mod) % Mod; return (x - y) % Mod; } vector<LL> vec; int prime[45],tot = 0; bool vis[45]; void init() { for(int i = 2;i < 40;++i) { if(!vis[i]) prime[++tot] = i; for(int j = 1;j <= tot && prime[j] * i < 40;++j) { vis[prime[j] * i] = 1; if(i % prime[j] == 0) break; } } LL ma = 1; rep(i,1,tot) { ma *= prime[i]; vec.push_back(ma); } } bool check(int x) { int m = sqrt(x); rep(i,2,m) { if(x % i == 0) return true; } return false; } void solve() { int n;scanf("%d",&n); if(n == 1) printf("-1\n"); else { int pos = upper_bound(vec.begin(),vec.end(),n) - vec.begin(); pos--; while(check(n)) n--; printf("%d %d\n",vec[pos],n); } } int main() { init(); int _; for(scanf("%d",&_);_;_--) { solve(); } //system("pause"); return 0; }
G:
This problem is still a little difficult.
We first deal with the interval in which f [i] < min (f [I - 1], f [i + 1]) can be taken for each position i.
Then, for all intervals, we can find the coverage times of a minimum coverage point.
1: For the processing of the first part, let's consider a little classification: suppose we are x at present and y at the other end
If x > y, then obviously b must be smaller to reverse, that is, the boundary is:
2B - x < y, i.e. 2B < x + y B < (x + y) / 2
Then for x < y, 2B - x > y, that is, b > (x + y) / 2;
2: For the second part, there are many ways.
At first, I wanted to do the discretization of the interval to cover, and then find the minimum value of the line segment tree.
Seeing that others have a simpler approach, we assume that the interval [L,r] assigns a value of 1 to L and a value of - 1 to r + 1, so leaving an interval is + 1 - 1 = 0
Then find the minimum value in the middle.
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5 + 5; const int M = 1e7 + 5; #define rep(at,am,as) for(int at = am;at <= as;++at) const LL Mod = 10000; #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline long long ADD(long long x,long long y) { if(x + y < 0) return ((x + y) % Mod + Mod) % Mod; return (x + y) % Mod; } inline long long MUL(long long x,long long y) { if(x * y < 0) return ((x * y) % Mod + Mod) % Mod; return x * y % Mod; } inline long long DEC(long long x,long long y) { if(x - y < 0) return (x - y + Mod) % Mod; return (x - y) % Mod; } int a[N]; bool cmp(pii a,pii b) { if(a.first == b.first) return a.second > b.second; else return a.first < b.first; } void solve() { int n;scanf("%d",&n); rep(i,1,n) scanf("%d",&a[i]); vector<pii> vec; int st = 0; rep(i,2,n - 1) { if(a[i] == a[i - 1] || a[i] == a[i + 1]) continue; int L = -INF,r = INF; if(a[i] < a[i - 1]) r = min(r,(a[i] + a[i - 1] - 1) / 2); else L = max(L,(a[i] + a[i - 1]) / 2 + 1); if(a[i] < a[i + 1]) r = min(r,(a[i] + a[i + 1] - 1) / 2); else L = max(L,(a[i] + a[i + 1]) / 2 + 1); if(L <= r) { if(L == -INF) ++st; else vec.push_back(pii{L,1}); if(r < INF) vec.push_back(pii{r + 1,-1}); } } int ans = st; sort(vec.begin(),vec.end(),cmp); for(auto v : vec) { st += v.second; ans = min(ans,st); } printf("%d\n",ans); } int main() { int _; for(scanf("%d",&_);_;_--) { solve(); } // system("pause"); return 0; }
K: Decide what the first two are and dp find the maximum number of green islands.
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<double,int> pii; const int N = 1e5 + 5; const int M = 1e7 + 5; #define rep(at,am,as) for(int at = am;at <= as;++at) const LL Mod = 10000; #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; inline long long ADD(long long x,long long y) { if(x + y < 0) return ((x + y) % Mod + Mod) % Mod; return (x + y) % Mod; } inline long long MUL(long long x,long long y) { if(x * y < 0) return ((x * y) % Mod + Mod) % Mod; return x * y % Mod; } inline long long DEC(long long x,long long y) { if(x - y < 0) return (x - y + Mod) % Mod; return (x - y) % Mod; } int n; string s; //1 - red,2 - green,3 - black int dp[N][4][4];//i The color of is k,i - 1 Color is j. int check(int x,int y) { memset(dp,-1,sizeof(dp)); dp[2][x][y] = (x == 2) + (y == 2); int mx = -1; rep(i,1,n) { rep(j,1,3) { rep(k,1,3) { if(dp[i - 1][j][k] == -1) continue; rep(m,1,3) { int sum1 = (j == 2) + (k == 2) + (m == 2),sum2 = (j == 1) + (k == 1) + (m == 1); if(s[i - 1] == 'G') { if(sum1 <= sum2) dp[i][k][m] = max(dp[i][k][m],-1); else dp[i][k][m] = max(dp[i][k][m],dp[i - 1][j][k] + (m == 2)); } if(s[i - 1] == 'R') { if(sum2 <= sum1) dp[i][k][m] = max(dp[i][k][m],-1); else dp[i][k][m] = max(dp[i][k][m],dp[i - 1][j][k] + (m == 2)); } if(s[i - 1] == 'B') { if(sum1 != sum2) dp[i][k][m] = max(dp[i][k][m],-1); else dp[i][k][m] = max(dp[i][k][m],dp[i - 1][j][k] + (m == 2)); } if(i == n) mx = max(mx,dp[i][k][m]); } } } } return mx; } void solve() { cin >> n >> s; int ans = -1; rep(i,1,3) { rep(j,1,3) { ans = max(ans,check(i,j)); } } printf("%d\n",ans); } int main() { // int _; // for(scanf("%d",&_);_;_--) { solve(); //} // system("pause"); return 0; }