吴国庆

acm

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

/ 注册

全部文章 / acm （共50篇）

2019牛客暑期多校训练营（第九场）E：All men are brothers

题目链接：https://ac.nowcoder.com/acm/contest/889/E 题意：给出m对朋友关系，朋友关系可以传递，每次给出一对朋友关系后，输出选择四个人两两都不是朋友的不同方案的数目思路：考虑每次新添入一对朋友对答案得影响，利用组合数学可以得出当前答案，一直更新即可代...

2020-05-04

0 413

2019杭电多校第7场 1006 Final Exam HDU 6651(思维)

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6651 题意：有n道题总分为m 完成一道x分的题所需得时间为x+1 问完成k题所需最少时间 n,m,k<1e9; 思路：分别从老师和学生两个方面想对于老师：如果想要学生挂k门科以上，至少有n-k+...

2020-05-04

0 576

（没懂）Codeforces Round #581 (Div. 2)Kirk and a Binary String (hard version)

链接：http://codeforces.com/contest/1204/problem/D2 题意：给一个0 1 串求在不改变每个区间的LIS的情况下使这个串的0 最多 n<1e5; 思路：要想使0最多那么首先原串中的0是不用改变的考虑把什么样的1变成零是不改变LIS的：：其实就...

2020-05-04

0 544

CodeForces - 830B Cards Sorting(思维)

链接：http://codeforces.com/problemset/problem/830/B 题意：给一个长度为n的数列（有重复数字），要重复进行下面的操作：如果第一个数是当前数列中最小的数那么就删除它，否则把它放到队尾，求这个数列能操作多少次思路：离散化后，把每个数字出现的位置i存...

2020-05-04

0 617

搜索

链接：[http://codeforces.com/problemset/problem/793/B] (http://codeforces.com/problemset/problem/369/C) http://codeforces.com/problemset/problem/369/C ...

2020-05-04

0 476

Cows and Sequence（思维，树状数组）

链接：http://codeforces.com/problemset/problem/284/C 思路：唯一需要注意的是操作1的区间修改，由于查询的时候只会查询最后一个元素并且区间总是从1开始所以只需用一个s【】数组维护就行树状数组：令c【i】为原数列，我们让s【i】为c【i】的差分数列即s...

2020-05-04

0 582

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 575