Codeforces Round 991 (Div. 3)(A-G)

2301_80299496

684人浏览 · 2024-12-06 19:01:39

2301_80299496 · 2024-12-06 19:01:39 发布

题目链接：Dashboard - Codeforces Round 991 (Div. 3) - Codeforces

A. Line Breaks

思路

根据题意模拟一下就行

代码

void solve(){
    int n,m;
    cin>>n>>m;
    vi a(n+10);
    int sum=0;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        a[i]=s.size();
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        sum+=a[i];
        if(sum>m) break;
        cnt++;
    }
    cout<<cnt<<"\n";
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) {
        solve();
    }
    return 0;
}

B. Transfusion

思路

可以发现奇数位置和偶数位置的数是分别联通的，那么只需要判断奇数和偶数位置分别的和即可

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
const int inf=INT_MIN;
const int mod=998244353;
const int base=283;

void solve(){
    int n;
    cin>>n;
    vi a(n+10);
    int sum=0;
    int s1=0,s2=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        if(i%2) s1+=a[i];
        else s2+=a[i];
    }
    if(sum%n){
        cout<<"NO\n";return;
    }
    if(n%2==0){
        if(s1==s2){
            cout<<"YES\n";return;
        }else{
            cout<<"NO\n";return;
        }
    }
    if(n%2){
        int t=s1-s2;
        if((s1>s2)&&(t*n==sum)){
            cout<<"YES\n";return;
        }else{
            cout<<"NO\n";return;
        }
    }
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) {
        solve();
    }
    return 0;
}

C. Uninteresting Number

思路

如果被9整除那么这个各位数字之和必须%9=0，可以发现只有2->4(+2)，3->9(+6)，所以只需要统计一下2和3的个数，然后枚举一下就行了

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
const int inf=INT_MIN;
const int mod=998244353;
const int base=283;


void solve(){
    string s;
    cin>>s;
    int cnt2=0,cnt3=0;
    int sum=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='2'){
            cnt2++;
        }
        if(s[i]=='3'){
            cnt3++;
        }
        sum+=(s[i]-'0');
    }
    if(sum%9==0){
        cout<<"YES\n";return;
    }

    for(int i=0;i<=cnt2;i++){
        for(int j=0;j<=cnt3;j++){
            int t=sum+i*2+j*6;
            if(t%9==0){
                cout<<"YES\n";return;
            }
        }
    }
    cout<<"NO\n";
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) {
        solve();
    }
    return 0;
}

D. Digital string maximization

思路

我去！原来这个题暴力就行了(bushi)，自己绞尽脑汁想别的方法，下面这个ac代码是我用来跑造的数据的答案的，实在想不出来交了一发看看能T几，结果过了，怪我没算时间复杂度，合着在这当了快一个小时的joker

贪心跑几遍就行了，当前这个数的后面一个数-1大于当前这个数交换就行了

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
const int inf=INT_MIN;
const int mod=998244353;
const int base=283;


void solve(){
    string s;
    cin>>s;
    int n=s.size();
    s=" "+s;
    vi a(n+10);
    for(int i=1;i<=n;i++){
        a[i]=s[i]-'0';
    }
    while(1){
        bool flag=false;
        for(int i=2;i<=n;i++){
            if(a[i]>(a[i-1]+1)){
                int t=a[i-1];
                a[i-1]=a[i]-1;
                a[i]=t;
                flag=true;
            }
        }
        if(flag==false) break;
    }
    
    for(int i=1;i<=n;i++){
        cout<<a[i];
    }cout<<"\n";
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) {
        solve();
    }
    return 0;
}

E. Three Strings

思路

动态规划，当然也可以用记忆化搜索写，

当前c的这个位置的字符，可以是随机更改而来的也可以是从a或b中而来的，跑一遍输出最小次数即可

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
const int inf=INT_MIN;
const int mod=998244353;
const int base=283;

//dp[i][j]表示字符串a到i位置，b到j位置时，字符c到i+j位置时，所能从a，b里匹配的最大数量
void solve(){
    string a,b,c;
    cin>>a>>b>>c;
    int la=a.size();
    int lb=b.size();
    int lc=c.size();
    vector<vi> dp(la+10,vi(lb+10));
    for(int i=0;i<=la;i++){
        for(int j=0;j<=lb;j++){
            if(i<la) dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
            if(j<lb) dp[i][j+1]=max(dp[i][j+1],dp[i][j]);

            if(i<la&&a[i]==c[i+j]) dp[i+1][j]=max(dp[i+1][j],dp[i][j]+1);
            if(j<lb&&b[j]==c[i+j]) dp[i][j+1]=max(dp[i][j+1],dp[i][j]+1);
        }
    }
    cout<<lc-dp[la][lb]<<"\n";
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) {
        solve();
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
const int inf=INT_MIN;
const int mod=998244353;
const int base=283;

void solve(){
    string a,b,c;
    cin>>a>>b>>c;
    int n=a.size();
    int m=b.size();
    vector<vi> dp(n+10,vi(m+10,-1));

    auto dfs=[&](auto self,int i,int j,int k)->int{
        if(j==n&&k==m) return 0;
        if(dp[j][k]!=-1) return dp[j][k];
        int ans=INF;
        if(j<n){
            if(a[j]==c[i]){
                ans=min(ans,self(self,i+1,j+1,k));
            }else{
                ans=min(ans,self(self,i+1,j+1,k)+1);
            }
        }
        if(k<m){
            if(b[k]==c[i]){
                ans=min(ans,self(self,i+1,j,k+1));
            }else{
                ans=min(ans,self(self,i+1,j,k+1)+1);
            }
        }
        return dp[j][k]=ans;
    };
    cout<<dfs(dfs,0,0,0)<<"\n";
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) {
        solve();
    }
    return 0;
}

F. Maximum modulo equality

思路

可以发现这一片区域内取余的数相等，那么这一堆数就可以是从等差数列里取出来的数，那么就用a[i]-a[i-1]，取最大公约数就行，可以用线段树查询区间

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define ull unsigned long long
#define bit __builtin_popcountll
#define lowbit(x) ((x)&-(x))
#define vi vector<int>
#define vb vector<bool>

typedef pair<int,int> pll;

const int N=2e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;
const int inf=INT_MIN;
const int mod=998244353;
const int base=283;


int t[N*4];
void push_up(int p){
    t[p]=gcd(t[p<<1],t[p<<1|1]);
}

void build(int p,int l,int r,vector<int>&a){
    if(l==r){
        t[p]=a[l];return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid,a);
    build(p<<1|1,mid+1,r,a);
    push_up(p);
}
int query(int p,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        return t[p];
    }
    int mid=(l+r)>>1,ans=0;
    if(x<=mid){
        ans=gcd(ans,query(p<<1,l,mid,x,y));
    }
    if(y>mid){
        ans=gcd(ans,query(p<<1|1,mid+1,r,x,y));
    }
    return ans;
}


void solve(){
    int n,q;
    cin>>n>>q;
    vi b(n+10);
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    vi d(n+10);
    for(int i=1;i<=n;i++){
        d[i]=b[i]-b[i-1];
    }
    build(1,1,n,d);
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<query(1,1,n,l+1,r)<<" ";
    }cout<<"\n";
}
signed main() {
    vcoistnt
    int _=1;
    cin>>_;
    while(_--) {
        solve();
    }
    return 0;
}

G. Tree Destruction

思路

不难发现我们去掉一条路径，那么它形成的连通分量就是 $s-2*k$ 其中s是路径上的每个点的链接边的个数，k是这条路径上边的个数，对于一个点来说处于最佳路径上要么以此为顶点，要么以此为路径的上的一点

我们设 $dp[i].x$ 表示以i为顶点的路径最多能形成多少个连通分量， $dp[i].x=max(dp[i].x,dp[j].x+du[i]-2)$ j表示i的子节点，du表示与i相连边的数量

设 $dp[i].y$ 表示以 i 为路径上的一点最多能形成几个连通分量，如果只有一个子节点 $dp[i].y=dp[i].x$ ，否则就取两个 $dp[j].x$ 最大的子节点相连

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

#define x first
#define y second

void solve(){
    int n;cin>>n;
    vector<vector<int>> g(n+10);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<pll> dp(n+10);

    auto dfs=[&](auto self,int x,int fa)->void{
        dp[x].x=g[x].size();
        int m1=-1,m2=-1;
        for(auto y:g[x]){
            if(y==fa) continue;
            self(self,y,x);
            dp[x].x=max(dp[x].x,dp[y].x+(int)g[x].size()-2);
            m2=max(m2,dp[y].x);
            if(m1<m2) swap(m1,m2);
        }
        dp[x].y=dp[x].x;
        if(m2!=-1){
            dp[x].y=m1+m2+g[x].size()-4;
        }
    };

    dfs(dfs,1,0);

    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,max(dp[i].x,dp[i].y));
    }
    cout<<ans<<"\n";
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}