吴国庆

分类

acm(50) Codeforces(6) Xcpc(4) 未归档(2) 算法学习(6) 题解(38)

/ 注册

全部文章（共106篇）

codeforces 940E Cashback(DP)

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【...

2020-05-04

0 746

Codeforces 1238E. Keyboard Purchase状压dp

Codeforces 1238E. Keyboard Purchase 每一个字母都对答案由两种影响 ①加②减分别是他相对于他前面对答案的影响和他对于他后面对答案的影响复杂对为2^m*（m*m）大概在4e8左右可以优化成1e8 __builtin_popcount（i）求i的二进制里1的个数...

2020-05-04

0 621

Codeforces Round #594 (Div. 2 )D2 The World Is Just a Programming Task (Hard Version) 思维

题目链接题意：给一个长度为n的括号序列，你可以选择其中两个进行交换，问怎样交换可以使该括号序列的循环位置的个数最大循环位置i可以理解为把前i个字符放到最后面之后能使这个括号序列变成合法序列例：（）（（）（））（）循环位置有 2,8,10；首先，如果一个序列的左右括号数量不相等。那他就没...

2020-05-04

0 550

Too Many Segments (hard version)贪心

添加链接描述题意：n，k表示有n条线段，求最少删掉几条后使所有点最多被k条线段覆盖（线段又端点小于等于2e5）思路：利用查分数组可以求出每一个点被多少条线段覆盖，将这些线段按左端点排序后，那么对于点i来说，只需要删掉经过i点最远的线段即可。即最大的右端点。因为求得是前x个的右端点最大值所以用优...

2020-05-04

0 589

Codeforces Round #596 (Div. 2)D. Power Products STL

传送门题意：求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...

2020-05-04

0 503

Codeforces Round #597 (Div. 2)D. Shichikuji and Power Grid 神奇的最小生成森林

传送门题意：n个城市，每一个城市有对应的Ci，Ki，和所在位置xi，yi； Ci代表点亮这座城市的代价，使两座城市连接起来的代价为（Ki+Kj）*曼哈顿距离；问使所有城市都亮起来的最小代价思路：非常容易想到，最终的结果一定是有几个城市被点亮，之后每个城市都会有他的附属城市（直接相连或间接相...

2020-05-04

0 614

codeforces E Enigma (DP)

传送门](http://codeforces.com/group/xrTA2IaQje/contest/258354) 题意：给一个大数（长度小于1000）和一个n 但是这个大数的有些位用？表示不确定，现在要把所有？填上后使他是n的倍数，并且最小。思路：简单DP dp[i][j]表示使第i位模数的...

2020-05-04

0 542

Codeforces Round #598 (Div. 3)

传送门 F：Equalizing Two Strings（我见过最水的F）题意：给你两个字符串S，T 你可以反转两个串的任意区间，任意次数，前提是两个串的翻转次数相同，每次反转区间的长度相同。问你能不能是这两个串相等思路：首先两个串的不同字母的数量必须相等，然后因为可以反转任意次，那么其实只要...

2020-05-04

0 479

树上两点间距离倍增法求LCA

#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[1...

2020-05-04

0 538

查询前缀串出现次数字典树

#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[20000...

2020-05-04

0 524