C. Three Circuits
首先显然需要有欧拉回路，即所有点度数都是偶数。
假如有 $6$ 度的点或者超过两个 $4$ 度点一定合法。如果不到两个 $4$ 度点就不合法。
当有两个 $4$ 度点时，考虑是否连成两个环，直接删去一个 $4$ 度点后判是否连通即可。
复杂度 $O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<iostream>
#include<cstdio>
#include<cstring>
#define N 200010
using namespace std;
int f[N];
int find(int x){return f[x]==x?f[x]:(f[x]=find(f[x]));}
int x[N],y[N],d[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d",&x[i],&y[i]),d[x[i]]++,d[y[i]]++;
for(int i=1;i<=n;i++) if(d[i]&1){puts("No");return 0;}
for(int i=1;i<=n;i++) if(d[i]>4){puts("Yes");return 0;}
int c=0;
for(int i=1;i<=n;i++) if(d[i]==4) c++;
if(c>2){puts("Yes");return 0;}
if(c<2){puts("No");return 0;}
for(int i=1;i<=n;i++) if(d[i]==4){c=i;break;}
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++) if(x[i]!=c && y[i]!=c) f[find(x[i])]=find(y[i]);
int d=find(c==1?2:1);
for(int i=1;i<=n;i++) if(i!=c && find(i)!=d){puts("Yes");return 0;}
puts("No");
return 0;
}
|
D. Rotation Sort
可以发现 $1$ 操作本质上是将一个数往右插，$2$ 就是把一个数往左插。
从左往右处理，考虑一个数如果向右插，等同于将其扔掉（直接计入答案）。所以考虑维护一个上升的序列表示没有向右插的集合。显然只要记录这个序列的最大值即可。
用 $f_{i,j}$ 表示前 $i$ 个数，上升序列最大值为 $j$ 的最小代价。
考虑新加数为 $x$，如果 $x>j$ 那么可以向右插或者加入序列。如果 $x<j$ 就只能向左插入序列。
复杂度 $O(n^2)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<iostream>
#include<cstdio>
#include<cstring>
#define N 5010
#define ll long long
using namespace std;
ll f[N][N];
int p[N];
void chkmin(ll &x,ll y){x=min(x,y);}
int main()
{
int n,a,b;
scanf("%d%d%d",&n,&a,&b);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
{
if(p[i]<j) chkmin(f[i][j],f[i-1][j]+b);
else chkmin(f[i][j],f[i-1][j]+a),chkmin(f[i][p[i]],f[i-1][j]);
}
ll ans=1e16;
for(int i=1;i<=n;i++) ans=min(ans,f[n][i]);
printf("%lld\n",ans);
return 0;
}
|
E. Modulo Pairing
显然只有两种可能：相加不超过 $M$ 与超过 $M$。
考虑先将原序列排序，可以证明，一定存在一个分界线，满足分界线左边右边各自首尾匹配。具体证明分类讨论一下即可。
右边部分显然要所有匹配 $>m$，而右边和显然是单减的，所以可以二分。
总复杂度 $O(n\log n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200010
#define ll long long
using namespace std;
int a[N],n,m,ans=2e9;
bool check(int x)
{
for(int i=1;2*x+2*i<=2*n;i++) if(a[2*x+i]+a[2*n-i+1]<m) return false;
return true;
}
void upd(int x)
{
int res=0;
for(int i=1;i<=x;i++) res=max(res,(a[i]+a[2*x-i+1])%m);
for(int i=1;2*x+2*i<=2*n;i++) res=max(res,(a[2*x+i]+a[2*n-i+1])%m);
ans=min(ans,res);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=2*n;i++) scanf("%d",&a[i]);
sort(a+1,a+2*n+1);
int l=0,r=n;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) upd(mid),r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}
|
F. One Third
考虑距离 $\frac 13$ 最近很难做，如果将序列每 $\frac 13$ 分成一块并且映射到一起，可以发现任意两个不同色的点之间距离就是到 $\frac 13$ 的距离。
这样转化为 $n$ 个点之间的不同色点距离最小值。
考虑一个式子：
$$
E(L_{k})=\frac 1n\left(\sum_{0<i<k}\frac 1{n-i}\right)
$$
其中 $L_{k}$ 表示第 $k$ 小的距离。具体证明可以用 min-max 容斥然后随便推一推。
这样枚举 $n$ 个点之间第 $k$ 对相邻点是第一对不同色点，那么前 $k$ 对一定是同色点，有：
$$
ans=\frac 1{3n}\sum_{i=1}^n\left(\frac{1}{3^{i-1}}-\frac{1}{3^i}\right)\sum_{j<i}\frac1{n-i}
$$
直接处理即可，复杂度 $O(n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<iostream>
#include<cstdio>
#include<cstring>
#define N 1000010
#define mod 1000000007
using namespace std;
int ksm(int a,int b=mod-2)
{
int r=1;
for(;b;b>>=1)
{
if(b&1) r=1ll*r*a%mod;
a=1ll*a*a%mod;
}
return r;
}
int _3[N];
int main()
{
int n;
scanf("%d",&n);
_3[1]=ksm(3),_3[0]=1;
for(int i=2;i<n;i++) _3[i]=1ll*_3[i-1]*_3[1]%mod;
int ans=0,res=ksm(n);
for(int i=1;i<=n;i++)
{
ans=(ans+1ll*(_3[i-1]-_3[i])%mod*res)%mod;
res=(res+ksm(n-i))%mod;
}
printf("%lld\n",1ll*ans*ksm(3*n)%mod);
return 0;
}
|