Educational Codeforces Round 118 (Rated for Div. 2)

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

先将两个数的数字部分补充成相同的长度，在比较两个数的长度，如果长度相同，就比较数字部分的大小。

#include
using namespace std; 
typedef long long ll;
int main(){
    int t;
    cin>>t;
    while(t--){
        ll p1,p2;
        string x1,x2;
        cin>>x1>>p1>>x2>>p2;
        while(x1.size()!=x2.size()){
            if(x1.size()x2.size()){
                x2+='0';
                p2--;
            }
            
        }
        if(p1p2){
            cout<<">"<x2){
                cout<<">"< 
C. Poisoned Dagger 
二分法
 
#include
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll w[110];
ll n,h;
int check( ll mid){
    ll res=h;
    for( int i=1;i<=n-1;i++){
        res-=min(mid,w[i+1]-w[i]);
        if(res<=0) return 1;
    }
    res-=mid;
    if(res<=0) return 1;
    return 0;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>h;
        for( int i=1;i<=n;i++){
            cin>>w[i];
        }
        ll l=0,r=1e18+1;
        while(l=1){
                r=mid;
            }
            else l=mid+1;
        }
        cout< 
D. MEX Sequences 
状态dp
 一共有三种情况，可以互相转移。
 分别是：
 对于数字i，比i小的所有数字都出现过
 对于数字i，除了i-1没有出现过，其他都出现过
 对于数字i，比i小的数字都出现过，且i+2也出现过
 
注意讨论端点问题
 
#include
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int N=500100;
ll w[N],dp[N][3];//0表示连续，1表示后一个点有空缺，2表示前一个点有空缺
ll cnt[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for( int i=1;i<=n;i++){
            cin>>w[i];
        }
        for( int i=0;i<=n+3;i++){
            dp[i][0]=dp[i][1]=dp[i][2]=0;
        }
        // dp[0][0]=1;
        for( int i=1;i<=n;i++){
            int x=w[i];
            dp[x][0]+=dp[x][0];
            if(x!=0) dp[x][0]+=dp[x-1][0];
            else dp[x][0]++;

            dp[x][1]+=dp[x][1];
            dp[x][1]+=dp[x+2][2];

            dp[x][2]+=dp[x][2];
            if(x!=0&&x!=1){
                dp[x][2]+=dp[x-2][0];
                dp[x][2]+=dp[x-2][1];
            }
            else if(x==1) dp[x][2]++;
            dp[x][0]%=mod;
            dp[x][1]%=mod;
            dp[x][2]%=mod;
        }
        ll ans=0;
        for( int i=0;i<=n;i++){
            ans+=dp[i][0]+dp[i][1]+dp[i][2];
            ans%=mod;
        }
        cout< 
E. Crazy Robot 
直接bfs，注意输入输出时间
 从L向四周dfs，对于每个位置，记录周围可以走的方向的个数，如果有多个方向可以走，那么就不能回到实验室，如果只有一个方向可以走，那么可以回到实验室。
 
#include  
using namespace std;

typedef long long ll;
const int N=1000100;
string s[N];
int mov[4][2]={0,1,0,-1,1,0,-1,0};
int n,m;
int check(pairx){
    if(x.first<0||x.first>=n||x.second<0||x.second>=m) return 0;
    if(s[x.first][x.second]=='#'||s[x.first][x.second]=='+'||s[x.first][x.second]=='L') return 0;
    
    return 1;
}
void bfs( int x,int y){
    queue >q;
    q.push(make_pair(x,y));
    for( int i=0;i<4;i++){
        pairtemp=q.front();
        temp.first+=mov[i][0];
        temp.second+=mov[i][1];
        if(check(temp)) q.push(temp);
    }
    while(!q.empty()){
        pairnow;
        now=q.front();
        q.pop();
        if(check(now)==0) continue;
        // s[now.first][now.second]='#';
        int cnt=0;
        for( int i=0;i<4;i++){
            pairtemp=now;
            temp.first+=mov[i][0];
            temp.second+=mov[i][1];
            if(check(temp)) cnt++;
        }
        if(cnt>1) continue;
        else s[now.first][now.second]='+';
        for( int i=0;i<4;i++){
            pair temp=now;
            temp.first+=mov[i][0];
            temp.second+=mov[i][1];
            if(check(temp)) q.push(temp);
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>m;
        int x,y;
        for( int i=0;i>s[i];
            for( int j=0;j