CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)

比赛链接

A. Jagged Swaps

思路：

考虑到题目要求，给定的排列第一位必须是1才会构造出可行性序列，如果不是就是没有办法

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long


void solve() {
	int n;
	cin>>n;
	std::vector<int> a;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		a.push_back(x);
	}
	if(a[0]!=1){
		cout<<"NO"<<endl;
		return ;
	}
	else{
		cout<<"YES"<<endl;
		return ;
		
	}
	
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int t; cin >> t; while(t--)
	solve();
	return 0;
}

B. AB Flipping

思路：

根据题意，我们不难发现如果存在合理的交换，每个连续的B都会交换一次，而与之有关系的A如果也是连续的，自然也是可以每个都可以交换一次，从后往前考虑

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
	int n;
	cin>>n;
	string s;
	cin>>s;
	int ans=0;
	int cnt=0;
	for(int  i=n-1;i>=0;i--){
		if(!cnt&&s[i]=='A'){
			continue;
		}
		if(s[i]=='B') cnt++;
		else{
			ans+=cnt;
			cnt=1;
		}
	}
	cout<<ans<<endl;
	

}
signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int t; cin >> t; while(t--)
	solve();
	return 0;
}

C. Matching Arrays

思路：

考虑一个贪心的思路，我们要求a中最大的x个数与b中最小的x个数字匹配
a中最小的n-x个数与b中最大的n-x个数匹配，一旦两者之中都出现不匹配的情况那就是无法构成一组可行性答案，直接输出NO

Code

#include<bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;

const int N = 200010;

int n, x;
int b[N], ans[N];
bool st[N];

void solve()
{
    cin >> n >> x;
    memset(st, false, sizeof st);
    vector<PII> a;
    
    for(int i = 0; i < n; i ++)
    {
        int ai;
        cin >> ai;
        a.push_back({ai, i});
    }
    for(int i = 0; i < n; i ++)cin >> b[i];
    sort(a.begin(), a.end());
    sort(b, b + n);
    
    int f = 1;
    for(int i = n - x, j = 0; j < x; j ++, i ++)
    {
        if(a[i].first <= b[j])
        {
            f = 0;
            break;
        }
        ans[a[i].second] = b[j];
    }
    if(!f)
    {
        cout << "NO" << endl;
        return;
    }
    
    for(int j = x; j < n; j ++)
    {
        int i = j - x;
        if(a[i].first > b[j])
        {
            f = 0;
            break;
        }
        ans[a[i].second] = b[j];
    }
    if(!f)
    {
        cout << "NO" << endl;
        return;
    }
    
    cout << "YES" << endl;
    for(int i = 0; i < n; i ++)cout << ans[i] << ' ';
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _;
    cin >> _;
    while(_ --)
    {
        solve();
    }
    
    return 0;
}