Educational Codeforces Round 118 (Rated for Div. 2)(A,B,C,D,E)
感觉这场就是菜狗abc拼手速了…
题目链接.
A. Long Comparison
#include<bits/stdc++.h>
#define ll long long
ll mod=998244353;
using namespace std;
int t;
int n;
ll h;
ll a[110];
ll check(ll x)
{
ll ans=x;
for(int i=2;i<=n;i++)
{
if(a[i]-a[i-1]>=x)ans+=x;
else ans+=a[i]-a[i-1];
}
return ans;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>h;
for(int i=1;i<=n;i++)cin>>a[i];
if(n>=h)
{
cout<<"1n";
continue;
}
ll l=2,r=h;
while(l<r)
{
ll mid=l+(r-l)/2;
if(check(mid)>=h)r=mid;
else l=mid+1;
}
cout<<l<<"n";
}
return 0;
}
B.Absent Remainder
#include<bits/stdc++.h>
#define ll long long
ll mod=998244353;
using namespace std;
int t;
int n;
int a[200010];
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
for(int i=n;i>(n+1)/2;i--)
{
cout<<a[i]<<" "<<a[1]<<"n";
}
}
return 0;
}
C. Poisoned Dagger
题意:读了好久才读懂题意。
有
n
n
n个时间点进行攻击,每次攻击持续
k
k
k秒(包括攻击的那一秒,如果时间不到
k
k
k秒就到达下次攻击,那么此次攻击结束进行下次攻击),攻击的每秒可减少
1
1
1点血量,求能打败怪兽(怪兽血量为
h
h
h)所需要的最小的
k
k
k。
思路:二分答案。
#include<bits/stdc++.h>
#define ll long long
ll mod=998244353;
using namespace std;
int t;
int n;
ll h;
ll a[110];
ll check(ll x)
{
ll ans=x;
for(int i=2;i<=n;i++)
{
if(a[i]-a[i-1]>=x)ans+=x;
else ans+=a[i]-a[i-1];
}
return ans;
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>h;
for(int i=1;i<=n;i++)cin>>a[i];
if(n>=h)
{
cout<<"1n";
continue;
}
ll l=2,r=h;
while(l<r)
{
ll mid=l+(r-l)/2;
if(check(mid)>=h)r=mid;
else l=mid+1;
}
cout<<l<<"n";
}
return 0;
}
D. MEX Sequences
d
p
[
x
]
[
0
]
dp[x][0]
dp[x][0]表示序列没有比x更大的情况
d
p
[
x
]
[
1
]
dp[x][1]
dp[x][1]表示序列存在比x更大的情况
#include<bits/stdc++.h>
#define ll long long
ll mod=998244353;
using namespace std;
int t,n;
ll dp[500010][2];
int main()
{
cin>>t;
while(t--)
{
cin>>n;
dp[1][0]=1;
for(int i=0;i<n;i++)
{
int x;cin>>x;x++;
dp[x+1][0]=dp[x+1][0]*2%mod;
dp[x+1][1]=dp[x+1][1]*2%mod;
dp[x+1][0]=(dp[x+1][0]+dp[x][0])%mod;
dp[x-1][1]=dp[x-1][1]*2%mod;
dp[x-1][1]=(dp[x-1][1]+dp[x-1][0])%mod;
}
ll ans=-1;
for(int i=1;i<=n+1;i++)
{
ans=(ans+dp[i][0]+dp[i][1])%mod;
dp[i][0]=dp[i][1]=0;
}
cout<<ans<<"n";
}
return 0;
}
E. Crazy Robot
思路:从L开始bfs判断每个位置是否可以为+
#include<bits/stdc++.h>
#define ll long long
ll mod=998244353;
using namespace std;
int t,n,m;
string s[1000010];
void bfs(int x,int y)
{
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
queue<pair<int,int>>q;
q.push({x,y});
while(!q.empty())
{
x=q.front().first;
y=q.front().second;
q.pop();
for(int i=0;i<4;i++)
{
int cx=x+dx[i];
int cy=y+dy[i];
if(cx>=0&&cx<n&&cy>=0&&cy<m&&s[cx][cy]=='.')
{
int k=0;
for(int j=0;j<4;j++)
{
int ccx=cx+dx[j];
int ccy=cy+dy[j];
if(ccx>=0&&ccx<n&&ccy>=0&&ccy<m&&s[ccx][ccy]=='.')k++;
}
if(k<=1)
{
s[cx][cy]='+';
q.push({cx,cy});
}
}
}
}
}
int main()
{
cin>>t;
while(t--)
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>s[i];
for(int i=0;i<n;i++)
{
int f=0;
for(int j=0;j<m;j++)
{
if(s[i][j]=='L')
{
f=1;
bfs(i,j);
break;
}
}
if(f)break;
}
for(int i=0;i<n;i++)cout<<s[i]<<"n";
}
return 0;
}