AtCoder Beginner Contest 296 A-E()-其他

AtCoder Beginner Contest 296 A-E()

AtCoder Beginner Contest 296

A – Alternately

 1 void solve(){
 2     int n=read();
 3     string s;
 4     cin>>s;
 5     int ans=1;
 6     for(int i=0;i<s.size()-1;i++){
 7         if(s[i]==s[i+1])ans=0;
 8     }
 9     puts(ans>0?"Yes":"No");
10 }

B – Chessboard

void solve(){
    int n=8,ansx,ansy;
    for(int i=1;i<=8;i++){
        for(int j=1;j<=8;j++){
            char a;
            cin>>a;
            if(a=='*'){
                ansx=i;
                ansy=j;
            }
        }
    }
    char ans;
    ans=ansy-1+'a';
    cout<<ans<<9-ansx<<endl;
}

C – Gap Existence

#define int long long
map<int,int>mp;
void solve(){
    int n=read(),k=read(),ans=0;
    for(int i=1;i<=n;i++){
        int x=read(); mp[x]++;
        if(mp[x+k]||mp[x-k]){
            ans=1;
        }
       
    }
    puts(ans>0?"Yes":"No");
}

D – M<=ab

比赛的时候一直尝试增大m找符合的因数 然后tle

赛后看了题解才知道 可以遍历1-1e6的因数 找每个因数第一个大于等于m的值 记录最小的就可以得到答案

 1 void solve(){
 2     int n=read(),m=read();
 3     int ans=INF;
 4     for(int i=1;i<=min(n,1000000ll);i++){
 5         int j=m/i;
 6         if(i*j<m){
 7             j++;
 8         }
 9         if(j<=n){
10             ans=min(ans,i*j);
11         }
12     }
13     if(ans==INF){
14         cout<<-1<<"\n";
15     }else cout<<ans<<"\n";
16 }

E – Transition Game

知道是求强连通 但是奈何本人太菜 只能赛后补知识点了/悲

int h[N], e[N], ne[N], idx, a[N];
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, siz[N];
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void tarjan(int u){
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
            }
            else if (in_stk[j])
                low[u] = min(low[u], dfn[j]);
        }
        if (dfn[u] == low[u]){
            ++ scc_cnt;
            int y;
            do {
                y = stk[top -- ];
                in_stk[y] = false;
                id[y] = scc_cnt;
                siz[scc_cnt]++;
            } while (y != u);
        }
    }
void solve(){
    idx = 0;
    memset(h, -1, sizeof h);
    int n=read(),ans=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(i!=a[i]){
            add(i,a[i]);
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i]!=i&&!dfn[i]){
            tarjan(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i]==i||siz[id[i]]>1){
            ans++;
        }
    }
    cout<<ans<<endl;
}

AtCoder Beginner Contest 296

A – Alternately

 1 void solve(){
 2     int n=read();
 3     string s;
 4     cin>>s;
 5     int ans=1;
 6     for(int i=0;i<s.size()-1;i++){
 7         if(s[i]==s[i+1])ans=0;
 8     }
 9     puts(ans>0?"Yes":"No");
10 }

B – Chessboard

void solve(){
    int n=8,ansx,ansy;
    for(int i=1;i<=8;i++){
        for(int j=1;j<=8;j++){
            char a;
            cin>>a;
            if(a=='*'){
                ansx=i;
                ansy=j;
            }
        }
    }
    char ans;
    ans=ansy-1+'a';
    cout<<ans<<9-ansx<<endl;
}

C – Gap Existence

#define int long long
map<int,int>mp;
void solve(){
    int n=read(),k=read(),ans=0;
    for(int i=1;i<=n;i++){
        int x=read(); mp[x]++;
        if(mp[x+k]||mp[x-k]){
            ans=1;
        }
       
    }
    puts(ans>0?"Yes":"No");
}

D – M<=ab

比赛的时候一直尝试增大m找符合的因数 然后tle

赛后看了题解才知道 可以遍历1-1e6的因数 找每个因数第一个大于等于m的值 记录最小的就可以得到答案

 1 void solve(){
 2     int n=read(),m=read();
 3     int ans=INF;
 4     for(int i=1;i<=min(n,1000000ll);i++){
 5         int j=m/i;
 6         if(i*j<m){
 7             j++;
 8         }
 9         if(j<=n){
10             ans=min(ans,i*j);
11         }
12     }
13     if(ans==INF){
14         cout<<-1<<"\n";
15     }else cout<<ans<<"\n";
16 }

E – Transition Game

知道是求强连通 但是奈何本人太菜 只能赛后补知识点了/悲

int h[N], e[N], ne[N], idx, a[N];
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, siz[N];
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void tarjan(int u){
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if (!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
            }
            else if (in_stk[j])
                low[u] = min(low[u], dfn[j]);
        }
        if (dfn[u] == low[u]){
            ++ scc_cnt;
            int y;
            do {
                y = stk[top -- ];
                in_stk[y] = false;
                id[y] = scc_cnt;
                siz[scc_cnt]++;
            } while (y != u);
        }
    }
void solve(){
    idx = 0;
    memset(h, -1, sizeof h);
    int n=read(),ans=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(i!=a[i]){
            add(i,a[i]);
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i]!=i&&!dfn[i]){
            tarjan(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i]==i||siz[id[i]]>1){
            ans++;
        }
    }
    cout<<ans<<endl;
}