Codeforces Round 996 (Div. 2)

A. Two Frogs

只看二蛙之间的格数即可，若为奇数，先手就可以一直贴着后手那只，反之则是后手可以贴着先手走

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=1e5+7, mod=1e9+7;

int n,a,b;

void solve(){
    cin>>n>>a>>b;
    int cha=abs(a-b)-1;
    if(cha&1)cout<<"YES\n";
    else cout<<"NO\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

B. Crafting

只要有两种材料数量小于需求就不行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;

int n,a[N],x;

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        cin>>x;
        a[i]-=x;
    }
    sort(a+1,a+1+n);
    if(a[1]+a[2]<0)cout<<"No\n";
    else cout<<"Yes\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

C. The Trail

行列和都相等，即

$$nx=mx$$

所以 x 只能为 0，那么只需要根据移动来确定已经离开的行或列即可。

若当前步为 D，那么上一行是已经确定的了，可以算一整行其余和，得到上一个位置的值。

反之，可以计算一整列的和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
#define int long long
const int N=1e3+7, mod=1e9+7;

int mp[N][N];

void solve(){
    int n,m;
    cin>>n>>m;
    string s;
    cin>>s;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cin>>mp[i][j];
    }
    int x=1,y=1;
    for(int i=0;i<=s.size();i++){
        ll sum=0;
        if(s[i]=='D'||x==n&&y==m){
            for(int j=1;j<=m;j++)sum+=mp[x][j];
            mp[x][y]=-sum;
            x++;
        }
        else{
            for(int j=1;j<=n;j++)sum+=mp[j][y];
            mp[x][y]=-sum;
            y++;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)cout<<mp[i][j]<<" ";
        cout<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

D. Scarecrow

第一步操作一定是最左侧的移动到 0，乌鸦移动到 $a_1$ 上。

接着贪心操作：

首先当前位置一定是在 $a_i + k$ 上的，这样一定最优

如果 $a_{i+1} - a_i < k$，那么说明 $a_{i+1}$ 还在当前位置左侧，如果 t 足够 $a_{i+1}$ 移动到当前位置，就移动过来，不用继续花费代价，反之，将其移动到最大能移动到的位置。
如果 $a_{i+1} - a_i >= k$，即 $a_{i+1}$ 在当前位置右侧，如果 t 足够其移动回来，则不花费代价，反之，要考虑同时移动左侧和右侧需要增加的代价，二者一个向右一个向左，贴近当前位置。

最后判断是否达到尽头，没有则移动最后一个稻草人。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


#include <bits/stdc++.h>
using namespace std;
#define ls now<<1
#define rs now<<1|1
#define endl "\n"
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int N=2e5+7, mod=1e9+7;

int n,k,l;
int a[N];

void solve(){
    cin>>n>>k>>l;
    k*=2,l*=2;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]*=2;
    }
    int t=a[1];
    a[1]=0;
    for(int i=1;i<n;i++){
        if(a[i+1]-a[i]<k){
            if(a[i+1]+t>=a[i]+k)a[i+1]=a[i]+k;
            else a[i+1]+=t;
        }
        else{
            if(a[i+1]-t<=a[i]+k)a[i+1]=a[i]+k;
            else {
                int dt=((a[i+1]-t)-(a[i]+k))/2;
                t+=dt;
                a[i+1]=a[i]+dt+k;
            }
        }
    }
    if(a[n]+k<l)t+=l-(a[n]+k);
    cout<<t<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}