当前位置：首页 > article >正文

CF补题第二天

article 2024/9/29 7:49:52

题1

先来一道最短路热身

题目描述：

思路：第一眼SPFA，结果直接超时，正解思路：每一条边只走一次，那么我们找出不同的连通块，然后拓扑排序求最短路（因为无环），拓扑排序时对于每个连通块内部跑dij

代码如下：

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=26000,M=3*1e6+10,INF=0x3f3f3f3f;
typedef pair<int,int> PII;

int h[N],e[M],ne[M],idx,w[M];

int id[N],vis[N];
vector<int>block[N];
int in[N];
int dist[N];
queue<int>q;
int cnt;
void add(int a, int b, int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u, int cnt){
    id[u]=cnt;
    block[cnt].push_back(u);
    for(int i=h[u]; ~i; i=ne[i]){
        int v=e[i];
        if(id[v])continue;
        dfs(v,cnt);
    }
}

void dij(int u){
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    for(auto v:block[u])heap.push({dist[v],v});

    while(!heap.empty()){
        auto [x,y]=heap.top();
        heap.pop();
        if(vis[y])continue;
        vis[y]=true;
        for(int i=h[y]; ~i; i=ne[i]){
            int v=e[i];
            int val=w[i];
            if(id[y]!=id[v] && --in[id[v]]==0)q.push(id[v]);
            if(dist[v]>dist[y]+val){
                dist[v]=dist[y]+val;
                if(id[y]==id[v]){
                    heap.push({dist[v],v});
                }
            }
        }
    }
}

void topsort(int s){
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;
    for(int i=1; i<cnt; i++){
        if(!in[i])q.push(i);
    }

    while(!q.empty()){
        int t=q.front();
        q.pop();
        dij(t);
    }
}


int main(){
    memset(h,-1,sizeof h);
    int n,num1,num2,s;
    cin>>n>>num1>>num2>>s;

    for(int i=0; i<num1; i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);add(b,a,c);
    }
    cnt=1;
    for(int i=1; i<=n; i++){
        if(!id[i]){
            dfs(i,cnt);
            cnt++;
        }
    }

    while(num2--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        in[id[b]]++;
    }

    topsort(s);
    for(int i=1; i<=n; i++){
        if(dist[i]>=INF/2)cout<<"NO PATH"<<endl;
        else cout<<dist[i]<<endl;
    }
}

题2

题目链接：https://codeforces.com/contest/2019/problem/C

思路：贪心O(1)check，如果avg>=mx，那么差值最多为1，否则至少补偿len*mx-sum；

代码如下：

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using namespace std;
void solve() {
    int n;
    i64 k;
    cin>>n>>k;
    i64 maxnum=0;
    i64 sum=0;
    for(int i=0; i<n; i++){
        i64 t;
        cin>>t;
        sum+=t;
        maxnum=max(maxnum,t);
    }
    int ans=1;
    for(int len=1; len<=n; len++){
        i64 avg=(sum+len-1)/len;
        if(avg>=maxnum && k>=(avg*len-sum)){
            ans=len;
        }
        else if(avg<maxnum && k>=maxnum*len-sum)ans=len;
    }
    cout<<ans<<endl;
}

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

题3

题目链接：https://codeforces.com/contest/2019/problem/E

思路：实际上是考虑一个点的贡献，然后前缀优化O(n)处理。剩下的就是跑树而已；

代码如下：

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using namespace std;
void solve() {
    int n;
    cin>>n;
    vector<int>e[n+1];
    vector<int>dep(n+1,0),deps(n+2,0),lastdep(n+1,0),sum(n+2,0);
    vector<int>siz(n+1,0);
    for(int i=0; i<n-1; i++){
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    
    function<void(int,int)> dfs=[&](int u, int fa)->void{
        siz[u]=1;
        for(auto v:e[u]){
            if(v==fa)continue;
            dfs(v,u);
            siz[u]+=siz[v];
        }
    };
    int maxlen=0;
  function<void(int,int)> dfs1=[&](int u, int fa)->void{
        dep[u]=dep[fa]+1;
        maxlen=max(maxlen,dep[u]);
        deps[dep[u]]+=siz[u]-1;
        lastdep[u]=dep[u];
        for(auto v:e[u]){
            if(v==fa)continue;
            dfs1(v,u);
            lastdep[u]=max(lastdep[v],lastdep[u]);
        }
        sum[lastdep[u]+1]++;
    };
    dfs(1,0);
    dfs1(1,0);
    for(int i=1; i<=n+1; i++){
        sum[i]+=sum[i-1];
    }
    int res=1e9;
    for(int i=1; i<=maxlen; i++){
        //cout<<deps[i]<<endl;
        res=min(res,deps[i]+sum[i]);
    }
    cout<<res<<endl;
    
}

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

题4

题目链接：https://codeforces.com/contest/2019/problem/D

思路：预处理左右最短时间，枚举每个点，暴力check

代码如下：

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using namespace std;
const int inf=1e9;
void solve() {
    int n;
    cin>>n;
    vector<int>a(n+2);
    for(int i=1; i<=n; i++)cin>>a[i];
    vector<pair<int,int>>l(n+2);
    vector<pair<int,int>>r(n+2);
    l[1]={inf,0};
    r[n]={inf,n+1};
    for(int i=2; i<=n; i++){
        int dis=l[i-1].first;
        if(dis>a[i-1]){
            l[i]={a[i-1],i-1};
        }else l[i]=l[i-1];
    }
    for(int i=n-1; i>=1; i--){
        int dis=r[i+1].first;
        if(dis>a[i+1]){
            r[i]={a[i+1],i+1};
        }else r[i]=r[i+1];
    }
    auto check=[&](int mid)->bool{
        int lp=mid,rp=mid;
        int times=1;
        while(true){
            if(times==n){
                break;
            }
            if(l[lp].first<r[rp].first ){
                times+=lp-l[lp].second;
                if(times>l[lp].first)return false;
                lp=l[lp].second;
            }
            else{
                times+=r[rp].second-rp;
                if(times>r[rp].first)return false;
                rp=r[rp].second;
            }
        }
        return true;
        
    };
    int ans=0;
    for(int i=1; i<=n; i++){
        if(check(i))ans++;
        //cout<<endl;
    }
    cout<<ans<<endl;
    
}

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

题5

题目链接：https://codeforces.com/contest/1996/problem/F

思路：实际上对于最大值，他一定是有某个数作为分割点，我们考虑二分这个数，如果这个数上面的res>k那么这个数一定小了,所以l=mid+1；否则r=mid；我们求出第一个res<=k的位置就是答案

代码如下：

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using namespace std;
const int inf=1e9;
void solve() {
    int n,k;;
    cin>>n>>k;
    vector<i64>a(n),b(n);
    i64 mx=0;
    for(int i=0; i<n; i++){
        cin>>a[i];
        mx=max(mx,a[i]);
    }
    for(int i=0; i<n; i++){
        cin>>b[i];
    }
    i64 l=0,r=mx;
    i64 sum=0;
    auto check=[&](i64 mid)->bool{
        i64 cnt=0;
        i64 res=0;
        for(int i=0; i<n; i++){
            if(a[i]>=mid){
                i64 t=(a[i]-mid+b[i]-1)/b[i];
                res+=t;
                cnt+=((a[i]-mid)%b[i]==0);
            }
        }
        return k>=res;
    };
    while(r>l){
        i64 mid=l+r>>1;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    i64 mid=l;
    i64 cnt=0;
    i64 res=0;
//cout<<mid<<endl;
    for(int i=0; i<n; i++){
        if(a[i]>=mid){
            i64 t=(a[i]-mid+b[i]-1)/b[i];
            res+=t;
            cnt+=((a[i]-mid)%b[i]==0);
            sum+=t*a[i]-(t-1)*t/2*b[i];
        }
    }
    sum+=(k-res)*l;
    cout<<sum<<endl;
    
}

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

总结：思路看起来很简单，但是我自己想却需要想1h左右，这是打CF的第30天，分数现在为1278，下一个月再接再励，先上1600。后面也会记录我在工程方面的学习。当然这些总结只是对我自己而写的。

查看全文

http://www.kler.cn/news/324312.html