题目链接 题意：给一个仅由小写字母组成的字符串，然后m个操作，每个操作一个区间，要求把区间中排列成字典序最小的回文串，如果不能形成回文串，就忽略该操作。 思路：和上一道线段树优化计数排序的题目很像，几乎是一样的。 同样的，26棵线段树，每种字母对应一棵。 每次统计询问区间中每种字母的个数。 然后先判断是否能形成回文（奇数长度只有一个个数为奇数的，偶数长度不能出现个数为奇数的） 能的话重置区间，然后前后分别覆盖。 注意如果是奇数长度的话，记得先覆盖中间点。 需要注意这道题的输入输出方式不是标准的。。。而是要加文件。。。不然会MLE 1 然而Tle 19....Tle了好久。。。 最后换了种线段树的写法就过了。。。 然而后面这种写法就 …

题目链接 题意：给出一个字符串，仅由小写字母组成。现在给出q个操作，每个操作l,r,k三个参数，k=1表示把区间[l,r]变为升序排列，k=0表示把区间[l,r]变为降序排列。 思路：首先，最重要的一点是，由于只有26个字母，联想到计数排序。 对于字符集数目比较小情况，一定要想到计数排序。 对于字符集数目比较小情况，一定要想到计数排序。 对于字符集数目比较小情况，一定要想到计数排序。 那么我们回顾计数排序，不妨考虑升序排列的情况，是怎么做的呢？ 做法是统计该区间中每种字符的个数，然后按照字符的大小，从小到大在区间上从左到右得放置每种字符。 大概是这样子： for(int j=x;j<=y;j++) cnt[s[j] - …

题目链接 题意：给出一个n个数的排列，每次可以把一个数放到最前面或者最后面的位置，问至少要进行多少次操作才能使得数列升序。 思路：考虑不被移动的那些数，当把所有一定的数去掉以后，这些剩下的数一定是一段数值连续，位置递增的数。如果想要移动的数最少，俺么这串递增的数就尽可能长。 dp[a[i]] = dp[a[i]-1] + 1 那么ans = n - max{dp[i]} 另外：对于要移动的数，我们可以按照一定顺序（放在前面的数按照递减顺序，放在最长序列后面的数按照递增顺序）移动，可以保证每个数只需要移动一次。 /* *********************************************** Author …

题目链接 题意：给一个n*m的由小写字母组成的table.要求从上往下每一行字典序不严格递增。问最少删除几列才能满足。 思路：一开始想的是用一个left数组维护每次删除后某一列左边是哪一列，目的是为了下次的判断。 再想了下，发现没必要。我们只需要知道，两行之间的关系是否确定就好了。over[i][j]为真表示第i行和第j行的胜负已分，对于胜负已分的行，大小无所谓。 对于胜负未分的行，如果table[i][j]>table[i+1][j]，就必须要删掉这一列了。。。。 需要注意的是，某一列最多删一次，记得打上标记。 以及ove标记的时候，要在最后确定这一列没有被删以后再标记。。。用一个set存下可能的胜负已分的行的下标即可。 …

题目链接 题意：n堆石子，每堆a[i]个，k种颜色。给每个石子涂色，要求对于每种颜色，任意两堆中该颜色石子的个数最多差一个。问是否有解，有解输出一组方案。 思路：我们发现有解与否只和最大值最小值有关。 设mn为最小值,mx为最大值。 当mx>mn+k时无解，否则有解。 如果有解。。。输出方案就好了。。。 /* *********************************************** Author :111qqz Created Time :2016年10月04日 星期二 02时40分20秒 File Name :code/cf/problem/509B.cpp …

题目链接 题意：nm个格子，有和.两种类型。定义一个湖为边相邻的只有.组成的最大点集合，且任何一个.不在边界上。现在给出一个nm的图保证至少有k个湖。问填多少个.成，才能使得恰好有k个湖。 思路：贪心，先处理出所有的湖的大小，然后从小往大填。 注意dfs的时候如果某个“可能”的湖遇到了边界，要把之前打的标记撤销掉。 /* *********************************************** Author :111qqz Created Time :2016年10月03日 星期一 21时18分03秒 File Name :code/cf/#375/D.cpp …

题目链接 题意：给出n,m，n个数，对其中的一些数进行修改，要求1..m中出现次数最少的数最大，输出这个最少的数最大是多少，以及修改的次数。 思路：最小的数最多出现n/m次。 竟然因为排序后下标变乱不知所措40分钟。。。我也是醉了。。。 /* *********************************************** Author :111qqz Created Time :2016年10月03日 星期一 19时29分52秒 File Name :code/cf/#375/C.cpp ************************************************ */ #include …

题目链接 。。。sad..... 果然没睡够&起来就写题脑子完全就是不清醒的状态。。。 这个不清醒。。。主要体现在。。。。10+次。。。忘记删条件编译。。。 改着改着。。。就忘记这件事了。。。好烦啊。。。本来早就A了。。。结果又接着去改。。。 题目链接：jag2016 就水了三道题。。。。 A是个暴力。。直接O(n2)算乘积，然后再check一下合法性就好。。。尼玛wa到我怀疑人生。。。过了好久才考虑也许是不支持条件编译的问题。 /* *********************************************** Author :111qqz Created Time :2016年10月03日 星期一 12 …

题目链接 题意：给出n，有1..n n个数，可以选择两个数进行加，减，乘，三种操作，操做完得到一个数放回。 n-1次操作后只剩下一个数。现在要求剩下的数为24.问方法。 思路：我们发现。。。两个数相减可以为1.。那么只要找到4个数的方案和5个数的方案就好了。。。 4个数：123*4 5个数：4*5+3+2-1 然而窝一开始以为必须前面减后面。。。 所以是按照4K,4K+1,4K+2,4K+3分的类。。。每4个数得到两个-1，再相乘。。。。麻烦了一点。。代码写了一半的时候意识到了按2K,2K+1分类就行。 /* *********************************************** Author :111qqz …

题目链接 题意：存在一个[2..100]之间的数，每次可以询问一个数是否是该数的因子，返回yes或者no,最多询问20次。每次要输出询问的数，以及最后要输出这个数是否是质数。 思路：第一次做交互题。。。发现完全不能按照以前的思路。。。 更像是相反的。。。把output看做某种输入。。。input里是某种结果。。。我要根据input里的东西来确定一些东西。 就是先有output，再有input。。。output是选手的输入（最后一个除外），input是返回结果(不是你写的代码的返回结果） 对于这道题。。我们要尽可能少得猜一个数的因子，以确定该数是否为质数。 一个数不是质数的话，就有至少两个大于1的因子。。。 很容易想到。。。判素因 …