B - Chessboard
难度: ⭐
题目大意
给定一个8*8的字符矩阵, 其中只有一个' * ', 输出它的坐标; 其坐标的列用字母表示, 行用数字表示, 具体看样例解释;
解题思路
签到题不多嗦了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e3 + 10;
typedef pair<int, int> PII;
int n, m;
signed main(){
for(int i = 1; i <= 8; i++){
string s;
cin >> s;
for(int j = 0; j < 8; j++){
if(s[j] == '*'){
printf("%c%d", 'a' + j, 8 - i + 1);
return 0;
}
}
}
return 0;
}
C - Gap Existence
难度: ⭐⭐
题目大意
给定n个数和一个X, 问这n个数中是否存在两个数Ai和Aj, 使得Ai - Aj = X; 其中i和j可能相等;
解题思路
先记录一下这n个数都有谁, 然后遍历这n个数作为Ai, 再根据X得到对应的Aj, 看看这n个数中是否存在即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m;
int f[N];
map<int, int> mp;
signed main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> f[i];
mp[f[i]]++;
}
for(int i = 1; i <= n; i++){
int x = m + f[i];
if(mp[x]){
cout << "Yes";
return 0;
}
}
cout << "No";
return 0;
}
D - M<=ab
难度: ⭐⭐⭐
题目大意
给定N和M, 要求找到一个数Q, Q是a和b的乘积; a和b是1~N中的两个数(a和b可能相同); 而且Q要求大于等于M; 请问Q最小的值是多少, 如果不存在则输出-1;
解题思路
因为N和M的数据范围很大, 所有考虑二分来找; 我们设x = sqrt(M)为界限, 如果a和b都大于x, 那么得到的Q一定是满足条件的, 但不一定是最小的; 所以我们考虑让a <= x, b >= x; 可以遍历a, 然后用二分来求最小满足条件的b; 但是如果这样没找到的话就只好让a和b都大于x了; 当然a和b的前提都是小于等于N;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m, minn = 1e18 + 10;
signed main(){
cin >> n >> m;
int i;
for(i = 1; i * i <= m; i++){
if(i > n) break;
int l = m / i , r = n;
while(l < r){
int mid = l + r >> 1;
int idx = i * mid;
if(idx >= m) r = mid;
else l = mid + 1;
}
int res = i * l;
if(res >= m && l <= n){
minn = min(res, minn);
}
}
if(minn == 1e18 + 10) {
if(i <= n) {
int res = i * i;
cout <<res;
}
else cout << -1;
}
else cout << minn;
return 0;
}
E - Transition Game
难度: ⭐⭐⭐
题目大意
给定n个数Ai; 小莫和安姐要进行n回合游戏; 第i回合安姐随机说一个数k, 小莫则从1~n中也挑选一个数s, 并把s写到黑板上, 然后把以下操作重复k次: 如果此时黑板上的数为x, 那么把x替换为Ax;(所有A的大小都是1 ~ n) 如果重复k次后黑板上的数是i, 那么本回合小莫赢, 否则安姐赢; 问小莫可以赢几次;
解题思路
因为k是可以无限大的, 所以如果小莫想要保证第i回合可以赢的话就得让i出现在一个环中, 无论k有多大, 我们只要根据k和环的大小来确定好起点, 那么就可以让k次后恰好轮到i这个数; 因此我们可以用拓扑排序来找出所有不在环中的数x; 第x回合是一定赢不了, 因为k无限大; 反之则一定赢;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m;
int f[N], d[N];
int bfs(){
queue<int> q;
for(int i = 1; i <= n; i++){
if(!d[i]) q.push(i);
}
int res = 0;
while(q.size()){
int t = q.front();
q.pop();
res++;
d[f[t]]--;
if(!d[f[t]]){
q.push(f[t]);
}
}
return n - res;
}
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> f[i];
d[f[i]]++;
}
cout << bfs();
return 0;
}
F - Simultaneous Swap
难度: ⭐⭐⭐⭐
题目大意
给定两个长度为n的数组A和B; 我们每次可以选择一个三元组(i, j, k), 然后让Ai和Aj互换, 让Bi和Bk互换; 请问最后是否可以让数组A和B相同;
解题思路
如果同时改变两个数组那么是很难去讨论的, 所以要考虑看能不能在让数组A不变的情况下改变B; 这样的话可以进行两次操作: 第一次: (Ai, Aj, Ak) -> (Ak, Aj, Ai), (Bi, Bj, Bk) -> (Bj, Bi, Bk); 第二次: (Ak, Aj, Ai) -> (Ai, Aj, Ak), (Bj, Bi, Bk) -> (Bj, Bk, Bi); 这样我们就在数组A保持不变的同时把 (Bi, Bj, Bk)变成了(Bj, Bk, Bi);使得Bi从最前面变到了最后面, 这样带来的结果是如果B数组中没有重复元素的话, 这就让B数组的逆序对+2或者-2; 如果存在重复元素则是逆序对+1或者-1; 这样我们就可以跟据数组A和B中逆序对的数量来判断结果; 因为如果B中没有重复元素, 那么无论+2还是-2, 逆序对数量的奇偶性不会改变, 只要A和B的逆序对数量的奇偶性相同就可以转换; 如果有重复元素那么无论奇偶都可以转换; 当然上面的前提都是数组A和B在排序后是相同的;
代码中是用树状数组来求逆序对, 要把归并排序简洁很多;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m;
int a[N], b[N], t1[N], t2[N], cb[N];
int lowbit(int x){
return x&-x;
}
void add(int x, int t[]){
for(int i = x; i <= n; i += lowbit(i)){
t[i]++;
}
}
int sum(int x, int t[]){
int sum = 0;
for(int i = x; i > 0; i -= lowbit(i)){
sum += t[i];
}
return sum;
}
signed main(){
cin >> n;
bool fb = false;
int x = 0, y = 0;
for(int i = 1; i <= n; i++) {
cin >> a[i];
add(a[i], t1);
x += sum(a[i] - 1, t1);
}
for(int i = 1; i <= n; i++) {
cin >> b[i];
if(cb[b[i]]) fb = true;
cb[b[i]]++;
add(b[i], t2);
y += sum(b[i] - 1, t2);
}
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + n);
for(int i = 1; i <= n; i++){
if(a[i] != b[i]){
cout << "No";
return 0;
}
}
if(fb){
cout << "Yes";
return 0;
}
if(x % 2 != y % 2){
cout << "No";
}
else cout << "Yes";
return 0;
}