526互联

Codeforces Round 911 (Div. 2)

发布时间 2023-12-04 19:06:16作者: zfxyyy

Codeforces Round 911 (Div. 2)

A. Cover in Water

，，，mc无限水

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

void solve(){
    int n;
    string s;
    cin>>n>>s;
    s = " " + s + " ";
    int cnt=0;
    for(int i=2;i<=n-1;i++){
        if(s[i]=='.'&&s[i-1]=='.'&&s[i+1]=='.'){
            cout<<2<<endl;
            return;
        }
        if(s[i]=='.') cnt++;
    }
    if(n!=1)cnt+=(s[1]=='.')+(s[n]=='.');
    else    cnt+=(s[1]=='.');
    cout<<cnt<<endl;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--) solve();
}

B. Laura and Operations

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

void solve(){
    int a,b,c;
    vector<int> ans;
    cin>>a>>b>>c;
    int len=abs(b-c);
    if(len&1) ans.push_back(0);
    else      ans.push_back(1);
    len=abs(a-c);
    if(len&1) ans.push_back(0);
    else      ans.push_back(1);
    len=abs(a-b);
    if(len&1) ans.push_back(0);
    else      ans.push_back(1);
    for(auto u:ans) cout<<u<<" ";
    cout<<endl;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--) solve();
}

C

比B简单

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 3e5 + 10;
int l[N],r[N];
int len[N];
int n;
string s;
void dfs(int u){
    if(l[u]==0&&r[u]==0) return;
    if(s[u]=='L')     len[l[u]]=len[u],len[r[u]]=len[u]+1;
    else if(s[u]=='R')len[r[u]]=len[u],len[l[u]]=len[u]+1;
    else len[r[u]]=len[u]+1,len[l[u]]=len[u]+1;
    if(l[u]!=0) dfs(l[u]);
    if(r[u]!=0) dfs(r[u]);
}
void solve(){
    cin>>n;
    cin>>s;
    s = " " + s;
    vector<int> leaf;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
        if(l[i]==0&&r[i]==0) leaf.push_back(i);
    }
    len[1]=0;
    dfs(1);
    int ans=1e18;
    for(auto u:leaf) ans=min(ans,len[u]);
    cout<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--) solve();
}

D

有种再写一遍又不会写的感觉。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;
int a[N];
int n;

void solve(){

    vector<vector<int>> factor(N+10);
    for(int i=1;i<=N;i++)
        for(int j=i;j<=N;j+=i)
            factor[j].push_back(i);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);

    vector<vector<int>> c(N+10);
    for(int i=1;i<=n;i++)
        for(auto u:factor[a[i]])
            c[u].push_back(n-i);

    vector<int> f(N+10);
    vector<int> g(N+10);
    for(int i=1;i<=N;i++)
        for(int j=0;j<c[i].size();j++)
            f[i] += c[i][j]*j;
    int ans=0;
    for(int i=N;i>0;i--){
        g[i]=f[i];
        for(int j=i*2;j<=N;j+=i) g[i] -= g[j];
        ans += g[i]*i;
    }
    cout<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--) solve();
}

E

缩点+拓扑

md没有初始化G，找错找半天。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10;
vector<int> G[N];
int a[N];
int n,m;
int dfn[N] , low[N] ,dfs_clock;
bool vis[N];
int fa[N] , siz[N] , sum[N] , du[N];
int tot;
vector<pair<int,int>> dp(N);
vector<int> path;
void tarjin(int u){
    dfn[u]=low[u]=++dfs_clock;
    vis[u]=true;
    path.push_back(u);
    for(auto v:G[u]){
        if(!dfn[v]){
            tarjin(v);
            low[u]=min(low[v],low[u]);
        }else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        int y;
        tot++;
        do{
            y=path.back();
            path.pop_back();
            vis[y]=false;
            siz[tot]++;
            fa[y]  =  tot;
            sum[tot] += a[y];
        }while(y!=u);
    }
}

void solve(){
    dfs_clock=tot=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        dfn[i]=low[i]=0;
        sum[i]=du[i]=0;
        dp[i].first=dp[i].second=0;
        fa[i]=i;
        siz[i]=0;
        vis[i]=false;
        G[i].clear();	//这里害我卡了一个小时
    }
    vector<pair<int,int>> edge(m);
    for(auto &[u,v]:edge){
        cin>>u>>v;
        G[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjin(i);

    for(int i=1;i<=n;i++) G[i].clear();
    for(auto [u,v]:edge){
        if(fa[u]==fa[v]) continue;
        G[fa[u]].push_back(fa[v]);
        du[fa[v]]++;
    }

    queue<int> que;
    for(int i=1;i<=tot;i++){
        if(du[i]==0){
            que.push(i);
            dp[i].first=siz[i];
            dp[i].second=sum[i];
        }
    }
    while(que.size()){
        int u=que.front();que.pop();
        for(auto v:G[u]){
            if(dp[u].first+siz[v]>dp[v].first){
                dp[v].first=dp[u].first+siz[v];
                dp[v].second=dp[u].second+sum[v];
            }else if(dp[u].first+siz[v]==dp[v].first){
                dp[v].second=min(dp[u].second+sum[v],dp[v].second);
            }
            if(--du[v]==0) que.push(v);
        }
    }
    int len=0;
    int all=0;
    for(int i=1;i<=n;i++){
        if(dp[i].first>len){
            len=dp[i].first;
            all=dp[i].second;
        }else if(dp[i].first==len)
            all=min(all,dp[i].second);
    }
    cout<<len<<" "<<all<<endl;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T=1;
	cin>>T;
	while(T--) solve();
}