写在前面
这是一次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;
}
F - Array Partition（ST表/线段树+二分 or 双指针）
题意
给你一个长度为$n$的序列，让你分成$3$段，请问是否存在第一段Max=第二段Min=第三段Max，如果有请输出这三段的长度，没有则输出NO
这里新建一个文章来写这道难度2100的题目