首页 > 其他分享 >【题解】NOIP2022

【题解】NOIP2022

时间：2023-09-04 20:11:13浏览次数：39  
标签：int 题解 texttt times 选择 leq NOIP2022 dp

怎么看 T3 也不是那么难，可是为啥赛时就是被卡死了[难过]
不补 \(B\) 题了，ad-hoc。

A.种花

题目描述：

小 C 决定在他的花园里种出 \(\texttt{CCF}\) 字样的图案，因此他想知道 \(\texttt C\) 和 \(\texttt F\) 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。

花园可以看作有 \(n\times m\) 个位置的网格图，从上到下分别为第 \(1\) 到第 \(n\) 行，从左到右分别为第 \(1\) 列到第 \(m\) 列，其中每个位置有可能是土坑，也有可能不是，可以用 \(a_{i,j} = 1\) 表示第 \(i\) 行第 \(j\) 列这个位置有土坑，否则用 \(a_{i,j} = 0\) 表示这个位置没土坑。

一种种花方案被称为 \(\texttt{C-}\) 形的，如果存在 \(x_1, x_2 \in [1, n]\)，以及 \(y_0, y_1, y_2 \in [1, m]\)，满足 \(x_1 + 1 < x_2\)，并且 \(y_0 < y_1, y_2 \leq m\)，使得第 \(x_1\) 行的第 \(y_0\) 到第 \(y_1\) 列、第 \(x_2\) 行的第 \(y_0\) 到第 \(y_2\) 列以及第 \(y_0\) 列的第 \(x_1\) 到第 \(x_2\) 行都不为土坑，且只在上述这些位置上种花。

一种种花方案被称为 \(\texttt{F-}\) 形的，如果存在 \(x_1, x_2, x_3 \in [1, n]\)，以及 \(y_0, y_1, y_2 \in [1, m]\)，满足 \(x_1 + 1 < x_2 < x_3\)，并且 \(y_0 < y_1, y_2 \leq m\)，使得第 \(x_1\) 行的第 \(y_0\) 到第 \(y_1\) 列、第 \(x_2\) 行的第 \(y_0\) 到第 \(y_2\) 列以及第 \(y_0\) 列的第 \(x_1\) 到第 \(x_3\) 行都不为土坑，且只在上述这些位置上种花。

样例一解释中给出了 \(\texttt{C-}\) 形和 \(\texttt{F-}\) 形种花方案的图案示例。

现在小 C 想知道，给定 \(n, m\) 以及表示每个位置是否为土坑的值 \(\{a_{i,j}\}\)，\(\texttt{C-}\) 形和 \(\texttt{F-}\) 形种花方案分别有多少种可能？由于答案可能非常之大，你只需要输出其对 \(998244353\) 取模的结果即可，具体输出结果请看输出格式部分。

对于所有数据，保证：\(1 \leq T \leq 5\)，\(1 \leq n, m \leq 10^3\)，\(0 \leq c, f \leq 1\)，\(a_{i,j} \in \{0, 1\}\)。

题目分析：

多测不清空直接见祖宗了，绝望。
先考虑统计 \(C\) 再考虑统计 \(F\)。
对于 \(C\)，其实就可以拆解为一个横下面加一个 \(L\) 形
所以可以考虑枚举 \(C\) 的左上顶点，这样答案就是下面 \(L\) 形的数量乘以这个点横的数量。
对于 \(L\) 形的数量显然可以使用前缀和快速维护。

对于 \(F\) 可以就是下面的 \(L\) 形变成了一个 \(L\) 形下面加一些竖。
这个东西放到前缀和里只是多乘了一些东西，也十分好维护。

代码：

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3+5;
const int MOD = 998244353;
int n,m,C,F;
char s[N][N];
int a[N][N],f[N][N],g[N][N];
int mod(int x){
	return ((x % MOD)+MOD)%MOD;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout); 
	int T,id;
	scanf("%lld%lld",&T,&id);
	while(T--){
		scanf("%lld%lld%lld%lld",&n,&m,&C,&F);
		for(int i=1; i<=n; i++)	scanf("%s",s[i]+1);
		for(int i=n; i>=1; i--){
			for(int j=1; j<=m; j++){
				if(s[i+1][j] == '0' && s[i][j] == '0')	f[i][j] = f[i+1][j];
				else if(s[i][j] == '0')	f[i][j] = i;
			}
		}
		for(int i=n; i>=1; i--){
			for(int j=m; j>=1; j--){
				if(s[i][j+1] == '0' && s[i][j] == '0')	g[i][j] = g[i][j+1];
				else if(s[i][j] == '0')	g[i][j] = j;
			}
		}
		for(int i=n; i>=1; i--){
			for(int j=m; j>=1; j--){
				if(g[i][j] >= j)	a[i][j] = mod(g[i][j] - j),a[i][j] = mod(a[i][j] + a[i+1][j]);
			}
		}
		int ans = 0;
		//求 C 的方案数
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				if(g[i][j] - j <= 0 || f[i][j] - i < 2)	continue;
				int cnt1 = mod(g[i][j] - j);
				int cnt2 = a[i+2][j];
				ans = mod(ans + cnt1 * cnt2);
			}
		} 
		printf("%lld ",C * ans);ans = 0;
		//求 F 的方案数
		 for(int i=n; i>=1; i--){
			for(int j=m; j>=1; j--){
				if(g[i][j] >= j){
					a[i][j] = mod((g[i][j] - j) * (f[i][j] - i));
					a[i][j] = mod(a[i][j] + a[i+1][j]);
				}
			}
		}
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				if(g[i][j] - j <= 0 || f[i][j] - i < 2)	continue;
				int cnt1 = mod(g[i][j] - j);
				int cnt2 = a[i+2][j];
				ans = mod(ans + cnt1 * cnt2);
				ans = mod(ans - cnt1 * a[f[i][j]][j]);
			}
		} 
		printf("%lld\n",F * ans);ans = 0;
		for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				f[i][j] = g[i][j] = a[i][j] = 0;
				s[i][j] = 'a';
			}
		}
	}
	return 0;
}

C.建造军营

题目描述：

A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。

A 国的国土由 \(n\) 座城市组成，\(m\) 条双向道路连接这些城市，使得任意两座城市均可通过道路直接或间接到达。A 国打算选择一座或多座城市（至少一座），并在这些城市上各建造一座军营。

众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（可以是一条或多条，也可以一条也不看守)，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。

A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出其对 \(1,000,000,007\left(10^{9}+7\right)\) 取模的值即可。两个方案被认为是不同的，当且仅当存在至少一 座城市在一个方案中建造了军营而在另一个方案中没有，或者存在至少一条道路在一个 方案中被派兵看守而在另一个方案中没有。

对所有数据，保证 \(1 \leq n \leq 5 \times 10^5\)，\(n - 1 \leq m \leq 10^6\)，\(1 \leq u_i, v_i \leq n\)，\(u_i \neq v_i\)。

题目分析：

注意到每次只可以删掉一条边，也就是说如果两个点满足边双联通那么无论怎么删都不会导致它们无法互相到达。
所以一个显然的想法就是对图进行边双联通分量缩点，这样我们缩点之后其实只需要关注树边就可以了，被缩掉的边选或者不选都无所谓。
可以发现的是如果 \(u,v\) 均建造了兵营，则树上 \(u,v\) 之间的路径必然全部被选择，所以一个显然的状态就是：\(dp[i][0/1][0/1]\) 表示以 \(i\) 为根的子树内，有/没有被选择点，点 \(i\) 有/没有被选择的方案数。
这样需要注意的一点就是如果我们要对 \(dp[i][..][1]\) 转移就必然要求其子树内被选择的点到 \(i\) 的所有边都被选择，但是这个状态的设计下我们完全没有办法处理这个东西，因为我们完全不知道这中间选了多少条边，所以考虑再加一维：\(dp[i][0/1][0/1][0/1]\) 表示以 \(i\) 为根的子树内，有/没有被选择点，点 \(i\) 有/没有被选择，点 \(i\) 子树被选择的点与 \(i\) 的路径上的边是/不是全部被选择的方案数。
这样的话每个点就有八个状态，看上去就超级头大，但是会发现的一点就是其中有实际意义的状态数很少，只有下面这几个：

  • \(dp[i][0][0][0/1]\) 表示这棵子树内没有被选择的点
  • \(dp[i][1][0][0]\) 代表这棵子树内选择的点与 \(i\) 之间的边没有被全部选择
  • \(dp[i][1][1][1]\) 代表这棵子树内选择的点与 \(i\) 之间的边被全部选择，且点 \(i\) 被选择
  • \(dp[i][1][0][1]\) 代表这棵子树内选择的点与 \(i\) 之间的边被全部选择，且点 \(i\) 不被选择

其实第三个和第四个可以合并为一个状态，因为显然在后续的转移中如果我们已经要求了边全部被选择，那么显然我们根节点选择或者不选择并不会产生任何影响。
所以总结一下我们只需要记录三个状态，也就是 \(dp[i][3]\)，其中：

  • \(dp[i][0]\) 代表子树内没选择任何点
  • \(dp[i][1]\) 代表子树内选择的点与 \(i\) 之间的边全部被选择
  • \(dp[i][2]\) 代表子树内选择的点与 \(i\) 之间的边没有被全部选择

考虑转移其实就是新加入一个子树：

  • \(dp[u][0]\)，转移显然，乘 \(2\) 的原因是边 \((u,v)\) 可以选择也可以不选择
    • \(dp[u][0] = dp[u][0] \times 2 \times dp[v][0]\)
  • \(dp[u][1]\)，就是考虑这个选择的点是来自于之前的子树，还是来自于新加入的子树
    • \(dp[u][1] = dp[u][1] \times (2 \times dp[v][0] + dp[v][1]) + dp[u][0] \times dp[v][1]\)
  • \(dp[u][2]\)，因为我们显然只能有一棵子树选点，不然不同子树的点之间的边不被选择就不合法了，所以转移就是讨论这个有点的子树，是新加入的这个子树，还是之前加入的子树
    • \(dp[u][2] = dp[u][2] \times 2 \times dp[v][0] + dp[u][0] \times (dp[v][1] + 2\times dp[v][2])\)

对 \(dp\) 的初始化其实就是只有 \(u\) 点这一个点情况下的 \(dp\) 值，设 \(szv_u\) 表示 \(u\) 这个边双代表的点的个数，\(sze_u\) 表示 \(u\) 这个边双代表的边的数量，也就是：

  • \(dp[u][0] = 2^{sze_u}\)
  • \(dp[u][1] = (2^{szv_u} - 1) \times 2^{sze_u}\)，减 \(1\) 的原因是根据状态定义至少要选择一个点
  • \(dp[u][2] = 0\)

代码：

点击查看代码 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+5;
const int MOD = 1e9+7;
struct edge{
	int nxt,to;
	edge(){}
	edge(int _nxt,int _to){
		nxt = _nxt,to = _to;
	}
}e[2 * N];
int cnt,head[N],f[N],fa[N],dep[N],sum[N],deg[N],dp[N][4],pos[N],sz_v[N],sz_e[N],pw[N*2],g[N][3],from[N],to[N];
bool vis[N];
void add_edge(int from,int to){
	e[++cnt] = edge(head[from],to);
	head[from] = cnt;
}
int find(int x){
	if(f[x] == x)	return x;
	return f[x] = find(f[x]);
}
void merge(int x,int y){
	f[find(x)] = find(y);
}
void dfs1(int u,int fath){
	vis[u] = true;fa[u] = fath;dep[u] = dep[fath] + 1;
	for(int i=head[u]; i; i=e[i].nxt){
		int v = e[i].to;
		if(vis[v])	continue;
		dfs1(v,u);
	}
}
void dfs2(int u,int fath){
	vis[u] = true;
	for(int i=head[u]; i; i=e[i].nxt){
		int v = e[i].to;
		if(vis[v])	continue;
		dfs2(v,u);
		sum[u] += sum[v];
	}
	if(u != 1 && sum[u])	merge(u,fath);
}
void get_dp(int u,int fath){
	dp[u][0] = g[u][0];
	dp[u][1] = g[u][1];
	dp[u][2] = 0;
	 
	for(int i=head[u]; i; i=e[i].nxt){
		int v = e[i].to;
		if(v == fath)	continue;
		get_dp(v,u);
		
		//注意这个 2 1 0 的顺序 
		//考虑 f[u][2] 的转移
		dp[u][2] = (dp[u][2] * 2 * dp[v][0] + (dp[v][1] + 2 * dp[v][2]) * dp[u][0])%MOD; 
	
		//考虑 f[u][1] 的转移
		dp[u][1] = (dp[u][0] * dp[v][1] + dp[u][1] * (2 * dp[v][0] + dp[v][1]))%MOD;
	
		//考虑 f[u][0] 的转移 
		dp[u][0] = dp[u][0] * dp[v][0] * 2 % MOD;
	}
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,m;scanf("%lld%lld",&n,&m);
	for(int i=1; i<=m; i++){
		scanf("%lld%lld",&from[i],&to[i]);
		add_edge(from[i],to[i]);add_edge(to[i],from[i]);
	}
	for(int i=1; i<=n; i++)	f[i] = i;
	dfs1(1,0);
	memset(vis,0,sizeof(vis));
	for(int i=1; i<=m; i++){
		if(fa[from[i]] == to[i] || fa[to[i]] == from[i])	continue;
		if(dep[from[i]] < dep[to[i]])	swap(from[i],to[i]);
		sum[from[i]]++,sum[to[i]]--;
	}
	dfs2(1,0);
	memset(vis,0,sizeof(vis));
	memset(head,0,sizeof(head));cnt = 0;
	int sz = 0;
	for(int i=1; i<=n; i++){
		if(!vis[find(i)]){
			pos[find(i)] = ++sz;
			vis[find(i)] = true;
		}
		sz_v[pos[find(i)]]++;
	}
	for(int i=1; i<=m; i++){
		int u = find(from[i]),v = find(to[i]);
		if(u == v){
			sz_e[pos[u]]++;
		}
		else{
			add_edge(pos[u],pos[v]);
			add_edge(pos[v],pos[u]);
			deg[pos[u]]++,deg[pos[v]]++;
		}
	}
	
//	for(int i=1; i<=sz; i++)	printf("%lld ",deg[i]);
//	printf("\n");
	//前面都是在缩边双，下面开始正式写题
	pw[0] = 1;
	for(int i=1; i<=n+m; i++)	pw[i] = pw[i-1] * 2 % MOD;
	for(int i=1; i<=sz; i++){
		g[i][0] = pw[sz_e[i]];
		g[i][1] = (pw[sz_v[i]] - 1) * pw[sz_e[i]] % MOD;  //因为不能完全不选 
	}
	get_dp(1,0); 
	printf("%lld\n",(dp[1][1] + dp[1][2])%MOD);
	return 0;
}

D.比赛

题目描述：

小 N 和小 O 会在 2022 年 11 月参加一场盛大的程序设计大赛 NOIP！小 P 会作为裁判主持竞赛。小 N 和小 O 各自率领了一支 \(n\) 个人的队伍，选手在每支队伍内都是从 \(1\) 到 \(n\) 编号。每一个选手都有相应的程序设计水平。具体的，小 N 率领的队伍中，编号为 \(i\)（\(1 \leq i \leq n\)）的选手的程序设计水平为 \(a _ i\)；小 O 率领的队伍中，编号为 \(i\)（\(1 \leq i \leq n\)）的选手的程序设计水平为 \(b _ i\)。特别地，\(\{a _ i\}\) 和 \(\{b _ i\}\) 还分别构成了从 \(1\) 到 \(n\) 的排列。

每场比赛前，考虑到路途距离，选手连续参加比赛等因素，小 P 会选择两个参数 \(l, r\)（\(1 \leq l \leq r \leq n\)），表示这一场比赛会邀请两队中编号属于 \([l, r]\) 的所有选手来到现场准备比赛。在比赛现场，小 N 和小 O 会以掷骰子的方式挑选出参数 \(p, q\)（\(l \leq p \leq q \leq r\)），只有编号属于 \([p, q]\) 的选手才能参赛。为了给观众以最精彩的比赛，两队都会派出编号在 \([p, q]\) 内的、程序设计水平值最大的选手参加比赛。假定小 N 派出的选手水平为 \(m _ a\)，小 O 派出的选手水平为 \(m _ b\)，则比赛的精彩程度为 \(m _ a \times m _ b\)。

NOIP 总共有 \(Q\) 场比赛，每场比赛的参数 \(l, r\) 都已经确定，但是 \(p, q\) 还没有抽取。小 P 想知道，对于每一场比赛，在其所有可能的 \(p, q\)（\(l \leq p \leq q \leq r\)）参数下的比赛的精彩程度之和。由于答案可能非常之大，你只需要对每一场答案输出结果对 \(2 ^ {64}\) 取模的结果即可。

对于所有数据，保证：\(1 \leq n, Q \leq 2.5 \times 10 ^ 5\)，\(1 \leq l _ i \leq r _ i \leq n\)，\(1 \leq a _ i, b _ i \leq n\) 且 \(\{a _ i\}\) 和 \(\{b _ i\}\) 分别构成了从 \(1\) 到 \(n\) 的排列。

题目分析：

考虑离线，按区间右端点 \(r\) 扫描线。
考虑实时维护 \(X_{l,r}，Y_{l,r}\) 分别表示区间 \([l,r]\) 的 \(a\) 以及 \(b\) 的最大值。
每新加入一个区间，就可以使用扫描线维护新加入的点对 \(X,Y\) 的影响，也就是一个区间覆盖操作。
对于区间 \([l,r]\) 的询问，相当于我们扫到 \(r\) 时区间 \([l,r]\) 的历史 \(X \times Y\) 的和，其实也就是：

\[S_{l,r} = \sum_{r'=l}^r X_{l,r'} \times Y_{l,r'} \]

答案就是 \(\sum_{l' = l}^{r} S_{l',r}\)

总结一下我们就是要支持区间 \(X\) 覆盖，区间 \(Y\) 覆盖，区间 \(S + X \times Y\)。
这个东西就通过线段树打标记可以维护，就是维护 \((s_x,s_y,a_x,a_y,a_{xy},a)\)，这个标记的含义就是：

\[S' = S + a_x \times X + a_y \times Y + a_{xy} \times XY + a \\ X' = \begin{cases} X & s_x = 0 \\ s_x & s_x \not= 0 \end{cases} \\ Y' = \begin{cases} Y & s_y = 0 \\ s_y & s_y \not= 0 \end{cases} \]

具体的维护就是钦定加法标记先于覆盖标记。
也就是说假设 \(X\) 会被覆盖为 \(s_x\) 则 \(a_{xy}\sum X_iY_i = a_{xy}s_x \sum y_i\)，也就是说会让 \(a_{xy}s_x\) 贡献到 \(a_y\) 中。
然后我们就

标签：int,题解,texttt,times,选择,leq,NOIP2022,dp
From： https://www.cnblogs.com/linyihdfj/p/17677390.html

相关文章

  • AT318 A-G 题解
    A枚举\(1\simn\)的每个数，判断是否有\(i-M\equiv0\pmodP\)即可。赛时代码B暴力覆盖即可，注意\(x,y\)均是左开右闭。赛时代码C贪心的想，如果要替换\(i\)项，那必然是替换最大的\(i\)项，因此只需要对\(f\)排序，预处理后缀和后再扫一遍取替换前\(i\)项的最小值即可......
  • 湖北省选模拟 2023 部分题解
    质量不错。为什么湖北会有这么hard的省选啊/fn。D1T1\(\color{Gold}\bigstar\)第一题就不会是我没想到的。考虑一下简单情况，一条链咋做，每次操作相当于把一个空隙的大小减小\(2\)，因此可以进行一个dp。具体咋dp，先咕。然后考虑只有一个环咋做，如果是偶环，那么肯定是一直操......
  • 【 LeetCode题解 】203. 移除链表元素
    【LeetCode题解】203.移除链表元素题目链接:https://leetcode.cn/problems/remove-linked-list-elements/博客主页链接：DuckBro博客主页关注博主，后期持续更新系列文章***感谢观看，希望对你有所帮助***目录【LeetCode题解】203.移除链表元素......
  • Xcode,swift:Error Domain=kCLErrorDomain Code=1 "(null)"问题解决
    问题描述:iOS开发时,当使用用户的位置权限时,获取用户经纬度报错:ErrorDomain=kCLErrorDomainCode=1"(null)",错误域=kCLError域代码=1“（null）”解决方法:打开模拟机的设置-通用-语言与地区将地区设置为中国(如果你的开发位置在中国的话) 点击左上方Features,选择Locati......
  • 网络规划设计师真题解析--交换机（一）（STP选择过程）
    下图所示是一个园区网的一部分，交换机A和B是两台接入层设备，交换机C和D组成核心层，交换机E将服务器群连接至核心层。如图所示，（2014年真题）如果采用默认的STP设置和默认的选举过程，其生成树的最终结果为(1)，ABCD这时候交换机B上的一台工作站，想要访问交换机E上的服务器的路径是(2)，A.B-D-E......
  • SqlServer2000数据库迁移"用户已存在"问题解决
    作者:fbysss关键字：sqlserver数据库用户，关联缺失背景：数据库从另外一台服务器备份之后还原，发现程序中登录数据库失败。排查：发现"安全性"->"登录"中的数据库用户与数据库没有关联，但是手工再关联，却报出错误21002:[sql-dmo]用户***已经存在的异常信息。而删除该数据库用户也无法进行，因为......
  • 洛谷P3808 【模板】AC 自动机（简单版）题解 AC自动机模板题
    题目链接：https://www.luogu.com.cn/problem/P3808AC自动机模板题。示例程序：#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e6+5;structNode{intson[26],fail,id;Node(){}Node(int_id){memset(son,0,sizeof(son));......
  • 【牛客周赛 Round 10】A-D题解
    Ahttps://ac.nowcoder.com/acm/contest/64272/A题意游游定义一个数组为“稳定的”，当且仅当数组相邻的两个元素之差的绝对值不超过1。例如[2,3,2,2,1]是稳定的，而[1,3,2]则不是稳定的。游游拿到了一个数组，她想求出该数组的最长的“稳定的”连续子数组的长度。题解首先，如果在某......
  • CF786c分块题解
    CF786c分块题解思路：首先思考一下如果直接硬着头皮做会怎么样？对于每一个k，我都要遍历一遍数组贪心求解ans，导致n方时间复杂度要发现一下性质：答案最多为ceil(n/k)。随着k的增加,答案单调不增。随着k的增加，答案越不容易改变(连续相同的答案越多)。由1可知，总共的答案数量大概......
  • 8.30 模拟赛 光和影(dream) 题解
    概括：大分类讨论。首先有个重要结论，无论是三种操作中的哪一种，他的左儿子仍然在他的左子树内，右儿子在右子树内。同时，旋转一个点一次，对他更上面的点的深度没有影响。以此，我们预处理出一个\(up_{u,0/1}\)表示将\(u\)splay到根上，对左子树和右子树深度的影响，由于上面的结论，这个东......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99