Educational Codeforces Round 118 (Rated for Div. 2)（A,B,C,D,E）

• A. Long Comparison
• B.Absent Remainder
• C. Poisoned Dagger
• D. MEX Sequences
• E. Crazy Robot

#include
#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=h)r=mid;
           else l=mid+1;
       }
       cout< 
B.Absent Remainder 
#include
#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< 
C. Poisoned Dagger 
题意：读了好久才读懂题意。
 有
    
     
      
       
        n
       
      
      
       n
      
     
    n个时间点进行攻击，每次攻击持续
    
     
      
       
        k
       
      
      
       k
      
     
    k秒（包括攻击的那一秒，如果时间不到
    
     
      
       
        k
       
      
      
       k
      
     
    k秒就到达下次攻击，那么此次攻击结束进行下次攻击），攻击的每秒可减少
    
     
      
       
        1
       
      
      
       1
      
     
    1点血量，求能打败怪兽（怪兽血量为
    
     
      
       
        h
       
      
      
       h
      
     
    h）所需要的最小的
    
     
      
       
        k
       
      
      
       k
      
     
    k。
 思路：二分答案。
 
#include
#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=h)r=mid;
           else l=mid+1;
       }
       cout< 
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
#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>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< 
E. Crazy Robot 
思路：从L开始bfs判断每个位置是否可以为+
 
#include
#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>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=0&&cy=0&&ccx=0&&ccy>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=0;i>s[i];
        for(int i=0;i