暑期cspj模拟赛1

T1

显然第i个位置会被变换n+1-i次,所以$a_i$最后的值$(a_i + n+1-i) mod 2$, 另一个问题是$a_i$最终会在哪里.从倒着来看,可以发现$a_n$ 在第一个位置,$a_{n-1}$在倒数第一个位置位置,$a_{n-2}$在第二个位置,$a_{n-3}$在倒数第二个位置, 显然我们找到了规律.按照n->1,左右轮着放就行.

#include<bits/stdc++.h>
using namespace std;
int n;
int s[2000010]; //s用来存储原序列
int ans[2000010]; //ans用来存储答案序列
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];
        s[i] = (s[i] + n + 1 - i) % 2;   // 这是每个位置最终的值
    }

    // 现在找每个位置 最终所在的位置
    int left = 1, right = n;
    bool isleft = true;
    for (int i = n; i >= 1; i--) {
        if (isleft) {
            ans[left] = s[i];
            left++;
        }else {
            ans[right] = s[i];
            right--;
        }
        isleft = !isleft;
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " "; //输出答案即可
    }
    return 0;
}

T2

过于简单,不解释了

#include <bits/stdc++.h>
using namespace std;
const int c=200005;
int n, bal, jobb, cnt, t[c];
void solve() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> t[i];
    }
    bal=t[1], jobb=t[n], cnt=2;
    while (2*bal<jobb) {
        int maxi=bal;
        for (int i=1; i<=n; i++) {
            if (t[i]>maxi && t[i]<=2*bal) {
                maxi=t[i];
            }
        }
        if (maxi==bal) {
            cout << -1 << "\n";
            return;
        }
        cnt++;
        bal=maxi;
    }
    cout << cnt << "\n";
}
int main() {
	ios_base::sync_with_stdio(false);
    int w;
    cin >> w;
    while (w--) {
        solve();
    }
}

T3

显然最终形成的是一个手拉手的环,遍历每一个排列,取最小修改值即可.

#include<bits/stdc++.h>
using namespace std;
int p[10], inf = 1000000000;
int vis[10][10];
int n, m, ans = inf;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        vis[u][v] = 1;
        vis[v][u] = 1;
    }

    for (int i = 1; i <= n; i++) {
        p[i] = i;
    }
    do {
        int cans = m;
        for (int i = 1; i <= n; i++) {
            cans += vis[p[i]][p[i % n + 1]]?-1:1;
        }
        ans = min(ans, cans);
    }
    while (next_permutation(p + 1, p + n + 1));
    cout << ans << '\n';
    return 0;
}

T4

https://www.luogu.com.cn/problem/solution/P11187