目录
题意:
从1,1走到n,m. 每次只能向右/上走奇数个方向. T先走. 如果下一步不能走了(已经在n,m了) 那么当前轮次的人输了. 输出谁会赢.
思路:
看样例直接找到规律
如果n+m是偶数(两个都是奇数或者都是偶数), 后手赢了.
本来写了一堆, 但发现写的太绕了...找个小规模的4x4 or 3x3的推一下就ok了.
code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
ll a, b;
cin >> a >> b;
if ((a + b) % 2 == 0)
cout << "Tonya\n";
else
cout << "Burenka\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}B. Mathematical Circus
题意:
问你对于每个给出的n, k是否存在n/2对a,b满足
存在输出yes和n/2组的a,b对, 否则no
思路:
开始读错题了, 以为不到n/2对的n也算是yes有多少输出多少. 被这个坑WA了2发.
观察下式子, 显然只要式子的乘号左右两边有一个能整除4即可.
1)我们发现k %= 4 or k = 0是一直不合法的.
2)k % 2 == 1的话证明k是奇数, 那么(奇数 + 奇数) * 偶数数, 乘号左面一定是偶数, 那么两边都一定是2的倍数, 故可以提出4.满足
3)构造乘号左/右整除4的情况. easy. but注意构造a+k整除4时候用i=4 - k % 4为起点, i每次加4来构造比较方便
code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, k;
cin >> n >> k;
if (k % 2 == 1) {
cout << "YES\n";
for (int i = 1; i <= n - 1; i += 2) {
cout << i << " " << i + 1 << "\n";
}
} else if (k % 2 == 0) {
if (k % 4 == 0 || k == 0) {
cout << "NO\n";
return;
}
cout << "YES\n";
for (int i = 4; i <= n; i += 4) {
if (i % 4 == 0) {
cout << i - 1 << " " << i<< "\n";
}
}
for (int i = 4 - k % 4; i <= n; i += 4) {
cout << i << " " << i - 1 << "\n";
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
C. Fighting Tournament
题意:
给你一个序列, 每次把前两个进行比较(
)小的放到队伍的最后面, 大的放到队伍的最前面, 大的击败数加一. 可以进行无限次. 给你q次询问, 每次问你第p个, 在进行了k次循环后所击败的人的数量.
思路:
卡的一点在:可能第k次循环之前已经开始击败了别人了或者第k次循环还没开始击败别人, 不能用k作为查询的目标点.
冗长版本解释:
? ? 首先, 观察我们可以发现一件事情: 当最大的循环到第一位时, 之后的击败全部由最大的贡献!?对于每个人他的击败都一定是连续的!因为他被人打败后就一定不能再次成为队首去打败别人了
? ? 其次, 想到对于每个的每次击败, 我们都记录这次击败的所处循环次数是哪次. 查询的时候再判断目标循环次数k和
记录的产生击败的回合之间的关系得到答案. 换句话来说就是记录每个
在哪些回合(循环)产生击败! 第二句结合代码比较容易明白.
? ? 最后, 我们发现对于k大于进行的轮数n-1时, 如果当前询问的p是最大值时, 存在以下: 最大值成为队首后一直打败别人的轮数 = 总轮数?-?成为队首所需轮数,?即?k - (n - 1)次. 把这个加到ans中即可(因为ans只记录n-1次循环进行后的结果)
简化版:
? ? 1)对n-1次循环(1~n-1), 对于每个循环的获胜者, 将这个循环的编号加到这个获胜者中.
? ? 2)对于每次询问, 找到获胜的场次中第一个大于等于k的下标, 从0到这个下标-1即为1~k次循环后
的答案(但
为最大值时不包括1~n-1次之后到k的), 即直接用upperbound的到的值表示.
? ? 3)对上述括号情况进行增添!
一点useful的事情?upper_bound在找不到指定元素大的时候会返回最后一个!
?
updata:简化了冗长的解释, 更新了输出, 更新了对没表述清楚的upperbound的解释(在代码中)
code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<vector<int>> f(n);//记录每个人的每次击败
int idx = 0;//记录当前最大的值是谁
for (int i = 1; i < n; i++) {
if (a[idx] < a[i]) {
idx = i;
}
f[idx].push_back(i);
}
while (q--) {
int p, k;
cin >> p >> k;
p --; //因为上面我a数组从0开始的下标
int ans = upper_bound(f[p].begin(), f[p].end(), k) - f[p].begin(); //红字部分
/*
新增upper_bound函数解释:
这个不是用来求大于等于k的值是谁的, 而是计算出第一个大于k的下标是谁!
即用来计算<=k的一共有多少个->推出k轮能够产生多少个答案.
因此我们 upperbound-f[p].begin(), 即可得到第一个大于k的下标,
因为第一个下标是0, 因此我们得到的下标正好是ans的数量, 不用再去加1!
*/
if (k - n + 1 > 0 && p == idx) { //是最大的那个 并且k要大于n次
ans += k - n + 1;
}
cout << ans << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}后记
一些sad and interesting的事情:
昨天赛时我写的思路和这个差不多, 不过实现的又臭又长还有bug, 当时写完居然过了pretest. 屎山如下....
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[200005];
int b[200005];
int beat[200005];
vector<int> H[200005];
void solve() {
int n, q;
int mx = 0, pos = 0, mi = 1e9;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] > mx) {
mx = a[i];
pos = i;
}
mi = min(mi, a[i]);
beat[a[i]] = 0;
H[i].clear();
b[i] = a[i];
}
int round = 0;
map<pair<int,int>, int>f;
map<int, int>now;
for (int i = 2; i <= pos; i++) {
if (a[i] > a[1]) {
a[1] = a[i];
beat[a[i]] ++;
} else {
beat[a[1]] ++;
}
f[{a[1], ++round}] = beat[a[1]];
H[a[1]].push_back(round);
}
while (q--) {
int p, k;
cin >> p >> k;
if (p == 1 && b[1] == mx) {
cout << k << "\n";
continue;
}
vector<int> tmp = H[b[p]];
if (tmp.size() == 0) {
cout<<"0\n";
continue;
}
if (k > tmp[tmp.size()-1]) {
if (b[p] == mx) {
cout << k - round + 1 << "\n";
} else {
cout << beat[b[p]] << "\n";
}
} else if (k == tmp[tmp.size()-1]){
cout << f[{b[p], k}] << "\n";
} else {
int prev = 0;
for (auto x : tmp) {
if (x <= k) {
prev = x;
} else break;
}
cout << f[{b[p], prev}] << "\n";
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}写完我一下子就想出了hack数据如下, 我当时想着T的原因是我当时在每次查询有个for(auto) 显然会t在这里,?但来不及改了想着一定FST了...
1
100000 100000
99999 1 2 3..... 100000
1 1
1 2
...
1 99999
结果居然没有FST!!!!? 震惊!!!!!
今天五点多交了个相同的code, 一看TLE了....估计是author更新了大数据
于是我开始改我的屎山, 改了两个多点, 改到吐WA了无数发如图, 还**T.
我发现可能是我的实现有大问题. 果断学习大佬们的写法, 狠狠A了hhh. 现在还在感叹于大佬们如此nb orz.
ok, 选课开始了, run去选课了owo. (对了, D1, D2今天需要补掉, 别懒.)