题意
给一个长度为n的字符串和k次操作，每次操作可以将原字符串 s的倒置 rev(s) 加到s后面或者s前面，
问在k次操作过后能得到几种不同的字符串
思路
经过一次操作后，必然成为回文串。对回文串进行操作就不会生成新的种类了。
只需要判断最开始的是不是回文就行了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
string a,b;
int n,k;
int main(){
int t;
cin>>t;
while(t--){
scanf("%d%d",&n,&k);
cin>>a;
if(k==0){
printf("1\n");
continue;
}
int flg=1;
for(int i=0;i<n;i++){
if(a[i]!=a[n-i-1]){
flg=0;
break;
}
}
if(flg){
printf("1\n");
}else{
printf("2\n");
}
}
return 0;
}
|
题意
给定长度为n的数组d和初始的数字x和最后得到的数字y，Alice拿着数字x而Bob拿着数字x + 3，他们会按照数组下标从小到大的顺序给x变化，每次可以选择 x=x+d[i] 或者 x=x xor d[i]
给出最后得到的数字y，问是由哪个人的最初数字得到的
保证Alice和Bob有且仅有一个人可以得到最后的y。
思路
加上或者异或上一个奇数，改变奇偶性质。
加上或者异或上一个偶数，不改变奇偶性质。
Alice的 X 和 Bob 的 X+3 奇偶性不同
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
long long aa;
long long x,y,n;
int main(){
int t;
cin>>t;
while(t--){
scanf("%lld%lld%lld",&n,&x,&y);
int cg=0;
for(int i=0;i<n;i++){
scanf("%lld",&aa);
if(aa%2){
cg++;
}
}
if((x+cg)%2==y%2){
printf("Alice\n");
}else{
printf("Bob\n");
}
}
return 0;
}
|
题意
给定一个大小为 $n∗k$的二维数组a的全排列（数组元素从1到n），一共n行，每行k个，问是否存在这么一个排列，对于每行来说，设为 i 行,不存在任何一组 $[l,r]$, 使得 $(a[i][l]+a[i][l+1]+…+a[i][r])/(r−l+1)$为小数，输出这个排列
思路
k==1，显然存在
k>=2时，每行任意相邻两个元素必须同奇偶，因此每行所有元素同奇偶
k>=2时，n必须为偶数，否则必然存在一行，不同奇偶
注意到只要每行满足等差数列，且奇偶一致，就满足整除的要求，所以直接构造即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>
using namespace std;
typedef pair<int,int> PII;
const int N=1010;
int main(){
int t,n,k;
cin>>t;
while(t--){
scanf("%d%d",&n,&k);
if(k==1){
printf("YES\n");
for(int i=1;i<=n;i++){
printf("%d\n",i);
}
continue;
}else{
if((n*k)%2){
printf("NO\n");
continue;
}else{
if(n%2){
printf("NO\n");
continue;
}else{
printf("YES\n");
for(int j=1,i=1;i<=n*k;j++,i+=2){
printf("%d ",i);
if(j%k==0) printf("\n");
}
for(int j=1,i=2;i<=n*k;j++,i+=2){
printf("%d ",i);
if(j%k==0) printf("\n");
}
continue;
}
}
}
}
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为单调递增的数组，a[1]==0，则
q(1)=a[4]−a[2]
q(2)=a[4]
q(3)=a[4]
q(4)=a[3]
容易得到最大的两个数一定不是0，那么对于任意的4个数，都可以排除掉两个数
当n为偶数的时候，容易得到需要询问 2n−4 次
当n为奇数的时候，容易得到需要询问 2n−2次
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
using namespace std;
int get(const vector <int>& x) {
cout << "? " << x[0] + 1 << " " << x[1] + 1 << " " << x[2] + 1 << endl;
int ans;
cin >> ans;
return ans;
}
signed main() {
ios_base::sync_with_stdio();
cin.tie(nullptr);
int t;
cin >> t;
while(t --> 0) {
int n;
cin >> n;
pair <int, int> possible = {0, 1};
for (int i = 2; i < n - 1; i += 2) {
vector <pair <int, int>> ch(4);
vector <int> now = {possible.first, possible.second, i, i + 1};
for (int j = 0; j < 4; j++) {
vector <int> x = now;
x.erase(x.begin() + j);
ch[j] = {get(x), now[j]};
}
sort(all(ch));
possible = {ch[0].second, ch[1].second};
}
if (n % 2 == 1) {
int other = 0;
while (possible.first == other || possible.second == other) {
other++;
}
vector <pair <int, int>> ch(4);
vector <int> now = {possible.first, possible.second, n - 1, other};
for (int j = 0; j < 4; j++) {
vector <int> x = now;
x.erase(x.begin() + j);
ch[j] = {get(x), now[j]};
}
sort(all(ch));
possible = {ch[0].second, ch[1].second};
}
cout << "! " << possible.first + 1 << " " << possible.second + 1 << endl;
}
return 0;
}
|
题意
给定m个一维数组，每个数组长度随机
将所有元素分到两个集合A、B中去，判断是否存在一个方案使得：
1、对于每个一维数组，分到A的元素个数和分到B的元素个数相等
2、集合A与集合B相同
思路
首先所有的数字必须出现偶数次
构造一个二分图$$：
$V_1$ : m个数组 $V_2$ : 所有出现的数字$n_i$
如果数字 $x$ 出现到了第 $i$ 个数组中，就连一条边。
问题转换为求该二部图的欧拉通路
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <bits/stdc++.h>
#define len(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define endl "\n"
using namespace std;
const int N = 4e5 + 100, H = 2e5 + 50;
vector <pair <int, int>> g[N];
string ans[N];
int pos[N];
void dfs(int v) {
if (pos[v] == 0) {
ans[v] = string(len(g[v]), 'L');
}
while (pos[v] < len(g[v])) {
auto [i, ind] = g[v][pos[v]];
if (i == -1) {
pos[v]++;
continue;
}
g[i][ind].first = -1, g[v][pos[v]].first = -1;
if (v < H) {
ans[v][pos[v]] = 'R';
}
pos[v]++;
dfs(i);
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
cin >> m;
map <int, int> ind, cnt;
int fre_ind = 0;
vector <vector <int>> nums(m);
for (int i = 0; i < m; i++) {
int n;
cin >> n;
for (int _ = 0; _ < n; _++) {
int x;
cin >> x;
if (!ind.count(x)) {
ind[x] = fre_ind++;
}
x = ind[x];
cnt[x]++;
nums[i].push_back(x);
g[i].emplace_back(x + H, len(g[x + H]));
g[x + H].emplace_back(i, len(g[i]) - 1);
}
}
for (auto [num, cn] : cnt) {
if (cn % 2 == 1) {
cout << "NO" << endl;
return 0;
}
}
for (int i = 0; i < N; i++) {
dfs(i);
}
cout << "YES" << endl;
for (int i = 0; i < m; i++) {
cout << ans[i] << endl;
}
return 0;
}
|
