Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
AGC031 解题记录
? 解题记录 ?
? Atcoder ?
2019-03-22 19:24:21
886
0
0
rockdu
? 解题记录 ?
? Atcoder ?
### A - Colorful Subsequence 简化版题意：输入一个字符串，输出每种字母的个数$+1$的乘积的结果$-1$。 $|S| \le 10^5$ 题解：按照题意模拟就完了。 ### B - Reversi 题意：有$N$个格子，每一个格子有一个颜色$c_i$，每次可以选择颜色相同的两个格子把夹在中间的格子的涂成一样的颜色，问可能形成多少种不同的序列。$N,c_i\le 2\times 10^5$ 题解：$Easy$的题目，容易发现用一段去包含之前盖过的一段是没有意义的，又因为选择的段不可能相交，那么所有的段相离。同时，连续一段的相同颜色格子等价于一个格子，可以缩起来。 按套路设$f_i$表示考虑到$i$位置的种类数，考虑当前这一个格子往不往前面盖，盖到哪里，发现每一次可以从之前相同颜色的所有格子的前一格转移过来。维护每种颜色前一格的$dp$值之和即可。 良心$B$啊 ``` #include<cstdio> using namespace std; const int mod = 1e9 + 7; int f[200005], lp[200005], sp[200005], a[200005], n, in; int main() { scanf("%d", &n), f[0] = 1; for(register int i = 1; i <= n; ++i) scanf("%d", &a[i]); for(register int i = 1; i <= n; ++i) { f[i] = f[i - 1]; if(a[i + 1] == a[i]) continue; (f[i] += sp[a[i]]) %= mod; (sp[a[i]] += f[in]) %= mod, in = i; } printf("%d", f[n]); return 0; } ```
上一篇:
省选模板：一些准备
下一篇:
更好实现的简单插值法——牛顿插值简介
0
赞
886 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册