速通挑战赛#8题解

。

2024-08-12 13:58:38

发布于：浙江

74阅读

14回复

5点赞

挑战赛#8
ヾ(≧▽≦*)o这次题目超有石粒，我也是耗费两天半才ak，实在难
暴力标记来判断0ms解决
现在来写 $题解$
so,let's go
$T1$
双倍经验

#include<iostream>
using namespace std;
int a[100005],cnt;
int main(){
	int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
    for(int i=l1;i<=r1;i++){
    	a[i]+=1;//先给蓝的做标记
    }
     for(int i=l2;i<=r2;i++){
    	a[i]+=2;//再给红的做标记
    }
    int n=max(l1,max(r2,max(l2,r1)));
    int d=min(l1,min(r2,min(l2,r1)));
    for(int i=d;i<=n;i++){
    	if(a[i]==3){
        	cnt++;
        }
    }
    if(cnt!=0)
        cout<<cnt-1;
    else{
        cout<<cnt;
    }//判断一下是否重叠，如果不等于0cnt-1，否则输出cnt
}

这道题目是签到题so easy
but next two
$T2$
卡我半小时的题目
开一个char数组来判断是不是dwl
双倍经验

#include <iostream>
using namespace std;
bool check(char a[1005][1005] , int n) {//wa了两个点后才发现check 有一个地方写漏了$恼$
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue; 
            if (a[i][j] == 'W' && a[j][i] != 'L') return false;
            if (a[i][j] == 'L' && a[j][i] != 'W') return false;
            if (a[i][j] == 'D' && a[j][i] != 'D') return false;
        }
    }
    return true;
}
int main() {
    int n;
    cin >> n;
    char a[1005][1005];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >>a[i][j];
        }
    }
    if (check(a, n)) {//判断check
        cout << "correct" << endl;
    } else {
        cout << "incorrect" << endl;
    }
    return 0;
}

$大水题顶多入门$ 但这是一道非常优质的入门食材
现在来到 $T3$ 😄q(≧▽≦q)
用map储存就行了也是一道水题，好奇？acgo前三道怎么都是大水题
双倍经验

//#include <bits/stdc++.h>
#include <iostream>
#include <map>
using namespace std;
int main() {
    int n;
    cin >> n;
    map<string, int> mp;//定义mp
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (mp.find(s) == mp.end()) {//标记寻找输入的s是否和上一个相同
            cout << s<< endl;
            mp[s] = 1;
        } else {
            int cnt = mp[s];否则就输出
            cout<<s<< "(" << cnt << ")" << endl;
            mp[s]++;
        }
    }
    return 0;
}//只要会stl容器这道题肯定会做出来

beautiful 现在来到了 $T4$
这是一道dp题嗯就是dp，我dp非常菜，我也是寻求~~老师才得到转移方程式~~
转移方程式如下:dp[i] = max(dp[i], dp[j] + suma[i] - suma[j+1]+sumb[i-j-1]);
双倍经验

#include <iostream>
using namespace std;
long long suma[100005], sumb[100005];//用前缀和优化否则会超是
long long dp[100005];
int main() {
    int n, m;
    cin >> n >> m;
    long long a[100005],b[100005];
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        suma[i] += suma[i - 1]+a[i] ; //没什么好说的
    }
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        sumb[x] = y;
    }
    for (int i = 1; i <= 5000; i++) {
        sumb[i] = sumb[i - 1]+sumb[i]; //这是给奖励b开的
    }

    for (int i = 1; i <= n; i++) {
        dp[i] = suma[i] + sumb[i];//接下来就是快乐dp环节
        for (int j = 1; j < i; j++) {
            dp[i] = max(dp[i], dp[j] + suma[i] - suma[j+1]+sumb[i-j-1]);
        }
    }
    cout << dp[n] << endl;
    return 0;
}

ok，现在已经到了 $T5$
这道题十分 $interesting$
有两种写法，就是转二进制或与非，但是会爆tm
所以我就就就用使用了dp大法也是开个三维dp来储存一个一个进行或与非运算就ok了（￣︶￣）虽然有亿点点毒瘤，但是能过就行
双倍经验

#include<iostream>
using namespace std;
int x,n,a[200001],t[200001],dp[35][3][300005];
int main(){
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>a[i];
	}for(int i=0;i<30;i++){
		for(int j=0;j<2;j++){
			dp[i][j][0]=j;
			for(int k=1;k<=n;k++){
				bool x=(a[k]>>i)&1;
				if(t[k]==1)dp[i][j][k]=dp[i][j][k-1]&x;
				else if(t[k]==2)dp[i][j][k]=dp[i][j][k-1]|x;
				else dp[i][j][k]=dp[i][j][k-1]^x;
			}
		}
	}for(int i=1;i<=n;i++){
		int ans=0,k=x;
		for(int j=0;j<30;j++){
			ans+=dp[j][k&1][i]*(1<<j);
			k>>=1;
		}cout<<ans<<endl;
		x=ans;
	}
}

到了T6我真哭死，竟然选了一道绿题，我一天半都在做那道题
so，就是一道归并排序逆序对，套个模版就行了，我真哭死，感觉阳寿耗尽😭😭😭😡( $ _ $ )
看代码

#include<bits/stdc++.h>
using namespace std;
//[双倍经验](https://www.luogu.com.cn/problem/AT_abc261_f)
#define ll long long
const int maxn=3e5;
int n,a[maxn+5],b[maxn+5],cnt[maxn+5],tmp[maxn+5],temp1[maxn+5],temp2[maxn+5];
ll ans;
void msort(int l,int r){//归并排序
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	msort(l,mid);
	msort(mid+1,r);
	for(int i=l;i<=r;i++){
		cnt[b[i]]=0;
	}
	for(int i=l;i<=mid;i++){
		cnt[b[i]]++;
	}
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i]<=a[j]){
			cnt[b[i]]--;
			tmp[k++]=i++;
		}
		else{
			ans+=mid-i+1-cnt[b[j]];
			tmp[k++]=j++;
		}
	}
	while(i<=mid){
		tmp[k++]=i++;
	}
	while(j<=r){
		tmp[k++]=j++;		
	}
	for(int i=l;i<=r;i++){
		temp1[i]=b[i],temp2[i]=a[i];
	}
	for(int i=l;i<=r;i++){
		a[i]=temp2[tmp[i]],b[i]=temp1[tmp[i]];
	}
}
int main(){//我就是~~sb~~
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	msort(1,n);
	cout<<ans;
	return 0;
}