Educational Codeforces Round 56 (Rated for Div. 2) ABCD

题目链接：https://codeforces.com/contest/1093

A. Dice Rolling

题意：

有一个号数为2-7的骰子，现在有一个人他想扔到几就能扔到几，现在问需要扔多少次，能使扔出的总和等于xi。

题解：

由于是special judge，模拟一下搞搞就行了= =

代码如下：

#include <bits/stdc++.h>

using namespace std;

int main(){

    int t;

    cin>>t;

    int n;

    while(t--){

        cin>>n;

        for(int i=;i<=;i++){

            if(n%i!=){

                cout<<n/i+(n%i!=)<<endl;

                break ;

            }

        }

    }

    return ;

}

B. Letters Rearranging

题意：

给出一个字符串，现在你可以任意交换字符位置，然后输出一种非回文串的方案，如果没有这样一种方案，输出-1。

题解：

注意回文串的性质，那么我们首先判断一下所有字符是否相同，如若相同直接输出-1。否则排个序就好了~

代码如下：

#include <bits/stdc++.h>

using namespace std;

int t;

const int N = ;

char s[N];

int main(){

    cin>>t;

    while(t--){

        scanf("%s",s);

        int flag = ;

        int len  =strlen(s);

        s[len]=s[];

        for(int i=;i<=len;i++){

            if(s[i]!=s[]) flag=;

        }

        if(flag) cout<<-<<endl;

        else{

            sort(s,s+len);

            for(int i=;i<len;i++) cout<<s[i];

            cout<<endl;

        }

    }

    return ;

}

C. Mishka and the Last Exam

题意：

一共有n个数，现在给出b1,b2....b_n/2，满足b_i=a_i+a_n-i+1。

现在要你构造出合法的a1....an，并且a1<=a2<=...<=an，保证输入有解。

题解：

对于b1=a1+an来说，我们让a1=0,a2=b1是最好的，这样可以让左右端点最大。

对于后面的每个b_i，我们令d=b_i-b_i-1,那么如若d>0，我们可以想，假若a2,an-1不变，那么他们之和是小于b2的，所以我们就让左端点变大（贪心策略）。

对于d=0或者d<=0都可以同样的策略去想（因为题目保证输入有解）。

代码如下:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4e5+;

int n;

ll a[N],b[N];

int main(){

    cin>>n;

    for(int i=;i<=n/;i++) cin>>b[i];

    a[]=;a[n]=b[];

    for(int i=;i<=n/;i++){

        ll d = b[i]-b[i-];

        if(d>=) a[i]=d+a[i-],a[n-i+]=a[n-i+];

        else a[i]=a[i-],a[n-i+]=a[n-i+]+d;

    }

    for(int i=;i<=n;i++) cout<<a[i]<<" ";

    return ;

}

D. Beautiful Graph

题意：

给出一个图，有n个点,m条边，每个点都有权值1，2或3。现在要你给点权赋值，满足相邻的两个点和为奇数。问一共有多少情况，注意这个图不一定保证连通。

题解:

根据题意我们知道，相邻的两个点必然为一奇一偶，所以我们可以用二分图染色来判断是否给出的图合法，能够满足条件。

在二分图染色的过程中，记录一下两种颜色的个数a,b，那么最终的答案就是对于每个图的2^a+2^b再求和。

注意一下单独一个点可能有1，2，3三种情况。

代码如下：

#include <bits/stdc++.h>

#define MOD 998244353

using namespace std;

typedef long long ll;

const int N = 3e5+;

int T;

int n,m,flag,num,sum;

vector <int> g[N];

int color[N];

void dfs(int u,int c){

    color[u]=c;sum++;

    if(color[u]==) num++;

    if(flag) return ;

    for(auto v:g[u]){

        if(!color[v]) dfs(v,-c);

        else if(color[v]==c){

            flag=;

            return ;

        }

    }

    return ;

}

ll quick(ll a,int b){

    ll ans = ;

    while(b){

        if(b&) ans=(ans*a)%MOD;

        a=(a*a)%MOD;

        b>>=;

    }

    return ans ;

}

int main(){

    cin>>T;

    while(T--){

        scanf("%d%d",&n,&m);flag=;

        for(int i=;i<=n;i++) g[i].clear(),color[i]=;

        for(int i=;i<=m;i++){

            int u,v;

            scanf("%d%d",&u,&v);

            g[u].push_back(v);g[v].push_back(u);

        }

        int tot =;

        ll ans =;

        for(int i=;i<=n;i++){

            if(!color[i] && !flag){

                num=;sum=;

                dfs(i,);

                if(sum==) ans=(ans*)%MOD;

                else ans=(ans*(quick(,num)+quick(,sum-num))%MOD)%MOD;

            }

        }

        if(flag) printf("0\n");

        else printf("%I64d\n",ans);

    }

    return ;

}

巴特西

Educational Codeforces Round 56 (Rated for Div. 2) ABCD

最新文章

热门文章