7.16 模拟赛

, ,

7.16 模拟赛

T1. park

Description

$n\le 10^6$

1s 512MB

Solution

优先队列模拟。复杂度 $O(n\log n)$。

由于题目的特殊性，取值最多只有 $O(\log n)$ 个，大概可以 $O(n)$。

第一次指导优先队列的常数比 set 小很多。

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 10000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,m,a[maxn],ans;
const int inf=1e12;
struct node{
	int l,r;
	node(int a=0,int b=0) {l=a;r=b;}
	bool operator <(const node &x) const {return r-l==x.r-x.l?l<x.l:r-l>x.r-x.l;}
}b[maxn];
inline bool cmp(node x,node y) {return x.l<y.l;}
set<node>t; 
int head,tail;
signed main(void){
    freopen("park.in","r",stdin);
  	freopen("park.out","w",stdout);
	int i,j;
	read(n);read(m);
	for (i=1;i<=m;i++) read(a[i]);
	t.insert(node(0,n+1));
	for (j=1;j<=m;j++) {
		node tmp=*t.begin();t.erase(t.begin());
		int id=(tmp.r+tmp.l)/2;
		b[j].l=id,b[j].r=a[j];
		t.insert(node(tmp.l,id));
		t.insert(node(id,tmp.r));
	}
	b[m+1]=inf;b[0]=-inf;
	sort(b+1,b+1+m,cmp);
	for (j=1;j<=m;j++) if (min(b[j].l-b[j-1].l,b[j+1].l-b[j].l)<=b[j].r) ans+=1-min(b[j].l-b[j-1].l,b[j+1].l-b[j].l)+b[j].r;
	printf("%lld",ans); 
	return 0;
}

T2. monster

Description

image-20230717201205457$n\le 10^5,a,b\le 10^9$

1s 512MB

Solution

感觉很妙的一道题。

假设我们以此打了$(a_{p1},b_{p2}),(a_{p1},b_{p2}),(a_{p3},b_{p3}),…(a_{pn},b_{pn})$。初始血量为任意时刻血量最小值的相反数。

因此目标最大化 $\min\sum\limits_{j=1}^{i-1}(b_{pj}-a_{pj})-a_{i}$。假如先打 $(a_i,b_i)$，再打 $(a_j,b_j)$，根据最大化原则，我们可以合并两个点：

  • 若 $a_i<a_i-b_i+a_j$，则合并为 $(a_i-b_i+a_j,b_j) $
  • 若 $a_i\ge a_i-b_i+a_j$，则合并为 $(a_i,b_i-a_j+b_j)$

之后考虑选择进攻点的顺序，对于 $(a_i,b_i)$ 和 $(a_j,b_j)$：

  • 如果 $a_i\le b_i$ ，$a_j\ge b_j$ ，则优先 $i$
  • 如果 $a_i\le b_i,a_j\le b_j$，则优先 $a$ 小的
  • 如果 $a_i\le b_i,a_j\le b_j$ ，则优先 $b$ 大的

考虑用优先队列维护这个关系。

在树结构中，假设已经知道了 $x$ 的儿子 $y_1,y_2,…,y_k$ 的攻击序列，且儿子的攻击序列均已有序。

那么显然，$x$ 只需要把所有的攻击序列归并一下就完事了。

但是，此时需要在序列的最开头加入 $x$，可能会破坏原来的顺序。则 $x$ 依次合并比其小的点。说明攻击完 $x$ 后，马上攻击比 $x$ 还要优的怪。

写法上，启发式合并是 $O(n\log ^2n)$，可并堆是 $O(n\log n)$。下面代码实现的第一种。

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 100005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
struct node{
	int a,b;
	node(int x=0,int y=0) {a=x;b=y;}
	node operator +(const node &x) const {
		if (x.a>b) return node(a+x.a-b,x.b);
		else return node(a,b+x.b-x.a);
	}
	bool operator <(const node &x) const {
		int t1=a<=b,t2=x.a<=x.b;
		if (t1^t2) return t1;
		else if (t1) return a<x.a;
		else return b>x.b;
	}
	bool operator >(const node &x) const {
		return x<*this;
	}
}a[maxn]; 
int n;
priority_queue<node,vector<node>,greater<node> >q[maxn];
vector<int>to[maxn];
inline void dfs(int x,int pre) {
	for (auto y:to[x]) if (y^pre) {
		dfs(y,x);
		if (q[y].size()>=q[x].size()) q[x].swap(q[y]);
		while (!q[y].empty()) q[x].push(q[y].top()),q[y].pop();
	}
	while (!q[x].empty()&&q[x].top()<a[x]) {
		a[x]=a[x]+q[x].top(),q[x].pop();
	}
	q[x].push(a[x]);
}
signed main(void){
    freopen("monster.in","r",stdin);
  	freopen("monster.out","w",stdout);
	int i,x,y;
	read(n);
	for (i=2;i<=n;i++) read(a[i].a),read(a[i].b);
	for (i=1;i<n;i++) read(x),read(y),to[x].push_back(y),to[y].push_back(x);
	dfs(1,0);
	node ans=node(0,0);
	while (!q[1].empty()) ans=ans+q[1].top(),q[1].pop();
	printf("%lld",ans.a);
	return 0;
}

T3. monster

Description

P8511

Solution

观察到样例相同的答案很多。我们事先用 01trie 求出全局异或最大的点对 $x,y$。除了子树中包含 $x$ 或者 $y$ ，其余答案皆为这个最大值。具体的，就是 $x$ 和 $y$ 的祖先。这里是 $O(n\log w)$ 的。

之后只需要从根到 $x$ 依次暴力加入 $x$ 的祖先，求答案即可。$y$ 同理。这里同样是 $O(n\log w)$ 的。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 500005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
vector<int>to[maxn];
int root,cnt,n;
struct yyy{
	int ls,rs,siz;
}f[maxn*62];
const ll base=61,N=(1ll<<(base+1))-1;
ll a[maxn];
inline void insert(ll l,ll r,int &rt,ll k,int deep) {
	if (!rt) rt=++cnt,f[rt].siz=f[rt].ls=f[rt].rs=0;
	f[rt].siz++;
	if (l==r) return ;
	ll mid=l+r>>1;
	if ((k>>deep)&1) insert(mid+1,r,f[rt].rs,k,deep-1);
	else insert(l,mid,f[rt].ls,k,deep-1);
}
int fa[maxn];
inline ll query(ll l,ll r,int &rt,ll k,int deep) {
	if (!rt) return 0;
	if (l==r) return 0;
	ll mid=l+r>>1;
	if ((k>>deep)%2==1) {
		if (f[f[rt].ls].siz) return (1ll<<deep)+query(l,mid,f[rt].ls,k,deep-1);
		else return query(mid+1,r,f[rt].rs,k,deep-1);
	} 
	else {
		if (f[f[rt].rs].siz) return (1ll<<deep)+query(mid+1,r,f[rt].rs,k,deep-1);
		else return query(l,mid,f[rt].ls,k,deep-1);
	}
}
ll Max,Ans[maxn],b[maxn],ans;
inline void clear(void) {
	root=cnt=ans=0;
}
inline void add(int x) {
	ans=max(ans,query(0ll,N,root,a[x],base));
	insert(0,N,root,a[x],base);
	for (auto y:to[x]) add(y);
}
inline void dfs(int x,int pre) {
	if (x!=1) dfs(fa[x],x);
	Ans[x]=ans;
	ans=max(ans,query(0,N,root,a[x],base));
	insert(0,N,root,a[x],base);
	for (auto y:to[x]) if (y^pre) add(y);
}
signed main(void){
	freopen("xor.in","r",stdin); 
	freopen("xor.out","w",stdout);
	int i,x,j,tmpx,tmpy;
	read(n);
	for (i=2;i<=n;i++) read(x),to[x].push_back(i),fa[i]=x;
	for (i=1;i<=n;i++) {
		scanf("%lld",&a[i]);
		b[i]=query(0,N,root,a[i],base);
		insert(0,N,root,a[i],base);
		Max=max(b[i],Max);
	}
	for (i=1;i<=n;i++) if (Max==b[i]) {
		tmpx=i;
		for (j=1;j<i;j++) if ((a[i]^a[j])==Max) {tmpy=j;break;} 
		break;
	}
	memset(Ans,-1,sizeof(Ans));
	clear();dfs(tmpx,0);
	clear();dfs(tmpy,0);
	Ans[1]=0;
	for (i=1;i<=n;i++) if (Ans[i]>=0) printf("%lld\n",Ans[i]);else printf("%lld\n",Max);
	return 0;
}

Hint

不要左移 $63$ 位，会爆 long long！！！

T4. boxing

Description

image-20230718074834660

$n\le 9,k\le 16,k\le n$

1s 512MB

Solution

dp 套 dp

先不考虑 $k$ 的限制。不妨先将 $m_i$ 个选手升序排序。令 $f[i][j]$ 表示前 $i$ 个选手，位置状态为 $j$ 。根据每个人选或者不选，排列一下。

考虑 LIS 的限制，有一个经典套路就是维护 $[1,i]$ （不一定以 $i$ 结尾）的最长上升子序列长度 ，差分一下，显然所有的值只有 $0,1$。维护的时候，按权值从小到大加入，加入第 $i$ 个位置的数时，只需要将第 $i$ 个点的位置改为 $1$ ，之后的第一个 $1$ 改为 $0$ ，如果后面没有 $1$ 则不修改。

这里的转移可以预处理。复杂度 $O(nm2^n\cdot 2^n)$ 。

令位置的状态 $S$， LIS 的状态 $T\subseteq S$，所以复杂度可以变为 $O(nm3^n)$

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=9,M=17,K=1<<N,P=K+10,mod=998244353;
int n,m,k,a[M];
int f[M][K][K],trs[K][N];
int C[P][P],fac[P];
int main(){
   	freopen("boxing.in","r",stdin); 
	freopen("boxing.out","w",stdout);
	for(int i=0;i<P;i++){
		for(int j=C[i][0]=1;j<=i;j++){
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
		}
	}
	for(int i=fac[0]=1;i<P;i++)fac[i]=1ll*fac[i-1]*i%mod;
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)cin>>a[i];
	sort(a+1,a+1+m);
	int U=(1<<n)-1;
	for(int S=0;S<=U;S++){
		for(int i=0;i<n;i++)if(~S>>i&1){
			trs[S][i]=S|(1<<i);
			for(int j=i+1;j<n;j++)if(S>>j&1){
				trs[S][i]^=1<<j;break;
			}
		}
	}
	f[0][0][0]=1;
	for(int i=1;i<=m;i++){
		for(int S=0;S<=U;S++){
			for(int T=0;T<=U;T++){
				if(!f[i-1][S][T])continue;
				(f[i][S][T]+=f[i-1][S][T])%=mod;
				for(int j=0;j<n;j++)if(~S>>j&1){
					int &nex=f[i][S|(1<<j)][trs[T][j]];
					if(a[i]-S-2<0)continue;
					nex=(nex+1ll*f[i-1][S][T]*C[a[i]-S-2][(1<<j)-1])%mod;
				}
			}
		}
	}
	int ans=0;
	for(int T=0;T<=U;T++){
		if(__builtin_popcount(T)<k)continue;
		(ans+=f[m][U][T])%=mod;
	}
	ans=(1ll<<n)*ans%mod;
	for(int i=0;i<n;i++)ans=1ll*ans*fac[1<<i]%mod;
	cout<<ans;
	return 0;
}