链接：http://codeforces.com/problemset/problem/284/C 思路：唯一需要注意的是操作1的区间修改，由于查询的时候只会查询最后一个元素并且区间总是从1开始 所以只需用一个s【】数组维护就行 树状数组：令c【i】为原数列，我们让s【i】为c【i】的差分数列即s【i】=c【i】-c【i-1】后 数组s的前i项和即为c【i】 对于区间x~y 加w 的操作 ：update(x,w);update(y+1,-w);仍不改变求和操作的正确性 代码： #include<bits/stdc++.h> using namespace std; typed...

http://codeforces.com/problemset/problem/940/E 思路：可以想到划分成k个长度为c的区间得到的答案一定比长度为k*c的区间要好 长度c+a的区间和c，a的区间得到的答案是一样的，这就很明显就是个dp了 dp【i】=min（dp【i-1】+a【i】，dp【i-c】+s【i】-s【i-c】-min（i-c+1~c））； 代码： #include<bits/stdc++.h> using namespace std;; typedef long long ll; ll a[100010]; ll s[100010]; ll dp[1001...

Codeforces 1238E. Keyboard Purchase 每一个字母都对答案由两种影响 ①加②减分别是他相对于他前面对答案的影响和他对于他后面对答案的影响 复杂对为2^m*（m*m） 大概在4e8左右 可以优化成1e8 __builtin_popcount（i） 求i的二进制里1的个数 #include<bits/stdc++.h> using namespace std; typedef long long L; char s[100100]; int dp[2000010]; int mp[32][32]; int main() {//cout<<I...

题目链接 题意：给一个长度为n的括号序列，你可以选择其中两个进行交换，问怎样交换可以使该括号序列的循环位置的个数最大 循环位置i可以理解为 把前i个字符放到最后面之后能使这个括号序列变成合法序列 例：（）（（）（））（） 循环位置有 2,8,10； 首先，如果一个序列的左右括号数量不相等。那他就没有循环位置，特判掉就可以。 那显然一个数量相等的括号序列一个可以通过位移 改变成一个合法的括号序列。恰巧，操作这个合法序列的括号位置和操作原来序列的括号位置得到的答案使一样的。（） 那么接下来就很简单了，我们考虑把括号分成 一级括号，二级括号，三级括号…； 那如果我们交换一级括号的左右括号，这时得...

添加链接描述 题意：n，k表示有n条线段，求最少删掉几条后使所有点最多被k条线段覆盖（线段又端点小于等于2e5） 思路：利用查分数组可以求出每一个点被多少条线段覆盖，将这些线段按左端点排序后，那么对于点i来说，只需要删掉经过i点最远的线段即可。 即最大的右端点。因为求得是前x个的右端点最大值所以用优先队列维护一下就可以 #include<bits/stdc++.h> using namespace std; typedef long long L; int c[200010],n,k,b[200010]; struct node { int l,r,id; }a[20...

传送门 题意：求n个数中满足 得对数 n<1e5,a[i]<1e5,2<=k<=100 STL！想到把每个数拆成素数的乘积得形式后 得到a[i]=p1^k1 （**） p2 ^k2… 那么对应满足条件得aj=p1^(K1)（*） p2 ^k2… 其中(k1+K1)%k==0 #include<bits/stdc++.h> using namespace std; typedef long long L; typedef pair<int,int> p; map<vector<p>,int>mp; bool prime[...

传送门 题意：n个城市，每一个城市有对应的Ci，Ki，和所在位置xi，yi； Ci代表点亮这座城市的代价， 使两座城市连接起来的代价为（Ki+Kj）*曼哈顿距离； 问使所有城市都亮起来的最小代价 思路：非常容易想到，最终的结果一定是有几个城市被点亮，之后每个城市都会有他的附属城市（直接相连或间接相连）。 仔细想想，这不就是变成了几个树吗！！！ 然后我们直接建立一个超级源点N+1（已经被点亮） 将他和所有的点连接起来，边权为Ci，在N^2处理出来所有连接两点的代价，当作边权。 然后直接求这个图的最小生成树就OK了！！！（每个连接N+1的城市即为直接被点亮的城市） 总结： 超级源点勉强算是本题难...

传送门](http://codeforces.com/group/xrTA2IaQje/contest/258354) 题意：给一个大数（长度小于1000）和一个n 但是这个大数的有些位用？表示不确定，现在要把所有？填上后使他是n的倍数，并且最小。 思路：简单DP dp[i][j]表示使第i位模数的为j的最小值，然后模拟就可以了 要注意的是我们要从后往前dp！！！这样在还原的时候才能保证字典序最小 因为如果从前往后dp，我们在还原答案的时候是从后往前还原的。这样的话会优先让低位最小而不是有限让高位最小 #include<bits/stdc++.h> using namespace...

传送门 F：Equalizing Two Strings（我见过最水的F） 题意：给你两个字符串S，T 你可以反转两个串的任意区间，任意次数，前提是两个串的翻转次数相同，每次反转区间的长度相同。问你能不能是这两个串相等 思路：首先两个串的不同字母的数量必须相等， 然后因为可以反转任意次，那么其实只要这两个串中有一个串是出现重复字母的 就一定能使这两个串相等（就相当于你一直翻转这俩重复的字母，然后去操作另一个串， 使他俩相等） 如果字母构成相同，并且没有重复字母。在s中选择一个len = 2的区间，再在t中选择一个len = 2的区间，就相当于在t中选择两个len = 2的区间。 那么只要t能...

#include<bits/stdc++.h> #define pb push_back using namespace std; typedef long long L; vector<int>vec[100010]; int dp[100010][30]; int d[100010],n,m; void init() { for(int i=0;i<=100000;i++)for(int j=0;j<=30;j++) dp[i][j]=0; for(int i=0;i<=100000;i++) d[i]=0,vec[i].clear...

#include<bits/stdc++.h> #define pb push_back using namespace std; typedef long long L; char s[200001]; int trie[200001][58],tot=0; int ed[200001]; void init() { for(int i=0;i<=tot;i++) for(int j=0;j<58;j++) trie[i][j]=0; for(int i=0;i<=tot;i++) ed[i]=0; } void add(char a[]) {...

x 进制 的 z 转换成 y 进制 ```java import java.io.*; import java.math.BigInteger; import java.util.*; public class Main{ public static void main(String args[]) throws Exception { Scanner cin=new Scanner(System.in); BigInteger x=cin.nextBigInteger(); BigIn...

tuble 元组（类似pair）

K Integers 题意：给n个数的一个全排列，每次交换相邻两个数 求使 数字1-k相邻且递增的最小步骤，k（1，n）； 思路： 当1-k已经相邻时，ans即为1-k的逆序数。 那么只需逐步算出使1-k这些数相邻所需的最小步骤 容易看出 使这k个数 向中间靠拢时花费步数最小 并容易推出如下公式 本题难点在于如何计算向中间靠拢时的步数 自己一直在考虑怎样正向算出答案， 并且没有想到利用优先队列来维护这个步数，而是推出来另一个看似可解的办法导致浪费很多时间，最后也没有完成 逆向思维 容斥 两个优先队列维护左右边 #include<bits/stdc++.h> using nam...