500pt: A. Mashmokh and Lights time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Mashmokh works in a factory. At the end of each day he must turn off all of the lights. The lights on the factory are indexed from 1 to n. There are n buttons in Mash...
题目链接 题意： 输入n个值，表示当前点与输入点（关联点）有一条边。初始从1开始，当到达一个点时，点值加一，如果此时值为奇数，那么将走到关联点，否则将到达右边相邻的点 求到达n+1时，要转移多少次 分析： 考虑一下第一次到达点P时候的情况，之前的每一个点的值肯定都是偶数（只能从之前的点过来，且只有在值为偶数时才能向右走）。此时因为当前点的值是奇数，所以会到达关联点Q（一定不在当前点的右侧），那么如果想到达...
codeforces.com/contest/426/problem/D 题意： 首先给出联通块的定义：对于相邻（上下和左右）的相同的数字视为一个联通块 现给一个n*m的只有0和1的矩形和数字k，求出最小反转个数使得整体包括若干个矩形联通块（即每个联通块均是矩形）(1?≤?n,?m?≤?100; 1?≤?k?≤?10) 如果最小次数比k大，输出-1 分析： 题目的特点是k比较小，也就是说反转的次数比较少，所以可以从这里入手。直接枚举所有的位置肯定是不行了，那么可以这样...
这场CF真是逗了。。。 因为早上7点起的，所以到做CF的时候已经17个小时没有休息了，再加上中午5小时的比赛。 头脑很不清晰。做第一个题的时候差点读成求最大字段和了。然后发现是水体，迅速A掉。 然后开始看了B题，第一遍没有看懂，此时大脑已经看不下去了。然后突然某个群说D是水题。 我去看了一下D，我去，D的题意好简单啊。。。。于是，冥思苦想中。。。。。一直到快要1点 的时候，还是没有结果。。。此时我感觉不行了。。...
CF424 A. Squats 题目意思： 有n（n为偶数）个x和X，求最少的变换次数，使得X的个数为n/2，输出变换后的序列。 解题思路： 统计X的个数ans,和n/2比较，少了的话，需要把n/2-ans个x变成X，多了的话需要把ans-n/2个X变成x.（从前往后扫一遍就行了）。 代码： //#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include...
Codeforces Round #244 (Div. 2)D （后缀自动机） （标号为0的节点一定是null节点，无论如何都不能拿来用，切记切记，以后不能再错了） 这题用后缀自动机的话，对后缀自动机的很多性质有足够深刻的理解。没想过后缀数组怎么做，因为不高兴敲。。。。 题意：给出两个长度均不超过5000的字符串s1,s2，求这两个串中，都只出现一次的最短公共子串。 解题思路：求的是公共子串，然后对出现的次数又有限制，第一想法就是后缀自动机啊...
题目链接 题意： 给定n个点，每个点有一个权值的有向图。现在需要选定一些点，使得这些点权值和最小，且满足：如果i能到达j且j能到达i，那么i、j可以只选一个 分析： 强联通模板题 //使用时只更新G完成构图//scc_cnt从1开始计数//pre[]表示点在DFS树中的先序时间戳//lowlink[]表示当前点和后代能追溯到的最早祖先的pre值//sccno[]表示点所在的双连通分量编号//vector G保存每个点相邻的下一个点序号//stack S是算法用到的栈c...
题目链接 题意： n个数a[i]，f(i, j) = (i - j) ^ 2 + sigma(a[k]) ^ 2, i < k <= j，求最小的f值 n (2?≤?n?≤?100000).(?-?104?≤?a[i]?≤?104) 分析： 关键在于题意的转换。简单的考虑，需要知道每个区间的信息，复杂度难以降下来，应该将题目的f函数进行化简。既然考虑区间是不可行的，那么就尝试是否能将区间分成两个短点的计算。这里用到了一个常用的转换：区间和转化为前缀和的差。转换后就得到f(i, j) = (i - j) ^ 2 ...
题目链接 题意： 给一棵树n个节点，1为根节点。操作为，选定一个节点x，当前值取反，x的孙子，孙子的孙子。。。均取反 现在告诉初始时每个点的值和最后每个点的目标值，求操作次数最少时需要选择那些节点 (1?≤?n?≤?105) 分析： 深度浅的点一定是受影响最小的（根节点只受自己的影响），所以从根依次向下递推处理即可 const int MAXN = 110000;VI G[MAXN], ans;int now[MAXN], goal[MAXN];void dfs(int u, int fa, int a...
B. Football Kit time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Consider a football tournament where n teams participate. Each team has t...
题目链接 题意： 一行a[i]，一行b[i]，a和b是一一对应的。选取任意个数对，使得sigma（a）/ sigma（b）等于k，求这时候sigma（a）的最大值 分析： 这个题目关键在于对sigma（a）/ sigma（b）== k的处理。对于这种式子，用每个数的比值显然是不行的，因为没法累加；而且是double型，没法DP 考虑一个每个数对对这个式子的影响，如果每个数都是a = k * b，那么显然是可以的；如果a小于k * b，那么在整体中，当前数对少的数肯定要...
题目链接：http://codeforces.com/contest/433/problem/A 题目大意：A有n个苹果，希望平分给B和C，但是没有刀子，不能切水果，只能给整个苹果。苹果有两种规格，100g和200g，给出A拥有的苹果，问能不能平分给B和C。 水题，不过有一个坑， 首先容易想到的是，将每个苹果的重量变成1或者2，把所有苹果的重量加起来之后，如果是奇数，则无法平分，否则能平分。 当A只有一个苹果时，是无法平分的，这个也不算坑，很容易想到，如果没...
Codeforces Round #247 (Div. 2) http://codeforces.com/contest/431 代码均已投放：https://github.com/illuz/WayToACM/tree/master/CodeForces/431 A - Black Square 题目地址 题意： Jury玩别踩白块，游戏中有四个区域，Jury点每个区域要消耗ai的卡路里，给出踩白块的序列，问要消耗多少卡路里。 分析： 模拟水题.. 代码： /** Author: illuz <iilluzen[at]gmail.com>* File: a.cpp* Cre...
Codeforces Round #249 (Div. 2) A B C http://codeforces.com/contest/435 代码均已投放：https://github.com/illuz/WayToACM/tree/master/CodeForces/435 435A - Queue on Bus Stop 题目地址 题意： 给出n组人的人数在排队等公交，每辆公交最多坐m人。 一定是按队列顺序坐，如果能坐上去尽量坐上去，坐不上去就等下一辆。 分析： 直接模拟即可。 代码： /** Author: illuz <iilluzen[at]gmail.com...
t题目：http://codeforces.com/problemset/problem/359/C n多的WA................................自己的代码能力还是很有问题的....................... 总结下自己写代码的状态： 1、没有理清思路就开始写...... 2、排错的时候，应该好好理理自己的逻辑，看看代码是否把自己的逻辑表达清楚 3、看别人代码的时候，别老是想着看不懂，那么你一定看不懂，理理思路，尤其模拟下，试试去理解。 4、排错的时候，不要稍微改动一点...
B. Maximum Value