Codeforces Round 996 (Div. 2)_ABCD
比赛链接
A. Two Frogs
题目描述
There are lilypads arranged in a row, numbered from
to
from left to right. Alice and Bob are frogs initially positioned on distinct lilypads,
and
, respectively. They take turns jumping, starting with Alice.
During a frog's turn, it can jump either one space to the left or one space to the right, as long as the destination lilypad exists. For example, on Alice's first turn, she can jump to either lilypad
or
, provided these lilypads are within bounds. It is important to note that each frog must jump during its turn and cannot remain on the same lilypad.
However, there are some restrictions:
- The two frogs cannot occupy the same lilypad. This means that Alice cannot jump to a lilypad that Bob is currently occupying, and vice versa.
- If a frog cannot make a valid jump on its turn, it loses the game. As a result, the other frog wins. Determine whether Alice can guarantee a win, assuming that both players play optimally. It can be proven that the game will end after a finite number of moves if both players play optimally.
Each test contains multiple test cases. The first line contains the number of test cases (
). The description of the test cases follows.
The first and only line of each test case contains three integers
,
, and
(
,
,
) — the number of lilypads, and the starting positions of Alice and Bob, respectively.
Note that there are no constraints on the sum of
over all test cases.
题解
假设a和b之间的距离为偶数，则一定先手赢，反则是先手输。如果a和b不在尽头也没有关系，因为不管a和b怎么走，他们之间的距离是加一个偶数的，不会影响结果。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e5+10;
int a[N];
void solve()
{
int n,a,b;
cin>>n>>a>>b;
if((max(a,b)-min(a,b))%2){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) solve();
}
n=int(input())
for _ in range(n):
n,a,b=map(int,input().split())
if (max(a,b)-min(a,b))%2:
print("NO")
else:
print("YES")
B. Crafting
题目描述
There are different types of magical materials, numbered from
to
. Initially, you have
units of material
for each
from
to
. You are allowed to perform the following operation:
- Select a material
(where
). Then, spend
unit of every other material
(in other words,
) to gain
as follows:
, and
for all
. Note that all
must remain non-negative, i.e. you cannot spend resources you do not have.
You are trying to craft an artifact using these materials. To successfully craft the artifact, you must have at least units of material
for each
from
to
. Determine if it is possible to craft the artifact by performing the operation any number of times (including zero).
Each test contains multiple test cases. The first line contains the number of test cases (
). The description of the test cases follows.
The first line of each test case contains three integers
(
,
) — the number of scarecrows, the teleportation distance, and the target position of the crow, respectively.
The second line of each test case contains
integers
(
) — the initial positions of the
scarecrows.
It is guaranteed that the sum of
over all test cases does not exceed
.
题解
会发现如果有俩个都需要增大，那么是不可能完成的，因为一个增加的过程中，另外一个必然会减小。如果只有一个需要增加，那么只需要判断一下其余的差值是否会能满足需要增加的值。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=2e5+10;
int a[N],b[N];
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
int f=0;
int x=0,id=0;
for(int i=1;i<=n;i++){
if(a[i]<b[i]) f++,x=b[i]-a[i],id=i;
}
if(f>=2){
cout<<"NO"<<endl;
return;
}else{
if(n==1){
cout<<"NO"<<endl;
return;
}
for(int i=1;i<=n;i++){
if(id==i) continue;
if(a[i]-b[i]<x){
cout<<"NO"<<endl;
return;
}
}
cout<<"YES"<<endl;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) solve();
}
t=int(input())
for _ in range(t):
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
f=0
x=0
id=0
for i in range(n):
if a[i]<b[i]:
f+=1
x=b[i]-a[i]
id=i
if f>=2:
print("NO")
else:
if n==1:
print("NO")
continue
for i in range(n):
if id==i: continue
if a[i]-b[i]<x:
print("NO")
break
else:
print("YES")
C. The Trail
题目描述
In the wilderness lies a region of mountainous terrain represented as a rectangular grid with rows and
columns. Each cell in the grid is identified by its position
, where
is the row index and
is the column index. The altitude of cell
is denoted by
.
However, this region has been tampered with. A path consisting of
cells, starting from the top-left corner
and ending at the bottom-right corner
, has been cleared. For every cell
along this path, the altitude
has been set to
. The path moves strictly via downward (
) or rightward (
) steps.
To restore the terrain to its original state, it is known that the region possessed a magical property before it was tampered with: all rows and all columns shared the same sum of altitudes. More formally, there exists an integer
such that
for all
, and
for all
.
Your task is to assign new altitudes to the cells on the path such that the above magical property is restored. It can be proven that a solution always exists. If there are multiple solutions that satisfy the property, any one of them may be provided.
Each test contains multiple test cases. The first line contains the number of test cases (
). The description of the test cases follows.
The first line of each test case contains two integers
and
(
) — the number of rows and columns in the grid.
The second line of each test case contains a string
of length
(
or
) — the steps the path makes from
to
. The character
represents a downward step, and
represents a rightward step.
The
-th of the next
lines each contain
integers
(
) — the altitude of each cell in the grid. It is guaranteed that if a cell
lies on the path, then
.
It is guaranteed that the sum of
over all test cases does not exceed
.
题解
假设n和m不相等，行，列的和为S，那么要满足，可以得出
的值为
。n和m相等时也成立。因为只会往下或者往右走，所以可以根据走向确定当前位置的值。如果往下走，当前位置的值就会变为当前行的和的相反数，如果往右走，当前位置的值就会变为当前列的和的相反数。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve()
{
int n,m;
cin>>n>>m;
vector<vector<int>> a(n+10,vector<int>(m+10));
string s;
cin>>s;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
vector<int> r(n+1),l(m+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
r[i]+=a[i][j];
l[j]+=a[i][j];
}
}
int x=1,y=1;
for(int i=0;i<s.size();i++){
if(s[i]=='D'){
a[x][y]=-r[x];
r[x]+=a[x][y];
l[y]+=a[x][y];
x++;
}else{
a[x][y]=-l[y];
r[x]+=a[x][y];
l[y]+=a[x][y];
y++;
}
}
a[x][y]=-r[x];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[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();
}
t=int(input())
for _ in range(t):
n,m=map(int,input().split())
a=[[0]*(m+1) for _ in range(n+1)]
s=input()
for i in range(1,n+1):
a[i][1:m+1]=map(int,input().split())
r=[0]*(n+1)
l=[0]*(m+1)
for i in range(1,n+1):
for j in range(1,m+1):
r[i]+=a[i][j]
l[j]+=a[i][j]
x,y=1,1
for c in s:
if c=='D':
a[x][y]=-r[x]
r[x]+=a[x][y]
l[y]+=a[x][y]
x+=1
else:
a[x][y]=-l[y]
r[x]+=a[x][y]
l[y]+=a[x][y]
y+=1
a[x][y]=-r[x]
for i in range(1,n+1):
print(*a[i][1:m+1])
D. Scarecrow
题目描述
A crow is sitting at position of the number line. There are
scarecrows positioned at integer coordinates
along the number line. These scarecrows have been enchanted, allowing them to move left and right at a speed of
unit per second.
The crow is afraid of scarecrows and wants to stay at least a distance of ahead of the nearest scarecrow positioned at or before it. To do so, the crow uses its teleportation ability as follows:
- Let
be the current position of the crow, and let
be the largest position of a scarecrow such that
. If
, meaning the scarecrow is too close, the crow will instantly teleport to position
.
This teleportation happens instantly and continuously. The crow will keep checking for scarecrows positioned at or to the left of him and teleport whenever one gets too close (which could happen at non-integral times). Note that besides this teleportation ability, the crow will not move on its own.
Your task is to determine the minimum time required to make the crow teleport to a position greater than or equal to , assuming the scarecrows move optimally to allow the crow to reach its goal. For convenience, you are asked to output twice the minimum time needed for the crow to reach the target position
. It can be proven that this value will always be an integer.
Note that the scarecrows can start, stop, or change direction at any time (possibly at non-integral times).
Each test contains multiple test cases. The first line contains the number of test cases (
). The description of the test cases follows.
The first line of each test case contains three integers
(
,
) — the number of scarecrows, the teleportation distance, and the target position of the crow, respectively.
The second line of each test case contains
integers
(
) — the initial positions of the
scarecrows.
It is guaranteed that the sum of
over all test cases does not exceed
.
题解
首先判断第一个位置的稻草人，如果必须需要移动到0，记录当前过去了多长时间和移动后的位置，然后乌鸦当前的位置在0+k，再进行判断后面的每个稻草人，若后续每个稻草人在乌鸦当前位置的前面，当前时间已经过去了ans单位，所以当前稻草人可以往后移动ans个位置，让稻草人尽可能往当前乌鸦的位置接近或重合，若稻草人在乌鸦当前位置的后面，当前时间已经过去了ans单位，所以当前稻草人可以往前移动ans位置，若ans个位置到不了稻草人当前的位置，稻草人移动后的位置和乌鸦当前位置的一半时间去移动前后两个稻草人，使得后一个稻草人可以和乌鸦重合，移动到后一个稻草人+k的位置，一直到最后一个稻草人。若到最后一个稻草人还未到达终点，则需要终点减当前位置个时间单位。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define db double
const int N=2e5+10;
int a[N];
void solve()
{
int n,k,m;
cin>>n>>k>>m;
for (int i=1;i<=n;i++){
cin>>a[i];
}
db now=0;
db ans=0;
ans+=a[1];
now=k;
for (int i=2;i<=n;i++)
{
if(now>=m) break;
if(a[i]>now){
db tp=a[i]-now;
if(ans>=tp){
a[i]=now;
now=a[i]+k;
}else{
a[i]-=ans;
tp=a[i]-now;
ans+=tp/2.0;
a[i]-=tp/2.0;
now+=tp/2.0;
now+=k;
}
}else{
db tp=now-a[i];
if(ans>=tp){
a[i]=now;
now+=k;
}else{
a[i]+=ans;
now=a[i]+k;
}
}
}
if(now<m){
ans-=now;
ans+=m;
}
cout<<(int)(ans*2)<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) solve();
}
t=int(input())
for _ in range(t):
n,k,m=map(int,input().split())
a=[0]*(n+1)
for i in range(1,n+1):
a[i]=int(input())
now=0
ans=0
ans+=a[1]
now=k
for i in range(2,n+1):
if now>=m:
break
if a[i]>now:
tp=a[i]-now
if ans>=tp:
a[i]=now
now=a[i]+k
else:
a[i]-=ans
tp=a[i]-now
ans+=tp/2.0
a[i]-=tp/2.0
now+=tp/2.0
now+=k
else:
tp=now-a[i]
if ans>=tp:
a[i]=now
now+=k
else:
a[i]+=ans
now=a[i]+k
if now<m:
ans-=now
ans+=m
print(int(ans*2))
查看13道真题和解析