Codeforces Round #648 (Div. 2)

或許更好的閱讀體驗(yàn)

A:Matrix Game

思路

題意可以說(shuō)是非常簡(jiǎn)單的，我們選定的格子的行列都不能存在1，可以發(fā)現(xiàn)我們可以放的格子一定是固定的，然后這題就變成了技術(shù)總共可以放多少個(gè)棋子了，所以我們直接開(kāi)兩個(gè)數(shù)組記錄一下行列是否有1存在，再通過(guò)暴力求解的到可放的格子的數(shù)量就行，具體看代碼注釋吧。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 55;int a[N][N], n, m, c[N], r[N];int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false);int t = read();while(t--) {n = read(), m = read();memset(c, 0, sizeof c);memset(r, 0, sizeof r);for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++) {a[i][j] = read();if(a[i][j]) c[i] = 1, r[j] = 1;//r[i]表示這一行是否有1，c[j]表示這一列是否有1，}int sum = 0;for(int i = 1; i <= n; i++) {//枚舉行。if(c[i]) continue;//如果這一行是有1的話，直接跳過(guò)，不用考慮了，for(int j = 1; j <= m; j++) {if(r[j]) continue;//同上，這一列有1不考慮else {//否則將這一列標(biāo)記上1，然后格子數(shù)量+1；sum++;r[j] = 1;break;}}}// cout << sum << endl;if(sum & 1) puts("Ashish");//判斷答案奇偶即可。else puts("Vivek");}return 0; }

Trouble Sort

思路

這題全靠瞎猜：分兩種情況。

• 一、原本的數(shù)列就是有序的，這是肯定可以復(fù)原的到的。
• 二、原本的數(shù)列是無(wú)序的，所以我們必須進(jìn)行交換，這個(gè)時(shí)候只有同時(shí)存在 0 ，1就行了。

賽后仔細(xì)想想好像確實(shí)是這樣，假設(shè)只存在一個(gè)1，然后全是0，我們可以通過(guò)交換得到任意的排列。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 510;int a[N], b[N], n;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false);int t = read();while(t--) {n = read();int sum0 = 0, sum1 = 0;for(int i = 1; i <= n; i++) {a[i] = read();b[i] = a[i];}sort(a + 1, a + 1 + n);for(int i = 1; i <= n; i++) {int temp = read();if(temp) sum1++;else sum0++;}// for(int i = 1; i <= n; i++) // printf("%d%c", a[i], i == n ? '\n' : ' ');int flag = 1;for(int i = 1; i <= n; i++)//判斷是否有序，if(a[i] != b[i]) {flag = 0;break;}if(flag) puts("Yes");//case 1else {//case 2if(sum1 && sum0) puts("Yes");else puts("No");}}return 0; }

Rotation Matching

思路

首先我們明白，左移和右移的操作是等價(jià)的，任何通過(guò)左移得到的序列，我們都可以通過(guò)右移得到，反之亦然。所以我直接統(tǒng)計(jì)b序列的每個(gè)位置向右移動(dòng)多少位可以得到在a中的相同位置，最后再統(tǒng)計(jì)一圈最大值就行了。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 2e5 + 10;int a[N], b[N], sum[N], n;struct Node {int value, id;bool operator < (const Node & t) const {return value < t.value;} }node[N];int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false);n = read();for(int i = 1; i <= n; i++) {node[i].value = read();node[i].id = i;}sort(node + 1, node + 1 + n);for(int i = 1; i <= n; i++) {a[i] = node[i].value;b[i] = read();}for(int i = 1; i <= n; i++) {int p = lower_bound(a + 1, a + 1 + n, b[i]) - a;p = node[p].id;//好像這里直接就可以是p = node[b[i]].id;，寫(xiě)比賽的時(shí)候傻了。// cout << p << endl;int len = p - i;if(len < 0) len += n;sum[len]++;}// for(int i = 0; i <= n; i++)// printf("%d%c", sum[i], i == n ? '\n' : ' ');int ans = 0;for(int i = 0; i <= n; i++)if(sum[i] > sum[ans])ans = i;printf("%d\n", sum[ans]);return 0; }

Solve The Maze

思路

我們要保證最優(yōu)，使所有的好人都可以到達(dá)$n,m$，所以我們一定要選擇在每一個(gè)$B$的邊上加墻，這個(gè)時(shí)候還有一點(diǎn)要注意，如果有好人是緊鄰壞人的，那么我們一定不存在一種方案得到答案，這里直接在加墻的時(shí)候特判就行了。

加完墻之后，我們要保證所有的好人和$n,m$點(diǎn)是聯(lián)通的，所以我們直接從$n,m$點(diǎn)開(kāi)始$dfs|bfs$去訪問(wèn)所有可以達(dá)到的點(diǎn)，最后加一個(gè)特判，判斷是否所有的好人和$n,m$是否聯(lián)通，也就是看visit數(shù)組對(duì)應(yīng)的點(diǎn)是否已經(jīng)標(biāo)記為1，然后這題就🆗了。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }typedef pair<int, int> PII; const int N = 55; const int ax[4] = {1, 0, 0, -1}, ay[4] = {0, 1, -1, 0};char maze[N][N]; int visit[N][N]; int n, m;struct node{int x, y;node(int a = 0, int b = 0) : x(a), y(b) {} }; queue<node> q;void bfs(int s,int t) {while(!q.empty()) q.pop();visit[s][t] = 1;q.push(node(s, t));while(!q.empty()) {node temp = q.front();q.pop();for(int i=0;i<4;i++) {int tempx = temp.x + ax[i];int tempy = temp.y + ay[i];if(maze[tempx][tempy] != '#' && visit[tempx][tempy] == 0) {visit[tempx][tempy] = 1;q.push(node(tempx, tempy));}}} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false);int t = read();while(t--) {n = read(), m = read();for(int i = 1; i <= n; i++)scanf("%s", maze[i] + 1);for(int i = 0; i <= m + 1; i++)maze[0][i] = maze[n + 1][i] = '#';for(int i = 0; i <= n + 1; i++)maze[i][0] = maze[i][m + 1] = '#';int flag = 1;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {if(maze[i][j] == 'B') {// cout << i << " " << j << endl;int x = i, y = j;for(int k = 0; k < 4; k++) {if(maze[x + ax[k]][y + ay[k]] == 'G') {//這個(gè)點(diǎn)一定要注意特判，不然直接wa，flag = 0;break;}if(maze[x + ax[k]][y + ay[k]] == '.')maze[x + ax[k]][y + ay[k]] = '#';}}if(!flag) break;}if(!flag) break;}memset(visit, 0, sizeof visit);if(maze[n][m] != '#') bfs(n, m);for(int i = 1; i <= n;i++) {for(int j = 1; j <= m; j++) {if(maze[i][j] == 'G') {if(visit[i][j]) continue;else {flag=0;break;}}if(!flag) break;}if(!flag) break;}if(flag) puts("Yes");else puts("No");}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #648 (Div. 2)（A， B， C， D）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。