CF634(div.3)A~D

http://codeforces.com/contest/1335

这几个题比较简单，笔记就放在一起写了，E1E2明天单独写一篇。

A. Candies and Two Sisters

题目描述

给你 \(n\) 个糖果分成 \(a,b\) 两份，要求 \(a>b>0\)，询问有多少种分法。

解题

\(ans = (n-1)/2\)

for i in range(int(input())):
    n = int(input())
    print((n-1)//2)

B. Construct the String

题目描述

要求构造一个长度为 \(n\) 的字符串，保证其中每长度为 \(a\) 的连续子段中，有 \(b\) 种不同的字符。

解题

在子段中前 \(a-b+1\) 个字符全部用同一个，然后再补上 \(b-1\) 个不同的字符，最后以该子段循环生成字符串则为答案。

例如 \(a=5,b=3\) ，则可以用 \(aaabc\) 循环生成得到答案 \(aaabcaaabcaaabcaaa...\)

#include<bits/stdc++.h>
#define ll long long

#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag)   for(int i=0;i<n&&flag;i++)

#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)

#define frrs(i,j,n,flag)    for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag)    for(int i=n-1;i>=j&&flag;i--)

#define arend(i,n) ((i!=n-1)?" ":"\n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end)    for(auto it = begin;it!=end;it++)  cout<<*it<<arend(it,end);
#define log_this(name,value)    cout<<name<<": "<<value<<endl;
#define e4 10004
#define e5 100005
#define e6 1000006
#define e7 10000007
#define e9 1000000000
#define INF 9999999
using namespace std;
int     to_int(string s)    {stringstream ss;ss<<s;int a;ss>>a;return a;}
string  to_str(double a)    {stringstream ss;ss<<a;return ss.str();}


int main(){

    cin.tie(0);
    //ios::sync_with_stdio(false);
    //cout<<setiosflags(ios::fixed)<<setprecision(0);

    //freopen("1.out","w",stdout);
    int t;
    while(cin>>t){
        while(t--){
            int a,b,n;
            cin>>n>>a>>b;
            int p = a - b + 1,l = 0;
            while(l<n){
                char c = ‘a‘;
                frrs(i,0,p,l<n){
                    cout<<c;
                    l++;
                }
                frrs(i,0,a-p,l<n){
                    c++;if(c>‘z‘){
                        c = ‘a‘;
                    }
                    cout<<c;
                    l++;
                }
            }
            cout<<endl;
        }
    }

    return 0;
}

C. Two Teams Composing

题面描述

从 \(n\) 个数字中选出一部分分成两组，要求第一组数字全部不同，第二组数字全部相同，而且两个组大小相同，询问分组的可以达到的最大大小。

解题

把重复最多的数字全部拿出来，用来组成第二组。然后再从剩下的数字中，尽可能多的挑选以组成第一组。如果此时第二组的大小比第一组多两个或以上，那么第二组可以分给第一组一个数字。

这样既可以得到最大的组大小。

#include<bits/stdc++.h>
#define ll long long

#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag)   for(int i=0;i<n&&flag;i++)

#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)

#define frrs(i,j,n,flag)    for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag)    for(int i=n-1;i>=j&&flag;i--)

#define arend(i,n) ((i!=n-1)?" ":"\n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end)    for(auto it = begin;it!=end;it++)  cout<<*it<<arend(it,end);
#define log_this(name,value)    cout<<name<<": "<<value<<endl;
#define e4 10004
#define e5 100005
#define e6 1000006
#define e7 10000007
#define e9 1000000000
#define INF 9999999
using namespace std;
int     to_int(string s)    {stringstream ss;ss<<s;int a;ss>>a;return a;}
string  to_str(double a)    {stringstream ss;ss<<a;return ss.str();}

int cta[2*e5];

int main(){

    cin.tie(0);
    //ios::sync_with_stdio(false);
    //cout<<setiosflags(ios::fixed)<<setprecision(0);

    //freopen("1.out","w",stdout);
    int t;
    while(cin>>t){
        while(t--){
            int n;cin>>n;
            fr(i,n) cta[i] = 0;
            int inp;
            int unsamenum = 0;
            int maxnum = 0;
            fr(i,n){
                cin>>inp;
                if(cta[inp-1]==0) unsamenum++;
                cta[inp-1]++;
                maxnum = max(maxnum,cta[inp-1]);
            }
            int ans = min(unsamenum-1,maxnum);
            if(maxnum-2>=unsamenum-1){
                ans++;
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

D. Anti-Sudoku

题面描述

给一个填好的 \(9*9\) 数独表，可以对其中的数字进行 \(9\) 次修改，要求实现以下条件：

• 每一行至少存在一个数字出现两次或以上
• 每一列至少存在一个数字出现两次或以上
• 每一个加粗的 \(3*3\) 小方块中至少存在一个数字出现两次或以上

解题

把原来的数独表中所有的 \(9\) 改成 \(1\)，这样你就得到了每行每列每块中都有两个 \(1\) 的 anti-?数独表。

#include<bits/stdc++.h>
#define ll long long

#define fr(i,n) for(int i=0;i<n;i++)
#define frs(i,n,flag)   for(int i=0;i<n&&flag;i++)

#define frr(i,j,n) for(int i=j;i<n;i++)
#define r_frr(i,j,n) for(int i=n-1;i>=j;i--)

#define frrs(i,j,n,flag)    for(int i=j;i<n&&flag;i++)
#define r_frrs(i,j,n,flag)    for(int i=n-1;i>=j&&flag;i--)

#define arend(i,n) ((i!=n-1)?" ":"\n")
#define memset0(dp) memset(dp,0,sizeof(dp))
#define print_arr(begin,end)    for(auto it = begin;it!=end;it++)  cout<<*it<<arend(it,end);
#define log_this(name,value)    cout<<name<<": "<<value<<endl;
#define e4 10004
#define e5 100005
#define e6 1000006
#define e7 10000007
#define e9 1000000000
#define INF 9999999
using namespace std;
int     to_int(string s)    {stringstream ss;ss<<s;int a;ss>>a;return a;}
string  to_str(double a)    {stringstream ss;ss<<a;return ss.str();}

char a[9][9];
int main(){

    cin.tie(0);
    //ios::sync_with_stdio(false);
    //cout<<setiosflags(ios::fixed)<<setprecision(0);

    //freopen("1.out","w",stdout);
    int t;
    while(cin>>t){
        while(t--){
            fr(i,9){
                fr(j,9){
                    cin>>a[i][j];
                }
            }
            fr(i,9){
                fr(j,9){
                    if(a[i][j]==‘9‘){
                        cout<<"1";
                    }else{
                        cout<<a[i][j];
                    }
                }
                cout<<endl;
            }
        }
    }
    return 0;
}

Codeforces Round #634 (div.3) A~D

原文：https://www.cnblogs.com/DOEMsy/p/12695437.html