A 九小时九个人九扇门
题意：给定n个数，随便组合，求出数字根分别为0-9的组合个数。
数字根：1、4、9 == 1 + 4 + 9 = 14 == 1 + 4 = 5， 所以数字1、4和9的数字根为5。
思路：dp， 01背包问题 结论性质：一个数的数字根等于这个数对9取模的结果（特别地，取模得 0则数字根为9） 定义：令𝑑𝑝[i][j]表示考虑了前𝑖个数，选择了一些数字使得求和对9取模得𝑗的方案 数
#include <bits/stdc++.h> using namespace std; const int N = 100010; const int mod = 998244353; int n; int f[N][10]; int main() { scanf("%d", &n); f[0][0] = 1; for (int i = 1; i <= n + 1; i++) { int x; scanf("%d", &x); x %= 9; for (int j = 0; j < 9; j++) { f[i][(j + x) % 9] = (f[i][(j + x) % 9] + f[i - 1][j]) % mod; f[i][j] = (f[i][j] + f[i - 1][j]) % mod; } } for (int i = 1; i < 9; i++) { printf("%d ", f[n][i]); } printf("%d\n", f[n][0] - 1); return 0; }
B 炸鸡块君与FIFA22
#include<bits/stdc++.h> using namespace std; const int M=2e5+5; int n,q; char str[M]; struct node{ int val[3]; }tree[M*4]; void Up(node &rt,node &ls,node &rs){ /* rt根，ls左，rs右（假设两个点） rt 的0对应的值应该是ls的0对应的值加上，rs的（ls已经有的0值+要模出的是0）互余（3）的值 */ rt.val[0]=ls.val[0]+rs.val[(0+ls.val[0])%3]; rt.val[1]=ls.val[1]+rs.val[(1+ls.val[1])%3]; rt.val[2]=ls.val[2]+rs.val[(2+ls.val[2])%3]; } void build(int L,int R,int p){ if(L==R){ if(str[L]=='W')tree[p].val[0]=tree[p].val[1]=tree[p].val[2]=1; else if(str[L]=='D')tree[p].val[0]=tree[p].val[1]=tree[p].val[2]=0; else { tree[p].val[0]=0; // % 3 == 0， 不变 tree[p].val[1]=tree[p].val[2]=-1; } return; } int mid=L+R>>1; build(L,mid,p<<1); build(mid+1,R,p<<1|1); Up(tree[p],tree[p<<1],tree[p<<1|1]); } node query(int l,int r,int a,int L,int R,int p){ if(l == L && R == r) return tree[p]; int mid=L+R>>1; if(r<=mid)return query(l,r,a,L,mid,p<<1); else if(mid<l)return query(l,r,a,mid+1,R,p<<1|1); else { node rt; node ls=query(l,mid,a,L,mid,p<<1),rs=query(mid+1,r,a,mid+1,R,p<<1|1); Up(rt,ls,rs); return rt; } } int main(){ scanf("%d %d",&n,&q); scanf("%s",str+1); build(1,n,1); for(int i=1;i<=q;i++){ int l,r,s; scanf("%d %d %d",&l,&r,&s); if(l>r)printf("%d\n",s); else{ node ans=query(l,r,s%3,1,n,1); printf("%d\n",s+ans.val[s%3]); } } return 0; }
C Baby’s first attempt on CPU
pass
D 牛牛做数论
问题一：由于𝜙 𝑥 = 𝑥 ∗ ς(1 − 1/𝑝𝑖)，之中𝑝𝑖取遍𝑥的所有种类的质因 子（注意是种类而不是个数，如素因子2出现两次在公式里也只乘上一次），则𝐻 𝑥 = ς(1 − 1/𝑝𝑖)，显然乘的项数越多、每一项越小𝐻(𝑥)就越小，而按照2,3,5,7,11 … …的顺序取𝑝𝑖就可以达到这一目标。
问题二：对于素数𝑝有𝜙 (𝑝) = 𝑝 − 1，因此𝐻 (𝑝) = (p-1)/p，直觉可以感到
这是挺大一数（毕竟𝐻(𝑥)最大不超过1），所以可以猜出取最大的素数𝑝即可
#include <bits/stdc++.h> using namespace std; #define int long long int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; int is_primer(int x) { for (int i = 2; i <= x / i; i++) { if(x % i == 0) return 0; } return 1; } int t; signed main() { cin >> t; while(t--) { int n; cin >> n; if(n == 1) { puts("-1"); continue; } int res1 = 1ll, res2 = n; for (int i = 0; ; i++) { if(res1 * prime[i] > n) break; res1 *= prime[i]; } while(is_primer(res2) == 0) res2--; cout << res1 << ' ' << res2 << endl; } return 0; }
E 炸鸡块君的高中回忆
签到
F 中位数切分
给定一个长为n的数组a和一个整数m，你需要将其切成连续的若干段，使得每一段的中位数都大于等于m，求最多可以划分成多少段。
简单做法：直接找比m大的 - 比m小的
证明二（不严谨）：先假设数组里只有≥ 𝑚的数字们（想象有一个只 有𝑐𝑛𝑡1个区间，且这些区间都是满足中位数 2的数组），他们都自己作为一个区间，则一共 ≥ 𝑚的要求的； 含≥ 𝑚的数的长为𝑐𝑛𝑡 • 然后考虑插一个< 𝑚的数字进去，这个数字需要和两个≥ 𝑚的数组组 成一个区间才可以满足中位数要求，因此原来两个区间变成了一个区 间，区间数减一，然后删掉这个数和某个≥ 𝑚的数，数组长变为 𝑐𝑛𝑡2 − 1； • （你可能会说这𝑐𝑛𝑡2 − 1 里有一个数其实是在刚才新组成的区间里， 这没问题吗，但这种新组成的区间并不影响上述操作，所以可以看作 一个≥ 𝑚的数字） • 以此类推，可以看出每个< 𝑚数字的作用就是说区间数减一
void solve() { int n, m; cin >> n >> m; int cnt1 = 0, cnt2 = 0; rep(i, 0, n) { int x; cin >> x; if(x < m) cnt2++; else cnt1++; } if(cnt1 - cnt2 <= 0) cout << -1 << endl; else cout << cnt1 - cnt2 << endl; }
G ACM is all you need
不会
