Codeforces Global Round 19

本弱弱只能A B C,大佬求带

A. Sorting Parts

input

output

YES
YES
NO

题意：给你一个数组，问你是否可以按照题目要求操作一次，这个数组不是递增的一个序列

操作要求：选择一个位置x，把[1,x],[x + 1,n]，进行排序

思路：只要找到一对前大后小的数，就能满足要求，或者用已经排好序的数组与原数组对比，不一样的超过两个就是可以的

AC代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define PII pair 
#define PDI pair 
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn = 1e4+5;
int a[maxn],b[maxn],t,n;
void solve()
{
	sort(b + 1,b + 1 + n);
	int cnt = 0;
	for(int i = 1 ; i <= n ; i++){
		if(a[i] != b[i]) cnt++;
		if(cnt >= 2){
			cout << "YES" << endl;
			return ; 
		}
	}
	cout << "NO" << endl; 
}
int main(){
	IOS;
	cin >> t;
	while(t--){
		cin >> n;
		for(int i = 1 ; i <= n ; i++) cin >> a[i],b[i] = a[i];
		solve();
	}
    return 0;
}

假如知道函数也可直接调用函数（参考官方题解）

#include 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        vector a(n);
        for (auto& u : a)
            cin >> u;
        if (!is_sorted(a.begin(), a.end()))
            cout << "YESn";
        else
            cout << "NOn";
    }
}

B. MEX and Array

本弱弱没读懂题意，望有大佬指点

官方题解

官方代码

#include 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        vector a(n);
        for (auto& u : a)
            cin >> u;
 
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (i + 1) * (n - i);
            if (a[i] == 0)
                ans += (i + 1) * (n - i);
        }
        cout << ans << 'n';
    }
}

C. Andrew and Stones

题意：给你 n 堆石头，给你一种操作规则，把 1 ~ n之间的石头放到第1堆和第n堆，问最小的操作次数

操作规则：可以选择三堆石头，中间的一堆假如石头的数量大于等于2，就可以向另外的两堆石头分别放置一块

思路：什么情况下是-1（解题关键），可以看看题目给的样例，很明显就是石头个数为1或者为奇数，但是偶数堆的石头可以让1或者奇数堆的石头变成偶数堆，然后循环下去，所以-1的情况只有中间石头个数全为1，或者就是特殊样例，中间只有一堆石头为奇数

AC代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define PII pair 
#define PDI pair 
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
const int maxn = 1e5+5;
int a[maxn],n,t;
void solve()
{
	ll ans = 0;
	int MAX = 0;
	for(int i = 2 ; i < n ; i++) MAX = max(a[i],MAX); 
	if(MAX == 1 || (n == 3 && a[2] % 2 == 1)){
		cout << -1 << endl;
		return;
	}
	for(int i = 2 ; i < n ; i++){
		if(a[i] & 1) ans = ans +  (a[i] + 1) / 2;
		else ans = ans + a[i] / 2;
	}
	cout << ans << endl;
}
int main(){
	IOS;
	cin >> t;
	while(t--){
		cin >> n;
		for(int i = 1 ; i <= n ; i++) cin >> a[i];
		solve();
	}
    return 0;
}

Codeforces Global Round 19

C/C++/C#相关栏目本月热门文章