Codeforces Round #110 (Div. 2)
C. Message
题意
- 给两个长度不超过2000的字符串\(s,u\),仅由小写字母构成。
- 找出\(s\)的一个子串\(t\),通过3种操作变换成字符串\(u\):
- 在首或尾添加一个字符;
- 删除首或尾的一个字符;
- 改变某个位置的字符。
- 求最小的操作步数。
思路
- 因为删除、插入的代价和修改的代价一样,显然找出和\(u\)长度一样的子串\(t\)可以求得最小代价。
- 显然\(u\)可以只匹配\(s\)的一个前缀或后缀,可以通过在\(s\)首或尾添加非字母字符。
代码
D. Suspects
题意
- 有\(N(N \le 10^5)\)个嫌疑人,其中一个是凶手。
- 每个人会有一个回答(\(+a_i或-a_i\)),分别表示\(i\)认为\(a_i\)是凶手和不是凶手。
- 已知全部回答中只有\(m\)个回答是真的,其余都是假的。
- 对于每个回答,判定嫌疑人是否在说谎,输出\(Truth\)或\(Lie\),如果无法判断,则输出\(Not defined\)。
思路
- 判断一个人是否是凶手:统计认为\(i\)是凶手的数量\(c[i]\),以及认为\(i\)不是凶手的数量\(nc[i]\),则为真的回答数=\[c[i]-nc[i]+\sum_{j=1}^{n}{nc[j]}\]
- 假定\(i\)是凶手,则\([1, i)\)和\((i, n]\)的人不是凶手。维护\(L\)的最大值,\(R\)的最小值,使得\([1, L)\)和\((R, n]\)的人不是凶手。
- 当\(a_i\)可能是凶手,也可能不是凶手时,就无法判断嫌疑人的回答是否撒谎。
代码
E. Cipher
题意
- 给长度不超过100的字符串\(s\)。
- 有两种操作,每次操作选择一个位置\(p(1 \le p \lt |s|)\):
- \(++s_p, --s_{p+1}\)
- \(--s_p, ++s_{p+1}\)
- 经过若干次操作,变成了串\(t\),求不同的串\(t\)的数量。
思路
- 认真想一下的话,可以发现串的总和是不变的,两种操作想当于把1扔到相邻的位置上。
- 那么用\(f[i][j]\)表示i个字符组成和为j的方案数即可。
代码
Codeforces Round #110 (Div. 2)的更多相关文章
-
Codeforces Round #485 (Div. 2) D. Fair
Codeforces Round #485 (Div. 2) D. Fair 题目连接: http://codeforces.com/contest/987/problem/D Description ...
-
Codeforces Round #497 (Div. 2)
Codeforces Round #497 (Div. 2) https://codeforces.com/contest/1008 A #include<bits/stdc++.h> u ...
-
Codeforces Round #247 (Div. 2) ABC
Codeforces Round #247 (Div. 2) http://codeforces.com/contest/431 代码均已投放:https://github.com/illuz/Wa ...
-
Codeforces Round #626 (Div. 2, based on Moscow Open Olympiad in Informatics)
A. Even Subset Sum Problem 题意 给出一串数,找到其中的一些数使得他们的和为偶数 题解 水题,找到一个偶数或者两个奇数就好了 代码 #include<iostream& ...
-
Codeforces Round #620 (Div. 2)
Codeforces Round #620 (Div. 2) A. Two Rabbits 题意 两只兔子相向而跳,一只一次跳距离a,另一只一次跳距离b,每次同时跳,问是否可能到同一位置 题解 每次跳 ...
-
Codeforces Round #633 (Div. 2)
Codeforces Round #633(Div.2) \(A.Filling\ Diamonds\) 答案就是构成的六边形数量+1 //#pragma GCC optimize("O3& ...
-
Codeforces Round #713 (Div. 3)AB题
Codeforces Round #713 (Div. 3) Editorial 记录一下自己写的前二题本人比较菜 A. Spy Detected! You are given an array a ...
-
Codeforces Round #366 (Div. 2) ABC
Codeforces Round #366 (Div. 2) A I hate that I love that I hate it水题 #I hate that I love that I hate ...
-
Codeforces Round #354 (Div. 2) ABCD
Codeforces Round #354 (Div. 2) Problems # Name A Nicholas and Permutation standard input/out ...
随机推荐
-
关于z-index鲜为人知的事情
关于z-index很少有人去深入的了解它,因为它看起来一点儿也不复杂,不就是谁的数字大,谁就显示在前面吗?然而今天所摘录的这篇博文,让我震惊了.我承认我从来没有花时间去看具体的z-index相关文档, ...
-
[网络安全] [视频分享]KaLi Linux基础培训2016 最新的哦【福吧资源网】
最新的教程同时针对kali linux2016最新版本的多个问题解决办法还有一些实例利用. 下载地址:http://www.fu83.cn/thread-310-1-1.html
-
Winform文件下载之断点续传
在本系列的前两篇文章中,分别向大家介绍了用于完成下载任务的 WebClinet 和 WinINet 的基本用法和一些实用技巧. 今天来为大家讲述下载过程中最常遇到的断点续传问题. 首先明确一点,本文所 ...
-
Qt Write and Read XML File 读写XML文件
在Qt中,我们有时候需要把一些参数写入xml文件,方便以后可以读入,类似一种存档读档的操作,例如,我们想生成如下的xml文件: <?xml version="1.0" enc ...
-
php 分词 —— PHPAnalysis无组件分词系统
分词,顾名思义就是把词语分开,从哪里分开?当然是一大堆词语里了,一大堆词语是什么?是废话或者名言.这在数据库搜索时非常有用. 官方网站 http://www.phpbone.com/phpanalys ...
-
cookie工作原理
当客户访问某个基于PHP技术的网站时,在PHP中可以使用setcookie()函数生成一个cookie,系统经处理把这个cookie发送到客户端并保存在C:\Documents andSettings ...
-
1、原生jdbc连接oracle数据库简单介绍
一.jbdc的常用API1.Connection:数据库的链接对象2.statement:数据库sql执行对象3.preparedStatment:sql的预编译处理对象,是statement子接口4 ...
-
$Django 数据库图片渲染设计 站点设计 截断函数
1.数据库图片渲染设计 1.模型层 class User_info (AbstractUser): head_img = models.FileField (upload_to='test', def ...
-
AttributeError: &#39;module&#39; object has no attribute &#39;main&#39;
本机环境:ubuntu16.04, ros-kinetic $ roscore 报错 Traceback (most recent call last): File , in <module& ...
-
tensorflow 中 reduce_sum 理解
定义如下: reduce_sum( input_tensor, axis=None, keep_dims=False, name=None, reduction_indices=None ) redu ...