2020 5月月赛题解

phython 2020-05-02 22:32:48 2020-05-02 23:15:51

2020 5月月赛题解

花絮

  • csf: 从参赛人数来看,我很满意
  • 中途为啥oj崩了,原因还在找= -=

1001. 社会热点题

送分题,不解释,直接输出7即可,注意需要添加文件IO操作。 不会的同学,请看这个链接https://turingjudge.com/problem/1001

1002. 功能实现题

读入字符串,将每个字符传换成大写字母即可。

	for(int i = 0;s[i];++i) {
		if(s[i] >= 'a' && s[i] <= 'z') {
			s[i] = ('A' - 'a') + s[i];
		}
	}

1003. 数学计算题

根据题目中的提示,面积的比值等于线比值的平方倍。

S_1 = 6.283185307

\frac{S_x}{S_1} = (\frac{x}{1})^2

S_x = S_1 \times x^2

注意精度问题,也就是说 S_1 表示的越精确越好。

1004. 朴素模拟题

这道题是错误率最高的一道题,其中有一个原因是是出题人的问题,第一个样例弄错了,还好修正及时,十分抱歉。

需要特别注意的是,左上角坐标是 (1,1) ,右下角坐标是 (N,M) ,也就是说 x 可以看成是行号, y 可以看成是列号。

U,D 指令相当于行在上下移动, L,R 相当于列在左右移动。

然后如果越界了,那么就重置为边界处就可以了。

参考代码:

	int len = st.size() >> 1;
	for (int i = 0; i < len; i++){
		char dir = st[i<<1];
		int step = st[i<<1^1] - '0';
		if (dir == 'L'){
			y -= step;
			y = max(1, y);
		}else if (dir == 'R'){
			y += step;
			y = min(m, y);
		}else if (dir == 'U'){
			x -= step;
			x = max(1, x);
		}else{ // D
			x += step;
			x = min(n, x);
		}
	}
	printf("%d %d\n", x, y);

1005. 递归分解题

这是一道非常明显的,考察递归的题目,如果分解出来的数字大于9,则需要继续进一步分解。

我们可以设计函数dfs(int n)表示对 n 进行分解。

那么代码就可以写成:

int _sum(int x) {
	int ans = 0;
	while(x) {
		ans += x % 10;
		x /= 10;
	}
	return ans;
}
void dfs(int x) {
	if(x < 10) {
		cout << x;
		return ;
	}
	int sum = _sum(x);
	cout << "[";
   	dfs(sum);
	cout	<< "](";
	dfs(sum+1);
	cout	<< ")";
}

1006. 动态规划题

这道题改编自“石子合并”问题,只不过石子合并是2堆相邻的石子进行合并,而这道题则是3个相邻的物体进行合并,但思路是一样的。

2堆石子合并的时候,是2个区间在合并;而3个相邻物体进行合并,则是3个区间在合并。

dp[l][r] 表示把 [l,r] 这段区间内的宠物合并成变异宠物的最大概率。

枚举两个分界点 i,j ,将区间 [l,r] 分解成3个相邻的区间 [l,i] [i+1,j-1] , [j,r] 那么我们就可以得到转移方程。

不妨设 x_1 = dp[l,i], x_2 = dp[i+1,j-1], x_3 = dp[j,r]

考虑所有的8种情况

情况1:三个区间都合成了变异宠物,这种情况的概率是 x_1*x_2*x_3 ,那么合并3个变异宠物得到变异宠物的概率是 1

P[1] = x_1*x_2*x_3*1

情况2:第一个区间普通宠物,第二、三区间变异宠物,这种情况的概率是 (1-x_1)*x_2*x_3 ,那么合并得到新的变异宠物概率是 p_1

P[2] = (1-x_1)*x_2*x_3*p_1

情况3:第一、二个区间普通宠物,第三区间变异宠物,这种情况的概率是 (1-x_1)*(1-x_2)*x_3 ,那么合并得到新的变异宠物概率是 p_2

P[3] = (1-x_1)*(1-x_2)*x_3*p_2

以下省略剩余5种情况。最后把所有情况的概率求和即得到本次分割的最大概率。

参考代码:

double dfs(int l, int r) {
    if (l == r) return a[l];
    if (vis[l][r]) return dp[l][r];
    vis[l][r] = true;
    for (int i = l; i < r; i += 2) {
        for (int j = r; j > i; j -= 2) {
            double x1 = dfs(l, i);
            double x2 = dfs(i + 1, j - 1);
            double x3 = dfs(j, r);
            double ans = x1 * x2 * x3;
            ans += p1 * (1 - x1) * x2 * x3;
            ans += p1 * x1 * (1 - x2) * x3;
            ans += p1 * x1 * x2 * (1 - x3);
            ans += p2 * (1 - x1) * (1 - x2) * x3;
            ans += p2 * (1 - x1) * x2 * (1 - x3);
            ans += p2 * x1 * (1 - x2) * (1 - x3);
            dp[l][r] = std::max(dp[l][r], ans);
        }
    }
    return dp[l][r];
}

// ans = dfs(0, n - 1)

1007. 图论扩展题

本题是出题人的失误,出的数据太弱了,放掉了一些看起来正确的“假算法”,过题的同学再仔细审视一下自己的算法,有没有问题。

考虑u是v的真祖先,我们就在图上连接一条从u到v的有向边。

按照拓扑排序的思想,所有v的祖先都会排在v的前面,进一步思考,我们发现v的父节点一定是v最靠后的那个祖先。

所以我们就有了思路,当节点u从队列中弹出的时候,根据拓扑排序的思想,我们需要把u指向的所有节点v的入度-1,此时,我们顺便把这个节点v的父节点覆盖为u即可,fa[v] = u;。 这样的话,一定是v的真正的父节点最后覆盖了fa[v]

时间复杂度 O(n)

参考代码:

	cin >> n >> m;
	for(int i = 1;i <= m;++i) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		indeg[v] ++;
	}

	queue<int> Q;
	for(int i = 1;i <= n;++i) {
		if(indeg[i] == 0) {
			Q.push(i);
		}
	}	
	while(!Q.empty()) {
		int u = Q.front();Q.pop();
		for(int i = 0;i < G[u].size();++i) {
			int v = G[u][i];
			fa[v] = u;
			if(--indeg[v] == 0) {
				Q.push(v);
			}
		}
	}
	for(int i = 1;i <= n;++i) {
		cout << fa[i] << " ";
	}
	cout << endl;

csl: 被我bitset直接草了

恭喜以下选手

共 1 条回复

FiLaReTKuN

前排

AMAZE UI
Hello world!