• 2022牛客多校联赛第七场 题解

    比赛传送门
    作者： fn

    目录

    签到题

    C题 Constructive Problems Never Die / 构造题不死

    题目大意
    给定序列 a a a ，构造一个排列 p p p ，让 p i ≠ a i p_i≠a_i pi​=ai​ 。
    无解输出 “No” 。

    考察内容
    构造，贪心，暴力

    分析
    优先放出现多的数，最后3个数字暴力一下。

    #include
using namespace std;
int t,n;
struct Node{
	int x,num=0;
}node[100001];

int l0[100001];
int line[100001];
bool cmp(Node a,Node b){
	return a.num>b.num;
}

void workline(){
	int l=1,r=2;
	if(n>=3){
		for(int i=1;i<=n-3;i++){
			if(l0[i]!=node[l].x){
				line[i]=node[l].x;
				l=r;
				r++;
			}
			else{
				line[i]=node[r].x;
				r++;
			}
		}
		if(l0[n-2]!=node[l].x && l0[n-1]!=node[r].x && l0[n]!=node[r+1].x){
			line[n-2]=node[l].x;
			line[n-1]=node[r].x;
			line[n]=node[r+1].x;
		}
		if(l0[n-2]!=node[r].x && l0[n-1]!=node[l].x && l0[n]!=node[r+1].x){
			line[n-2]=node[r].x;
			line[n-1]=node[l].x;
			line[n]=node[r+1].x;
		}
		if(l0[n-2]!=node[l].x && l0[n-1]!=node[r+1].x && l0[n]!=node[r].x){
			line[n-2]=node[l].x;
			line[n-1]=node[r+1].x;
			line[n]=node[r].x;
		}
		if(l0[n-2]!=node[r].x && l0[n-1]!=node[r+1].x && l0[n]!=node[l].x){
			line[n-2]=node[r].x;
			line[n-1]=node[r+1].x;
			line[n]=node[l].x;
		}
		if(l0[n-2]!=node[r+1].x && l0[n-1]!=node[r].x && l0[n]!=node[l].x){
			line[n-2]=node[r+1].x;
			line[n-1]=node[r].x;
			line[n]=node[l].x;
		}
		if(l0[n-2]!=node[r+1].x && l0[n-1]!=node[l].x && l0[n]!=node[r].x){
			line[n-2]=node[r+1].x;
			line[n-1]=node[l].x;
			line[n]=node[r].x;
		}
	}
	else{
		for(int i=1;i<=n;i++){
			if(l0[i]!=node[l].x){
				line[i]=node[l].x;
				l=r;
				r++;
			}
			else{
				line[i]=node[r].x;
				r++;
			}
		}
	}
	for(int i=1;i<=n-1;i++){
		printf("%d ",line[i]);
	}
	printf("%d\n",line[n]);
}
signed main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){
			node[i].x=i;
			node[i].num=0;
		}
		for(int i=1;i<=n;i++){
			int d;
			cin>>d;
			l0[i]=d;
			node[d].num++;
		}
		sort(node+1,node+1+n,cmp);
		if(node[1].num==n){
			printf("NO\n");
		}
		else{
			printf("YES\n");
			workline();
		}
	}
	return 0;	
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101

    F题 Candies / 糖果

    题目大意
    给定一个环形序列 a a a ，相邻两个数字相同或者和为 x x x 可以消除。
    求最多消除几次。

    考察内容
    贪心，链表，栈

    分析
    可以消除时直接消除，用双向链表或者栈维护一下即可。

    #include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e5+5;
ll n,x;

struct node{ 
	ll val;
	ll before,nxt;
}a[N]; // 双向链表 

void del(int x){ // 删除位置为x的结点 
	a[a[x].before].nxt=a[x].nxt;
	a[a[x].nxt].before=a[x].before;
}

int main(){ // 贪心+链表 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>a[i].val;
		a[i].before=i-1;
		a[i].nxt=i+1;
	}
	a[1].before=n;
	a[n].nxt=1;
	
	if(n==1){ // 特判 
		cout<<0<<endl;
		return 0; 
	}
	
	// n>=2时 
	int p=1,q=2;
	int p0,q0;
	int cnt=0;
	ll ans=0;
	
	ll h=n*4; // 枚举的次数 
	while(q!=p && cnt<=h && ans<n){ // 
		while(a[p].val==a[q].val || a[p].val+a[q].val==x){
			if(p==q)break; // 
			 
			p0=a[p].before; // 记录p前1个
			del(p);
			del(q);
			p=p0; 
			q=a[p].nxt; // 获得p后面1格 
			 
			cnt+=2; // 
			ans++; // 累计答案 
		}
		
		p=a[p].nxt; // 往后走1格 
		q=a[p].nxt; // 获得p后面1格 
		cnt++;
	} 
	cout<<ans<<endl;
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63

    基本题

    G题 Regular Expression / 正则表达式

    题目大意
    给定字符串，求能匹配它的最短的正则表达式的长度和个数。

    考察内容
    思维

    分析
    n = 1 n=1 n=1 时，只有"a”和“.”可以匹配
    n ≥ 2 n≥2 n≥2 时，“.*” 可以匹配所有串，所以只需要考虑长度为2的正则表达式。分类讨论一下即可。

    #include
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e5+10;
const ll mod=998244353;
ll n,m,a[N];
string s[N];
int main(){ 
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		
		ll len=s[i].size();
		if(len==1){
			cout<<"1 2"<<endl;
			continue;
		}
		
		// len>=2
		cout<<"2 "; 
		
		ll num;  
		if(len==2){ // 两个 
			if(s[i][0]!=s[i][1]){ // ab
				num=6;
			}
			else{ // aa
				num=8;
			}
		}
		else{ // len>=3 
			int same=1;
			for(int j=0;j<=len-2;j++){
				if(s[i][j]!=s[i][j+1]){
					same=0; // 不是全部相同 
					break;
				}
			}
			
			num=2; // .*, .+
			if(same)num+=2; // a*,a+
		} 
		cout<<num<<endl;
	}
	return 0;
}
/*
1
aaa

*/ 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    进阶题

    J题 Melborp Elcissalc / 梅尔博普 埃尔西萨克

    题目大意
    把数组的 “优度” 定义为数组中总和 mod 𝑘=0 的非空连续子串的数目。

    请计算长度为 n n n 的优度为 t t t 的数组的数量，数组仅包含从 0 0 0 到 k − 1 k-1 k−1 的数字。答案对 998244353 998244353 998244353 取模。

    考察内容
    动态规划，前缀和

    分析

    考虑问题反过来怎么解决，即给定序列怎么求有多少子区间和 mod 𝑘=0 。

    前缀和后考虑 0 0 0 ~ 𝑘 − 1 𝑘−1 k−1 中每个数的出现次数 x x x ，答案就是 𝐶 𝑥 2 𝐶_𝑥^2 Cx2​ 。

    又因为前缀和数组和原数组一一对应，对于原问题可以直接dp满足条件的前缀和数组有多少种。

    记 𝑓 ( 𝑖 , 𝑗 , 𝑘 ) 𝑓(𝑖,𝑗,𝑘) f(i,j,k) 代表考虑完了 0 0 0 ~ 𝑖 𝑖 i 的数，放进了 𝑗 𝑗 j 个位置，对优度贡献为 𝑘 𝑘 k 的方案数，则 𝑓 ( 𝑘 − 1 , 𝑛 , 𝑡 ) 𝑓(𝑘−1,𝑛,𝑡) f(k−1,n,t) 即为答案。

    #include 
using namespace std;
const int N=70,P=998244353;
int n,k,t,C[N][N],f[N][N*N];
int Pre[N];
int main(){ // dp
	scanf("%d%d%d",&n,&k,&t);
	C[0][0]=1;
	for (int i=1;i<=n;i++){
		Pre[i+1] = Pre[i]+i;
	} 
	for (int i=1;i<=n;++i){
		C[i][0]=C[i][i]=1;
		for (int j=1; j<i;++j){
			C[i][j] = (C[i-1][j-1]+C[i-1][j])%P;
		} 
	}
	for (int i=0;i<=n&&Pre[i+1]<=t;++i){
		f[i][Pre[i+1]]=C[n][i];
	} 
	for (int i=1;i<k;++i)
		for (int j=n;j;j--)
			for (int l=1;l<=j &&Pre[l]<=t;l++)
				for (int r=0;r<=t-Pre[l];r++)
					if (f[j-l][r]){
						f[j][r+Pre[l]]=(1ll*f[j-l][r]*C[n-j+l][l]+f[j][r+Pre[l]])%P;
					} 
	cout<<f[n][t];
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    K题 Great Party / 盛大的聚会

    题目大意
    桌子上有成堆的石头，第 i i i 堆有 a i a_i ai​ 个。
    ​
    两名玩家参与游戏，依次操作石头。在每个玩家的回合中，玩家将执行以下两个步骤：

    1. 选择一堆非空的石头，选择要从中移除的正数量的石头。
    2. 保持堆中剩余的石头不动，或将剩余的石头塞给另一个非空的石头堆。

    那些不能操作的人会输掉比赛。
    q q q 次区间询问。每一个问题询问 [ l , r ] [l, r] [l,r] 中有多少子段满足了这样的要求：如果该段中的桩单独取出进行游戏，第一个玩家将获胜。

    考察内容

    NIM博弈，莫队（离线+分块），前缀和，结论

    分析
    结论：
    一个区间如果长度是奇数，那么先手必胜；否则如果石子个数减一的异或和不为0，先手必胜；否则后手必胜。

    归纳证明：
    如果区间长度是 1 1 1 ，直接取完就能胜利，显然先手必胜。

    如果区间长度为 2 2 2 ，先后手必定不能把某一堆石子取完，不然该玩家必败。那么每堆石子有一个是不能取的，除此之外是一个NIM模板。

    如果区间长度为 ≥ 3 ≥3 ≥3 的奇数，假设一共有 n n n ( n n n 是奇数) 堆，先全部 − 1 -1 −1，再把这 n n n 堆全部异或起来，得到 m m m ，选择一个 m m m 的最高二进制位为 1 1 1 的数进行操作（移除若干石头，剩下的石头留着或者塞给别人），一定可以获得一个区间长度为偶数且石子个数减一的异或和为 0 0 0 的局面，所以先手必胜。（这段是经过群友讨论后得出的， “一定可以获得” 这里还是有些猜结论的意思，严格证明不会QAQ，有大佬知道的可以在评论区补充）

    如果区间长度为 ≥ 4 ≥4 ≥4 的偶数，同理，先后手必定不能把某一堆石子取完，不然区间长度奇偶性会发生改变，导致该玩家必败。每堆石子有一个是不能取的，除此之外是一个NIM模板。

    区间询问有多少子区间先手必胜则可以通过前缀异或和以及离线+分块的算法完成。时间复杂度 𝑂 ( 𝑛 𝑚 ) 𝑂(𝑛\sqrt{𝑚}) O(nm ​) 。

    #include
using namespace std;
inline int in(){ // 快读 
	int x;
	scanf("%d",&x);
	return x;
}
const int N=1e5+5,M=1<<20|5,B=300;
int n,Q;
int a[N],s[N];
struct qes{
	int l,r,id;
}q[N];
inline bool cmp(qes a,qes b){
	int x=a.l/B,y=b.l/B;
	if(x==y)return a.r<b.r;
	return x<y;
}
long long res,ans[N];
int c[2][M];
void ins(int p){
	res += c[p&1][s[p]]++;
}
void del(int p){
	res -= --c[p&1][s[p]];
}
int main(){ // NIM变式+莫队 
	n=in(); Q=in();
	for(int i=1;i<=n;i++){
		a[i]=in()-1; // 要-1,每堆留下一个石子 
		s[i]=s[i-1]^a[i]; // 异或前缀和 
	}
	for(int i=1;i<=Q;i++){
		q[i].l=in()-1;
		q[i].r=in();
		q[i].id=i;
	}
	sort(q+1,q+Q+1,cmp);
	int L=1,R=0;
	for(int i=1;i<=Q;i++){
		int l=q[i].l,r=q[i].r;
		while(R<r)ins(++R);
		while(L>l)ins(--L);
		while(R>r)del(R--);
		while(L<l)del(L++);
		int len=r-l;
		ans[q[i].id]=(long long)len*(len+1)/2-res;
	}
	for(int i=1;i<=Q;i++)printf("%lld\n",ans[i]);
	return 0;
}
/*
5 1
14 13 12 9 1
1 5

// -1后
13 12 11 8 0
xor和为2,选11(塞到0上，把0变成9)就可以 
*/ 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
  • 相关阅读:
    计算机组成原理习题课第四章-1（唐朔飞）
    swagger2配置及注释详解
    Stanford CS224N - word2vec
    【node进阶】深入浅出前后端身份验证(下)---JWT
    【Vue-Element】矢量字体库iconfont字体图标库使用
    EventLoop
    JVM 对象的内存布局
    【仿牛客网笔记】项目进阶，构建安全高效的企业服务——将文件上传至云服务器
    微擎模块 酷炫小程序相册V4.4开源版，新增广告+评论功能相册点赞功能
    JUC中的AQS底层详细超详解
  • 原文地址：https://blog.csdn.net/weixin_51937688/article/details/126232608