Codeforces Round #770 (Div. 2)
题意:给一个长度为n的字符串和k次操作,每次操作可以将原字符串 $s$ 的倒置 $rev(s)$ 加到s后面或者s前面,也就是将s变成s + rev(s)或者rev(s) + s
问在k次操作过后能得到几种不同的字符串
解法:在一次操作后就必定变成回文串了,之后的操作不会增加更多种类的了,直接判断即可
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n, k; cin >> n >> k;
string s; cin >> s;
bool is = true;
for (int i = 0; i < n; i ++ ) if (s[i] != s[n - i - 1]) is = false;
if (is) {
cout << 1 << endl;
} else {
if (k >= 1) cout << 2 << endl;
else cout << 1 << endl;
}
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
题意:给定长度为n的数组d和初始的数字x和最后得到的数字y,Alice拿着数字x而Bob拿着数字x + 3,他们会按照数组下标从小到大的顺序给x变化,每次可以选择 $x = x + d[i]$ 或者 $x = x \,xor\, d[i]$
给出最后得到的数字y,问是由哪个人的最初数字得到的
解法:思维,奇偶判断
我们容易得到,加上一个数和对一个数异或的奇偶性是相同的,而x和x + 3的奇偶性不同,所以我们可以根据这个判断即可
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n; cin >> n;
LL x, y; cin >> x >> y;
int cnt = 0;
for (int i = 1; i <= n; i ++ ) {
LL tmp; cin >> tmp;
if (tmp & 1) cnt ++;
}
if (x % 2 == 0) {
if (y & 1) {
if (cnt & 1) cout << "Alice\n";
else cout << "Bob\n";
} else {
if (cnt & 1) cout << "Bob\n";
else cout << "Alice\n";
}
} else {
if (y & 1) {
if (cnt & 1) cout << "Bob\n";
else cout << "Alice\n";
} else {
if (cnt & 1) cout << "Alice\n";
else cout << "Bob\n";
}
}
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
题意:给定一个大小为 $n * k$ 的二维数组a的全排列,一共n行,每行k个,问是否存在这么一个排列,对于每行来说,设为 $i$ 行,不存在任何一组 $[l, r]$ 使得 $(a[i][l] + a[i][l + 1]+…+a[i][r]) / (r - l + 1)$ 为小数,输出这个排列
解法:思维,排列
注意到每行一定要排成一个等差数列,且一定要奇偶一致,否则相邻的数的平均数会为小数,直接输出即可,注意特判 k = 1
#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n, k; cin >> n >> k;
if (k == 1) {
cout << "YES\n";
for (int i = 1; i <= n; i ++ ) cout << i << endl;
return ;
}
if (n * k % 2 != 0) {cout << "NO\n"; return ;}
if (n * k / 2 % k != 0) {cout << "NO\n"; return ;}
cout << "YES\n";
int cnt = 1;
for (int i = 1; i <= n / 2; i ++ ) {
for (int j = 1; j <= k; j ++, cnt += 2) cout << cnt << ' ';
cout << endl;
}
cnt = 2;
for (int i = 1; i <= n / 2; i ++ ) {
for (int j = 1; j <= k; j ++, cnt += 2) cout << cnt << ' ';
cout << endl;
}
}
int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
题意:交互题,有一个长度为n的数组a,有且仅有一个0存在于这个数组中,每次可以询问下标为i,j,k的数的 $max(a[i], a[j], a[k]) - min(a[i], a[j], a[k])$,在至多 $2n - 2$ 次的询问中找出最有可能为0的两个下标。
解法:思维
首先我们想一个子问题,如果当前的数为4个,应该怎么做
我们设这个数组为a,且设 $q(i)$ 表示除了对 $a[i]$ 以外的三个数进行询问的结果,设a为单调递增的数组,则
$q(1) = a[4] - a[1]$
$q(2) = a[4]$
$q(3) = a[4]$
$q(4) = a[3]$
容易得到最大的两个数一定不是0,那么对于任意的4个数,都可以排除掉两个数
当n为偶数的时候,容易得到需要询问 $2n - 4$ 次
当n为奇数的时候,容易得到需要询问 $2n - 2$ 次
#include <bits/stdc++.h>
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}
inline void solve() {
int n; cin >> n;
vector<bool> st(n + 1);
int tmp = -1;
auto query = [&](int a, int b, int c, int d) {
vector<PII> v;
cout << "? " << b << ' ' << c << ' ' << d << endl;
int x; cin >> x;
v.emplace_back(x, a);
cout << "? " << a << ' ' << c << ' ' << d << endl;
cin >> x;
v.emplace_back(x, b);
cout << "? " << a << ' ' << b << ' ' << d << endl;
cin >> x;
v.emplace_back(x, c);
cout << "? " << a << ' ' << b << ' ' << c << endl;
cin >> x;
v.emplace_back(x, d);
sort(v.begin(), v.end());
st[v[3].second] = st[v[2].second] = true;
if (n & 1) tmp = v[3].second;
return PII(v[1].second, v[0].second);
};
PII last = query(1, 2, 3, 4);
int idx = 5;
while (idx <= n) {
if (idx + 1 > n) last = query(last.first, last.second, idx, tmp);
else last = query(last.first, last.second, idx, idx + 1);
idx += 2;
}
int r1 = -1, r2 = -1;
for (int i = 1; i <= n; i ++ ) {
if (st[i]) continue;
if (r1 == -1) r1 = i;
else r2 = i;
}
if (r2 == -1) r2 = n;
if (r2 == r1) {
if (r1 != 1) r2 = r1 - 1;
else r2 = 2;
}
cout << "! " << r1 << ' ' << r2 << endl;
}
int main() {
#ifdef DEBUG
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
auto now = clock();
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(2);
int T; cin >> T;
while (T -- )
solve();
#ifdef DEBUG
cout << "============================" << endl;
cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
return 0;
}
没有 E 和 F 吗/kk
QAQ最近太忙了等闲下来一定补