[数据结构与算法]Codeforces Round #778 (Div. 1 + Div. 2 based on Technocup 2022 Final Round)（ABCDE）

Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round)（ABCDE）

A. Maximum Cake Tastiness

题意：输出最大+次大的和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
int n,m,q,a[N];

void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1,greater<int>());
    printf("%d\n",a[1]+a[2]);
}

int main(){
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}

B. Prefix Removals
题意：如果首字符在字符串后面还有出现，就可以删除首字符，问最终字符串的形式
思路：先记录每个字符出现的次数，然后从前往后遍历，如果后面还有该字符，就该字符数量-1，否则结束，输出剩下字符串。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
char s[N];
int num[40];

void solve(){
    for(int i=0;i<26;i++) num[i]=0;
    scanf("%s",s+1);
    int len=strlen(s+1);
    for(int i=1;i<=len;i++) num[s[i]-'a']++;
    int idx;
    for(int i=1;i<=len;i++){
        if(num[s[i]-'a']>1) num[s[i]-'a']--;
        else {idx=i;break;}
    }
    for(int i=idx;i<=len;i++) printf("%c",s[i]);
    puts("");
}

int main(){
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}

C. Alice and the Cake
题意：有一个蛋糕，切n-1刀，使蛋糕分成n份。每次去切蛋糕时，选择一块蛋糕大小w>=2的，切成$?w2?和?w2?$两部分。
现在给出最终n块小蛋糕的大小，问是否存在原蛋糕，满足切法后构成该n块小蛋糕。
思路：我们发现每次切蛋糕都是“平分”上一个蛋糕，总大小是不变的，所有初始序列a的总和就是原蛋糕的大小，然后我们去切蛋糕，同时记录每块蛋糕的大小，如果最终存在该大小就移除该蛋糕，问最终剩余蛋糕是否为0就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll n,sum;
vector<ll>now,tmp;
map<ll,int>mp;

void solve(){
    sum=0;
    mp.clear();now.clear();tmp.clear();
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++){
        ll x;scanf("%lld",&x);
        sum+=x;
        mp[x]++;
    }
    now.push_back(sum);
    ll yu=n;
    while(yu>=now.size()&&now.size()&&yu){
        for(auto it:now){
            if(mp[it]) mp[it]--,yu--;
            else{
                if(it>=2){
                    tmp.push_back(it/2);
                    tmp.push_back((it+1)/2);
                }
                else tmp.push_back(1);
            }
        }
        now=tmp;
        tmp.clear();
    }
    if(yu==0) puts("YES");
    else puts("NO");
}

int main(){
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}

D. Potion Brewing Class
题意：有n个节点的一颗树，n-1条边，每边满足$a[i]/a[j]=x/y$,问满足全部比例的树的最小权值和
思路：
由于比例可能是分数的形式，累乘起来分数形式可能比较大，不好操作。
所以我们当我们知道某个节点的值，剩下的去dfs就可以确定其他所有节点的值
这里我们确定节点1的值，我们拿其他所有点来跟节点1操作，通过变换公式，我们可以得到节点1的值，防止数太大，节点1的值分解质因数的形式表示，最后再暴力枚举质因子得到节点1的值$($

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5;
const ll mod=998244353;
ll n,ned[N],mxned[N],ans;
ll inv[N],prime[N],cnt,lst[N];
bool vis[N];
map<ll,ll>mp;
struct node{ll v,x,y;};
vector<node>edge[N];

void init(){
    //线性求逆元
    inv[1]=1;
    for(ll i=2;i<N;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;

    //线性筛
    for(ll i=2;i<N;i++){
        if(!vis[i]) prime[++cnt]=i,mp[i]=cnt;
        for(ll j=1;i<N/prime[j];j++){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}

void change(ll x,int type){
    for(ll i=1;i<=cnt;i++){ //分解质因数
        ll num=prime[i];
        if(num*num>x) break;
        while(x%num==0){
            ned[i]=ned[i]+type;
            x/=num;
        }
        mxned[i]=max(mxned[i],ned[i]); 
    }
    if(x>1){
        ned[mp[x]]=ned[mp[x]]+type;
        mxned[mp[x]]=max(mxned[mp[x]],ned[mp[x]]);
    }
}

void dfs1(ll u,ll fa){
    ll len=edge[u].size();
    for(ll i=0;i<len;i++){
        ll v=edge[u][i].v;
        if(v==fa) continue;
        ll x=edge[u][i].x,y=edge[u][i].y;
        change(y,-1);
        change(x,1);
        dfs1(v,u);
        change(x,-1);
        change(y,1);
    }
}

void dfs2(ll u,ll fa,ll val){
    ll len=edge[u].size();
    ans=(ans+val)%mod;
    for(ll i=0;i<len;i++){
        ll v=edge[u][i].v,x=edge[u][i].x,y=edge[u][i].y;
        if(v==fa) continue;
        dfs2(v,u,val*y%mod*inv[x]%mod); //等价变换公式
    }
}

void solve(){
    scanf("%lld",&n);
    for(ll i=1;i<n;i++){
        ll u,v,x,y; scanf("%lld%lld%lld%lld",&u,&v,&x,&y);
        ll gd=gcd(x,y);
        x/=gd,y/=gd;
        edge[u].push_back({v,x,y});
        edge[v].push_back({u,y,x});
    }
    dfs1(1,0);
    ll val_1=1;
    for(ll i=1;i<=cnt;i++){ //暴力得到节点1的值
        for(ll j=1;j<=mxned[i];j++){
            val_1=(val_1*prime[i])%mod;
        }
    }
    dfs2(1,0,val_1); //知道节点1的值，去dfs2其他节点
    printf("%lld\n",ans);

    ans=0;
    for(ll i=1;i<=cnt;i++) ned[i]=mxned[i]=0;
    for(ll i=1;i<=n;i++) edge[i].clear();
}

int main(){
    init();
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}

E. Arithmetic Operations

题意：长度为n的序列，变换多少次，可以使得任意$(2<=i<=n?1)$,满足$a[i+1]?a[i]=a[i]?a[i?1]$
思路：(典型的题意简单题目难)
我们发现最终序列一定会是一个等差数列，所以题目就变成了找原序列中最长等差子序列，$n>=1e5$数据较大不会找。
枚举小公差$(?300<=d<=300)$，用数组记录每个数字减去位置乘公差的值出现的次数，出现最多的次数就是在枚举范围内的最优解。
对于大公差，我们发现序列中不会出现特别多的满足条件的数$(1<=a[i]<=1e5)$。
$mp[i][j]$:以i结尾的为d的边有多长。
找出两种情况的最优值mx，就是原序列中最长等差子序列，答案也是n-mx

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n,ans,a[N],d=300;
int b[N*300];

int go(){
    int mx=0;
    for(int i=0;i<d;i++){
        for(int j=1;j<=n;j++){
            b[a[j]+(n-j)*i]++;
            mx=max(mx,b[a[j]+(n-j)*i]);
        }
        for(int j=1;j<=n;j++) b[a[j]+(n-j)*i]--;
    }

    map<int,int>mp[n+1];

    for(int i=1;i<=n;i++){
        for(int j=max(1,i-N/d);j<i;j++){
            int D=(a[i]-a[j])/(j-i);
            int r=(a[i]-a[j])%(j-i);
            if(D>=d&&!r){
                mp[i][D]=max(mp[i][D],mp[j][D]+1);
                mx=max(mx,mp[i][D]+1);
            }
        }
    }
    return mx;
}

void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    ans=go();
    reverse(a+1,a+n+1);
    ans=max(ans,go());
    printf("%d\n",n-ans);
}

int main(){
    int T=1;
    while(T--) solve();
    return 0;
}