概述

切了 ABCE，Room83 第一

还行吧

A - Happy Birthday, Polycarp!

题解

显然这样的数不会很多。

于是可以通过构造法，直接求出 \([1,10^9]\) 内所有符合要求的数。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

int a[]={1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,111,222,333,444,555,666,777,888,999,1111,2222,3333,4444,5555,6666,7777,8888,9999,11111,22222,33333,44444,55555,66666,77777,88888,99999,111111,222222,333333,444444,555555,666666,777777,888888,999999,1111111,2222222,3333333,4444444,5555555,6666666,7777777,8888888,9999999,11111111,22222222,33333333,44444444,55555555,66666666,77777777,88888888,99999999,111111111,222222222,333333333,444444444,555555555,666666666,777777777,888888888,999999999,1000000001};

int T,n;

int main(){
    cin>>T;
    while(T--){
        cin>>n;int ans=0;
        for(int i=1;a[i]<=n;i++) ++ans;
        cout<<ans+1<<endl;
    }
    return 0;
}

B - Make Them Odd

题解

显然每次从最大的数进行处理最划算。

于是用个优先队列存储所有的数，用 map 记录这个数是否还要付出代价即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

const int maxn=2000007;

int T,n;
int a[maxn];
int b[maxn],t[maxn];
int m;
map<int,bool>mp;

#define pii(x,y) make_pair(x,y)
priority_queue < int>q;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);mp.clear();
        int ans=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            q.push(a[i]);
        }
        while(q.size()){
            int x=q.top();//x=-x;
            q.pop();
            if(x&1) continue;
            if(mp[x]) continue;
            ++ans;mp[x]=1;
            q.push(x/2);
        }
        printf("%d\n",ans);
    }
}

C - As Simple as One and Two

题解

这种题目 WA 了一次 pretest ，说明我水平低下。

two 和 one 放在一起是非常美妙的字符串。

如果有子串 twone ，显然删去中间的 o 最优。

再处理 two 和 one ，为了不造成新的这样的串，删掉中间的 w 或 n 。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

const int maxn=150007;

int T,val[maxn];
char s[maxn];

int ans[maxn],cnt;

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",s+1);
        int len=strlen(s+1);cnt=0;
        memset(val,0,sizeof(val));
        for(int i=1;i+4<=len;i++){
            if(s[i]=='t'&&s[i+1]=='w'&&s[i+2]=='o'&&s[i+3]=='n'&&s[i+4]=='e'){
                ans[++cnt]=i+2;
                s[i+2]=' ';
            }
        }
        for(int i=1;i+2<=len;i++){
            if(s[i]=='o'&&s[i+1]=='n'&&s[i+2]=='e'){
                ans[++cnt]=i+1;s[i+1]=' ';
            }
            if(s[i]=='t'&&s[i+1]=='w'&&s[i+2]=='o'){
                ans[++cnt]=i+1;s[i+1]=' ';
            }
        }
        printf("%d\n",cnt);
        for(int i=1;i<=cnt;i++){
            printf("%d ",ans[i]);
        }
        puts("");
    }
}

E - Two Fairs

题解

这种***题花了一个小时还 WA 了一次 pretest，说明我水平低下。

扫一遍，并查集一下就行了。

神仙 zzk 有两次 bfs 的做法？

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

const int maxn=200007;
const int maxm=1000007;

int T;
int n,m,a,b;

#define pii(x,y) make_pair(x,y)

vector <pair<int,int> >e;

int cnt;

int f[maxn];

set<int>A,B;

void clear(void){
    e.clear();
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) f[i]=i;
    A.clear();B.clear();
}

int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}

void merge(int x,int y){
    int xx=find(x),yy=find(y);
    if(xx!=yy) f[xx]=yy;
}

void Init(void){
//  for(int i=1;i<=n;i++){
//      cout<<f[i]<<" ";
//  }
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(a!=x&&a!=y&&b!=x&&b!=y) merge(x,y);
        else e.push_back(pii(x,y));
    }
//  for(int i=1;i<=n;i++){
//      cout<<f[i]<<" ";
//  }
}

void Work(void){
    for(auto it:e){
        int x=it.first,y=it.second;
        if(y<x) swap(x,y);
        if(a==x) A.insert(find(y));
        if(a==y) A.insert(find(x));
        if(b==x) B.insert(find(y));
        if(b==y) B.insert(find(x));
    }
    int aa=0,bb=0;
    for(int i=1;i<=n;i++){
//      if(i==a||i==b) continue;
        if(i!=a&&i!=b&&A.count(find(i))&&B.count(find(i))==0) ++aa;
        if(i!=a&&i!=b&&B.count(find(i))&&A.count(find(i))==0) ++bb;
    }
    for(auto it:e) merge(it.first,it.second);
    if(find(a)==find(b)) printf("%d\n",aa*bb);
    else puts("0");
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d%d",&n,&m,&a,&b);
        clear();
        Init();
        Work();
    }
}