CSP-J2020第二轮 解题分析

CSP-J2020第二轮 解题分析,第1张

1.优秀的拆分

算法分析

奇数不存在优秀的拆分。


偶数一定存在优秀的拆分。


从大到小枚举2的 i i i次方,从24到1。


如果 n n n能被 2 i 2^i 2i整除,说明 2 i 2^i 2i是他的一个拆分项,输出。


2 i 2^i 2i可以表示为 1 < < i 1<1<<i


#include 
#include 
#include 
using namespace std;
int main()
{
	int n; scanf("%d", &n);
	if (n % 2) printf("-1\n");
	else
	{
		for (int i = 24; i >= 1; --i)
		{
			if (n / (1 << i) == 1) 
			{
				n -= (1 << i);
				printf("%d ", 1 << i);
			}			
		}
	}
	return 0;
}

算法拓展

打表。


预处理出 2 i 2^i 2i次方的值,用数组存起来。


对每个预处理的值进行标记。


倒序枚举 n n n,如果枚举的值被标记了,说明他是 2 i 2^i 2i


可以直接输出,相应的 n n n的值也要减去 2 i 2^i 2i


#include 
#include 
#include 
using namespace std;
int b[30] ={0,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216};
int v[18000000];
int main()
{
	int n; scanf("%d", &n);
	if (n % 2) 
	{
		printf("-1"); return 0;
	}
	for (int i = 1; i <= 24; ++i) v[b[i]] = 1;
	int x = n;
	while (x)
	{
		if (v[x]) 
		{
			printf("%d ", x);
			x = n - x;
			n = x;
		}else --x;
	}
	return 0;
}

2.直播获奖

算法分析

每个选手的成绩取值范围是 [ 0 , 600 ] [0, 600] [0,600],可以用hash思想。


读到一个成绩的时候,就标记一下。


然后从600到0倒序枚举分数线统计个数,当个数大于等于获奖人数时退出,此时就是答案。


时间复杂度 O ( 600 n ) O(600n) O(600n) n n n最大为10万,可以过。


注意事项:对于 p ∗ w % p * w\% pw%的下取整,要注意精度跳变,可以用整除替换: p ∗ w / 100 p * w / 100 pw/100


#include 
#include 
#include 
#include 
#include 
using namespace std;
int f[610];
int main()  
{ 
	int n, w, cnt, d;
	scanf("%d%d", &n, &w);
	for (register int t = 1; t <= n; ++t)
	{
		scanf("%d", &d);
		++f[d];  // 记录该成绩的人数有多少个  
		cnt = t * w / 100;
		if (cnt < 1) cnt = 1;
		// 找排名第cnt的分数 
		int s = 0, k;
		for (k = 600; k >= 0; --k)
		{
			s += f[k];
			if (s >= cnt) break; 
		} 
		printf("%d ", k);
	}
	return 0;
}

算法拓展

1.插入排序。


由大到小排序,增加一个人时,直接向前邻项交换。


由大到小取。


排到最后,其实就相当于一遍完整插入排序的时间复杂度。


插入排序时间复杂度不稳定,最坏情况是 O ( n 2 ) O(n^2) O(n2),最好情况是 O ( n ) O(n) O(n),不知道能过多少点。


2.对顶堆。


对顶堆可以维护单调区间第k大数或第k小数。


本题适用于求第k大数。


左边的是小根堆q1,右边的是大根堆q2。


两者拼接起来就是由大到小。


假设该轮的获奖人数为t。


第x个选手成绩出来后,如果此时q1的个数小于t,则把x丢进q1。


如果q1的个数还是小于t,则q2的堆顶出堆,进入q1,直到q1的个数等于t。


此时q1的堆顶分数就是答案。


入堆和出堆时间复杂度都是 l o g log log的,整体复杂度 O ( n l o g n ) O(nlogn) O(nlogn)


3.表达式

算法分析

对于后缀表达式的计算,朴素的算法可以借助数字栈。


从左到右扫描,遇到数字就入栈,遇到 *** 作符op,从栈中依次d出两个数字x2和x1,进行运算 x 1   o p   x 2 x1 \,op \,x2 x1opx2,然后将运算结果再入栈。


如果是动态取反某个数字q次查询,这个复杂度就高了,为 O ( n ∗ q ) O(n*q) O(nq)


对于这种改变的地方很少,但是需要整体结果的,就需要考虑将改变的影响降到最少。


表达式树。


建立表达式树的时候还得借助栈。


在表达式中,数字都是叶结点,运算符都是非叶结点。


叶结点的编号按照1~n进行,运算符按照从左到右的顺序在n的基础上分别加1。


结点开结构体,存父节点、左右儿子、值、字符。


struct node
{
	int par, lchild, rchild,  data;
	char c;
}stree[1000010];

字符串用 g e t c h a r getchar getchar读入。


当读入 x x x的时候,后面跟的就是数字,把数字处理出来,然后建立结点并入栈。


当读入 ! ! !的时候,建立结点,栈顶的结点作为该结点的左儿子。


当读入 & \& & ∣ | 时,建立结点,栈顶的结点分别作为他们的右儿子和左儿子。


这样就建成了表达式树。


根结点的值就是整体结果。


查询时。


取反的结点都是叶结点。


只需要改变该叶结点到根结点之间的结点的值就可以了。


如果数据是随机的,每次查询的平均复杂度就是 l o g log log级别的。


一个很重要的优化:当某个结点的值和原先的值相同时,则直接返回根节点的值。


本题有特殊数据,以下代码官方数据能得95分。


#include 
#include 
#include 
using namespace std;
char s[1000010];
int a[100010], n, cnt, sstack[1000010], stop;
struct node
{
	int par, lchild, rchild,  data;
	char c;
}stree[1000010];
int main()
{
	int len = 0;
	while ((s[++len] = getchar()) != '\n'); s[len] = 32;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	cnt = n; 
	for (int i = 1; i <= len; ++i) 
	{
		if (s[i] == 'x')
		{
			int snum = 0, t = i + 1;
			while (s[t] != 32)
			{
				snum = snum * 10 + s[t] - '0';
				++t;
			}
			i = t;
			sstack[++stop] = snum;
			stree[snum].data = a[snum]; stree[snum].c = a[snum] + '0';
		}else if (s[i] == '!')
		{
			stree[++cnt].lchild = sstack[stop]; --stop;
			stree[stree[cnt].lchild].par = cnt;
			stree[cnt].data = !stree[stree[cnt].lchild].data;
			stree[cnt].c = '!';
			sstack[++stop] = cnt;
		}else if (s[i] == '&')
		{
			stree[++cnt].rchild = sstack[stop]; --stop;
			stree[cnt].lchild = sstack[stop]; --stop;
			stree[stree[cnt].lchild].par = cnt;
			stree[stree[cnt].rchild].par = cnt;
			stree[cnt].data = stree[stree[cnt].lchild].data & stree[stree[cnt].rchild].data;
			stree[cnt].c = '&';
			sstack[++stop] = cnt;
		}else if (s[i] == '|')
		{
			stree[++cnt].rchild = sstack[stop]; --stop;
			stree[cnt].lchild = sstack[stop]; --stop;
			stree[stree[cnt].lchild].par = cnt;
			stree[stree[cnt].rchild].par = cnt;
			stree[cnt].data = stree[stree[cnt].lchild].data | stree[stree[cnt].rchild].data;
			stree[cnt].c = '|';
			sstack[++stop] = cnt;
		}
	}
	int q; scanf("%d", &q);
	while (q--)
	{
		int t; scanf("%d", &t);
		int p, sres = !a[t];
		while (1)
		{
			p = stree[t].par;
			if (stree[p].c == '!') sres = !sres;
			else if (stree[p].c == '&')
			{
				if (stree[p].lchild == t) sres = sres & stree[stree[p].rchild].data;
				else sres = sres & stree[stree[p].lchild].data;
			}else if (stree[p].c == '|')
			{
				if (stree[p].lchild == t) sres = sres | stree[stree[p].rchild].data;
				else sres = sres | stree[stree[p].lchild].data;
			}
			if (sres == stree[p].data) 
			{
				sres = stree[cnt].data; break;
			}
			t = p;
			if (stree[t].par == 0) break;
		}
		printf("%d\n", sres);
	}
	return 0;
}

以上表达式树不是平衡树,有3种特殊情况会过不了。


1.全都是 ! ! !或大部分是。


树退化成了链。



2.全都是 & \& &或大部分是。


树几乎退化成了链。



3.全都是 ∣ | 或大部分是。


树几乎退化成了链。


如下图:


在上述过程中,我们可以发现,某些点的值无论怎么变,都不会影响最终的结果。


比如 0   &   a 0\,\&\,a 0&a a a a的值无论怎么改变都不会影响结果,此时我们可以给值为 a a a的这个点打个标记。


相似的还有 1   ∣   a 1\,|\,a 1a


建立表达式树后,从根结点开始向下 O ( n ) O(n) O(n)的复杂度就可以完成打标记。


如果一个叶结点到跟结点的路径上,有一个点被打标记了,那么该结点也要被打标记,即标记可以下传。


这样我们最终只要判断取反的叶结点是否打了标记。


如果打标记了,则结果为根结点的值。


如果没打标记,则结果为根结点的值取反。


为什么?假设取反的叶结点没有打标记,则该叶结点到根结点的路径上都没有打标记。


则该叶结点的父结点的值就要取反,该父结点的父结点的值也要取反,依次类推,到根结点之间包含根结点的值都要取反。


查询的复杂度是 O ( 1 ) O(1) O(1)


#include 
#include 
#include 
#include 
using namespace std;
char s[1000010];
int a[100010], n, cnt, sstack[1000010], stop;
struct node
{
	int lchild, rchild,  data, tag;
	char c;
}stree[1000010];
void print_tag(int t)
{
	if (stree[t].lchild == 0 && stree[t].rchild == 0) return;  // 叶结点  
	if (stree[t].tag == 1)
	{
		stree[stree[t].lchild].tag = stree[stree[t].rchild].tag = 1;
	}else if (stree[t].c == '&')
	{
		if (stree[stree[t].lchild].data == 0) stree[stree[t].rchild].tag = 1;
		if (stree[stree[t].rchild].data == 0) stree[stree[t].lchild].tag = 1;
	}else if (stree[t].c == '|')
	{
		if (stree[stree[t].lchild].data == 1) stree[stree[t].rchild].tag = 1;
		if (stree[stree[t].rchild].data == 1) stree[stree[t].lchild].tag = 1;
	}
	print_tag(stree[t].lchild);
	print_tag(stree[t].rchild);
}
int main()
{
	int len = 0;
	while ((s[++len] = getchar()) != '\n'); s[len] = 32;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	cnt = n; 
	for (int i = 1; i <= len; ++i) 
	{
		if (s[i] == 'x')
		{
			int snum = 0, t = i + 1;
			while (s[t] != 32)
			{
				snum = snum * 10 + s[t] - '0';
				++t;
			}
			i = t;
			sstack[++stop] = snum;
			stree[snum].data = a[snum]; stree[snum].c = a[snum] + '0';
		}else if (s[i] == '!')
		{
			stree[++cnt].lchild = sstack[stop]; --stop;
			stree[cnt].data = !stree[stree[cnt].lchild].data;
			stree[cnt].c = '!';
			sstack[++stop] = cnt;
		}else if (s[i] == '&')
		{
			stree[++cnt].rchild = sstack[stop]; --stop;
			stree[cnt].lchild = sstack[stop]; --stop;
			stree[cnt].data = stree[stree[cnt].lchild].data & stree[stree[cnt].rchild].data;
			stree[cnt].c = '&';
			sstack[++stop] = cnt;
		}else if (s[i] == '|')
		{
			stree[++cnt].rchild = sstack[stop]; --stop;
			stree[cnt].lchild = sstack[stop]; --stop;
			stree[cnt].data = stree[stree[cnt].lchild].data | stree[stree[cnt].rchild].data;
			stree[cnt].c = '|';
			sstack[++stop] = cnt;
		}
	}
	
	print_tag(cnt);  // 打标记,打上标记的结点,值是否改变,对结果不影响  
	
	int ans = stree[cnt].data;
	int q; scanf("%d", &q);
	while (q--)
	{
		int t;  scanf("%d", &t);
		if (stree[t].tag == 0) printf("%d\n", !ans); else printf("%d\n", ans);
	}
	return 0;
}

4.方格取数

算法分析

这种矩阵上求最值的题目,dp无疑了。


但是每次可以向上、向下和向右走,定义两个维度如 f [ i ] [ j ] f[i][j] f[i][j]表示从 ( 1 , 1 ) (1, 1) (1,1)走到 ( i , j ) (i, j) (i,j)的最值会有后效性。


可以考虑以列作为阶段,从左到右推进。


对于每个点 ( i , j ) (i, j) (i,j)有从上到下、从左到右和从下到上、从左到右两种方式到达。


然后再合并两种方式的最值。


f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0]:第 j j j列从上到下、从左到右到达 ( i , j ) (i, j) (i,j)的最大值。


f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1]:第 j j j列从下到上、从左到右到达 ( i , j ) (i, j) (i,j)的最大值。


f [ i ] [ j ] [ 2 ] f[i][j][2] f[i][j][2]:合并以上两种方式,到达 ( i , j ) (i, j) (i,j)的最大值。


需要开 l o n g   l o n g long \, long longlong


#include 
#include 
#include 
#define ll long long
using namespace std;
int n, m, a[1010][1010];
ll f[1010][1010][3];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
	
	for (int i = 1; i <= n; ++i) f[i][1][1] = f[i][1][0] = f[i][1][2] = f[i-1][1][0] + a[i][1];
	
	for (int j = 2; j <= m; ++j)
	{
		// f[i][j][0] 
		f[1][j][0] = f[1][j-1][2] + a[1][j];
		for (int i = 2; i <= n; ++i)
			f[i][j][0] = max(f[i][j-1][2], f[i-1][j][0]) + a[i][j];
		// f[i][j][1]
		f[n][j][1] = f[n][j-1][2] + a[n][j];
		for (int i = n - 1; i >= 1; --i)
			f[i][j][1] = max(f[i][j-1][2], f[i+1][j][1]) + a[i][j];
		// f[i][j][2]
		for (int i = 1; i <= n; ++i)
			f[i][j][2] = max(f[i][j][0], f[i][j][1]);
	}
	printf("%lld\n", f[n][m][2]);
	return 0;
}

算法拓展

记忆化搜索。


f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0]表示从上到下、从左到右到达 ( i , j ) (i, j) (i,j)的最大值, f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1]表示从下到上、从左到右到达 ( i , j ) (i, j) (i,j)的最大值。


目标值是 f [ n ] [ m ] [ 0 ] f[n][m][0] f[n][m][0]


倒序组织记忆化dfs代码。


核心代码:

ll dfs(int x, int y, int t)
{
	if (x < 1 || x > n || y < 1 || y > m) return mininf;
	if (f[x][y][t] != mininf) return f[x][y][t];
	if (t == 0) f[x][y][t] = max(dfs(x-1, y, 0), max(dfs(x, y-1, 0), dfs(x, y-1, 1))) + a[x][y];
	else f[x][y][t] = max(dfs(x+1, y, 1), max(dfs(x, y-1, 0), dfs(x, y-1, 1))) + a[x][y];
	return f[x][y][t];
}
printf("%lld\n", dfs(n, m, 0));

其实记忆化搜索就是dp的一种组织形式,也是dfs中优化的利器。


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/562249.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-01
下一篇 2022-04-01

发表评论

登录后才能评论

评论列表(0条)