C. Pekora and Trampoline（暴力）
给定数列，有一个兔子，从数列的任意一处开始跳，直到跳至数组边界。
假设当前兔子在第i个位置，那么跳的下一个位置就是i+a[i]。
跳完之后当前位置a[i]--(a[i]==1时不变)。
问跳跃的最小次数。
考虑第i个位置的情况。
前面i-1个数对第i个数及其后面的数的贡献可以用一个变量保存下来。即，前面 i-1 个数跳到 i 及其后的数的次数有几次。
若 a[i] 大于前面的数的贡献，则说明它不会增加跳跃次数，反之增加的次数为a[i] - cnt - 1。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
ll read(){
char ch=getchar();
ll x=0,f=1;
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch^48),ch=getchar();
return x*f;
}
ll maxx(ll a, ll b)
{
return a > b ? a : b;
}
void solve(){
ll n = read(), a[maxn], b[maxn], ans = 0;
for (int i = 1; i <= n; i++) a[i] = read();
ll pre = 0;
for (int i = 1; i <= n; i++)
{
ll cnt = pre;
for (int j = 1; j < i - 1; j++)
{
if (a[j] + j >= i) cnt++;
}
ans += maxx(a[i] - cnt - 1, 0ll);
if (cnt + 1 > a[i]) pre = cnt + 1 - a[i];
else pre = 0;
}
cout << ans << endl;
}
int main(){
int t;cin>>t;
while(t--){
solve();
}
}
自定义函数maxx小卡常，影响不大。
D. Zookeeper and The Infinite Zoo
给定两个整数u，v，询问这两个整数之间是否满足以下运算：
如果能够找到一个数v‘，使得 u & v’ == v’， 则u 与 u + v’之间存在着一条单向路。
询问u v之间是否存在着一条路径。
问题的核心在于u & v == v这个式子上。 由于是二进制运算，所以将其用二进制表达出来会更好。
对于任意的一个u 1..00.01..00..
若存在u & v == v，则 v 必定满足以下条件：
1.u为0的位置，v必定为0,。
2.u为1的位置，v可以为0，也可以为1。
所以，u 与 v 做 + 运算，1的数量增加，或0的数量增加(当v的第一位数为1时)。
显然，u v之间存在路径 与 v中1的个数大于等于u 为充要条件。最后代码十分简短。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
ll read(){
char ch=getchar();
ll x=0,f=1;
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘) x=x*10+(ch^48),ch=getchar();
return x*f;
}
void solve(){
ll x = read(), y = read(), cnt = 0, flag = (x <= y);
for (int i = 0; i < 30; i++)
{
if ((x >> i) & 1) cnt++;
if ((y >> i) & 1) cnt--;
if (cnt < 0) flag = 0;
}
if (flag) puts("Yes");
else puts("No");
}
int main(){
int t;cin>>t;
while(t--){
solve();
}
}
Codeforces Global Round 13 C-D
原文：https://www.cnblogs.com/clo91eaf/p/14468253.html