写在前面

这是一次4.21的vjudge训练，打算认真做一次，出题还算可以不过有点慢，慢慢靠过题数达到了前方，E题我觉得是最难的但是20.12.31补过这个...我打算直接开F，没想到做了2h的F也没写出来，我用的双指针，指针移动的方式错误，我查不到数据，wa2的testcase721...
比赛链接：Dashboard - Codeforces Round #686 (Div. 3) - Codeforces

A - Special Permutation（思维+构造）

题意

给你一个长度为$n$的序列，让你输出任意一个排列，满足：$i\neq p_i$，也就是说第$i$位不能是$i$

思路

每次$2 1 4 3 6 5...$这样错一位构造，但是如果最后是三个，需要调换三个顺序$9 7 8$，都需要换一下

我傻*了，实际上123456只需要移最后一个到前面来，变成612345就可以完全错位！

代码

inline void Case_Test()
    {
        cin>>n;
        int res=n;cnt=1;
        while (res>3)
        {
            res-=2;
            cout<<cnt+1<<" "<<cnt<<" ";
            cnt+=2;
        }
        if (res==3) cout<<cnt+2<<" "<<cnt<<" "<<cnt+1<<endl;
        else cout<<cnt+1<<" "<<cnt<<endl;
    }

B - Unique Bid Auction（思维）

题意

给你一个长度为$n$的序列，问你最小的只出现一次的数位置是，如果没有输出-1

思路

直接拿map存，因为map是按key值从小到大排序，正好满足我需要的，所以这个时候就只要看第二个数，再用一个容器存一下位置就好，这个时候不用管位置是否会被覆盖，因为能输出的只会出现一次。

代码

map<int,int> mp,pos;
inline void Case_Test()
{
    mp.clear();
    pos.clear();
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        mp[x]++;
        pos[x]=i;
    }
    for (auto i:mp)
        if (i.second==1) 
        {
            cout<<pos[i.first]<<endl;
            return;
        }
    cout<<-1<<endl;
}

C - Sequence Transformation（思维）

题意

给你一个$n$的序列，每次操作可以删除一段不含该$x$的连续序列，问最后只剩下$x$的最少操作数是多少

思路

不难看出，对于多个$x$，就把序列分成了若干段，每段必须删除，所以我们拿个数组来需要来记录分成了多少段。
每次跟前一个比较，如果不相等的话说明a[i]需要多一次操作来删去前面的，注意用vis数组统计一下是否出现，答案肯定是要在出现里面选

代码

inline void Case_Test()
{
    cin>>n;
    ans=INF;
    for (int i=1;i<=n;i++) num[i]=vis[i]=0;
    for (int i=1;i<=n;i++) {cin>>a[i];vis[a[i]]=1;}
    for (int i=2;i<=n;i++)
        if (a[i]==a[i-1]) continue;
        else num[a[i]]++;
    for (int i=1;i<=n;i++)
        if (vis[i]&&a[n]!=i) num[i]++;//出现过，且要删除到最后
    for (int i=1;i<=n;i++)
        if (vis[i])
            ans=Min(ans,num[i]);
    cout<<(ans==INF?0:ans)<<endl;
}

D - Number into Sequence（构造+数学）

题意

给你一个$n$，问你最多能写成满足要求的$k$个数的乘积，要求是从$2$开始，每个数是前一个数的倍数

思路

草稿打了一下，大胆猜测，发现只需要质因数分解，找到最大的那个质因数(假如有num个)，那么为了满足需求，输出前num-1个该质数，剩下的数输出最后一个。
例如:$x=2^3\times 3^5\times 5^2\times 11$，你会发现有$5$个3，所以前面输出$3,3,3,3,$最后输出剩下的$x'=2^3\times 3^1\times 5^2\times 11$即可。

代码

代码很丑

inline int divide(int n)
{
    int num = 0,res=0,ans;
    int x=n;
    while (x%2==0)
    {
        res++;
        x/=2;
    }
    num=res;res=0;ans=2;
    for (int i=3;i*i<=x;i+=2)
    {
        if (x%i==0)
        {
            res=0;
            while (x%i==0)
            {
                res++;
                x/=i;
            }
            if (res>num)
            {
                num=res;
                ans=i;
            }
        }
    }
    if (x>1)
    {
        if (1>num) num=1,ans=x;
    }
    if (num>1) return ans;
    else return 0;
}//时间复杂度O(sqrt(n))
inline void Case_Test()
{
    cin>>n;
    int t=divide(n);//找满足最大的质因数
    if (t==0) {cout<<1<<endl<<n<<endl;return ;}
    vector<int> v;
    while (n%t==0)
    {
        v.push_back(t);
        n/=t;
    }
    n*=t;v.pop_back();
    if (n>1) v.push_back(n);
    cout<<v.size()<<endl;
    for (int i=0;i<v.size();i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

E - Number of Simple Paths（DFS)

忘记了，复制我当时的代码

#include<bits/stdc++.h>
using namespace std;
const int N = 200007;
int y,x,n,d[N],u,v;
unsigned long long num;
bool exist[N];
vector<int>G[N];
inline void dfs(int x)
{
    num++;
    for (int i=0;i<G[x].size();i++)
    {
        int y=G[x][i];
        if (exist[y]) continue;
        exist[y]=1;
        dfs(y);
    }
}
inline void solve()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        exist[i]=1;d[i]=0;G[i].clear();
    }
    for (int i=1;i<=n;i++)
    {
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
        d[u]++;d[v]++;
    }
    queue<int> Q;
    for (int i=1;i<=n;i++)
        if (d[i]==1) Q.push(i);
    while (!Q.empty())
    {
        u=Q.front();Q.pop();
        if (exist[u]==0) continue;
        exist[u]=0;
        for (int i=0;i<G[u].size();i++)
        {
            v=G[u][i];
            if (exist[v]==1&&d[v]>=2)
            {
                d[v]--;
                if (d[v]==1) Q.push(v);
            }
        }
    }
    unsigned long long ans=(unsigned long long)n*(n-1);
    for (int i=1;i<=n;i++)
    {
        if (exist[i]==1)
        {
            num=0;
            dfs(i);
            ans-=num*(num-1)/2;
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while (T--)
    {
        solve();
    }
    return 0;
}