Codeforces Global Round 1 晕阙记
我做这场比赛的时候晕得要死。做这三道题做太久了，rating涨不起来啊！
A
如果愿意的话你可以看做是膜2意义下的运算，写快速幂等各种膜运算。只不过对手速有考验。
B
我题意差点理解不了了。这里讲一下题意：
给你\(m\)条棍子，编号从\(1\)到\(m\)，有\(n\)个位置的棍子断了。你有无限长的修改带，求你用\(k\)次机会修补棍子，所用修改带的最小长度。允许修补到没断的棍子，允许修改区间重叠。
比赛的时候硬死想不出来，其实挺sb的：
我们贪心地覆盖前\(n-k\)短的区间，剩下的区间直接一个点覆盖即可。
没错，就这么sb且贪心。
我是想不出来。
C
题意当然是看不懂啦！我们打表看看有没有规律。
打表出来的规律就是：如果数字满足\(2^k-1\)，那答案是个奇怪的没有规律的答案，否则答案是比它大的第一个\(2^k-1\)。
这里就有两种做法：
- 脑子不会转弯的做法：可以发现：答案都是当\(b\)取其中的某个因数时得到。所以我们碰到这些\(2^k-1\)的时候，分解因数，\(O(\log n)\)求解。
- 比较聪明的人才会的解法：可以发现：这些特殊的数字没多少个啊！我们直接打表不就可以了吗？？！！
/************************************************************************* @Author: Garen @Created Time : Thu 07 Feb 2019 09:15:33 PM CST @File Name: A.cpp @Description: ************************************************************************/#includeusing std::cin;using std::cout;using std::endl;#define ll long longconst ll INF = 0x3f3f3f3f3f3f3f3f;ll gcd(ll x, ll y) { return y == 0 ? x : gcd(y, x % y);}ll f(ll a) { ll res = -INF, idx = -1; for(ll b = 1; b < a; b++) { ll temp = gcd(a ^ b, a & b); //res = std::max(res, gcd(a ^ b, a & b)); if(temp > res) { res = temp; idx = b; } } cout << idx << endl; return res;}bool check(ll a) { ll i = 1; while(i <= a) { if(i == a) return true; i = (i << 1 | 1); } return false;}void baoli(ll a) { ll bound = sqrt(a); ll ans = -INF; for(ll i = 1; i <= bound; i++) { if(a % i == 0) { if(i != 1) ans = std::max(ans, gcd(a ^ i, a & i)); if(a / i != i) { ll j = a / i; if(j != a) ans = std::max(ans, gcd(a ^ j, a & j)); } } } if(ans == -INF) ans = 1; cout << ans << endl;}int main() { ll q; cin >> q; while(q--) { ll a; cin >> a; if(check(a)) { baoli(a); } else { ll i = 1; while(i <= a) i = (i << 1 | 1); cout << i << endl; } } /* for(ll a = 1; a <= 10000; a++) { cout << "f(" << a << ") = "; if(check(a)) { baoli(a); } else { ll i = 1; while(i <= a) i = (i << 1 | 1); cout << i << endl; } } */ return 0;}
E
这里立一个flag。听说不难的样子。