题解-牛客练习赛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 条链的答案是 q_i,每条链互不影响,所以根据乘法原理,答案就是:



有了这样的一个大概思路,接下来有几个问题有待解决:

- 如何将其拆成几个互不影响的链?
- 如何计算每条链的答案?

考虑对这个限制的性质入手。

x=ky 或者 都是不能满足的。做题多的同学不难想到构造一条链(或者说序列?),设其首项为 a,满足:



对于每一个之前没有用过的 都做一个这样的序列,计算它们的答案就行了。

这样,拆出来的每一条链都是互相不影响的。我觉得很显然吧。

考虑计算答案,发现对于一条链来说,两个限制就相当于:

- 不能选择相邻的两个数(就是距离为 );
- 不能选择距离为 的两个数。

再回看 ,显然状压解决。

看实现情况,。其实本意是用来乱搞的。



往里面随便走下性质。

- 性质 1:如果一个数能作为一条链(序列)的首项,那么这个数一定不是 k 的倍数。
随便猜都猜得到吧。

- 性质 2:当两个不同的首项 ,构造出来的序列长度是相等的,那么这个两个首项的链的贡献是一样的。
因为限制是相同的嘛。

所以可以只做一遍 dp,然后循环枚一遍就完了,时间复杂度



有点大。

综合上面推出来的两个性质,加上一点简单的数论分块的知识,我们可以改写答案。

c_x 为作为首项(注意,这里不包含不能作为首项的数)构造出来的序列长度为 的数的数量,sum_x 为构造出的序列长度为 的贡献是多少。答案就是:



sum_x 早就算出来了,考虑这个 c_x 怎么算。

用一点简单的数论分块的知识,推出一段区间,使得里面的每一个数构造出来的序列长度为 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

结论与板子题。

这么 ex,肯定是有结论的,先给结论。

然后这里有两种证明过程,可以逆推和正推,先看逆推(需要你猜出结论)。

正推的话是一样的,考虑一下这个 实际含义,对于每一个 都相当于在求在 以内有多少个数是 的倍数且是 的倍数。

然后带入原式子。




后面这个不就是枚举的约数个数吗?



然后这东西怎么算,把式子拆成两部分,就是要求 的前缀和,考虑 min_25 筛。

算一下质数下的取值。
,套进 min_25 筛的板子即可。时间复杂度 ,如果用 min_26 筛,可以做到 ,但是没有必要。
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;
}



全部评论
min_26可还行
点赞 回复
分享
发布于 2021-04-24 10:07
C题的 dp 不能是线性的嘛
点赞 回复
分享
发布于 2021-04-24 13:20
微众银行
校招火热招聘中
官网直投
不懂就问,E题最后一个式子第一个求和是枚举T吧.
点赞 回复
分享
发布于 2021-04-24 22:39
第四题点分治怎么做啊
点赞 回复
分享
发布于 2021-04-25 12:53
好家伙,E题太卡常了把,写个快速幂就被卡了
点赞 回复
分享
发布于 2021-04-26 11:20
请问出题人,T4最后一组数据是有什么坑吗,一直TLE过93.3的数据
点赞 回复
分享
发布于 2021-04-26 16:51
C题有标程吗
点赞 回复
分享
发布于 2021-04-27 19:24

相关推荐

5 2 评论
分享
牛客网
牛客企业服务