题解-牛客练习赛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;
}
海康威视公司福利 1134人发布
查看9道真题和解析
