Dashboard - Codeforces Round 941 (Div. 2) - Codeforces
A. Card Exchange
既然只看数量,咱也别统计是谁了,就看能不能变了。
首先先明确,如果现在都一样比如n个,可以一直操作直到 k-1。
我们可以先根据数量用map统计,然后放在vector后按数目排序,别管是谁了。
从大到小先一直变,像“招募”一样,每个位置,损失一个,然后全部招募下来,
直到不能招募,把总招募的压缩为k-1即可。
参考代码:
#define ll long long
#define endl "\n"
#define PII pair<int,int>
#define int long longconst int maxn = 1e5 + 5;void solve()
{map<int, int>mm;int n, k;cin >> n >> k;int other = 0;int ret = 0;for (int i = 0; i < n; i++){int tmp;cin >> tmp;mm[tmp]++;if (mm[tmp] == k){mm[tmp] = 0;other += k - 1;}}vector<int>arr;for (auto [a, b] : mm)arr.emplace_back(b);sort(arr.begin(), arr.end(),less<int>());for (int i = 0; i < arr.size(); i++){if (arr[i] + other >= k)other += arr[i] - 1;elseret += arr[i];}if (other == 0)cout << ret << endl;elsecout << ret + k - 1 << endl;
}
B. Rectangle Filling
任意两个同色之间的方块都可以转成这个颜色。
不管中间怎么变,最后肯定要把边上的,死角的给改变。
发现只要四个边上各有一个白色或者黑色即可。
(死角可以算两条边)
一行也无所谓,因为咱们会看到第一列和最后一列滴(赛时还以为得特判TWT)
#define ll long long
#define endl "\n"
#define PII pair<int,int>
#define int long longconst int maxn = 1e3 + 5;char arr[maxn][maxn];
int n, m;
bool check(char aim)
{for (int i = 1; i <= m; i++){if (arr[1][i] == aim)break;if (i == m)return false;}for (int i = 1; i <= m; i++){if (arr[n][i] == aim)break;if (i == m)return false;}for (int i = 1; i <= n; i++){if (arr[i][1] == aim)break;if (i == n)return false;}for (int i = 1; i <= n; i++){if (arr[i][m] == aim)break;if (i == n)return false;}return true;
}
void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> arr[i][j];if (check('W')||check('B'))cout << "YES" << endl;elsecout << "NO" << endl;
}
C. Everything Nim
吓得我赶紧复习了NIM,原来是异或。
然而这道题是叫NIM的博弈题。。
每次操作是对所有堆都拿的(那相同大小的堆就没有意义,统计一次即可),最大为当前最小堆的值,最少拿一个。
那我们是不是总共最多拿 最大堆的值 捏
然后就是看连续的情况了,只要不连续,我就可以一直掌握“主动权”。
(我有主动权,我这堆拿的只剩一个,你不得不只拿一个,下一次还是我操作。如果只剩一堆了,我直接拿完就胜了)
然而连续,就意味着可能失去主动权。如果连续是奇数个,就失去了。如果是偶数个,相当于没变。
————
看最开始谁先手,如果开局不是1,那么就是Alice先手,不然就同上,偶数个是Alice。(1 2 4)
^ ^
然后遍历一遍数组即可。
#define ll long long
#define endl "\n"
#define PII pair<int,int>
#define int long longconst int maxn = 2e5 + 5;int arr[maxn];
void solve()
{set<int>ss;int n;cin >> n;for (int i = 0; i < n; i++){int tmp; cin >> tmp;ss.insert(tmp);}if(ss.size() == 1){cout << "Alice" << endl;return;}int tot = 0;int flag = 1;for (auto x : ss)arr[tot++] = x;if(arr[0] == 1)for (int i = 0; i < tot; i++){if (arr[i] != i + 1){if (i % 2 == 1)flag = 0;break;}if (i == tot - 1){if (i % 2 == 0)cout << "Alice" << endl;elsecout << "Bob" << endl;return;}}if(flag == 0)cout << "Bob" << endl;elsecout << "Alice" << endl;
}