挑战赛#8题解

暑假神（开学祭

2024-08-15 15:16:03

发布于：浙江

101阅读

0回复

0点赞

前言

这次挑战赛更难了亿点啊。为了精简题解长度，已经去了头文件、部分宏定义和快读快写。

T1

首先是 $0$ 的情况： $L_1\leq R_2\ \operatorname{or}\ L_2\leq R_1$ ，两条线段不交/只交于一点。

然后暴力分讨。

$L_1\leq L_2\ \operatorname{and}\ R_1\geq R_2$
线段 $L_2R_2$ 被 $L_1R_1$ 包含。直接输出 $L_2R_2$ 的长度即可。
$L_1\leq L_2\ \operatorname{and}\ R_1\leq R_2$
线段 $L_1R_1$ 与 $L_2R_2$ 的交集为 $R_1L_2$ 。输出 $R_1L_2$ 的长度即可。
$L_1\geq L_2\ \operatorname{and}\ R_1\leq R_2$
类似于 1。
$L_1\geq L_2\ \operatorname{and}\ R_1\geq R_2$
类似于 2。

int main(){
	int a,b,c,d;
	scanf("%d%d%d%d",&a,&b,&c,&d);
    if(b<=c||d<=a){
        printf("0");return 0;
    }
	if(a<=c&&b>=d){
		printf("%d",d-c);
	}else if(a<=c&&b<=d){
		printf("%d",b-c);
	}else if(a>=c&&b<=d){
		printf("%d",b-a);
	}else if(a>=c&&b>=d){
		printf("%d",d-a);
	}
	
	return 0;
}

T2

依然是分讨。设 $1\leq i,j\leq n,i\neq j$ ：

$A_{i,j}=\texttt{D}$ ： $A_{j,i}$ 也应该为 $\texttt{D}$ 。
$A_{i,j}=\texttt{W}$ ： $A_{j,i}$ 应该为 $\texttt{L}$ 。
$A_{i,j}=\texttt{L}$ ： $A_{j,i}$ 应该为 $\texttt{W}$ 。

枚举判断即可。

char a[1005][1005];

int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%s",a[i]+1);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
            if(i==j)continue;
			if(a[i][j]=='D'){
				if(a[j][i]!='D'){
					puts("incorrect");
					return 0;
				}
			}else if(a[i][j]==a[j][i]){
				puts("incorrect");
				return 0;
			}
		}
	}
	puts("correct");
	
	return 0;
}

T3

使用 map 计数字符串出现的次数即可。如果这个字符串没有出现过，就直接输出；否则要再输出出现的次数。然后在 map 对这个字符串计数。

map<string,int>mp;

int main(){
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		string s;cin>>s;
		cout<<s;
		if(mp[s])cout<<'('<<mp[s]<<')';
		cout<<'\n';
		mp[s]++;
	}
	
	return 0;
}

T4

这题开始上难度了 qwq

首先看数据范围： $M,N\leq 5000$ ，也许我们可以设计一个时空 $O(n^2)$ 的 DP。无后效性是满足的，第 $i$ 次硬币的状态由 $i-1$ 次转移而来。

发现状态只需要硬币和计数器。所以考虑这样设状态：设 $f(i,j)$ 表示第 $i$ 次掷硬币，计数器为 $j$ 时的最大收益。从硬币维开始枚举。每一次枚举有两种可能：

正面

设计数器本次显示 $j$ ，第 $i$ 次掷硬币时掷到正面可以获得 $X(i)$ 元，计数器为 $i$ 时可以获得 $Y(i)$ 元，则容易推得：

$f(i,j)=f(i-1,j-1)+X(i)+Y(j)\qquad(j\geq1)$

反面

计数器本次必然显示 $0$ 。可以由上一轮的所有状态取最大值直接转移而来，即 $f(i,0)=\max\limits_{j=0}^{i-1}f(i-1,j)$ 。

结果为投掷第 $n$ 次硬币的最大值，即 $\max\limits_{i=0}^{n}f(n,i)$ 。

实现还是很简单的。注意开 long long。嫌空间大可以把动态规划数组滚掉一维，是可选的。

int x[5005],jl[5005];
ll f[5005][5005];

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",x+i);
	}
	for(int i=1;i<=m;i++){
		int c,y;
		scanf("%d%d",&c,&y);
		jl[c]=y;
	}
	for(int i=1;i<=n;i++){
		for(int k=0;k<i;k++) f[i][0]=max(f[i][0],f[i-1][k]);
		for(int j=1;j<=i;j++){
			f[i][j]=f[i-1][j-1]+x[i]+jl[j];
		}
	}
	ll ans=0;
	for(int i=0;i<=n;i++){
		ans=max(ans,f[n][i]);
	}
	printf("%lld",ans);
	
	return 0;
}

T5

前置知识：位运算。

这道题直接模拟是 $O(n^2)$ 的，必然超时。

首先位运算很多，发现位与位之间是没有关系的，我们考虑逐位计算，可以简单很多。接下来的讨论都是基于每一位的。

先考虑怎么降时间复杂度。发现每一次依次完成 $1-i$ 操作后，一定是以下两个情况之一：

反转当位
将当位设置为固定值

然后考虑将 $1-(i-1)$ 操作的情况拓展至 $1-i$ 。设有覆盖标记 $t1$ ，反转标记 $t2$ 。又分为六种情况：

&0 操作。覆盖标记设 $0$ ，反转标记清零。
&1 操作。无需操作。
|0 操作。无需操作。
|1 操作。覆盖标记设 $1$ ，反转标记清零。
^0 操作。无需操作。
^1 操作。反转反转标记。

如果存在覆盖标记，则直接将原数赋值为覆盖标记。如果存在反转标记，则对原数进行反转。每一次操作完毕后记录过程性答案，时间复杂度 $O(n)$ 。细节注释都放在代码里了。

int x;
int t[200005],a[200005];
int ans[200005];

int main(){
	int n;
	scanf("%d%d",&n,&x);
	for(int i=1;i<=n;i++){
		scanf("%d%d",t+i,a+i);
	}
	for(int i=0;i<30;i++){
		int tt=x&(1<<i); // 原数
		int t1=-1,t2=0; // 覆盖标记，反转标记
		// 这两个标记是要复用的！每一轮都会继承上一轮的值。
		for(int j=1;j<=n;j++){
			if(t[j]==1){ // 与运算
				tt&=(a[j]&(1<<i)); // 修改原数当位
				if(!(a[j]&(1<<i))) t1=t2=0;
				// 如果为 0，覆盖标记设 0，清空反转标记
			}
			if(t[j]==2){ // 或运算
				tt|=(a[j]&(1<<i)); // 修改原数当位
				if(a[j]&(1<<i)) t1=1<<i,t2=0;
				// 如果为 0，覆盖标记（当位）设 1，清空反转标记
			}
			if(t[j]==3) t2^=a[j]&(1<<i); // 异或运算，修改反转标记
			if(t1>=0)tt=t1; // 覆盖标记
			tt^=t2; // 反转标记
			ans[j]|=tt; // 记录答案
		}
	}
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	
	return 0;
}

T6

前置知识：归并排序求逆序对

首先忽略颜色限制。只能两两交换，把序列排成升序，需要几次操作？显然是逆序对的个数。使用归并排序可以在 $O(n\log n)$ 的时间内求逆序对，这里直接贴上代码。

void Msort(int l,int r){
	if(l>=r) return;
	int mid=l+r>>1;
	Msort(l,mid);
	Msort(mid+1,r);
	
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]>a[j]) b[k++]=a[i++],ans+=r-j+1;
		else b[k++]=a[j++];
	}
	while(i<=mid) b[k++]=a[i++],ans+=r-j+1;
	while(j<=r) b[k++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=b[i];
}

那么加上颜色限制之后，就变得复杂了。先不要急，首先求出原序列的逆序对个数。但是显然有一些逆序对不需要交换。是哪些逆序对呢？当然是同色的逆序对。因此，我们直接将各个颜色的数按序分进桶。~~（我就是因为没有按序被卡了好久www）~~ 然后对各个桶内的球进行归并排序求逆序对。原序列的逆序对个数，减去同色逆序对个数，就是异序逆序对个数，也就是我们要求的答案了。

实现当然还是轻轻松松。注意一下 long long，然后桶使用 vector 维护就行了。总复杂度 $O(n\log n)$ 。

ll ans;
int a[300005],b[300005],c[300005];

void Msort(int l,int r){
	if(l>=r) return;
	int mid=l+r>>1;
	Msort(l,mid);
	Msort(mid+1,r);
	
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]>a[j]) b[k++]=a[i++],ans+=r-j+1;
		else b[k++]=a[j++];
	}
	while(i<=mid) b[k++]=a[i++],ans+=r-j+1;
	while(j<=r) b[k++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=b[i];
}

vector<int>buc[300005];

void Msort(vector<int>&a,int l,int r){
	if(l>=r) return;
	int mid=l+r>>1;
	Msort(a,l,mid);
	Msort(a,mid+1,r);
	
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]>a[j]) b[k++]=a[i++],ans+=r-j+1;
		else b[k++]=a[j++];
	}
	while(i<=mid) b[k++]=a[i++],ans+=r-j+1;
	while(j<=r) b[k++]=a[j++];
	for(int i=l;i<=r;i++) a[i]=b[i];
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",c+i);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
	}
	for(int i=1;i<=n;i++){
		buc[c[i]].push_back(a[i]);
	}
	Msort(1,n);
	ll aans=ans;
	for(int i=1;i<=300000;i++){
		if(buc[i].size()){
			ans=0,Msort(buc[i],0,buc[i].size()-1),aans-=ans;
		}
	}
	printf("%lld\n",aans);
	
	return 0;
}