yngcy

刷题

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

/ 注册

全部文章 / 刷题（共39篇）

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

codeforces1670F Jee, You See?（DP/位运算/前缀和/组合数）

题目链接：codeforces 1670F 题目思路：首先，对于 sum，有 s u m = a 1 + a 2 + ⋯ + a n sum = a_1 + a_2 + \cdots + a_n sum=a1+a2+⋯+an 根据前缀的思想，所以得到 ans = sum[r] - su...

2024-03-16

0 0

codeforeces1748C Zero-Sum Prefixes（贪心）

题目链接：codeforeces 1748C 题目思路：首先，不难想到修改的次数要最少；其次，对于一次修改，影响的是前缀和的后缀。因此，根据贪心思想，可以找原数组非零段，用它前面的0修改成这段前缀和的值出现次数最多的那个数的相反数即可。参考代码： #include <bits/st...

2024-03-16

0 0