Codeforces Round #664 (Div. 2)A~D题解

发布于 2020-08-13  0 次阅读


A. Boboniu Likes to Color Balls

题目大意:

给你四种颜色的球,给你一种操作:选择前三种各一个,将这三个变成最后一种,你可以执行任意次该操作
问,球的数量可不可以形成回文

思路:

分情况考虑一下球的奇偶性就行,奇数有0个,1个,4个都是可以的,奇数为3个的时候就需要分别考虑了,如果其中无0的话直接将前三个转成最后一个,就是三偶一奇了,有0的话只能在d上,不然就NO

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;

void solve(){
    int a, b, c, d;
    int ans=0;
    cin>>a>>b>>c>>d;
    if(a&1)     ans++;
    if(b&1)     ans++;
    if(c&1)     ans++;
    if(d&1)     ans++;
    int mi=min(a,min(b,min(c,d)));
    if(ans==0 || ans==1 || ans==4) cout<<"YES";
    else if(ans==3 && mi)  cout<<"YES";
    else if(ans==3 && d==0)    cout<<"YES";
    else cout<<"NO";
    cout<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

B. Boboniu Plays Chess

题目大意:

给你一个n×m的方格,给你一个起始点(x,y),你可以像象棋中的车那样移动,你需要将所有点全部去一次
问你路径

思路:

先将给的点的这一行输出(首先输出初始点)
然后从第一行到最后一行挨个输出就行,S型输出(1-m然后m-1然后1-m …)

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=2e5 +9;
int n, m, x, y;
void solve(){
    cin>>n>>m>>x>>y;
    cout<<x<<" "<<y<<endl;
    for(int i=1; i<=m; i++) if(i!=y)    cout<<x<<" "<<i<<endl;
    int step=m;
    for(int i=1; i<=n; i++){
        if(i==x)    continue;

        if(step==m) {for(int j=m; j>=1; j--) cout<<i<<" "<<j<<endl;; step=1;}
        else if(step==1)    {for(int j=1; j<=m; j++) cout<<i<<" "<<j<<endl; step=1; step=m;}
    }
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

C. Boboniu and Bit Operations

题目大意:

给你一个长度为n的序列a,一个长度为m的序列b,其中c [ i ] = a [ i ] & b [ j ](j为b中的任意位)
求满足条件的最小的c [ 1 ] ∣ c [ 2 ] ∣ . . . ∣ c [ n ]

思路:

注意到a和b的取值范围为(0,29),所以我们可以直接枚举c的值,然后判断每个a [ i ]中有无b [ j ] 可以满足该c(与c按位与即可),最后取个最小即可

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=209;
int n, m;
int a[N], b[N];
void solve(){
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int j=1; j<=m; j++) cin>>b[j];
    int flag1, flag2, ans=INF;
    for(int i=0; i<(1<<10); i++){
        flag1=1;
        for(int j=1; j<=n; j++){
            flag2=0;
            for(int k=1; k<=m; k++) if(((a[j]&b[k])|(i)) == i)  {flag2=1; break;}
            if(!flag2)  {flag1=0; break;}
        }
        if(flag1)   ans=min(ans, i);
    }   
    cout<<ans<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

D. Boboniu Chats with Du(枚举)

题目大意:

一个人喜欢说有趣的话,但会嘲讽到另外一个人,另外一个人有他的忍耐限度m,超过这个限度就会禁言他d天
现在给你n天,和一个长度为n的序列
忍耐限度m和有趣的人被禁言的天数d
求有趣的人可以说的话的有趣值的最大值

思路:

给的序列中,其实可以分成两种,会被禁言的和不会被禁言的,我们只需要考虑禁言的话到底说不说,说多少
所以就可以直接枚举禁言的话到底说多少,通过样例可以发现最后一天说禁言的话是很好的选择,因为只会消耗一天
所以,禁言的话消耗的天数就是( i − 1 ) ∗ ( d + 1 ) + 1,剩下的天数就尽可能的说最有趣但不会禁言的,然后相加取最大值
对于不会禁言的话可以提前打表,但是要注意打表到n天去

AC Code:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
#define int long long
// #define TDS_ACM_LOCAL
const int N=1e5 +9;
int n, d, m, x;
int mx[N], mi[N], cntx, cnti;
int prex, prei[N];
bool cmp(int a, int b){ return a>b;}

void solve(){
    cin>>n>>d>>m;
    cntx=cnti=0;
    for(int i=1; i<=n; i++){
        cin>>x;
        //mx为会被禁言的,mi为不会被禁言的
        if(x>m) mx[++cntx]=x;
        else    mi[++cnti]=x;
    }
    sort(mx+1, mx+1+cntx, cmp); sort(mi+1, mi+1+cnti, cmp);
    for(int i=1; i<=n; i++)  prei[i]=prei[i-1]+mi[i];   //提前对不会禁言的话打表,注意打到n去
    int ans=0, sum, temp;
    for(int i=0; i<=cntx; i++){
        if(i==0)    sum=0;
        else        sum=(i-1)*(d+1)+1;
        prex=prex+mx[i];
        if(sum>n)   break;
        temp=prex+prei[n-sum];
        ans=max(ans, temp);
    }
    cout<<ans<<endl;
    return ;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的大学在读本科生