Refact.ai Match 1 (Codeforces Round 985) 总结

A

集合中的元素为 \(l \le x \le r\)，有 \(k\) 个 \(x\) 的倍数在其中才可删，可以求出最大可删的元素，直接计算。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1;
ll l,r,k;
void solve()
{
    cin>>l>>r>>k;
    r=r/k;
    cout<<max(0ll,r-l+1)<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

B

思考一下，发现我们并不关心 \(0\) 和 \(1\) 的顺序，只关心数量，只要同时有 \(0\) 和 \(1\) 就能进行操作，这样模拟过程即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1e5+5;
int n;
string s,r;
int a[2];
void solve()
{
	cin>>n>>s>>r;
	a[0]=a[1]=0;
	for(int i=0;i<n;i++) a[s[i]-'0']++;
	for(int i=0;i<n-1;i++)
	{
		if(a[0]&&a[1])
		{
			a[0]--,a[1]--;
			a[r[i]-'0']++;
		}
		else 
		{
			cout<<"No\n";
			return ;
		}
	}
	cout<<"Yes\n";
}
int main ()
{
	#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif 
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

C

首先要明确一点，更大的初始值在通过几场比赛后的评分一定不劣于更小的初始值。

答案的范围显然为 \([1,n-1]\)，计算最大的可能评分，考虑二分答案。
如何检验？设 \(b_i\) 为通过前 \(i\) 场比赛能获得的评分，再取前缀最大值。检验的时候从后往前扫，逆过程当 \(x=a_i\) 时能有三种情况，显然我们要令 \(x\) 更小，所以当 \(x \le a_i\) 时，\(x\) 要减一，否则加一。若此时 \(b_{i-1}>=x\)，则说明前缀中出现了大于等于能达到答案的最小的评分的值，返回真。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n;
int a[N],b[N];
bool check(int k)
{
    int x=k;
    for(int i=n;i>=1;i--)
    {
        if(b[i-1]>=x) return 1;
        if(a[i]>=x) x--;
        else x++;
    }
    return 0;
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n==1)
    {
        cout<<0<<'\n';
        return ;
    }
    int x=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>x) x++;
        else if(a[i]<x) x--;
        b[i]=max(b[i-1],x);
    }
    int l=1,r=n,mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(check(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<min(ans,n-1)<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

D

操作数最多为 \(2 \times \max(n,m)\)，可以考虑先将图全部拆了再建树。

对于每个度数大于 \(1\) 的点 \(x\)，选择于点 \(x\) 相邻的两个点 \(y\)，\(z\)，对 \((x,y,z)\) 进行一次操作，若 \(y\) 于 \(z\) 有边相连，则会减少 \(3\) 条边，否则会减少 \(1\) 条边。因此这样拆图的操作数最大为 \(m-1\)。

最终整个图就都是些度数小于等于 \(1\) 的点。也就是说，要么是单个点，要么是两个点连一条边。如果都是单个点显然就不用继续了，否则考虑其中一个度数为 \(1\) 的点为 \(x\)，与其相连的点为 \(y\)，接下来建的树以 \(x\) 为根。每次选择没合并进来的点 \(z\) 不管它的度数，对 \((x,y,z)\) 进行操作。此时 \(y\) 与 \(z\) 相连，\(z\) 与 \(x\) 相连，将 \(y\) 更新为 \(z\) 继续操作。每次至少能合并一个点，所以这个过程的操作数最大为 \(n-1\)。

考虑两个过程如何实现，第一个过程用 set 存边，可以轻易实现删边和加边。
第二个过程可以使用并查集，因为只有合并的操作。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=4e5+5;
int n,m;
set<int> s[N];
int deg[N];
struct node 
{
    int x,y,z;
}ans[M];
int tot;
void add(int x,int y)
{
    s[x].insert(y);
    s[y].insert(x);
}
void del(int x,int y)
{
    s[x].erase(y);
    s[y].erase(x);
}
int fa[N];
int find(int x)
{
    if(x==fa[x]) return x;
    return fa[x]=find(fa[x]);
}
void solve()
{
    cin>>n>>m;
    tot=0;
    for(int i=1;i<=n;i++) s[i].clear(),deg[i]=0,fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        deg[x]++,deg[y]++;
    }
    for(int i=1;i<=n;i++)
    {
        while(deg[i]>1)
        {
            auto it=s[i].begin();
            int x=*it;
            it++;
            int y=*it;
            del(x,i),del(y,i);
            deg[i]-=2;
            ans[++tot]={i,x,y};
            if(s[x].count(y))
            {
                del(x,y);
                deg[x]-=2;
                deg[y]-=2;
            }
            else add(x,y);
        }
    }
    bool st=0;
    int x,y;
    for(int i=1;i<=n;i++)
    {
        if(deg[i])
        {
            st=1;
            x=i,y=*s[i].begin();
            fa[find(x)]=find(y);
        }
    }
    if(st)
    {
        x=find(x);
        for(int i=1;i<=n;i++)
        {
            int z=find(i);
            if(z!=x)
            {
                ans[++tot]={x,y,z};
                y=z;
                fa[z]=x;
            }
        }
    }
    cout<<tot<<'\n';
    for(int i=1;i<=tot;i++) cout<<ans[i].x<<' '<<ans[i].y<<' '<<ans[i].z<<'\n';
}
int main ()
{
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}