练习记录-cf-Codeforces Round 881 (Div. 3)A-F1-526互联

E是补的太蠢了没想到

期末考完的复健

A. Sasha and Array Coloring

题意：可以给不同数字涂上很多颜色，每个颜色的贡献是同一个颜色内的数字最大值和最小值的差

思路：排序一遍，取头和尾的差

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
int a[MAXN];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    int l=1,r=n;
    int sum=0;
    while(l<=r){
        sum+=a[r]-a[l];
        r--;l++;
    }
    cout<<sum<<"\n";
}
signed main(){
    int t;
    cin>>t;
    while(t--) 
    solve();
}

View Code

B. Long Long

题意：可以选某一段区间，改变它的正负性，求整个都是正的情况的改变次数

思路：遇到第一个负的标记，随后遇到第一个正的取消标记，遇到负的再标记标记次数就是答案

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int long long
void solve(){
    int n;cin>>n;
    int sum=0;
    int cnt=0;
    int flag=0;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        if(a<0&&flag==0) {
            flag=1;
            cnt++;
        }
        else if(a>0&&flag==1){
            flag=0;
        }
        if(a<0) sum+=(a*-1);
        else sum+=a;
    }
    cout<<sum<<" "<<cnt<<"\n";
}
signed main(){
    int t;cin>>t;
    while(t--) 
    solve();
}

View Code

C. Sum in Binary Tree

题意：给你一个点，求它到二分树顶点1的路径和

思路：这个树的性质是父节点是子节点/2 一直除就行了

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int long long
void solve(){
    int n;cin>>n;
    int sum=0;
    while(n){
        sum+=n;
        n/=2;
    }
    cout<<sum<<'\n';
}
signed main(){
    int t;cin>>t;
    while(t--)
    solve();
}

View Code

D. Apple Tree

题意：给你一棵树，从某两个节点掉下两个苹果，问调到树的叶子上的可能性组合（有序对）

思路:用树上dfs求出每个节点连通的叶子节点个数，查询时O（1）乘一下就行了

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int ll
vector<int> adj[MAXN];
int ans[MAXN];
void dfs1(int u,int fa){
    if(u!=1&&adj[u].size()==1) ans[u]=1;
    for(auto &v:adj[u]){
        if(v==fa) continue;
        dfs1(v,u);
        ans[u]=ans[u]+ans[v];
    }
}
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) adj[i].clear(),ans[i]=0;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(1,-1);
    int q;cin>>q;
    while(q--){
        int u,v;
        cin>>u>>v;
        cout<<ans[u]*ans[v]<<"\n";
    }
}
signed main(){
    close;
    int t;cin>>t;
    while(t--)
    solve();
}

View Code

E. Tracking Segments

题意：有一个线段，你会按照给定顺序（q）把上面某个位置变成1 给定一些标准子段，你需要求出在第几步变成1操作的时候刚好有第一个标准字段中的1的个数严格大于长度的1/2

思路：二分答案给定一个指定步数mid 先标记所有1 我们可以通过前缀和来求出x点前有几个1 于是我们知道此时是否有标准子段满足要求就是遍历所有子段，复杂度为O（m），算其长度和里面1个数即可因为要找这个分界点满足二分写一个二分查找第一个满足的点即可总复杂度O（mlog（q))

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
#define int ll
int n,m,q;
struct node{
    int l,r;
}N[MAXN];
int Q[MAXN];
int a[MAXN];
int pre[MAXN];
bool check(int mid){
    int flag=0;
    for(int i=1;i<=n;i++) a[i]=0,pre[i]=0;
    for(int i=1;i<=min(mid,q);i++) a[Q[i]]=1;
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+a[i];
    }
    for(int i=1;i<=m;i++){
        int l=N[i].l,r=N[i].r;
        if(pre[r]-pre[l-1]>((r-l+1)/2)) flag=1;
    }
    if(flag) return true;
    else return false;
}
void solve(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>N[i].l>>N[i].r;
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>Q[i];
    }
    int l=1,r=inf;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    if(l==inf||r==inf) cout<<"-1\n";
    else cout<<l<<"\n";
}
signed main(){
    close;
    int t;cin>>t; 
    while(t--)
    solve();
}

View Code

F1. Omsk Metro (simple version)

题意：题目会逐渐构建一棵树，然后询问树上一条路径u-v是否存在点权和为w的一段

f1只会问到树根的

思路：这个思路有点蠢，记录某个点从顶点过来的总的最大值，从上个点出发的最大值（上个点是负的就是0+w），以及同理最小值每次添加新点时更新总的Max和带上这个点的Nowmax 以及最小值查询时看看是否在范围就行了

//待更新

#include<bits/stdc++.h>
#define close     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll MAXN = 3e5+7;
const ll mod =1e9+7;
const ll inf =0x3f3f3f3f;
const ll INF =0x3f3f3f3f3f3f3f3f;
int a[MAXN];
vector<int> adj[MAXN];
int Min[MAXN],Max[MAXN],Nowmax[MAXN],Nowmin[MAXN];
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) a[i]=0,Min[i]=0,Max[i]=0,Nowmax[i]=0,Nowmin[i]=0;
    a[1]=1;Min[1]=0;
        Max[1]=1;
        Nowmax[1]=1;
        Nowmin[1]=0;
    int cnt=1;
    while(n--){
        char ch;cin>>ch;
        
        if(ch=='+'){
            cnt++;
            int u,w;cin>>u>>w;
            a[cnt]=w;
            Min[cnt]=min({0,w,Nowmin[u]+w,Min[u]});
            Max[cnt]=max({0,w,Nowmax[u]+w,Max[u]});
            Nowmax[cnt]=max({w,Nowmax[u]+w,0});
            Nowmin[cnt]=min({w,Nowmin[u]+w,0});
        }
        else{
            int u,v,w;
            cin>>u>>v>>w;
            if(w==0){
                cout<<"Yes\n";
                continue;
            }
            if(w<Min[v]||w>Max[v]) cout<<"No\n";
            else cout<<"Yes\n";
        }
    }
}
signed main(){
    close;
    int t;cin>>t;
    while(t--)
    solve();
}

View Code

感觉F2是树dp 晚点补补

cf-codeforces codeforces round 881

codeforces round 881 a-f

codeforces round 881 div

cf-codeforces codeforces round 909

codeforces round 888 a-f

codeforces round 874 a-f

codeforces round 889 a-f

cf-codeforces

round 881 div cf

educational codeforces round rated