UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346)

CJ_Fu · 2024-03-24 23:12:02 · 个人记录

第一个五题 ABC，纪念一下

A - Adjacent Product

给数列 a，输出 a_i\times a_{i+1}。

略。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200003];
signed main(){
    cin>>n; cin>>a[1];
    for(int i=2;i<=n;i++)
        cin>>a[i],cout<<a[i]*a[i-1]<<' ';
    return 0;
}

B - Piano

钢琴键位以 wbwbwwbwbwbw 循环排列，求是否存在恰好有 a 个 w，b 个 b 的子串。

a,b\le 100

感觉这题可以有加强版？应该可以开到 10^{18}。

最暴力的做法，直接拼出一个 200 长的串然后枚 l,r，判断串是否合法，前缀和可以 O(n^2) 但是这题没必要他，时间复杂度 O(n^3)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m; // n white,m black
string t="wbwbwwbwbwbw";
string s;
signed main(){
    cin>>n>>m;
    while(s.length()<=100) s+=t;
    for(int i=0;s[i];i++){
        for(int j=i;s[j];j++){
            int cntn=0,cntm=0;
            for(int k=i;k<=j;k++){
                if(s[k]=='w') cntn++;
                else cntm++;
            }
            if(cntn==n&&cntm==m){
                cout<<"Yes\n";
                return 0;
            }
        }
    }
    cout<<"No\n";
    return 0;
}

C - Σ

给你一个长度为 N 的正整数序列 A=(A_1,A_2,\dots,A_N) 和一个正整数 K 。

求 1 与 K 之间，未出现在序列 A 中的整数之和。

1\leq N \leq 2\times 10^5
1\leq K \leq 2\times 10^9
1\leq A_i \leq 2\times 10^9

首先将 A 排序去重，然后容斥一下，用总和减去 A_i\le K 的数即可，时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;int a[200003],ans;
signed main(){
    cin>>n>>k; ans=k*(k+1)/2;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    n=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=n;i++)
            if(a[i]<=k) ans-=a[i];
    cout<<ans;
    return 0;
}

D -Gomamayo Sequence

给你一个长度为 N 的字符串 S ，它由 0 和 1 组成，修改 S_i 需要 C_i 代价，求让 S 有且仅有两个相邻位置的字符相同的最小代价。

2 \leq N \leq 2 \times 10^5
1 \leq C_i \leq 10^9

考虑 DP，设 f[i][0/1][0/1] 为（到位置 i，前面是否存在两个相邻位置的字符相同，当前字符）的最小代价。初始条件 f[1][0][S_1\oplus 1]=C_1,f[1][0][S_1]=0，其他为 INF。则有转移（设 t=S_i）

f[i][0][t]&=f[i-1][0][t\oplus 1] \\ f[i][0][t\oplus 1]&=f[i-1][0][t]+C_i \\ f[i][1][t]&=\min(f[i-1][0][t],f[i-1][1][t\oplus 1]) \\ f[i][1][t\oplus 1]&=\min(f[i-1][0][t\oplus 1],f[i-1][1][t])+C_i \\ \end{aligned}

答案为 \min(f[n][1][0],f[n][1][1])，时间复杂度 O(n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200003];
char s[200003];
int f[200003][2][2];
signed main(){
    cin>>n;
    cin>>(s+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(f,0x3f,sizeof f);
    f[1][0][(s[1]-'0')^1]=a[1];
    f[1][0][s[1]-'0']=0;
    for(int i=2;i<=n;i++){
        int t=s[i]-'0';
        f[i][0][t]=f[i-1][0][t^1];
        f[i][0][t^1]=f[i-1][0][t]+a[i];
        f[i][1][t]=min(f[i-1][0][t],f[i-1][1][t^1]);
        f[i][1][t^1]=min(f[i-1][0][t^1],f[i-1][1][t])+a[i];
    }
    cout<<min(f[n][1][0],f[n][1][1]);
    return 0;
}

E - Paint

问题陈述

有一个行数为 H 列数为 W 的网格。初始时，所有单元格都涂有颜色 0 。

您将按照 i = 1, 2, \ldots, M 的顺序执行以下操作。

如果是 T_i = 1 ，则使用颜色 X_i 重新绘制 A_i -th 行中的所有单元格。
如果是 T_i = 2 ，则使用颜色 X_i 重新绘制 A_i -th 列中的所有单元格。

完成所有操作后，针对网格中存在的每种颜色 i ，找出被涂上颜色 i 的单元格数量。

1 \leq H, W, M \leq 2 \times 10^5
0 \leq X_i \leq 2 \times 10^5

第一眼 2022 春测，没想到还真像，只是改了一下统计方式。

其他思路与春测无异，只是统计的时候按时间戳倒序统计，就比如计两个数 lv1,lv2，若本次是行覆盖就统计 ton[col_{now}]+=lv2,lv1\to lv1-1，列同理，时间复杂度 O(m\log m)。

主体代码从春测贺的（）

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,t,q;
struct M{
    int c,tix;
    bool operator<(const M &o)const{return tix>o.tix;}
}mat[2][200003];
// op=1 row
// op=0 col
int ton[200003],cnt;
signed main(){
    ios::sync_with_stdio(0);
        cin>>n>>m>>q;
        for(int i=1;i<=m;i++) mat[1][i].c=0, mat[1][i].tix=-1;
        for(int i=1;i<=n;i++) mat[0][i].c=0, mat[0][i].tix=-1;
        for(int i=1,op,x,c;i<=q;i++){
            cin>>op>>x>>c; op--;
            mat[op^1][x].c=c;
            mat[op^1][x].tix=i;
        }
        sort(mat[0]+1,mat[0]+m+1);
        sort(mat[1]+1,mat[1]+n+1);
        int l=1,r=1,lvl=m,lvr=n;
        while(l<=m&&r<=n){
            M L=mat[0][l],R=mat[1][r];
//          cout<<L.tix<<' '<<L.c<<'\n';
//          cout<<R.tix<<' '<<R.c<<'\n';
            if(L.tix<R.tix){
                ton[R.c]+=lvl;
                lvr--, r++;
            }else{
                ton[L.c]+=lvr;
                lvl--, l++;
            }
        }
        while(l<=m){
            ton[mat[0][l].c]+=lvr;
            l++;
        }
        while(r<=n){
            ton[mat[1][r].c]+=lvl;
            r++;
        }
//      ton[0]=n*m;
        for(int i=0;i<=200000;i++){
//          ton[0]-=ton[i];
            if(ton[i]) cnt++;
        }
        cout<<cnt<<'\n';
        for(int i=0;i<=200000;i++){
            if(ton[i]) cout<<i<<' '<<ton[i]<<'\n';
        }

    return 0;
}