Codeforces Round #677 (Div. 3)——ABCDE解题报告

2024-03-27 08:48:34

Codeforces Round #677 (Div. 3)——ABCDE解题报告

比赛链接:https://codeforces.com/contest/1433

A.Boring Apartments

题解

直接按照题意模拟整个过程即可。

代码

#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
const int N = 1e5+7;
int a[N];
void solve(){
    string s;cin>>s;
    string cur="1";
    int num=1;
    int ans=0;
    while(cur!=s){
        ans+=cur.size();
        if(cur.size()==4){
            num++;
            cur=(num+'0');
            continue;
        }
        cur+=(num+'0');
        // outval2(num,cur);
    }
    cout<<ans+cur.size()<<endl;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    //debug = 1;
#endif
    //time_t beg, end;
    //if(debug) beg = clock();

    int T;cin>>T;
    while(T--) solve();

    /*
    if(debug) {
        end = clock();
        printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    }
    */
    return 0;
}

B.Yet Another Bookshelf

题解

数据比较小，我们可以首先枚举作为中心的连续 1 1 1的串。
然后分为两种情况进行考虑：
1.在中心左边的连续 1 1 1的串
2.在中心右边的连续 1 1 1的串
当该串在中心的左边时，根据贪心的原则从小到大每次把小的连续 1 1 1的串换到第一个比他大的连续的 1 1 1的串的左边最优。
举个例子模拟一下这个过程：
假设串为 1010011010 1010011010 1010011010。
当前作为中心的连续的 1 1 1串为 11 11 11。
把中心左边的连续 1 1 1串交换的步骤如下：
1. 1010011010 − − 0110011010 1010011010--0110011010 1010011010−−0110011010
2. 0110011010 − − 0001111010 0110011010--0001111010 0110011010−−0001111010
这样可以保证交换次数最小，中心右边的情况类似，只不过逆序维护。
最后我们会发现，每次枚举中心的答案都是一样的，因此我们就可以直接求出以第一个连续 1 1 1作为中心的最小交换次数即可，至于为什么？可以自己想一想。

代码

#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
const int N = 1e5+7;
int a[N];
struct node{
    int l,r;
}p[N];
int tot;
void solve(){
    int n=read();
    rp(i,1,n) a[i]=read();  
    tot=0;
    rp(i,1,n){
        if(!a[i]) continue;
        int l=i;
        while(i<n&&a[i+1]) i++;
        p[++tot]={l,i};
    }
    int ans=0;
    rp(i,1,tot-1) ans+=p[i+1].l-p[i].r-1;
    cout<<ans<<endl;
}
int main(){
    //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    //debug = 1;
#endif
    //time_t beg, end;
    //if(debug) beg = clock();

    int T=read();
    while(T--) solve();

    /*
    if(debug) {
        end = clock();
        printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    }
    */
    return 0;
}

C.Dominant Piranha

题解

直接暴力枚举开始位置的数，然后模拟整个过程即可。
注意要逆序枚举。

代码

#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
const int N = 3e5+7;
int a[N];
void solve(){
    int n=read();
    rp(i,1,n) a[i]=read();
    a[0]=a[n+1]=INF;
    RP(i,n,1){
        int f=0;
        int cur_num=a[i];
        int num=1;
        int l=i-1,r=i+1;
        while(num<n){
            // outval3(cur_num,l,r);
            if(a[l]<cur_num) cur_num++,l--,num++;
            else if(a[r]<cur_num) cur_num++,r++,num++;
            else{
                f=1;
                break;
            }
        }
        // outval2(i,num);
        if(num==n){
            cout<<i<<endl;
            return ;
        } 
    }
    cout<<-1<<endl;
}
int main(){
    //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    //debug = 1;
#endif
    //time_t beg, end;
    //if(debug) beg = clock();

    int T=read();
    while(T--) solve();

    /*
    if(debug) {
        end = clock();
        printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    }
    */
    return 0;
}

D.Districts Connection

题解

c f cf cf常规构造题，这个构造不是特别难想。
首先当只有一个类型时肯定不行，输出NO即可。
否则的话，首先输出YES。
然后选择第一个类型的第一个数，和其他不是一个类型的所有数建边，
最后再把第一个类型中(除了第一个数)的所有数和其他(排除了第一个类型)的类型的任意一个数建边即可。

代码

#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
const int N = 5e3+7;
int a[N];
vector<int> v[N];
vector<int> data;
void init() { data.clear(); }
void Insert(int val) { data.push_back(val); }
void doit() {
    sort(data.begin(), data.end());
    data.erase(unique(data.begin(), data.end()), data.end());
}
int g(int val) { return lower_bound(data.begin(), data.end(), val) - data.begin() + 1; }
void solve(){
    int n=read();
    init();
    rp(i,1,n) a[i]=read(),Insert(a[i]);
    doit();
    int len=data.size();
    if(len==1){
        pN;
        return ;
    }
    pY;
    rp(i,1,n) a[i]=g(a[i]);
    rp(i,1,n) v[i].clear();
    rp(i,1,n) v[a[i]].push_back(i);
    // rp(i,1,len){
    //     cout<<i<<endl;
    //     for(auto val:v[i]) cout<<val<<" ";
    //     cout<<endl;
    // }
    int cnt=0;
    int cur=v[1][0];
    rp(i,2,len){
        cnt+=v[i].size();
        for(auto val:v[i]) cout<<cur<<" "<<val<<endl;
    }
    rp(i,1,v[1].size()-1){
        cnt++;
        cout<<v[1][i]<<" "<<v[2][0]<<endl;
    }
}
int main(){
    //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    //debug = 1;
#endif
    //time_t beg, end;
    //if(debug) beg = clock();

    int T=read();
    while(T--) solve();

    /*
    if(debug) {
        end = clock();
        printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    }
    */
    return 0;
}

E.Two Round Dances

题解

数学组合计数题，首先考虑选取两轮舞蹈的所有方案数 u p up up。
不难得到 u p = C n n 2 × A n 2 n 2 × C n 2 n 2 × A n 2 n 2 up=C_{n}^{\frac{n}{2}}\times A_{\frac{n}{2}}^{\frac{n}{2}}\times C_{\frac{n}{2}}^{\frac{n}{2}}\times A_{\frac{n}{2}}^{\frac{n}{2}} up=Cn2n​​×A2n​2n​​×C2n​2n​​×A2n​2n​​。
然后我需要考虑重复的个数 d o w n down down，手推2,4,6,8的情况可以得到 d o w n = ( n 2 ) × ( n 2 ) × 2 down=(\frac{n}{2})\times (\frac{n}{2}) \times 2 down=(2n​)×(2n​)×2。
最终答案就是所有方案数除以重复个数（即 u p d o w n \frac{up}{down} downup​）。

代码

#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
inline int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}
const int N = 1e5+7;
ll fac[N];
ll C(int n,int m){
    return fac[n]/(fac[n-m]*fac[m]);
}
ll A(int n,int m){
    return fac[n]/fac[n-m];
}
void solve(){
    int n=read();
    fac[0]=1;
    rp(i,1,n) fac[i]=(fac[i-1]*i);
    cout<<C(n,n/2)*A(n/2,n/2)*A(n/2,n/2)/((1ll*n*n)/2)<<endl;
}
int main(){
    //ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
    //debug = 1;
#endif
    //time_t beg, end;
    //if(debug) beg = clock();

    int T=1;
    while(T--) solve();

    /*
    if(debug) {
        end = clock();
        printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
    }
    */
    return 0;
}
上一篇：677 vue3组件化开发初体验：组件的名称，全局组件，局部组件


下一篇：Codeforces Round #677 (Div. 3)