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;
}
- Beginner AtCoder Contest 296 abcbeginner atcoder contest 296 beginner atcoder contest abc contest programming beginner atcoder beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315