首页 > 其他分享 >NOIP2023题解

NOIP2023题解

时间：2024-01-19 15:36:36浏览次数：22  
标签：ch return int 题解 while max NOIP2023 getchar

目录

NOIP2023

T1 词典(dict)

考察：贪心

题解Link

题目传送门

首先任意多次操作本质就是随意排序，所以如果要使 \(w_i\) 最小，我们一定会使 \(w_i\) 从 \(a\) 到 \(z\) 排，其它都 \(z\) 到 \(a\) 排。然后考虑比较字典序的实质：

  • 如果 \(w_i\) 中第一个（即最小的）字符都比 \(w_j\) 中第一个（即最大的）字符大，那么显然不可能满足性质。

  • 如果相同，那么若存在，我们考虑第一个不同的位置，发现一定有 \(w_i>w_j\)，而若不存在，则等价于两串相同，也不符合

因此我们只需要记录每个串的最大最小字符即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}
int n,m,minn[3005],maxn[3005],fl;
char s[3005];
signed main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		minn[i]=27;
		scanf("%s",s+1);
		for(int j=1;j<=m;j++) 
			minn[i]=min(minn[i],s[j]-'a'+1ll),maxn[i]=max(maxn[i],s[j]-'a'+1ll);
	}
	for(int i=1;i<=n;i++) {
		fl=1;
		for(int j=1;j<=n;j++)
			fl&=(i==j||minn[i]<maxn[j]);
		printf("%lld",fl);
	}
	return 0;
}

时间复杂度 \(O(nm+n^2)\)，理论可以优化到 \(O(nm+n)\)，但完全没必要。

T2 三值逻辑(tribool)

考察：模拟、图论（？）

题解Link

题目传送门

我们拿个数组分别记录每个值在此刻与谁相等或与谁相反，特殊的，对于定值，多用 \(3\) 个变量记录，这是好模拟的。

然后操作结束后会得到若干初始值之间的相等与相反关系，考虑用无向有权图来刻画，那么由于每个点最多只贡献一条边，最终得到的是一个树与基环树的森林。

考虑对于每个联通块统计答案，容易发现，一个联通块要么全是 \(U\) 要么全不是 \(U\)，所以：如果其中有 \(U\)，那么只能算上贡献，否则除非迫不得已，我们一定不会赋 \(U\)。什么叫迫不得已？只有一种情况，就是基环树的环为奇环（奇环树（雾）），然后答案就是好统计的了。

但是细节很多，比如你基环树会找环吗？

我的代码相当丑。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}
int c,t,n,m,a[100005],fl[100005];
char op[5];int x,y;
int h[100005],cnt;
struct QWQ{int v,w,nxt;} e[100005*2];
void add(int u,int v,int w) {e[++cnt]={v,w,h[u]},h[u]=cnt;}
int vis[100005],num,ff,ans;
stack<int> st,wt;
void dfs(int u,int p,int ww) {
	vis[u]=1;num++;
	st.push(u);wt.push(ww);
	for(int i=h[u];i;i=e[i].nxt) {
		int v=e[i].v,w=e[i].w;
		if(v==p) continue;
		if(vis[v]&&ff==-1) {
			ff=w;
			while(st.size()&&st.top()!=v) {
				ff^=wt.top();
				st.pop();wt.pop();
			}
		}
		if(!vis[v]) dfs(v,u,w);
	}
	if(ff==-1) st.pop(),wt.pop();
}
signed main() {
	cin>>c>>t;
	while(t--) {
		n=read(),m=read();
		for(int i=1;i<=n+3;i++) a[i]=i,fl[i]=0;
		memset(h,0,sizeof(h));cnt=0;
		memset(vis,0,sizeof(vis));
		ans=0,num=0;
		for(int i=1;i<=m;i++) {
			scanf("%s%lld",op+1,&x);
			switch(op[1]) {
				case '+':y=read();a[x]=a[y],fl[x]=fl[y];break;
				case '-':y=read();a[x]=a[y],fl[x]=fl[y]^1;break;
				case 'T':a[x]=n+1,fl[x]=0;break;
				case 'F':a[x]=n+2,fl[x]=0;break;
				case 'U':a[x]=n+3,fl[x]=0;break;
			}
		}
		for(int i=1;i<=n;i++)
			add(i,a[i],fl[i]),add(a[i],i,fl[i]);
		while(st.size()) st.pop(),wt.pop();ff=-1;
		dfs(n+3,0,0);
		ans+=num-1;
		while(st.size()) st.pop(),wt.pop();ff=-1;
		if(!vis[n+1]) dfs(n+1,0,0);
		while(st.size()) st.pop(),wt.pop();ff=-1;
		if(!vis[n+2]) dfs(n+2,0,0);
		for(int i=1;i<=n;i++) {
			if(!vis[i]) {
				while(st.size()) st.pop(),wt.pop();ff=-1;
				int las=num;
				dfs(i,0,0);
				if(ff==1) ans+=num-las;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

时间复杂度 \(O(\sum n+m)\)。

T3 双序列拓展(expand)

考察：\(dp\)、人类智慧（

题解Link

题目传送门

部分分启示正解。

  • \(35pts\) 的 \(O(qnm)\)

将原题目转化为这样：两个指针分别指着两个序列，每次将任意至少一个指针向后移一个位置，并使每时每刻都满足两个指针所指的位置有单调的偏序关系。

所谓单调的偏序关系可以用第一个位置来判断，在下文我们只考虑 \(a<b\) 的情况。

我们考虑 \(dp\)：记 \(f_{i,j}\) 表示 \(a_{1-i}\) 能否和 \(b_{1-j}\) 匹配，那么有转移 \(f_{i,j}=(a_i<b_j)\&(f_{i-1,j}|f_{i,j-1}|f_{i-1,j-1})\)。此时即可 \(O(qnm)\) 完成本题。

  • \(70pts\) 的特殊性质

我们考虑构造 01 矩阵 \(c\)，其中 \(c_{i,j}=[a_i<b_j]\)，那么等价于我们要判断是否存在只走 \(1\)，只能向下、向右、向右下的路径从 \((1,1)\) 到 \((n,m)\)。

其实我们不会向右下走，因为可以证明不存在

1 0
0 1

这样的矩阵，但对正解没啥作用，所以我就没管了。

由于性质保证，我们发现最后一列与最后一行都是 \(1\)。接下来我们考虑 \(a\) 除 \(a_n\) 最小值 \(a_{min}\) 与 \(b\) 除 \(b_m\) 的最小值 \(b_{min}\)，如果 \(a_{min}<b_{min}\)，那么 \(a_{min}\) 所在的列也全是 \(1\)，于是我们可以递归下去；否则，一定有 \(b_{min}\) 所在的行全是 \(0\)。

对于 \(a_{max}\) 和 \(b_{max}\) 我们同样考虑，如果 \(b_{max}>a_{max}\) 那么就继续递归，否则一定有 \(a_{max}\) 所在的列全是 \(0\)，然后你发现，\(b_{min}\) 所在的行与 \(a_{max}\) 所在的列把 \((1,1)\) 围起来了！于是就直接返回 \(false\)。

实现的话预处理前缀 \(min\)、\(max\) 即可。

  • \(100pts\)

其实 \(70pts\) 就是 \(100pts\) 的一半，物理意义的一半，我们寻找全局 \(a_{min}\) 和全局 \(b_{max}\)，只要有一列或一行全是 \(0\)，那么就相当于分割了 \((1,1)\) 和 \((n,m)\)，否则做两次特殊性质即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}
int cc,n,m,q,c[500005],d[500005],a[500005],b[500005],pax[500005],pan[500005],sax[500005],san[500005],pbx[500005],pbn[500005],sbx[500005],sbn[500005];
bool calc1(int x,int y) {
	if(x==1||y==1) return 1;
	int ax=pax[x-1],an=pan[x-1],bx=pbx[y-1],bn=pbn[y-1];
	if(a[an]<b[bn]) return calc1(an,y);
	if(b[bx]>a[ax]) return calc1(x,bx);
	return 0;
}
bool calc2(int x,int y) {
	if(x==n||y==m) return 1;
	int ax=sax[x+1],an=san[x+1],bx=sbx[y+1],bn=sbn[y+1];
	if(a[an]<b[bn]) return calc2(an,y);
	if(b[bx]>a[ax]) return calc2(x,bx);
	return 0;
}
bool check() {
	if(a[1]>b[1]) {
		for(int i=1;i<=n;i++) a[i]*=-1;
		for(int i=1;i<=m;i++) b[i]*=-1;
	}
	pax[1]=1,pan[1]=1;
	for(int i=2;i<=n;i++)
		pax[i]=(a[pax[i-1]]>a[i]?pax[i-1]:i),
		pan[i]=(a[pan[i-1]]<a[i]?pan[i-1]:i);
	pbx[1]=1,pbn[1]=1;
	for(int i=2;i<=m;i++)
		pbx[i]=(b[pbx[i-1]]>b[i]?pbx[i-1]:i),
		pbn[i]=(b[pbn[i-1]]<b[i]?pbn[i-1]:i);
	sax[n]=n,san[n]=n;
	for(int i=n-1;i>=1;i--)
		sax[i]=(a[sax[i+1]]>a[i]?sax[i+1]:i),
		san[i]=(a[san[i+1]]<a[i]?san[i+1]:i);
	sbx[m]=m,sbn[m]=m;
	for(int i=m-1;i>=1;i--)
		sbx[i]=(b[sbx[i+1]]>b[i]?sbx[i+1]:i),
		sbn[i]=(b[sbn[i+1]]<b[i]?sbn[i+1]:i);
	int ax=pax[n],an=pan[n],bx=pbx[m],bn=pbn[m];
	if(a[an]>=b[bn]) return 0;
	if(b[bx]<=a[ax]) return 0;
	return calc1(an,bx)&calc2(an,bx);
}
signed main() {
	cin>>cc>>n>>m>>q;
	for(int i=1;i<=n;i++)
		a[i]=c[i]=rd();
	for(int i=1;i<=m;i++)
		b[i]=d[i]=rd();
	cout<<check();
	while(q--) {
		for(int i=1;i<=n;i++) a[i]=c[i];
		for(int i=1;i<=m;i++) b[i]=d[i];
		int k1=rd(),k2=rd();
		for(int i=1;i<=k1;i++) {
			int p=rd(),v=rd();
			a[p]=v;
		}
		for(int i=1;i<=k2;i++) {
			int p=rd(),v=rd();
			b[p]=v;
		}
		cout<<check();
	}
	return 0;
}

时间复杂度 \(O(q(n+m))\)。

T4 天天爱打卡(run)

考察：\(dp\)、线段树

题解Link

题目传送门

先考虑 \(n=10^5\) 的部分分。动态规划是显然的：记 \(f_{i,0/1}\) 表示前 \(i\) 位，最后一位选/不选的最大能量。转移： \(f_{i,0}=max(f_{i-1,0},f_{i-1,1})\)，\(f_{i,1}=max_{i-j+1\le k}(f_{j-1,0}+val(j,i))\)。也是显然的线段树优化，把 \(val\) 拆成加减两部分，减的部分是简单的，而加的部分对挑战按结束时间排序，然后指针扫描即可。

接下来考虑满分做法，基于一个贪心理念：跑步的目的是为了完成挑战，所以显然就是对所有挑战的起始与终止点进行离散化，但是转移就有点不同了。

记 \(f_{i,0/1}\) 表示前 \(i\) 个关键点，最后一个选/不选的最大能量。

\(f_{i,0}=max(f_{i-1,0},f_{i-1,1})\) 是同理的，但 \(f_{i,1}\) 稍微有点不同，首先，我们枚举最后一段跑步之后，在上文中我们只能从 \(f_{j-1,0}\) 转移，这是为了使跑步不再连续，但在这儿，我们是可能可以从 \(f_{j-1,1}\) 转移的，因为两个关键点之间也许有空隙，我们只要在空隙中不跑步那么依然是不连续的，所以要特判关键点是否连续。然后转移的范围可以使用另一个指针来扫描，\(val\) 中加的部分与上文相同（因为所有起始终止点都是作为关键点参与离散化的），可减的部分就有点不同了：我们把其拆为 \(-d(p_i-p_{i-1})-d(p_{i-1}-p_{i-2})-\dots-d(p_{j+1}-p_j)-d\)，然后考虑贡献，但是千万注意最后的那个 \(-d\)！被坑了好久，，，

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
	int s=0,m=0;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
	while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return m?-s:s;
}
#define inf ((int)1e12)
int c,t,n,m,k,d,b[200005],cnt,f[200005][2];
struct QWQ {int l,r,v;} a[100005];
bool cmp(QWQ a1,QWQ a2) {return a1.r<a2.r;}
struct Node {int l,r,d,laz;};
struct Segment_Tree {
  	Node t[4*200005];
	int ls(int p) {return p<<1;}
	int rs(int p) {return p<<1|1;}
	void pushup(int p) {t[p].d=max(t[ls(p)].d,t[rs(p)].d);}
	void pushdown(int p) {
		t[ls(p)].d+=t[p].laz,t[rs(p)].d+=t[p].laz;
		t[ls(p)].laz+=t[p].laz,t[rs(p)].laz+=t[p].laz;t[p].laz=0;
	}
	void clear(int p,int l,int r) {
		t[p].l=l,t[p].r=r,t[p].d=-inf,t[p].laz=0;
		if(l==r) return;int m=(l+r)>>1;
		clear(ls(p),l,m);clear(rs(p),m+1,r);
	}
	void update(int p,int l,int r,int v) {
		if(l>r) return;
		if(l<=t[p].l&&t[p].r<=r) {t[p].d+=v,t[p].laz+=v;return;}
		pushdown(p);int m=(t[p].l+t[p].r)>>1;
		if(l<=m) update(ls(p),l,r,v);
		if(r>m) update(rs(p),l,r,v);pushup(p);
	}
	int query(int p,int l,int r) {
		if(l<=t[p].l&&t[p].r<=r) return t[p].d;
		pushdown(p);int s=-inf,m=(t[p].l+t[p].r)>>1;
		if(l<=m) s=max(s,query(ls(p),l,r));
		if(r>m) s=max(s,query(rs(p),l,r));return s;
	}
} tt;
signed main() {
	cin>>c>>t;
	while(t--) {
		cin>>n>>m>>k>>d;
		b[cnt=1]=n;
		for(int i=1;i<=m;i++) {
			int x=read(),y=read();
			b[++cnt]=a[i].l=x-y+1,b[++cnt]=a[i].r=x,a[i].v=read();
		}
		sort(b+1,b+cnt+1);int q=unique(b+1,b+cnt+1)-b-1;
		tt.clear(1,1,200002);
		memset(f,-0x3f,sizeof(f));f[0][0]=0;tt.update(1,1,1,inf);
		for(int i=1;i<=m;i++)
			a[i].l=lower_bound(b+1,b+q+1,a[i].l)-b,a[i].r=lower_bound(b+1,b+q+1,a[i].r)-b;
		sort(a+1,a+m+1,cmp);
		for(int i=1,j=1,r=1;i<=q;i++) {
			tt.update(1,1,i-1,-d*(b[i]-b[i-1]));
			while(b[i]-b[j]+1>k) j++;
			while(r<=m&&a[r].r==i)
				tt.update(1,1,a[r].l,a[r].v),r++;
			f[i][0]=max(max(f[i-1][0],f[i-1][1]),0ll);
			f[i][1]=tt.query(1,j,i)-d;
			if(b[i+1]-b[i]==1) tt.update(1,i+1,i+1,inf+f[i][0]);
			else tt.update(1,i+1,i+1,inf+max(f[i][0],f[i][1]));
		}
		printf("%lld\n",max(f[q][0],f[q][1]));
	}
	return 0;
}

时间复杂度 \(O(m\log m)\)。

标签：ch,return,int,题解,while,max,NOIP2023,getchar
From： https://www.cnblogs.com/operator-/p/17974763

相关文章

  • CF1899G题解
    UnusualEntertainment题目传送门题解真的不要太典，，，考虑点\(u\)是\(v\)的后代等价于\(u\)在子树\(v\)中，dfs序直接走起，变成判断是否存在\(i\)使得：\[in_x\lein_{p_i}\leout_x,l\lei\ler\]二维数点，启动！代码：#include<bits/stdc++.h>usingnamespacestd;#defi......
  • CF1899F题解
    Alex'swhims题目传送门题解构造题，感觉比G更难？可能是我不擅长构造。考虑点的度数，发现一次操作\(u,v_1,v_2\)会使\(deg_{v_1}\)减\(1\)，使\(deg_{v_2}\)加\(1\)，即一次操作最多减少一个叶子，那如果存在一个时刻使我们的叶子数量大于\(3\)个，下一次若问\(n-1\)则直接......
  • P6550题解
    P6550[COCI2010-2011#2]LUNAPARK题目传送门题解论证简单，构造逆天（好吧其实就是烦了点）。每个格子是正整数，所以我们必然尝试多走格子。我们发现，只要\(r,c\)中有一个是奇数，我们就可以全部走到，构造很简单：我们找准奇数边，假设是\(r\)，蛇形地走，显然在奇数行我们会结束在末尾，在偶数......
  • P5133题解
    P5133tb148的客人题目传送门题解唯一的一篇题解还是交错题的……很简单的一个二分加差分题。显然是二分答案，考虑检验。如果\(2mid+1\gen\)，那么所有人可以自由去到任意位置，一定可行；否则，我们求出每个人可以去到的区间范围，并以此推出要满足这个人的限制，\(1\)号需要在哪个区......
  • P3867题解
    P3867[TJOI2009]排列计数题目传送门题解\(k\)很小，不是分讨就是突破口。如果我们用这种方式生成排列：将\(1\)到\(n\)按顺序插入当前状态，那么你会发现当前的数\(x\)的插入被很大程度的限制住了，我们只需记录当前\(x-k\)到\(x-1\)的位置即可枚举出所有可能的下一状态，因......
  • P7312题解
    P7312[COCI2018-2019#2]Sunčanje题目传送门题解分类讨论的思想有点像P4169?要你对于每一个矩形，求是否存在编号比它大，与它有交的矩形。直接做需要用一个比较神仙的线段树用法，所以我们可以容斥：我们求出编号比它大，与它无交的矩形数量，最后与所有可能覆盖它的矩形共\(n-i\)个......
  • P6554题解
    P6554PromisesICan'tKeep题目传送门题解看题解都有些做烦了，就来发一篇。换根dp。第一遍dfs处理出\(Lef_u\)表示\(u\)子树内的叶子个数（包含自己），然后求出以\(1\)为根时的答案\(\sumLef_u*val_u\)，注意特判根为叶子的情况。第二遍dfs大力换根就好了，从根\(u\)......
  • P9744题解
    P9744「KDOI-06-S」消除序列题目传送门题解记错时间错过模拟赛的sb来也。题目中的最关键信息就是\(a_i,b_i,c_i\ge0\)，这意味着多做无用的操作一定不优，所以有：结论\(1\)：优先进行\(1\)操作。这是因为我们不管我们在\(1\)操作前做什么操作都会被其推平覆盖，是无用操......
  • P8047题解
    P8047[COCI2015-2016#4]GALAKSIJA题目传送门题解显然是要删边变加边的，然后联通性也是显然要用并查集维护的，就是路径异或和需要一个数据结构来维护。发现：加边删边不影响两个点的路径异或和。所以我们可以处理出每个点到\(1\)号节点的路径异或和\(d\)，于是\(Path_{u,v}=d_u......
  • P8034题解
    P8034[COCI2015-2016#7]Ozljeda题目传送门题解评橙差不多了。手玩一下样例，很容易发现\(x\)的循环节为\(K+1\)，每一段分别为\(a_1,a_2,a_3,\dots,a_K,\bigoplus_{i=1}^Ka_i\)这几项，然后恰好循环节的异或值为\(0\)，所以就可以直接维护前缀异或值，然后取模求答案。代码：#i......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99