CF#692 div2

缺乏、安全感 2022-12-29 06:47 140阅读 0赞

A 从后往前找连续)最长长度判断是否大于n/2即可

B 一个数字只会出现1-9，而1-9的最小公倍数为7560 所以你最多自增7560个数后必能找到符合条件的数，所以暴力模拟即可

C 因为m小于n所以必能找到符合条件的，我们想想后会发现一些规律

出现的点分为这几种情况：

1.本身就在斜对角线上，无需挪动，不管他就好

2.几个点互为环的情况例如 2,3 3,4, 4,5 5,2 这样得吧一个点换到空行去，然后....（不会讲了，反正这种情况步数是5,（环长度+1））

3.几个点为链情况 2,3 3,4 4,5 5,6 这样步数为4（链长度）（一个点也算链）

那么很明显，先连边建图，再找每条链长度，每个环大小即可

代码如下（还是建议你们想通了自己写，我的码风....一言难尽）

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e5+107;
    #define int ll
    vector<int>son[N];
    int hang[N];
    int lie[N];
    pair<int,int>a[N];
    int vis[N];///标记跑过的点
    void solve()
    {
        int n,m;
        cin>>n>>m;
       for(int i=1;i<=n;i++) hang[i]=lie[i]=0;
        for(int i=1;i<=m;i++)
        {
            son[i].clear();
            vis[i]=0;
            cin>>a[i].first>>a[i].second;
            if(a[i].first==a[i].second) {vis[i]++;continue;}
            lie[a[i].second]=i;
            hang[a[i].first]=i;
        }
        for(int i=1;i<=n;i++)
        {
           if(hang[i]&&lie[i])
            {
                int a1=hang[i],a2=lie[i];
                son[a1].push_back(a2);
                son[a2].push_back(a1);
            }
        }
        /*for(int i=1;i<=m;i++)
        {
            cout<<i<<':';
            for(int j=0;j<son[i].size();j++) cout<<son[i][j]<<' ';cout<<endl;
        }*/
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            if(vis[i]) continue;
            vis[i]++;
            if(son[i].size()==0) {ans++;continue;}///链只有一个点情况
               int d=son[i][0];
               int cnt=1;
               int last=i;
               while(d!=i)
               {
                   vis[d]++;cnt++;
                   if(son[d].size()==1)
                    break;
                   if(son[d][0]==last)
                       last=d,
                       d=son[d][1];
                   else
                    last=d,d=son[d][0];
    
               }
              if(d==i) ans+=cnt+1;///环
              else///链
              {
                  if(son[i].size()==2)///当前点不为链端点
                  {
                      d=son[i][1];
                      last=i;
                       while(d!=i)
                        {
                   vis[d]++;cnt++;
                   if(son[d].size()==1)
                    break;
                   if(son[d][0]==last)
                       last=d,
                       d=son[d][1];
                   else
                    last=d,d=son[d][0];
    
                        }
                  }
                  ans+=cnt;
              }
        }
        cout<<ans<<endl;
    }
    signed main()
    {
        int zs;
        cin>>zs;
        while(zs--)
        solve();
    }
    /*
    1
    5 4
    4 5
    5 1
    2 2
    3 3
    */

D 看了题解，最优的结果是所有的?前部分全为0后部分全为1或全部分全为1后部分全为0，但是我不知道为什么这样就对了，前缀和维护，枚举第几个？开始，找最小ans就完事了。