Codeforces Round #383 (Div. 2) 題解【ABCDE】

Codeforces Round #383 (Div. 2)

A. Arpa’s hard exam and Mehrdad’s naive cheat

題意

求1378^n mod 10

題解

直接快速幂

代碼

#include<bits/stdc++.h>
using namespace std;
long long quickpow(long long  m,long long n,long long k)
{
    long long b = 1;
    while (n > 0)
    {
          if (n & 1)
             b = (b*m)%k;
          n = n >> 1 ;
          m = (m*m)%k;
    }
    return b;
}

int main()
{
    int n;
    scanf("%d",&n);
    printf("%lld\n",quickpow(1378,n,10));
}
           

B - Arpa’s obvious problem and Mehrdad’s terrible solution

題意

問裡面有多少對數，滿足a[i]^a[j]=x,且i<j

題解

注意a[i]^a[j]=x,那麼a[i]^x=a[j]

mp[i]表示大小為i的有多少個，然後不停的去掃，然後ans+=mp[a[i]^x]就好了

mp的數組得開大一點，因為a[i]^x不一定小于等于100000

代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int n,x,a[maxn];
int mp[maxn];
int main()
{
    scanf("%d%d",&n,&x);
    long long ans = 0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        ans+=mp[a[i]^x];
        mp[a[i]]++;
    }
    cout<<ans<<endl;
}
           

C - Arpa's loud Owf and Mehrdad's evil plan

題意

x->a[x]->a[a[x]]->.....->y 這樣一直循環下去

題目中需要找到一個最小的t，使得任何一個x經過t步可以到達某一個y，且y也可以經過t步走到x

題解

顯然就是把所有環都找出來，如果環的大小是偶數的話，那麼就讓這個環除2，如果這個環的大小為奇數的話，取這個環的大小。

然後都取最小公倍數就好了

代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int n,a[maxn],vis[maxn];
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int flag=0;
    vector<int>ans;
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        int now=i;
        int cnt=0;
        while(!vis[now]){
            vis[now]=i;
            now=a[now];
            cnt++;
        }
        if(now!=i)
            return puts("-1"),0;
        if(cnt%2==0)cnt/=2;
        ans.push_back(cnt);
    }
    long long Ans=ans[0];
    for(int i=1;i<ans.size();i++)
        Ans=Ans*ans[i]/gcd(Ans,ans[i]);
    cout<<Ans<<endl;
}
           

D - Arpa's weak amphitheater and Mehrdad's valuable Hoses

題意

現在有n個人，每個人有w[i]重量的禮物，禮物的魅力值為B[i]

現在他們組成了一些集體，每個集體要麼來一個人，要麼就不來，或者全部來

然後你最多收重量和為W的物品，現在問你能獲得的最大魅力值是多少

題解

并查集+背包dp，注意這個背包dp不要滾動優化，不然很容易從集體裡面轉移過來

題解

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

int n,m,weight,fa[1005],w[1005],b[1005],dp[1005][1005],W[1005],B[1005];
vector<int>WW[1005],BB[1005];
int fi(int x){
    return fa[x]==x?x:fa[x]=fi(fa[x]);
}
void combine(int x,int y){
    x=fi(x),y=fi(y);
    if(x==y)return;
    fa[x]=y;
}
int main()
{
    scanf("%d%d%d",&n,&m,&weight);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        combine(x,y);
    }
    for(int i=1;i<=n;i++){
        W[fi(i)]+=w[i];
        B[fi(i)]+=b[i];
        WW[fi(i)].push_back(w[i]);
        BB[fi(i)].push_back(b[i]);
    }
    int Ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=weight;j++)
            dp[i][j]=dp[i-1][j];
        if(fi(i)!=i)continue;
        for(int j=weight;j>=W[i];j--)
            dp[i][j]=max(dp[i][j],dp[i-1][j-W[i]]+B[i]);
        for(int j=0;j<WW[i].size();j++)
            for(int k=weight;k>=WW[i][j];k--)
                dp[i][k]=max(dp[i][k],dp[i-1][k-WW[i][j]]+BB[i][j]);
        for(int j=0;j<=weight;j++)
            Ans=max(Ans,dp[i][j]);
    }
    cout<<Ans<<endl;
}
           

E - Arpa’s overnight party and Mehrdad’s silent entering

題意

有一個環形的桌子，一共有n對情侶，2n個人，一共有兩種菜。

現在讓你輸出一種方案，滿足以下要求：

1. 情侶間吃不同的菜
2. 相鄰的三個人不能都吃同一種菜

題解

将不能吃統一種菜的人連邊，發現這個圖并不存在奇數長度度的環（顯然成立，不然就是三角戀了）

那麼肯定有答案

然後按照二分圖去染色就好了

代碼

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+7;
int n;
vector<int> E[maxn];
int b[maxn],g[maxn],ans[maxn];
void dfs(int x,int y){
    if(ans[x])return;
    ans[x]=y;
    for(int i=0;i<E[x].size();i++)
        dfs(E[x][i],1-y);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        E[2*i-1].push_back(2*i);
        E[2*i].push_back(2*i-1);
    }
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        E[x].push_back(y);
        E[y].push_back(x);
        b[i]=x,g[i]=y;
    }
    int now=0,tmp=0;
    for(int i=1;i<=2*n;i++){
        if(!ans[i])dfs(i,tmp);
    }
    for(int i=1;i<=n;i++)
        cout<<ans[b[i]]+1<<" "<<ans[g[i]]+1<<endl;
}
           

轉載于:https://www.cnblogs.com/qscqesze/p/6140564.html