练习记录-AtCoder Beginner Contest 296(A-F)

标签：AtCoder 连通 const Beginner Contest int ll long MAXN

vp的感觉整场挺智慧

A - Alternately

找有没有连续的男女

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;

int lowbit(int x){ return x&-x; }
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    int n;cin>>n;
    string s;cin>>s;
    int flag=1;
    for(int i=0;i<s.length();i++){
        if(i!=0&&s[i]==s[i-1]) flag=0;
    } 
    if(flag)cout<<"Yes\n";
    else cout<<"No\n";
}
int main(){
    solve();
}

View Code

B - Chessboard

输出*的序号

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
char a[10][10];
int ans1;
char ans2;
int lowbit(int x){ return x&-x; }
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    for(int i=8;i>=1;i--){
        for(int j=1;j<=8;j++){
        //    char ch;
            cin>>a[i][j];
            if(a[i][j]=='*'){
                ans1=i;
                ans2='a'+j-1;
            }
        }
    }
    cout<<ans2<<ans1;
}
int main(){
    solve();
}

View Code

C - Gap Existence

找是否有两个数满足a-b=x

存map里然后再遍历一遍每个数+x的情况看看有没有存在的就行了

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int long long
map<int,int> sz;
int a[MAXN];
int lowbit(int x){ return x&-x; }
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    int n,x;cin>>n>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sz[a[i]]++;
    }
    int flag=0;
    for(int i=1;i<=n;i++){
        int k=a[i]+x;
        if(sz[k]>0) flag=1; 
    }
    if(flag) cout<<"Yes\n";
    else cout<<"No\n";
}
signed main(){
    solve();
}

View Code

D - M<=ab

寻找每个数作为因子，去逼近m的数字比如m=9 i=2的时候，逼近的值就是2*(9/2+1)=10 以此类推，从1遍历到sqrt(m)+1（+1是防止边界出问题）然后一个一个遍历如果没有取到就输出-1

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int long long
int lowbit(int x){ return x&-x; }
int gcd(int x,int y){int k=0; if(x<y){k=x;x=y;y=k;}while(x%y!=0){k=x%y;x=y;y=k;}return y;}
ll _power(ll a,int b){ll ans=1,res=a;while(b){if(b&1) ans=ans*res%mod;res=res*res%mod;b>>=1;}return ans%mod;}
void solve(){
    int n,m;
    cin>>n>>m;
    int ans=INF;
    int flag=0;
    if(n==1&&m==1){
        cout<<1;
        return;
    }
    for(int i=2;i<=sqrt(m*1.0)+2;i++){
        int k=m/i;
        if(k*i!=m) k++;
        if(k>n||i>n) continue;
        if(k*i<m) continue;
        ans=min(ans,k*i);
        flag=1;
    }
    if(flag==0) cout<<-1;
    else cout<<ans;
}
signed main(){
    solve();
}

View Code

E - Transition Game

题意就是第i=(1 to n) 轮 A可以随便在黑板上写一个数字j 你再在黑板上写一个x 然后结经过j轮把x替换成a[x]的操作,如果能让此时的x为i 那么你+1分求最后的总分

此时我们不难发现因为A可以随便写无限大的j 你只有让替换的行为形成一个环才行也就是强连通单个的也算 i对应的a[i] 看作i->a[i]

毛了个强连通的板子自己还没学图论就不贴代码了

F - Simultaneous Swap
在a串和b串中选 ij和ik 分别交换位置，问能否让两个字串一样

我们直接把a看作标准，然后把b变成a

1.首先这两个串包含的数字数量必须完全一致

2.其次如果一致，并且有某个数字出现两次，那么一定可以因为就把那个数字当成temp 可以一直交换然后i和j全选成这个数字 k自由选来交换

3.如果以上条件均判断过那就剩下每个数字都不同的情况然后判断、

把一串需要互相交换的数字当作连通块比如 123 321 那么 13是连通块 2是连通块如此

我们不难发现当连通块大小为奇数的时候比如 123 与 312 连通块内选择一个不变的i 能通过偶数次的交换让b等于a 意思就是随便选一个j 进行偶数次操作是不会改变i 又能把i变成j的

所以奇数的连通块是不用考虑的

偶数的时候假如说是 12 21 显然不能通过连通块内偶数次交换一定是奇数

但是还有情况就是 123456 与 321654 的时候我通过两次变换 i选择1 j随便 k选择3和4 b串就会变成623154 a串仍然是123456 很明显只有连通块变成奇数了

所以我们得出结论两个偶数的连通块能变成1个奇数的

因此我们只需要判断偶数大小的连通块的数量数量是奇数就是no 偶数就是yes

使用并查集维护连通块大小

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
int f[MAXN],n,m;
int a[MAXN],b[MAXN],ta[MAXN],tb[MAXN],t[MAXN];
//ta a中出现数字的个数 tb b中出现数字个数
//t：以i为祖先的连通块大小 
void clean(){
    for(int i=1;i<=n;i++) f[i]=i;
}
int find(int x){
    if(x!=f[x]) f[x]=find(f[x]);  return f[x];
} 
void add(int x,int y){
    int fx=find(x),fy=find(y); 
    if(fx!=fy) f[fx]=fy;
}
void solve(){
    cin>>n;
    clean();
    int flag=0,res=1,flag2=0;
    for(int i=1;i<=n;i++){
         cin>>a[i];
         ta[a[i]]++;
         if(ta[a[i]]==2) flag=1;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        tb[b[i]]++;
    //    if(tb[b[i]]>ta[b[i]]) res=0;
        if(b[i]!=a[i]) {
            add(a[i],b[i]);
        }
        else flag2=1;
    }
    for(int i=1;i<=n;i++){
        if(tb[i]!=ta[i]) res=0;
    }
    if(res==0){
        cout<<"No\n";
    }
    else if(flag){
        cout<<"Yes\n";
    }
    else{
        for(int i=1;i<=n;i++){
            int fa=find(b[i]);
            t[fa]++;
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(t[i]%2==0&&t[i]!=0){//找偶数大小的连通块数量 
                cnt++;
            }
        }
        if(cnt%2==1) cout<<"No\n";
        else
        cout<<"Yes\n";
    }
}
int main(){
    solve();
}

View Code

看官方题解好像是逆序对的数学太烂不懂逆序对orz 这里就提供一下这个连通块的做法

标签：AtCoder,连通,const,Beginner,Contest,int,ll,long,MAXN
From： https://www.cnblogs.com/xishuiw/p/17299074.html

练习记录-AtCoder Beginner Contest 296(A-F)

相关文章

赞助商

阅读排行