NOIP2022模拟赛2 1

, , ,

T1

前缀和，开 long long。

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<bits/stdc++.h>
#define maxn 100005
#define int long long
#define put() putchar('\n')
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;
}
int sum[maxn],n;
int a[maxn];
signed main(void){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	int i;
	sum[1]=a[1]=1;
	read(n);
	for (i=2;i<=n;i++) {
		a[i]=sum[i-1]%i;
		sum[i]=a[i]*i+sum[i-1];
	}
	printf("%lld",a[n]);
	return 0;
}

T2

单调栈预处理出右边第一个比 $i$ 小的位置 $p_i$

线段树做法 $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
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
#include<bits/stdc++.h>
#define maxn 300005
#define ll long long
#define put() putchar('\n')
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;
}
int n,a[maxn];
int qmin[maxn],qmax[maxn];
int stac[maxn],tot;
int f[maxn<<2],dp[maxn];
inline void Update(int l,int r,int rt,int head,int k) {
	if (l==r) return f[rt]=k,void();
	int mid=l+r>>1;
	if (head<=mid) Update(l,mid,rt<<1,head,k);
	if (head>mid) Update(mid+1,r,rt<<1|1,head,k);
	f[rt]=min(f[rt<<1],f[rt<<1|1]);
}
inline int Query(int l,int r,int rt,int head,int tail) {
//	printf("%d %d %d : %d\n",l,r,rt,f[rt]);
	if (head<=l&&r<=tail) return f[rt];
	int mid=l+r>>1,tmp1=1e9,tmp2=1e9;
	if (head<=mid) tmp1=Query(l,mid,rt<<1,head,tail);
	if (tail>mid)  tmp2=Query(mid+1,r,rt<<1|1,head,tail);
	return min(tmp1,tmp2);
}
vector<int>h[maxn];
signed main(void){
	freopen("split.in","r",stdin);freopen("split.out","w",stdout);
	int i;
	read(n);
	memset(f,0x3f,sizeof(f));
	for (i=1;i<=n;i++) read(a[i]);
	a[0]=1e9;a[n+1]=-1e9;
	stac[0]=0;
	for (tot=0,i=1;i<=n;i++) {
		while (tot&&a[stac[tot]]<=a[i]) tot--;
		qmax[i]=stac[tot];
		stac[++tot]=i;
	}
	stac[0]=n+1;
	for (tot=0,i=n;i>=1;i--) {
		while (tot&&a[stac[tot]]>=a[i]) tot--;
		qmin[i]=stac[tot];
		stac[++tot]=i;
	}
	for (i=1;i<=n;i++) h[qmin[i]].push_back(i);
//	for (i=1;i<=n;i++) printf("%d %d\n",qmax[i],qmin[i]);
	dp[1]=1;Update(1,n,1,1,0);
	for (i=2;i<=n;i++) {
//		printf("case %d\n",i); 
		Update(1,n,1,i,dp[i-1]);
		for (auto j:h[i]) Update(1,n,1,j,1e9);//,printf("%d ",j);put();
		dp[i]=Query(1,n,1,qmax[i]+1,i)+1;
	}
	printf("%d",dp[n]);
	return 0;
}

线性做法：

待补

T3

原题 CF335F

一个物品分为三种状态，全款付，买一送一那个买的，还有白嫖的。

有一种很naive的做法就是能白嫖就白嫖，但是这样显然是错的。

最小化权值就是最大化白嫖的费用。

考虑反悔贪心。建小根堆。存储白嫖的费用。建小根堆的原因是弹出最小的保留最大，从而最大化权值。

先将从大到小排序。当前要决策的是 $c$ 。

一种情况是与全款付的一起，变为白嫖的。

另一种情况，是将堆顶弹出，弹出的设为 $k$。

  • 如果 $c>k$ ，直接换

  • 否则有两种情况

    1. $2*c>k$ 那么买 $k$ ，然后一个替上原来的位置，一个当买 $k$ 送的。放入 $2c-k$
    2. 再把 $k$ 放进去

    如果两个同时选，就是两个 $c$ 被另外的给送的。

细节有点多。

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
#include<bits/stdc++.h>
#define maxn 500005
#define int long long
#define put() putchar('\n')
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;
}
int a[maxn],ans,n,b[maxn],c[maxn],tot;
int rt[maxn],num;
inline bool cmp(int x,int y) {return x>y;}
priority_queue<int,vector<int>,greater<int> >q;
signed main(void){
	int i,sum=0,j;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),ans+=a[i];
	sort(a+1,a+1+n);
	reverse(a+1,a+1+n);
	b[tot=1]=a[1],c[1]=1;
	for (i=2;i<=n;i++) {
		if (a[i]!=a[i-1]) b[++tot]=a[i],c[tot]++;
		else c[tot]++;
	}
//	for (i=1;i<=tot;i++) printf("%lld %lld %lld\n",i,b[i],c[i]);
	for (i=1;i<=tot;i++) {
		num=0;
		int tmp=min(sum-(int)q.size()*2,c[i]),rest=min(sum-tmp,c[i]-tmp);
		for (j=1;j<=tmp;j++) rt[++num]=b[i];
		for (j=1;j<=rest;j+=2) {
			int x=q.top();q.pop();
			if (b[i]>x) {
				rt[++num]=b[i];
				if (j<rest) rt[++num]=b[i];
			}
			else {
				rt[++num]=x;
				if (j<rest&&b[i]*2>=x) rt[++num]=b[i]*2-x;
			}
		}
		for (j=1;j<=num;j++) q.push(rt[j]);
		sum+=c[i];
	}
	while (!q.empty()) ans-=q.top(),q.pop();
	printf("%lld",ans); 
	return 0;
}

T4

Peaks

数据错了，我内存也开小了，乐。

Kruskal重构树+可持久化线段树。

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 maxn 200005
#define ll long long
#define put() putchar('\n')
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;
}
int n,m,q;
int h[maxn];
struct yyy{int x,y,z;}e[1000005];
inline bool cmp(yyy x,yyy y){return x.z<y.z;}
int father[maxn],w[maxn],fa[maxn][21],deep[maxn],lg[maxn];
int to[maxn][2],root[maxn],times,ql[maxn],qr[maxn],id[maxn];
inline int getfa(int x) {return x==father[x]?x:father[x]=getfa(father[x]);}
inline void dfs(int x,int pre) {
	if (!x) return ;
	ql[x]=++times;id[times]=x;
	int i;deep[x]=deep[pre]+1;fa[x][0]=pre;
	for (i=1;i<=lg[deep[x]];i++) fa[x][i]=fa[fa[x][i-1]][i-1];
	dfs(to[x][0],x);dfs(to[x][1],x);
	qr[x]=times;
}
const int base=1e9;
struct node{int ls,rs,size;}f[maxn*50];
int fnum;
inline int Update(int l,int r,int pre,int head,int k) {
	int rt;
	f[rt=++fnum]=f[pre];f[rt].size++;
	if (l==r) return rt;
	int mid=l+r>>1;
	if (head<=mid) f[rt].ls=Update(l,mid,f[rt].ls,head,k);
	else f[rt].rs=Update(mid+1,r,f[rt].rs,head,k);
	return rt; 
}
inline int Query(int l,int r,int rt1,int rt2,int k) {
	if (l==r) return l;
	int mid=l+r>>1,s=f[f[rt2].rs].size-f[f[rt1].rs].size;
	if (k<=s) return Query(mid+1,r,f[rt1].rs,f[rt2].rs,k);
	else return Query(l,mid,f[rt1].ls,f[rt2].ls,k-s); 
}
inline void init(void) {
	int i;int cnt=n;
	sort(e+1,e+1+m,cmp);
	for (i=1;i<=n*2;i++) father[i]=i;
	for (i=2;i<=n*2;i++) lg[i]=lg[i/2]+1;
	for (i=1;i<=m;i++) {
		int fx=getfa(e[i].x),fy=getfa(e[i].y);
		if (fx^fy) {
			w[++cnt]=e[i].z;
			to[cnt][0]=fx;to[cnt][1]=fy;
			father[fx]=father[fy]=cnt;
			//printf("%d %d %d  %d\n",fx,fy,cnt,e[i].z);
		}
	}
//	printf("%d\n",cnt);
	for (i=1;i<=cnt;i++) if (father[i]==i )dfs(i,0);
	root[0]=fnum=1;
	for (i=1;i<=cnt;i++) {
		if (id[i]<=n) root[i]=Update(1,base,root[i-1],h[id[i]],1);
		else root[i]=root[i-1];
	//	printf("%d %d %d [%d,%d]\n",f[root[i]].size,id[i],h[id[i]],ql[id[i]],qr[id[i]]);
	}
}
signed main(void){
	freopen("mountain.in","r",stdin);
	freopen("mountain2.out","w",stdout);
	int las=0,i,j,x,y,z;
	read(n);read(m);read(q);
	for (i=1;i<=n;i++) read(h[i]);
	for (i=1;i<=m;i++) read(e[i].x),read(e[i].y),read(e[i].z);
	init();
//	printf("%d %d %d\n",w[14],fa[1][1],fa[1][2]);
	while (q--) {
		read(x);read(y);read(z);
		if (las>0) x^=las,y^=las,z^=las;
	//	printf("111 %d %d %d ",x,y,z);
		for (i=20;i>=0;i--) if (fa[x][i]&&w[fa[x][i]]<=y) x=fa[x][i];
	//	printf("%d %d\n",x,f[root[qr[x]]].size-f[root[ql[x]-1]].size);
		if (f[root[qr[x]]].size-f[root[ql[x]-1]].size<z) las=-1;
		else las=Query(1,base,root[ql[x]-1],root[qr[x]],z);
		printf("%d\n",las); 
	}
	return 0;
}