yngcy

分类

刷题(39) 编程工具(1) 题解(4)

/ 注册

全部文章（共49篇）

codeforces1621B Integers Shop(贪心）

题目链接：codeforces 1621B 题目大意：有 n 个线段 [ l i , r i ] [l_i,r_i] [li,ri]，需要 c i c_i ci 的花费。特别的，如果选了两个不重合的线段，中间的点也会被选中。第 s s s 天只有前 s s s 个线段，求第 s...

2024-03-16

0 0

codeforces1625C Road Optimization（线性DP）

题目链接：codeforces 1625C 题目思路：定义 dp[i][j] 为终点为 i i i，选中 j j j 个点所需要的最少时间。状态转移方程： d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ u ] [ j − ( i − ...

2024-03-16

0 0

codeforces1624F Interacdive Problem（交互/二分）

题目链接：https://codeforces.com/problemset/problem/1624/F 题目大意：已知 n n n，猜数字 x x x。对于每次询问： + c：返回 $\lfloor \frac{x+c}{n} \rfloor $。题目思路：二分，每...

2024-03-16

0 0

codeforces1627C Not Assigning（思维）

题目链接：codeforces 1627C 题目思路：给一颗树的边赋值，单条边的权值为质数，相邻两条边的权值和也为质数。不难发现必然有一条边的权值是 2 2 2，与这条边相邻的边的权值是其他任意质数。所以，显然，如果存在可行解的的话，这颗树已经退化成一条链，即不可能有一个节点的度为 3...

2024-03-16

0 0

codeforces1622D Shuffle（组合/容斥）

题目链接：codeforces 1622D 题目思路：暴力枚举区间 [l, r]，每次考虑把边界上的 1 1 1 放在中间的方案数。用预处理的方法求组合数。参考代码： #include <iostream> #include <vector> #include ...

2024-03-16

0 0

codeforces1622C Set or Decrease（贪心）

题目链接：codeforces 1622C 题目思路：贪心思想，显然，用最小的数去替换数组中的数。答案与顺序无关，不妨先从小到大排个序，假设替换了末 j j j 个数字，当前和为 s u m sum sum。比较好想的是，如果当前 s u m ≤ k sum \le k sum≤...

2024-03-16

0 0

codeforces1620E Replace the Numbers（并查集）

题目链接：codeforces 1620E 题目思路：倒序遍历每次的操作，对于操作 2 2 2，相当于把 x 加入到代表元是 y 的集合。参考代码： #include<iostream> using namespace std; const int N = 5e5 + 10...

2024-03-16

0 0

2022牛客寒假训练营1-A（01背包/同余）

题目思路：首先有个结论：一个数的数字根是它对 9 9 9 取模的余数，特别的，如果余数为 0 0 0，则树根为 9 9 9。于是问题就转化为，求这 n n n 个数不同余数的方案数，用01背包即可。需要注意的有两点：因为是余数，所以根据同余的性质，直接让 a[i] 对 ...

2024-03-16

0 0

codeforces1631E Paint the Middle（线性DP）

题目链接：codeforces 1631E 题目思路：如果数字之间不影响，那么直接考虑贪心，每次选最长的区间，然后中间的改为 1 1 1。但是有可能中间的数字有可能是其他区间的端点。考虑用动态规划来解决。首先某个数字最后出现的位置一定是区间的右端点，用一个数组 pos 记录某个数字最后出...

2024-03-16

0 0

codeforces1631D Range and Partition（二分/思维）

题目链接：codeforces 1631D 题目思路： y − x y-x y−x 越大，所选的区间长度越长，对应的分割后的个数越少，所以二分查找这个最小的差值。那么怎么保证划分后的每个区间的在 [ x , y ] [x,y] [x,y] 内的个数大于在 [ x , y ] [x,y]...

2024-03-16

0 0