纪念这次div2让我上绿名，但还是有点遗憾，差一点就可以过三题超神了
比赛链接cf908div2
A
这题是个骗人题，整个比赛会停下来就是一个人赢够了回合数，那么在谁这停下来就是谁赢了整个比赛，不用管每回合赢得规则。
#include<iostream>
using namespace std;
#include<string>
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
string s;
cin >> s;
int A = 0, B = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == 'A')
{
A++;
}
else
{
B++;
}
}
if (s[s.size() - 1] == 'A')cout << "A" << endl;
else cout << "B" << endl;
}
return 0;
}
B
先从最简单的情况考虑，或者说分析一下给的三个条件必须正好满足两个是什么意思
如果序列为一个数a重复三次，那么要满足任意两个条件，都不可避免的同时满足了三个条件
那么自然想到，要将两个条件分配给两个数，让他们分别去实现其中一个条件，比如，有两个5，两个6，那么就可以给两个5分别赋值为1,2，给两个6分别赋值为1 3
那么，我们可以先明确不满足的情况是这样的：出现次数大于等于2的数字小于两个。
而如果出现次数大于等于2的数字大于两个，我们就可以任意找两个数字，找到他们的两次出现位置，分别赋值为1,2，和1,3，然后其他所有位置都是1，就一定满足。
#include<iostream>
#include<unordered_map>
#include<queue>
using namespace std;
const int maxn = 100020;
#include<vector>
int main()
{
int t;
cin >> t;
while (t--)
{
int a[maxn] = { 0 };
int b[maxn] = { 0 };
int n;
cin >> n;
unordered_map<int, int>mp; //记录每个数出现了多少次
int count_2 = 0; //记录有多少个数出现次数大于等于2
unordered_map<int, int>asdf;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
mp[a[i]]++;
}
for (int i = 1; i <= n; i++)
{
if (mp[a[i]] >= 2&&asdf.count(a[i])==0)
{
count_2++;
}
asdf[a[i]]++;
}
if (count_2 < 2)
{
cout << -1 << endl;
}
else
{
int firstnum = -1, secondnum = -1;
int index = -1;
for (int i = 1; i <= n; i++)
{
if (mp[a[i]] >= 2)
{
firstnum = a[i];
index = i;
break;
}
}
for (int i = index + 1; i <= n; i++)
{
if (mp[a[i]] >= 2&&a[i]!=firstnum)
{
secondnum = a[i];
break;
}
}
int countfirst = 0, countsecond = 0;
for (int i = 1; i <= n; i++)
{
if (a[i] == firstnum)
{
countfirst++;
b[i] = countfirst;
if (countfirst == 2)
{
break;
}
}
}
for (int i = 1; i <= n; i++)
{
if (a[i] == secondnum)
{
countsecond++;
b[i] = countsecond;
if (countsecond == 2)
{
b[i] = 3;
break;
}
}
}
for (int i = 1; i <= n; i++)
{
if (b[i] == 0)
{
b[i] = 1;
}
}
for (int i = 1; i <= n; i++)
{
cout << b[i] << " ";
}
cout << endl;
}
}
return 0;
}
C
这题手动模拟几次可以发现，如果给的那个最终序列最后一个位置是x，那么它的上一个序列其实就是这个序列的后x位移动到序列前面，给定最终序列，那么如此反向操作k次，结果是唯一的。
如果中间发现这个最后一个数x>n，那么就说明不可能。
如果我们想模拟这个反向操作，可以把序列复制很多次，也可以用模运算，具体见代码：
#include<iostream>
using namespace std;
const int maxn = 200200;
#include<unordered_map>
#include<string>
#include<cstring>
long long a[maxn];
int main()
{
int t;
cin >> t;
int tt = t;
while (t--)
{
memset(a, 0, sizeof a);
long long n, k;
cin >> n >> k;
for (int i = 0; i <n; i++)
{
cin >> a[i];
}
int flag = 1;
long long count = 0;
unordered_map<long long, long long >num;
for (long long i = n - 1; count <k;i=((i-a[i])+n)%n) //count<k而不是<=k,因为要求是正好k次
{
if (a[i]>n)
{
flag = 0;
break;
}
count++;
if (num.count(i) != 0) //遇到了重复下标，说明进入一个循环的过程了，就一定可以
{
flag = 1;
break;
}
num[i]++;
}
if (flag == 1)cout << "Yes" << endl;
else if(flag==0)cout << "No" << endl;
}
return 0;
}