Codeforces Round 1003 (Div. 4)

Ding0023 · 2025-02-10 13:27:11 · 个人记录

A. Skibidus and Amog'u

没啥好说的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
string s;
int t;
void solve(){
    cin >> s;
    for(int i=0;i<s.size()-2;i++) cout << s[i];
    cout << "i" << endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}

B. Skibidus and Ohio

可以考虑将两个字母合并结果设为-1暂时存放，在合并时可将-1变为所需要值，然后就贪心的能合就合。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int a[maxn];
int b[maxn];
string s;
int t;
void solve(){   

    cin >> s;
    for(int i=0;i<(int)s.size();i++) a[i+1]=s[i]-'a'; 
    int cnt1=s.size(),cnt2=0;
    bool flag=true;
    while(flag){
        cnt2=0;
        flag=false;
        for(int i=1;i<cnt1;i++){
            if(a[i]==a[i+1]||a[i]==-1||a[i+1]==-1){
                b[++cnt2]=-1;
                i++;
                flag=true;
                continue;
            }
            b[++cnt2]=a[i];
        } 
        for(int i=1;i<=cnt2;i++) a[i]=b[i];
        cnt1=cnt2;
        //cout << cnt1 << " ";
    }
    cout << cnt1+1 << endl;

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}

C1,C2. Skibidus and Fanum Tax

贪心的，希望a[i]为满足限制条件的最小值，可以考虑将b排序，这样子可以通过二分在logm的复杂度找到满足条件的最小b[j]-a[i]。将b[j]-a[i]和a[i]的情况进行分类讨论取合法最小即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5;
const int inf=1e9+5;
int a[maxn];
int b[maxn];
int t;
int n,m;
void solve(){   
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=m;i++) cin >> b[i];
    sort(b+1,b+1+m);
    a[0]=-inf;
    for(int i=1;i<=n;i++){
        int l=1,r=m;
        while(l<r){
            int mid=(l+r)>>1;
            if(b[mid]-a[i]<a[i-1]) l=mid+1;
            else r=mid;
        }
        int ans1=b[l]-a[i];
        int ans2=a[i];
        if(ans1>=a[i-1]&&ans2>=a[i-1]){
            a[i]=min(ans1,ans2);
        }else if(ans1>=a[i-1]){
            a[i]=ans1;
        }else if(ans2>=a[i-1]){
            a[i]=ans2;
        }else{
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
    return;
}
signed main(){
//  ios::sync_with_stdio(false);
//  cin.tie(0);
//  cout.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}

D. Skibidus and Sigma

通过交换法发现，最优顺序为按照数组sum降序排序

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5;
const int inf=1e9+5;
vector<int> a[maxn];
int sum[maxn];
int t,n,m;
int ans,cnt;
bool cmp(int x,int y){
    return x>y;
} 
void solve(){   
    ans=0;
    cin >> n >> m;
//  cnt=0;
    for(int i=1;i<=n;i++){
        sum[i]=0;
        cnt=0;
        for(int j=1;j<=m;j++){
            int x;
            cin >> x;
            sum[i]=sum[i]+x;
            cnt+=x;
            ans+=cnt; 
        }
    }

    sort(sum+1,sum+1+n,cmp);
    cnt=0;
    for(int i=1;i<=n;i++){
        ans+=cnt*m; 
        cnt+=sum[i];
    }
    cout << ans << endl;
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}

E. Skibidus and Rizz

按题意构造就好了qwq

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5;
const int inf=1e9+5;
int t,n,m,k;
void solve(){   
    cin >> n >> m >> k;
    if(abs(n-m)>k||(n<k&&m<k)) cout << -1;
    else {
        if(n<m){
            for(int i=1;i<=k;i++) cout << 1;
            for(int i=1;i<=max(m-k,n);i++){
                if(i<=n) cout << 0; 
                if(i<=m-k) cout << 1;
            }   
        }else{
            for(int i=1;i<=k;i++) cout << 0;
            for(int i=1;i<=max(m,n-k);i++){
                if(i<=m) cout << 1; 
                if(i<=n-k) cout << 0;

            }   
        }
    }
    cout << endl;
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}

F. Skibidus and Slay

若存在严格众数，则必然存在相同数间长度为1或2的路径，于是枚举每个点，用map维护一下连边值就好了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e5+5;
vector<int> e[maxn];
map<int,bool> s;
int ans[maxn];
int a[maxn];
int t,n;
void solve(){   
    cin >> n;
    for(int i=1;i<=n;i++) e[i].clear();
    for(int i=1;i<=n;i++) ans[i]=0;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        s.clear();
        s[a[i]]=true;
        for(auto to:e[i]){
            if(s[a[to]]) ans[a[to]]=true;
            s[a[to]]=true;
        }
    }
    for(int i=1;i<=n;i++) cout << ans[i];
    cout << endl;
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}

G. Skibidus and Capping

容易发现，两数最小公倍数为为半素数，只有两种情况

两数为不相等素数
其中一数为半素数，另一数为前一数因数（考虑到半素数质因数次数和只有2，可以直接枚举）

可以考虑先用埃筛处理出所有数字的因数个数，然后用桶记录每个数字出现次数，然后扫一遍就好了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
int t,cnt,n,ans;
int a[maxn];
int p[maxn][30];
int len[maxn];
int Size[maxn];
void init(){
    for(int i=2;i<maxn;i++){
        p[i][++len[i]]=i;
        if(len[i]!=1) continue;
        for(int j=2;i*j<maxn;j++){
            p[i*j][++len[i*j]]=i;
        }
    }
}
void solve(){   
    cnt=0;
    ans=0;
    cin >> n;
    for(int i=1;i<=n;i++) Size[i]=0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        Size[a[i]]++; 
        if(len[a[i]]==1) cnt++;
    }
    for(int i=1;i<=n;i++){
        if(len[a[i]]==1){
            ans+=cnt-Size[a[i]];
        }else if(len[a[i]]==2){
            if(p[a[i]][1]*p[a[i]][1]!=a[i]) continue;
            ans+=Size[p[a[i]][1]]*2;
            ans+=Size[a[i]]+1;
        }else if(len[a[i]]==3){
            if(p[a[i]][1]*p[a[i]][2]!=a[i]) continue;
            ans+=(Size[p[a[i]][1]]+Size[p[a[i]][2]])*2;
            ans+=Size[a[i]]+1;
        }
    }
    ans/=2; 
    cout << ans << endl;
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    init();
    while(t--) solve();
    return 0;
}

H. Bro Thinks He's Him

不会(悲