A. o-padding
code
#include<bits/stdc++.h>
using namespace std;
int main(){int n;string s,pre = "";cin >> n >> s;for(int i = s.size()+1; i <= n; ++i)pre += 'o';cout << pre << s;
}
B. Magic Square
code
#include<bits/stdc++.h>
using namespace std;
const int NN = 108;
int a[NN][NN];
int n;
int main(){ios::sync_with_stdio(false),cin.tie(0);cin >> n;int x = 0, y = (n-1)/2,cnt = 0;for(int i = 1; i <= n; ++i){for(int j = 1; j <= n; ++j){a[x][y] = ++cnt;if(j != n){x = (n+x-1) % n;y = (y+1) % n;}else{x = (x+1) % n;}}}for(int i = 0; i < n; ++i){for(int j = 0; j < n; ++j){cout << a[i][j] << " ";}cout << endl;}
}
C. 2x2 Placing
不得不说，C 题的实现是有一点困难的
至少在脑袋不够用的情况下卡了本人很久的实现 TAT
就是一个在平面内查询一个点是否被覆盖的问题
code
#include<bits/stdc++.h>
using namespace std;
const int NN = 1e6 + 8;
int n,m;
int fx[9] = {-1,-1,-1,0,0,0,1,1,1};
int fy[9] = {-1,0,1,-1,0,1,-1,0,1};
struct Node{int num;int x,y;bool operator < (const Node &A)const{if(x == A.x){if(y == A.y) return num < A.num;return y <= A.y;}else return x < A.x;}bool operator <= (const Node &A)const{if(x == A.x){if(y == A.y) return num <= A.num;return y <= A.y;}else return x < A.x;}
}a[NN],b[NN];
bool d[NN];
vector<int> now,pre;
int check(int x,int y){int i = lower_bound(b+1,b+1+m,(Node){0,x,y}) - b;if(b[i].x == x && b[i].y == y && d[b[i].num]) return b[i].num;else return 0x3f3f3f3f;
}
int main(){cin >> n >> m;for(int i = 1; i <= m; ++i)cin >> a[i].x >> a[i].y, b[i].x= a[i].x, b[i].y = a[i].y, b[i].num = i;sort(b+1,b+1+m);int ans = 0;for(int i = 1; i <= m; ++i){bool vis = 1;for(int j = 0; j <= 8; ++j)if(check(a[i].x + fx[j],a[i].y + fy[j]) < i){// cout << i << ":" << a[i].x + fx[j] << " " << a[i].y + fy[j] << "get\n";vis = 0;break;}if(vis) d[i] = 1,++ans;}cout << ans << endl;
}
D. Teleport Maze
bfs 即可
code
#include<bits/stdc++.h>
using namespace std;
const int NN = 1e3 + 8;
int H,W;
string s;
int step[NN][NN];
int vis[NN][NN];
int fx[4] = {0,0,1,-1};
int fy[4] = {1,-1,0,0};
struct Node{int x,y;
};
vector<Node> Ch[30];inline int trans(char c){return c-'a'+1;
}
void search(){queue<Node> q;q.push({1,1});step[1][1] = 0;while(!q.empty()){Node u = q.front();q.pop();int ux = u.x, uy = u.y, stu = step[ux][uy];if(vis[ux][uy] != 0){int c = vis[ux][uy];for(auto j : Ch[c]){int vx = j.x, vy = j.y;if(step[vx][vy] == -1){q.push({vx,vy});step[vx][vy] = stu + 1;}}Ch[c].clear();}for(int j = 0; j < 4; ++j){int vx = ux + fx[j], vy = uy + fy[j];if(vx <= 0 || vx > H || vy <= 0 || vy > W) continue;if(step[vx][vy] == -1 && vis[vx][vy] != -1){q.push({vx,vy});step[vx][vy] = stu + 1;}}}
}
int main(){memset(step,-1,sizeof(step));cin >> H >> W;step[1][1] = 0;for(int i = 1; i <= H; ++i){cin >> s;s = ' ' + s;for(int j = 1; j <= W; ++j)if(s[j] == '#'){vis[i][j] = -1;}else if(isalpha(s[j])) Ch[trans(s[j])].push_back({i,j}), vis[i][j] = trans(s[j]);}search();cout << step[H][W];
}
E. Minimum Swap
这道题就是通过排列连边之后，询问最小环的大小
code
#include<bits/stdc++.h>
using namespace std;
const int NN = 3e5 + 8;
int n;
int a[NN],rev[NN];
int main(){cin >> n;for(int i = 1; i <= n; ++i)cin >> a[i];long long ans = 0;for(int i = 1; i <= n; ++i){if(i != a[i]){int cnt = 1;int t = a[i];while(a[i] != i) swap(a[i],a[t]), t = a[i], ++cnt;ans += 1ll * cnt * (cnt-1) / 2;}}cout << ans;
}