题解-牛客练习赛81
鸽子出题人来发题解了。
首先很抱歉因为出题人都是初三党所以时间调来调去,题解所以发得也比较慢。
特别感谢内测的那几位验题人以及审题人提出的建议。
。
首先很抱歉因为出题人都是初三党所以时间调来调去,题解所以发得也比较慢。
特别感谢内测的那几位验题人以及审题人提出的建议。
T1-小 Q 与异或
签到题,主要考察关于异或的这个性质 我看大多数的人代码都比官方的做法简洁了 100 倍,甚至还有直接随机卡过去的。
下面是做法:
首先肯定要按
从小到大排序,这里有一个很坑的地方:如果同一个位置出现了不同的
值,直接输出
。
如果当前位置离上一次的位置是偶数,就可以这样子构造:
for (int j = be + 1; j < i - 1; j++) ans[j] = s[be]; if (now == 0) { ans[i - 1] = (1ll << 30); ans[i] = (1ll << 30) ^ s[be]; }else { ans[i - 1] = (1ll << 30) ^ s[be]; ans[i] = (1ll << 30) ^ now; }
就直接把中间一段先赋值为上一次的异或前缀和,然后看这一次要的值是不是
奇数的话有点麻烦:
for (int j = be + 1; j < i; j++) ans[j] = (1ll << 30); if (now == 0 && s[be] == 0) { ans[be + 1] = (1ll << 30) ^ (998244353); ans[i] = 998244353; } else ans[i] = (now ^ s[be]);
如果当前的值是零而且
,那么你需要重新异或上一个常数,不然可能会构造出
,导致答案错误。
std
#include <map> #include <queue> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define int long long #define LL long long template <typename T> inline void read(T &t) { t = 0; char c = getchar(); int f = 1; while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); } while (c >= '0' && c <= '9') { t = (t << 3) + (t << 1) + c - '0'; c = getchar(); } t *= f; } template <typename T, typename... Args> inline void read(T &t, Args &... args) { read(t); read(args...); } template <typename T> inline void write(T x) { if (x < 0) { x = -x; putchar('-'); } if (x > 9) write(x / 10); putchar(x % 10 + '0'); } void Min(int &a, int b) { if (a > b) a = b; } void Max(int &a, int b) { if (a < b) a = b; }; int n, m, maxx, ans[1000005], s[1000005]; vector<int> G[1000005]; signed main() { read(n, m); for (int i = 1; i <= m; i++) { int x, y; read(x, y); maxx = max(maxx, x); G[x].push_back(y); } int be = 0; for (int i = 1; i <= n; i++) { if (G[i].size()) { bool flag = 0; for (int j = 1; j < G[i].size(); j++) { int y = G[i][j]; if (y != G[i][0]) { flag = 1; break; } } if (flag) { write(-1); return 0; } if (be == 0) { int now = G[i][0]; if (i % 2 == 1) { for (int j = 1; j < i; j++) ans[j] = (1 << 30); if (now == 0) { ans[1] = (1ll << 30) ^ (998244353); ans[i] = 998244353; } else ans[i] = now; } else { for (int j = 1; j < i - 1; j++) ans[j] = (1ll << 30); ans[i - 1] = (1ll << 30); ans[i] = (1ll << 30) ^ now; } } else { int now = G[i][0]; if (be + 1 == i) { if ((now ^ s[be]) == 0) { write(-1); return 0; } else { ans[i] = (now ^ s[i - 1]); } } else { if ((i - be) % 2 == 1) { for (int j = be + 1; j < i; j++) ans[j] = (1ll << 30); if (now == 0 && s[be] == 0) { ans[be + 1] = (1ll << 30) ^ (998244353); ans[i] = 998244353; } else ans[i] = (now ^ s[be]); } else { for (int j = be + 1; j < i - 1; j++) ans[j] = s[be]; if (now == 0) { ans[i - 1] = (1ll << 30); ans[i] = (1ll << 30) ^ s[be]; } else { ans[i - 1] = (1ll << 30) ^ s[be]; ans[i] = (1ll << 30) ^ now; } } } } for (int j = be + 1; j <= i; j++) s[j] = s[j - 1] ^ ans[j]; be = i; } } for (int i = maxx + 1; i <= n; i++) ans[i] = (LL)2e10; for (int i = 1; i <= n; i++) if (ans[i] == 0) { printf("-1"); return 0; } for (int i = 1; i <= n; i++) write(ans[i]), printf(" "); return 0; }
T2-小 Q 与彼岸花
这题为了比赛变得更加简单数据范围被削弱了,削弱后就是个简单题了,直接
区间 dp 就行。
说以下
的做法,考虑分块,记
表示第
块到第
块之间的答案,这个可以用 trie
搞出来,
是值域。
然后查询的话就上一个可持久化 trie,然后查边角就行。
std
#include <bits/stdc++.h> using namespace std; #define Int int #define MAXN 100005 #define num bel[n] template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;} template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);} template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');} int n,m,cur,rt[MAXN],val[MAXN],bel[MAXN]; int ch[MAXN * 32][2],cnt[MAXN * 32],Ans[705][705]; int sta[705],fin[705]; void Insert (int a,int b,int t,int x){ if (t < 0) return ; int i = (x >> t) & 1; ch[a][i] = ++ cur; ch[a][i ^ 1] = ch[b][i ^ 1]; cnt[ch[a][i]] = cnt[ch[b][i]] + 1; Insert (ch[a][i],ch[b][i],t - 1,x); } int query (int a,int b,int t,int x){ if (t < 0) return 0; int i = (x >> t) & 1; if (cnt[ch[a][i ^ 1]] > cnt[ch[b][i ^ 1]]) return (1 << t) + query (ch[a][i ^ 1],ch[b][i ^ 1],t - 1,x); else return query (ch[a][i],ch[b][i],t - 1,x); } signed main(){ read (n,m); int siz = sqrt (n); memset (sta,0x7f,sizeof (sta)); for (Int i = 1;i <= n;++ i) read (val[i]),bel[i] = (i - 1) / siz + 1; for (Int i = 1;i <= n;++ i) sta[bel[i]] = min (sta[bel[i]],i),fin[bel[i]] = i; for (Int i = 1;i <= n;++ i) rt[i] = ++ cur,Insert (rt[i],rt[i - 1],17,val[i]); for (Int i = 1;i <= num;++ i){ int start = sta[i]; for (Int j = i;j <= num;++ j){ Ans[i][j] = Ans[i][j - 1]; for (Int k = sta[j];k <= fin[j];++ k) Ans[i][j] = max (Ans[i][j],query (rt[k],rt[start - 1],17,val[k])); } } while (m --){ int l,r; read (l,r); if (bel[r] - bel[l] <= 2){ int ans = 0; for (Int i = l;i < r;++ i) ans = max (ans,query (rt[r],rt[i],17,val[i])); write (ans),putchar ('\n'); } else{ int bl = bel[l] + 1,br = bel[r] - 1; int ans = Ans[bl][br]; for (Int i = l;i < sta[bl];++ i) ans = max (ans,query (rt[r],rt[l - 1],17,val[i])); for (Int i = fin[br] + 1;i <= r;++ i) ans = max (ans,query (rt[i],rt[l - 1],17,val[i])); write (ans),putchar ('\n'); } } return 0; }
T3-小 Q 与构造
可以很简单的将整个序列拆成若干条链(如果你高兴也可以说若干个序列),使得这些链互不影响。设有 x 条链,第 i 条链的答案是
有了这样的一个大概思路,接下来有几个问题有待解决:
- 如何将其拆成几个互不影响的链?
- 如何计算每条链的答案?
考虑对这个限制的性质入手。
x=ky 或者
对于每一个之前没有用过的
这样,拆出来的每一条链都是互相不影响的。我觉得很显然吧。
考虑计算答案,发现对于一条链来说,两个限制就相当于:
- 不能选择相邻的两个数(就是距离为
- 不能选择距离为
再回看
看实现情况,
往里面随便走下性质。
- 性质 1:如果一个数能作为一条链(序列)的首项,那么这个数一定不是 k 的倍数。
随便猜都猜得到吧。
- 性质 2:当两个不同的首项
因为限制是相同的嘛。
所以可以只做一遍 dp,然后循环枚一遍就完了,时间复杂度
综合上面推出来的两个性质,加上一点简单的数论分块的知识,我们可以改写答案。
设
用一点简单的数论分块的知识,推出一段区间,使得里面的每一个数构造出来的序列长度为 x 不就得了(实际操作就是除法)。然后挪动区间就直接
注意要将算出来的区间中,排除掉能够整除
代码不长。注意
T4-小 Q 与树
简单题,想怎么做就怎么做,可以淀粉质,可以树上启发式合并,甚至可以上权值线段树合并。 std 写的是树上启发式合并套平衡树,也没什么好讲的,合并的时候统计一下贡献就行。
#include <ctime> #include <bits/stdc++.h> using namespace std; #define int long long #define Int int #define MAXN 200005 template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;} template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);} template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');} #define mod 998244353 int mul (int a,int b){return 1ll * a * b % mod;} int dec (int a,int b){return a >= b ? a - b : a + mod - b;} int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;} vector <int> G[MAXN]; int n,ans,rt[MAXN],val[MAXN],dep[MAXN]; struct fhq_Treap{ int son[MAXN][2],key[MAXN],siz[MAXN],sum1[MAXN],sum2[MAXN],sum3[MAXN]; #define ls(x) son[x][0] #define rs(x) son[x][1] void Pushup (int x){ siz[x] = siz[ls(x)] + siz[rs(x)] + 1, sum1[x] = add (sum1[ls(x)],add (sum1[rs(x)],val[x])); sum3[x] = add (sum3[ls(x)],add (sum3[rs(x)],dep[x])); sum2[x] = add (sum2[ls(x)],add (sum2[rs(x)],mul (val[x],dep[x]))); } void Split (int u,int k,int &x,int &y){ if (!u) return x = y = 0,void (); if (val[u] <= k) x = u,Split (rs(u),k,rs(u),y); else y = u,Split (ls(u),k,x,ls(u)); Pushup (u); } int Merge (int x,int y){ if (!x || !y) return x + y; if (key[x] < key[y]) return rs(x) = Merge (rs(x),y),Pushup (x),x; else return ls(y) = Merge (x,ls(y)),Pushup (y),y; } void clear (int u){son[u][0] = son[u][1] = 0,key[u] = rand(),Pushup (u);} void insert (int &root,int u){ int x,y;Split (root,val[u],x,y); root = Merge (x,Merge (u,y)); } void count (int u,int du,int root){ int x,y;Split (root,val[u],x,y); int res1 = add (sum2[x],mul (dec (dep[u],2 * du),sum1[x])); int res2 = add (mul (val[u],sum3[y]),mul (siz[y],mul (val[u],dec (dep[u],2 * du)))); ans = add (ans,add (res1,res2)),Merge (x,y); } void ergodic (int u,int now,int &ano,bool flg){ if (!now) return ; ergodic (u,ls(now),ano,flg),ergodic (u,rs(now),ano,flg); if (flg == 0) count (now,dep[u],ano); if (flg == 1) clear (now),insert (ano,now); } }Tree; void dfs (int u,int fa){ dep[u] = dep[fa] + 1; for (Int v : G[u]) if (v ^ fa) dfs (v,u); } void dfs1 (int u,int fa){ for (Int v : G[u]) if (v ^ fa) dfs1 (v,u); Tree.insert (rt[u],u); for (Int v : G[u]) if (v ^ fa){ if (Tree.siz[rt[v]] > Tree.siz[rt[u]]) swap (rt[u],rt[v]); Tree.ergodic (u,rt[v],rt[u],0),Tree.ergodic (u,rt[v],rt[u],1); } } signed main(){ srand(time(0)); read (n); for (Int i = 1;i <= n;++ i) read (val[i]),Tree.key[i] = rand(); for (Int i = 2,u,v;i <= n;++ i) read (u,v),G[u].push_back (v),G[v].push_back (u); dfs (1,0);for (Int i = 1;i <= n;++ i) Tree.Pushup (i);dfs1 (1,0),write (mul(ans,2)),putchar ('\n'); return 0; }
T5-小 Q 与函数求和 1
简单莫比乌斯反演题。 先不考虑
的时候。
当
然后就可以
解决了。
T6-小 Q 与函数求和 2
结论与板子题。
然后这里有两种证明过程,可以逆推和正推,先看逆推(需要你猜出结论)。
正推的话是一样的,考虑一下这个
然后带入原式子。
后面这个不就是枚举的约数个数吗?
然后这东西怎么算,把式子拆成两部分,就是要求
算一下质数下的取值。
std:
#include <cstdio> #include <map> #include <iostream> #include <algorithm> #include <queue> #include <cstring> #include <cmath> using namespace std; #define LL long long const int mod = 998244353; int dec(int x, int y) { return x >= y ? x - y : x + mod - y; } int mul(int x, int y) { return 1ll * x * y % mod; } int add(int x, int y) { if (x + y >= mod) return x + y - mod; return x + y; } LL qkpow(LL x, LL power, LL mod) { x %= mod; LL ans = 1; for (; power; power >>= 1, (x *= x) %= mod) if (power & 1) (ans *= x) %= mod; return ans; } int sq, size, cnt; int prime[1000005], id1[1000005], id2[1000005]; LL n, num[1000005], g[1000005], gprime[1000005]; bool vis[1000005]; LL S1(LL x, LL y) { if (prime[y] >= x) return 0; int p = (x <= sq ? id1[x] : id2[n / x]); int ans = dec(g[p], mul(4, y)); for (int i = y + 1; i <= cnt && 1ll * prime[i] * prime[i] <= x; i++) { LL pkx = prime[i]; for (int k = 1; pkx <= x; k++, pkx *= prime[i]) { LL pkxm = pkx % mod; ans = add(ans, mul(add(k, 1), mul(add(k, 1), S1(x / pkx, i) + (k > 1)))); } } return ans; } LL S2(LL x, LL y) { if (prime[y] >= x) return 0; int p = (x <= sq ? id1[x] : id2[n / x]); int ans = mul(4, dec(g[p], gprime[y])); for (int i = y + 1; i <= cnt && 1ll * prime[i] * prime[i] <= x; i++) { LL pkx = prime[i]; for (int k = 1; pkx <= x; k++, pkx *= prime[i]) { LL pkxm = pkx % mod; ans = add(ans, mul(pkxm, mul(add(k, 1), mul(add(k, 1), S2(x / pkx, i) + (k > 1))))); } } return ans; } signed main() { int T; scanf("%d", &T); LL inv2 = qkpow(2, mod - 2, mod); while (T--) { scanf("%lld", &n); sq = sqrt(n * 1.0); cnt = size = 0; for (int i = 0; i <= sq; i++) vis[i] = id1[i] = id2[i] = gprime[i] = g[i] = 0; for (int i = 2; i <= sq; i++) { if (!vis[i]) prime[++cnt] = i, gprime[cnt] = add(gprime[cnt - 1], i); for (int j = 1; j <= cnt && prime[j] * i <= sq; j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } for (LL l = 1, r; l <= n; l = r + 1) { r = n / (n / l); num[++size] = n / r; LL Num = (n / r) % mod; g[size] = mul(4, Num - 1); if (n / r <= sq) id1[n / r] = size; else id2[r] = size; } for (int i = 1; i <= cnt; i++) { LL sqr = 1ll * prime[i] * prime[i]; for (int j = 1; j <= size && num[j] >= sqr; j++) { LL p = num[j] / prime[i]; p = (p <= sq ? id1[p] : id2[n / p]); g[j] = dec(g[j], dec(g[p], mul(4, dec(i, 1)))); } } LL totans = mul(add(n % mod, 1), add(S1(n, 0), 1)); size = 0; for (LL l = 1, r; l <= n; l = r + 1) { r = n / (n / l); num[++size] = n / r; LL Num = (n / r) % mod; g[size] = dec(mul(Num, mul(add(Num, 1), inv2)), 1); if (n / r <= sq) id1[n / r] = size; else id2[r] = size; } for (int i = 1; i <= cnt; i++) { LL sqr = 1ll * prime[i] * prime[i]; for (int j = 1; j <= size && num[j] >= sqr; j++) { LL p = num[j] / prime[i]; p = (p <= sq ? id1[p] : id2[n / p]); g[j] = dec(g[j], mul(prime[i], dec(g[p], gprime[i - 1]))); } } totans = dec(totans, add(S2(n, 0), 1)); printf("%lld\n", totans); } return 0; }