526互联

Codeforces Round 867 (Div. 3)

发布时间 2023-04-27 20:28:18作者: bible_w

Codeforces Round 867 (Div. 3)

A - TubeTube Feed

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=50+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int q,n,t,a[N],b[N];

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>q;
    while(q--){
        cin>>n>>t;
        for(int i=1;i<=n;++i)cin>>a[i];
        for(int i=1;i<=n;++i)cin>>b[i];
        int s=0,ma=0,p=-1;
        for(int i=1;i<=n;++i){
            if(s+a[i]<=t){
                if(b[i]>ma){
                    ma=b[i];p=i;
                }
            }
            s++;
        }
        cout<<p<<'\n';
    }
    return 0;
}
View Code

 

B - Karina and Array

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

ll t,n,a[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;++i)cin>>a[i];
        sort(a,a+n);
        ll x=a[0]*a[1],y=a[n-1]*a[n-2];
        cout<<max(x,y)<<'\n';
    }
    return 0;
}
View Code

 

C - Bun Lover

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

ll t,n;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        ll s=n*n+2*n+2;
        cout<<s<<'\n';
    }
    return 0;
}
View Code

 

D - Super-Permutation

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int t,n;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        if(n==1)cout<<1<<'\n';
        else if(n%2)cout<<-1<<'\n';
        else{
            int l=n,r=1,p=n/2;
            while(p--){
                cout<<l<<' ';l-=2;
                cout<<r<<' ';r+=2;
            }cout<<"\n";
        }
    }
    return 0;
}
View Code

 

E - Making Anti-Palindromes

思路：分类讨论，奇数和某种字母个数超过n/2的不行，否则交换有两种：a.回文对与回文对，b.回文对与非回文对；显然优先进行a；

判断回文对中出现次数的最大值ma，若ma大于总回文对数的一半，则交换ma次，否则直接回文对两两互换，交换总回文对数/2（上取）

 

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;

int t,n,a[30],b[30];
string s;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--) {
        cin>>n;
        cin>>s;
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
        int ma=0,cnt=0,mma=0;
        if(n%2)cout<<-1<<'\n';
        else{
            for(int i=0;i<n;++i){
                a[s[i]-'a']++;
                ma=max(ma,a[s[i]-'a']);
                if(i<n/2){
                    if(s[i]==s[n-i-1]){
                        cnt++;
                        b[s[i]-'a']++;
                        mma=max(mma,b[s[i]-'a']);
                    }
                }
            }
            if(ma>n/2)cout<<-1<<'\n';
            else{
                int s=max(mma,(int)ceil(1.0*cnt/2));
                cout<<s<<'\n';
            }
        }
    }
    return 0;
}
View Code

 

F - Gardening Friends

思路：找到直径的两端点p，q，根节点到树上任意一点的最远路径一定过p或q，求出1，p，q到每个点最短路即可算出最大收益

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e6,S=1e6;

const double eps=1e-6;
typedef long long ll;
ll t,n,k,c;

auto bfs(vector<vector<int>>ve,int u){
    vector<ll>d(n+1,-1);
    queue<int>q;
    q.push(u),d[u]=0;
    while(q.size()){
        int v=q.front();q.pop();
        for(auto w:ve[v]){
            if(d[w]!=-1)continue;
            d[w]=d[v]+1;q.push(w);
        }
    }
    return d;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>k>>c;
        vector<vector<int>>ve(n+1);
        for(int i=0,x,y;i<n-1;++i){
            cin>>x>>y;
            ve[x].push_back(y),ve[y].push_back(x);
        }
        auto d1=bfs(ve,1);
        int p= max_element(d1.begin(),d1.end())-d1.begin();
        auto d2=bfs(ve,p);
        int q=max_element(d2.begin(),d2.end())-d2.begin();
        auto d3=bfs(ve,q);
        ll res=0;
        for(int i=1;i<=n;++i){
            res=max(res,max(d2[i],d3[i])*k-d1[i]*c);
        }
        cout<<res<<'\n';
    }
    return 0;
}
View Code

 

G1 - Magic Triples (Easy Version)

思路：ai，aj=b*ai，ak=b*b*ai，枚举ai和b可以求出总个数，b的范围为1e3

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-6;
typedef long long ll;
ll t,n,cnt[N];
int main(){
    cin>>t;
    while(t--){
        set<ll>se;
        ll x;
        cin>>n;
        for(int i=0;i<n;++i){
            cin>>x;
            se.insert(x);cnt[x]++;
        }
        ll res=0;
        for(auto v:se){
            if(cnt[v]>=3)res+=(cnt[v]*(cnt[v]-1)*(cnt[v]-2));
            for(int b=2;b*b*v<=*se.rbegin();++b){
                res+=(cnt[v]*cnt[v*b]*cnt[v*b*b]);
            }
        }
        for(auto v:se)cnt[v]=0;
        cout<<res<<'\n';
    }
    return 0;
}
View Code

 

G2 - Magic Triples (Hard Version)

思路：可以枚举aj，那么 ai=aj/b，aj，ak=aj*b，ai和b为aj的因子，那就枚举aj所有因子，复杂度为aj开根号，暴力枚举会超；

方法：当aj<S，枚举因子，否则暴力枚举，可知当S取1e6时，复杂度为1e3

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e6,S=1e6;

const double eps=1e-6;
typedef long long ll;
int t,n;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        map<ll,ll>cnt;

        for(int i=0;i<n;++i){
            ll x;
            cin>>x;
            cnt[x]++;
        }
        ll res=0;
        for(auto [x,y]:cnt){
            res+=y*(y-1)*(y-2);
            if(x<S){
                vector<ll>f;
                for(int i=1;i<=x/i;++i){
                    if(x%i)continue;
                    f.push_back(i);
                    if(x/i!=i)f.push_back(x/i);
                }
                for(auto v:f){
                    if(v==1)continue;
                    if(v*x>cnt.rbegin()->first)continue;
                    if(cnt.count(x/v)&&cnt.count(x*v))
                        res+=cnt[x/v]*cnt[x*v]*y;
                }
            }
            else{
                for(int b=2;b*x<=cnt.rbegin()->first;++b){
                    if(x%b==0&&cnt.count(x/b)&&cnt.count(x*b))
                        res+=cnt[x/b]*cnt[x*b]*y;
                }
            }
        }
        cout<<res<<'\n';

    }
    return 0;
}
View Code