首页 > 其他分享 >Codeforces 909 A-F

Codeforces 909 A-F

时间:2024-11-08 14:31:17浏览次数:2  
标签:语句 题目 int 线段 909 Codeforces print dp

CF909 题解

题目链接

A B C D E F
难度:红 黄 绿 蓝 绿 紫

题解

A

题目翻译:给定两个字符串,求字典序最小的“两字符串非空前缀拼接形成的字符串”。

算法标签:贪心

题目分析:
字典序最小,即从左往右依次比较字符,直到一方不剩字符或两字符不同。因此想到贪心。由于前缀非空,因此在前一字符串上不断输出,直到输出结束或字符大于后一字符串的第一个字符。
代码略。

B

题目翻译:

输入 \(n\),由此得到 \(\frac{n(n+1)}{2}\) 个线段。你可以将它们拼接在一起,但要注意不能改变它们的左右端点位置。求拼接形成的线段最小数量。下图为当 \(n=4\) 时的最优解。
image

算法标签:数学、构造、贪心

题目分析:本题有多种解题思路。

  1. 打标找规律(其一)
    若将答案按照 \(n(0 \le n)\) 的大小排成一个数列,则该数列的前几项为:

0, 1, 2, 4, 6, 9, …

不难发现答案为 \(\lfloor \frac{n+1}{2} \rfloor \times \lceil \frac{n+1}{2} \rceil\)。直接做就做完了。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    n++;
    cout << floor(n / 2.0) * ceil(n / 2.0) << endl;
    return 0;
}
  1. 打标找规律(其二)
    不难发现答案有规律 \(f_i=2\times f_{i-1}-2\times f_{i-3}+f_{i-4}\)。直接做就做完了。
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    if (n == 1) puts("1");
    else if (n == 2) puts("2");
    else if (n == 3) puts("4");
    else if (n == 4) puts("6");
    else {
        int a = 1, b = 2, c = 4, d = 6, e;
        n -= 4;
        while (n--) {
            e = 2 * d - 2 * b + a;
            a = b;
            b = c;
            c = d;
            d = e;
        }
        printf("%d\n", d);
    }
    return 0;
}
  1. 对规律进行证明
    因为规律可能错误,为了避免罚时(CF 赛制)和挂分(OI 赛制),需要对规律进行证明。
    以下内容翻译自官方题解

考虑长度为 \(1\) 的段 \([i, i + 1]\)。显然,覆盖此段的所有段必须属于不同的层。为了覆盖它,线段的左端必须位于点 \(0, 1,…, i\)(共 \(n-i\) 种选择),而右端分别在点 \(i+1,i+2,…,n\)(共 \(n-i\) 种选择)。所以覆盖 \([i, i + 1]\) 的段数等于 \(m_i=(i + 1)(n - i)\)。在所有 \(i=0,…,n-1\) 中,\(m_i\) 的最大值给出了层数的下界。
由于该问题不需要显式构造,我们可以猜测这个界限是精确的。最大值 \(m_i\) 可以在 \(O(n)\) 内找到;或者,可以看出,当 \(n\) 为奇数时,最大值出现在中间段,而当 \(n\) 为偶数时,最大值出现在两个中间段之一。
所以答案是 \((\lfloor\frac{n}{2}\rfloor+1)\cdot\lceil\frac{n}{2}\rceil\)。
我们也可以通过一个明确的构造来证明这一点。将所有线段按照其左端点的非降序排列,然后再按照其右端点的升序排列。尝试贪心地为每个下一段找到一个位置:如果 \(i\) 是当前线段的左端点,且线段 \([i, i+1]\) 在某一层是空闲的,则将当前线段添加到该层;否则,用当前线段开始一个新的层。
是的,这就是个 \(O(1)\) 的问题!(滑稽)

C

题目翻译:

题目给定一段类 Python 代码(只有两种语句:p(代表print)和f(代表for)),要求计算出这段代码有多少种合法的缩进。答案对 \(10^9+7\) 取模。

算法标签:动态规划

题目分析:类 Python 语言的缩进规则如下:

  • 第一条语句不加缩进
  • 对于其他语句有:
    • 若其为某条 for 的循环体时,加该 for 语句缩进的下一级
    • 否则不缩进
  • 特别的,每条 for 都必须有至少一条语句作为循环体
    这是一个例子:
print
print
for
	print
	for
		print
		print
	print
print

于是可以想到动态规划。设 \(dp_{i,j}\) 表示第 \(i\) 条语句缩进 \(j\) 级的方案数,\(s_i\) 表示第 \(i\) 条语句。

显然当 \(s_{i-1}=\text{"f"}\) 时,\(dp_{i,j}\) 只能从 \(dp_{i-1,j-1}\) 转移;而当 \(s_{i-1}=\text{"p"}\) 时,它可以从任意 \(dp_{i, k}(j \le k \le i)\) 处转移。因此可以维护后缀和加速。时间复杂度 \(O(n^2)\)。

#include <bits/stdc++.h>
using namespace std;
int dp[5010][5010], sum[5010], n, cnt = 0;
string s, lst;
const int mod = 1e9 + 7;
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	lst = s;
	dp[1][0] = 1;
	for (int i = 2; i <= n; i++) {
		cin >> s;
		if (lst == "f") {
			for (int j = 1; j <= i; j++) {
				dp[i][j] = dp[i - 1][j - 1];
			}
		} else {
			for (int j = i; j >= 0; j--) {
				dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) % mod;
			}
		}
		lst = s;
	}
	int ans = 0;
	for (int i = 0; i <= n; i++) ans = (ans + dp[n][i]) % mod;
	cout << ans << "\n";
	return 0;
}

D

题目大意:

标签:语句,题目,int,线段,909,Codeforces,print,dp
From: https://www.cnblogs.com/chenaknoip/p/18534352

相关文章

  • Codeforces Global Round 27
    Preface这场其实是上周六VP的,但因为后面连着好几天组队训练就一直没补题,拖到今天才补这场VP的时候写了A~E,F感觉会了但是急着吃饭就跑了,今天写了下F发现贼好写写完就过了,亏麻了A.Sliding签到,手玩下式子即可#include<cstdio>#include<iostream>#defineintlonglon......
  • Codeforces Round 982 (Div. 2)(A~C)
    对dp还不是特别熟练只做到了C(还是太菜了),开始前刚好各种事情来了,vp晚了10多分钟开才始做题,喜提排名(不是)3000+,后面有时间就尽量把dp补掉A.RectangleArrangement你需要在一个无限的方格网格上涂色,所有格子最初都是白色的。为了完成这项任务,你有\(n\)个印章。每个印章是一个......
  • Educational Codeforces Round 161 (Rated for Div. 2) - VP记录
    Preface先被A题硬控\(20\)分钟,有点不爽。又看到E题AC的人比D题多而去嗑E题去了,结果D题反而是我更能做的。将问题排序:根据你所需付出的努力,将能够最快解决的问题排在前面。(答题的次序为:以前做过的,容易的,不熟悉的,难的)——李博杰《骗分导论》\(\rmP_{114}\)所以......
  • CF1909题解
    CF1909A一眼秒之题,我们发现就是四个方向选三个方向,若是存在一个点它的方向恰好在(0,0)点的另外一个方向,则一定不成立枚举4个方向,发现有点在这个方向,显然选除这个点之外的三个方向的方案就不可行点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=105;int......
  • Codeforces Round 983 (Div. 2) 10.31 ABC题解
    CodeforcesRound983(Div.2)10.31题解A.Circuit数学(math)贪心(greedy)模拟(implementation)题意:有\(n\)盏灯,对应\(2\astn\)个开关,即每盏灯对应两个开关,开关打开或者关闭用\(1\)和\(0\)表示。给出\(2\astn\)个开关的状态,需要求解出可能开灯的最小数量和最大数量。......
  • Educational Codeforces Round 171 (Rated for Div. 2) 题解
    A.PerpendicularSegments显然构造一个\(k\timesk\)的左下角是原点的正方形即可。voidslv(){ intx,y,k;Read(x,y,k); intmn=min(x,y); if(mn*mn*2>=k*k) Write(0,'',0,'',mn,'',mn,'\n'), Write(0,......
  • Codeforces Round 984 div3 个人题解(A~F)
    CodeforcesRound984div3个人题解(A~F)Dashboard-CodeforcesRound984(Div.3)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#include<cassert>#include<cmath>#in......
  • Codeforces Round 983 (Div. 2) 题解
    CodeforcesRound983(Div.2)题解CodeforcesRound983(Div.2)Problem-A-Codeforces解题思路考虑贪心,每个灯连两个开关,即两个开的灯可以关闭一盏灯,则灯数最多则尽可能让两个开关都开的灯尽量少,灯数最少则反之#include<bits/stdc++.h>#defineendl'\n'usingnam......
  • Codeforces Round 983 (Div. 2) A~D
    链接:CodeforcesRound983(Div.2)A:Circuit大意:    n个灯,每个灯连两个开关,每个开关只连一个灯,每个灯对应的两个开关如果异或为1就亮    现给定开关状态,求灯亮的最大和最小数量思路:    求最小数量的话,将开关为1的尽量组一起,我们发现,如果开关为1的......
  • Codeforces Round 983 Div2 A-C
    目录A-CircuitB-MediansC-TrinityD-总结与思考A-Circuit题目概述Alice刚刚制作了一个包含n个灯和2n个开关的电路。每个组件(灯或开关)有两种状态:开或关。灯和开关的排列方式如下:每个灯连接恰好两个开关。每个开关连接恰好一个灯。但并不知道每个开关......