test20191031

发表于

闲扯

今天的题除了 $T3$ 不是很难的样子。

但是为什么 $T2$ 貌似 $O(n^3\log n)$ 的跑的比 $O(n^3)$ 快啊。。

题面

题面

$T1$

Solution

根据题目描述，我们可以知道一件事：如果存在一个单调下降的序列，那么最后剩下的一定是最后一个数。

然后这道题就完了，在个数之前放一个单调下降的序列，最后判断填完没有就行。

Code

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
 const int MAXN = 3e5+5;
 int n,m,k,rest,now,val[MAXN],ans[MAXN];
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),read(k),rest=n-k;
	for(ri i=1;i<=k;++i) read(val[i]);
	for(ri i=1;i<=k;++i){
		int lim=min(rest,m-val[i]);
		for(ri j=1,a=m;j<=lim;++j,--a) ans[++now]=a,--rest;
		ans[++now]=val[i];
	}
	if(now==n){
		puts("Yes");
		for(ri i=1;i<=n;++i) print(ans[i]),putchar(' ');
	}
	else puts("No");
	return 0;
}

$T2$

Solution

首先，我们可以确定的是 $k$ 具有单调性，所以我们可以用二分。

二分+玄学

然后我们就有了一个二分的做法，然后想怎么判断是否合法。

我们直接循环多次，每次判断所有的还没有加入的边能否被加入，如果可以就加入，且端点的度数加 $1$ 。

如果这一轮一条边都没有加入，那么我们就 $break$ 掉，判断是否加入了所有的边即可。

这么做的时间复杂度是玄学的，但是实测比 $O(n^3)$ 的快了 $10$ 倍。

$O(n^3)$ 的正常做法

这道题还有一个复杂度稳定的做法。

我们要找的是最大的 $k$ ，考虑从大到小考虑每一个 $k$ 。

将能够选择的边加入一个队列中，每次取出一条边，将端点 $u,v$ 的度数加 $1$ ，然后看 $u,v$ 能不能向外拓展。

当所有边都已经加入之后，当前的枚举的 $k$ 就是答案。

Code

二分+玄学

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 505;
int n,m,u,v,deg[MAXN],cnt[MAXN];
char lt[MAXN][MAXN],tr[MAXN][MAXN];
inl bool check(int lim){
	memcpy(tr,lt,sizeof(tr));
	memcpy(cnt,deg,sizeof(cnt));
	while(1) {
		char fla=0;
		for(ri i=1;i<n;++i)
			for(ri j=i+1;j<=n;++j)
				if(!tr[i][j]&&cnt[i]+cnt[j]>=lim)
					tr[i][j]=tr[j][i]=1,++cnt[i],++cnt[j],fla=1;
		if(!fla) break;
	}
	for(ri i=1;i<=n;++i) if(cnt[i]!=n-1) return false;
	return true;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=m;++i) read(u),read(v),++deg[u],++deg[v],lt[u][v]=lt[v][u]=1;
	ri l=0,r=2*n;
	while(l<r){
		if(check(mid+1)) l=mid+1;
		else r=mid;
	}
	print(l);
	return 0;
}

$O(n^3)$

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 505;
int n,m,deg[MAXN],u,v,cnt;
char mp[MAXN][MAXN];
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
queue<pii> q;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m);
	for(ri i=1;i<=m;++i) read(u),read(v),mp[u][v]=mp[v][u]=1,++deg[u],++deg[v],++cnt;
	for(ri ans=2*n;ans>=0;--ans){
		for(ri i=1;i<n;++i)
			for(ri j=i+1;j<=n;++j)
				if(!mp[i][j]&&deg[i]+deg[j]>=ans)
					q.push(mk(i,j)),mp[i][j]=mp[j][i]=1;
		while(!q.empty()){
			pii tmp=q.front();q.pop();
			u=tmp.first,v=tmp.second;
			++cnt,++deg[u],++deg[v];
			for(ri i=1;i<=n;++i) if(i!=u&&!mp[i][u]&&deg[i]+deg[u]>=ans) q.push(mk(u,i)),mp[i][u]=mp[u][i]=1;
			for(ri i=1;i<=n;++i) if(i!=v&&!mp[i][v]&&deg[i]+deg[v]>=ans) q.push(mk(v,i)),mp[i][v]=mp[v][i]=1;
		}
		if(cnt==(n-1)*n/2){print(ans);break;}
	}
	return 0;
}