A. Array Divisibility

?

思路:

找出特例,發現輸出?1～𝑛?符合題意。直接輸出1~n即可.

代碼:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[N], w[N], v[N], h[N];
ll dis[1005][1005];
ll a, b, c, n, m, t;
ll ans, sum, num, minn = 1e9 + 7, maxx = 0;
struct node {ll a, b, c;
}f[N];
string s1, s2;
int main()
{cin >> t;while (t--){cin >> n;for (int i = 1; i <= n; i++){cout << i << " ";}cout << endl;}return 0;
}

B. Corner Twist

?

?思路:

關鍵的充要條件是?𝑎,𝑏?的每一行/列的和模?3?后相等。證明的話，首先要想到?2×2?的操作是可以完成所有大小的子矩陣操作的，手模一下可以發現是對的。接著考慮比較暴力的方式，我們遍歷?𝑖,𝑗?從?1～𝑛?1?和?1～𝑚?1，然后把?𝑎𝑖,𝑗?按對應操作修改成?𝑏𝑖,𝑗，經過這樣之后前?𝑛?1?行和?𝑚?1?列都是可以相等的，所以也就是看最后那一列是否滿足。而這個遍歷順序又是可以變化的，也就是最后剩下的行列可以是任意一行一列，所以要所有行列均滿足模?3?結果相等。

代碼:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000005
ll dp[N], w[N], v[N], h[N];
char a[505][505], b[505][505];
ll x1[505], x2[505], y[505], y2[505];
ll  n, m, t;
ll ans, sum, num, minn = 1e9 + 7, maxx = 0;
struct node {ll a, b, c;
}f[N];
string s1, s2;
int main()
{cin >> t;while (t--){cin >> n >> m;memset(x1, 0, sizeof(x1));memset(x2, 0, sizeof(x2));memset(y, 0, sizeof(y));memset(y2, 0, sizeof(y2));for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> a[i][j];x1[i] += a[i][j]-'0';y[j] += a[i][j]-'0';}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> b[i][j];x2[i] += b[i][j]-'0';y2[j] += b[i][j]-'0';}}int flag = 1;for (int i = 1; i <= n; i++) {if (x1[i] % 3 != x2[i] % 3) {flag = 0;break;}}for (int j = 1; j <= m; j++) {if (y[j] % 3 != y2[j] % 3) {flag = 0;break;}}if (flag == 1)cout << "YES" << endl;elsecout << "NO" << endl;}return 0;
}

C. Have Your Cake and Eat It Too

?

?

思路:

枚舉三個人的順序，然后把序列分成三段就行了，判斷可以直接?𝑂(𝑛)，至于枚舉順序不需要重復粘貼六次代碼，用一個?next_permutation?函數就行了。

代碼:

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
typedef long long ll;
typedef unsigned long long ull;
ll n, m, t, h, k;
ll ans, num, sum, cnt;
ll dp[N], ac[4][N], a[4][N], get1[N], get2[N];
bool flag, vis[N];
struct node {ll mark, x, y;
}f[N];
bool cmp(node a, node b) {return a.mark < b.mark;
}
int main()
{cin >> t;while (t--){cin >> n;ac[1][0] = ac[2][0] = ac[3][0] = sum = 0;for (int i = 1; i <= 3; i++) {for (int j = 1; j <= n; j++) {cin >> a[i][j];if(i==1) sum += a[i][j];ac[i][j] = ac[i][j - 1] + a[i][j];}}sum = (sum + 2) / 3;for (int i = 1; i <= 3; i++) {for (int j = 1; j <= n; j++) {if (ac[i][j] >= sum) {get1[i] = j;break;}}}for (int i = 1; i <= 3; i++) {for (int j = n - 1; j >= 0; j--) {if (ac[i][n]-ac[i][j] >= sum) {get2[i] = j+1;break;}}	}ll order[3] = { 1,2,3 };flag = 1;do {for (int i = 0; i < 3; i++)f[i].mark = order[i];f[1].x = get1[order[0]] + 1, f[1].y = get2[order[2]] - 1;if (ac[order[1]][f[1].y] - ac[order[1]][f[1].x - 1] < sum)continue;f[0].x = 1, f[0].y = get1[order[0]];f[2].x = get2[order[2]], f[2].y = n;sort(f , f + 3, cmp);for (int i = 0; i < 3; i++) {cout << f[i].x << " " << f[i].y << " ";}cout << endl;flag = 0;break;} while (next_permutation(order, order + 3));if (flag)cout << -1 << endl;}return 0;
}

D. Swap Dilemma

?

思路:

首先如果元素不同直接輸出"NO",如果相同,那么我們可以通過求出個兩個序列的轉換成相同序列的次數,也就是會改變?𝑎,𝑏?逆序對的數量，并且同時改變其數量奇偶性,所以怎么只要保證兩次序列的奇偶性相同即可,但我們可以進行優化,將只對一個序列進行操作,只要將序列B映射到序列A上,那么問題就變成了只需要求映射后的序列B的逆序對個數即可.

代碼:

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
typedef long long ll;
typedef unsigned long long ull;
ll n, m, t, h, k;
ll ans, num, sum, cnt;
ll temp[N], a[N], f1[N], f2[N];
bool flag, vis[N];
struct node {ll mark, x, y;
}f[N];
bool cmp(node a, node b) {return a.mark < b.mark;
}
void merge_sort(int l, int r)
{if (l == r)return;int mid = l + r >> 1;merge_sort(l, mid);merge_sort(mid + 1, r);int ll = l, st = l, rr = mid + 1;while (l <= mid and rr <= r){if (a[l] <= a[rr])temp[ll++] = a[l++];elsetemp[ll++] = a[rr++], ans += mid - l + 1;}while (l <= mid)temp[ll++] = a[l++];while (rr <= r)temp[ll++] = a[rr++];for (int i = st; i <= r; i++)a[i] = temp[i];return;
}
int main()
{cin >> t;while (t--){ans = 0,flag=1;cin >> n;map<ll, ll>mp;for (int i = 1; i <= n; i++) {cin >> f1[i];mp[f1[i]] = i;}for (int i = 1; i <= n; i++) {cin >> f2[i];}for (int i = 1; i <= n; i++) {if (mp.count(f2[i]) == 0) {flag = 0;break;}a[i] = mp[f2[i]];}merge_sort(1, n);if (flag == 0) {cout << "NO" << endl;}else {if (ans % 2==0)cout << "YES" << endl;elsecout << "NO" << endl;}}return 0;
}