WORIA

https://atcoder.jp/contests/abc173/tasks E - Multiplication 4   题意：给定n个数，要选k个数，乘积最大。 很典型的贪心了。 只有在非负数没有选择空间时最终结果才可能是负数。在这种情况下直接选绝对值最小的负数即可。 其它情况下结果都是非负数。先选择k个绝对值最大的数，如果其中有奇数个负数，则要换掉一个负数变为非负数，或者换掉一个非负数变为负数。这两种情况都要模拟，最终选更大的情况。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f ...

https://atcoder.jp/contests/abc172/tasks E - NEQ   题意：要求构造两个长度为n的数列A，B，满足每个数列内部都不相等，且两个数列间对位不相等，即 A[i]≠B[i]A[i]\neq B[i]A[i]=B[i]，且每个数大于0，小于等于m。问有多少种构造方式。 容斥 先构造出两个内部不相等的数列，构造方式就是1到m中选n个数全排列。 再把有对位重复的去掉，对于至少 i 位重复的情况，先从n位里选出 i 位，再给这 i 位分配数字，其它位还是全排列。 由于这过程中都满足内部不相等，所以直接容斥后结果就是答案。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ...

https://atcoder.jp/contests/abc171/tasks F - Strivore   题意：给定一个字符串s，问有几个长度为n+k的不同的字符串包含这个字符串作为子序列。 计数 关键是不能重复。所以要做出限制。 限制前 n+k−in+k-in+k−i 个字符中只出现一次串s，而后 iii 个字符任意。方法是先选n个位置作为s，再限定s串的第 jjj 位到第 j+1j+1j+1 位中间这部分不能出现 s[j+1]s[j+1]s[j+1]，则必定只出现一次s串。而后 iii 位任意。 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ll mod = 1e9 + 7;const int N ...

https://atcoder.jp/contests/abc168/tasks E - ∙ (Bullet)   题意：有n个物品，每个物品都有Ai,BiA_i,B_iAi​,Bi​两个值，选出一个非空子集，且满足子集中不存在两个物品的 Ai⋅Aj+Bi⋅Bj=0A_i \cdot A_j + B_i \cdot B_j = 0Ai​⋅Aj​+Bi​⋅Bj​=0，问有多少种选择方式。 思路比较简单，式子移项得到 AiBi=−BjAj\frac{A_i}{B_i}=-\frac{B_j}{A_j}Bi​Ai​​=−Aj​Bj​​，所以维护每个物品的 AiBi\frac{A_i}{B_i}Bi​Ai​​，最后计数即可。 但是写起来还是有技巧的。 首先要考虑分母为零，还要考虑精度。 所以可以考虑不除过去，而是直接维护 (Ai,Bi)(A_i,B_i)(Ai​,Bi​)，对应 (−Bi,Ai)(-B_i, A_i)(−Bi​,Ai​)，把这两类合并为一类，并用 (Ai,Bi),Ai>0,Bi≥0(A_i,B_i),A_i>0,B_i\ge 0(Ai​,Bi​),Ai​>0, ...

https://atcoder.jp/contests/abc163 E - Active Infants   题意：有n个孩子从1排到n，每个孩子有权值，要求重排一次，每个孩子的快乐度为他的权值乘他移动的距离，要求所有孩子的快乐度之和最大。 dp 首先要发现先分配权值大的孩子更优，因为第一个分配的和第二个分配的孩子移动距离的差最大只有1，那么如果先分配权值小的，他的移动距离最多只会增多1，显然是不如先分配大的。 而当分配一个孩子时，显然是要把它往两边分配。 所以策略就是按照权值从大到小按顺序分配，每次向两边分配。 然后就是类似区间dp的部分了。 dp[i][j]dp[i][j]dp[i][j] 表示左边分配了i个，右边分配了j个，最大快乐和。 i+j=已分配的孩子数；更新分配到左边或右边。 注意这里并没有固定分割线，所以最终取答案时要遍历分割线取最大值。 12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>using namespace ...

https://atcoder.jp/contests/abc162/tasks E - Sum of gcd of Tuples (Hard)   题意：m个数，每个数取值范围1到K，问所有可能数列的gcd之和。 莫比乌斯反演 枚举所有gcd，计算gcd为该值的可能数。 ∑i=1n∑j=1n∑k=1n[gcd=D]=∑i=1n/D∑j=1n/D∑k=1n/D[gcd=1]=∑i=1n/D∑j=1n/D∑k=1n/D∑d∣gcdμ(d)=∑d=1n/Dμ(d)⌊n/Dd⌋⌊n/Dd⌋⌊n/Dd⌋=∑d=1n/Dμ(d)⌊n/Dd⌋3\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n[gcd=D]\\ =\sum_{i=1}^{n/D}\sum_{j=1}^{n/D}\sum_{k=1}^{n/D}[gcd=1]\\ =\sum_{i=1}^{n/D}\sum_{j=1}^{n/D}\sum_{k=1}^{n/D}\sum_{d|gcd}\mu(d)\\ =\sum_{d=1}^{n/D}\mu(d)\lfloor{\frac{n/D}{d}}\rfloor\lfl ...

https://atcoder.jp/contests/abc161/tasks C - Replacing Integer   题意：给定x，k，每次操作把x变为 ∣x−k∣|x-k|∣x−k∣，问x最小值。 考虑x<k的情况，则此时只会在x,k-x这两个数里变化，找到小的那个即可，而如果x大于k，则一定可以变为x<k。 1234567891011#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;ll n, k;int main() { cin >> n >> k; cout << min(n%k, k - n % k) << endl; return 0;}   D - Lunlun Number   题意：要求的数相邻十进制位的差值必须小于等于1，问第x个这样的数是几。 x最大只有1e5，而这样的数的个数是随着位数以 ...

https://atcoder.jp/contests/abc160 F - Distributing Integers   题意：给定一棵树，选定一个点作为初始点，赋值 111，对于 222 到 nnn，可以赋值给任意与已赋值点相邻的点，问以每个点作为初始点时各有多少种赋值方式。 数论+树形dp+换根dp 先考虑固定根的情况下求赋值方式数。 以 uuu 为根的子树的赋值结果是u的子孙节点的排列，假设 uuu 共有 CCC 个子孙节点，则第一个子节点的子树的赋值结果可以选 ccc 个位置中的几个放入，其内部的顺序就是该子树的赋值结果，可以递归得到。而 uuu 的所有子节点都选好位置后，就构成了 uuu 的赋值结果。 所以这是一个可重排列的问题，从 CCC 个位置中选择 c1c_1c1​ 个位置放第一个子节点， c2c_2c2​ 个位置放第二个子节点，······，而对于各个子节点内部是怎样的顺序，我们并不关心，所以就是 C!c1!⋅c2!⋯ck!\frac{C!}{c_1!\cdot c_2!\cdots c_k!}c1​!⋅c2​!⋯ck​!C!​。再乘以各个子节点的递归值，就是u的 ...

https://atcoder.jp/contests/abc159 E - Dividing Chocolate   题意：一个黑白的网格，要求切成几块，每块白格个数不超过k，问最少切几刀。1≤H≤10,1≤W≤10001 \leq H \leq 10,1 \leq W \leq 10001≤H≤10,1≤W≤1000 H这么小，显然是状压枚举，然后贪心地纵向切最少刀。 然后就是模拟题了。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;int n, m, k;char mz[20][1010];int U[1010], D[1010], tot, cnt ...

https://atcoder.jp/contests/abc154/tasks E - Almost Everywhere Zero   1≤N<101001≤N<10^{100}1≤N<10100 1≤K≤31≤K≤31≤K≤3 题意：找到 111 到 NNN 中在十进制下有 kkk 个非零位的数的个数。 记忆化dfs 深搜状态 (第 iii 位，有 kkk 个非零位，是否0到9随便选)，状态不多。 分类比较细，要考虑当前位是否可以随便选，还是有上限。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<ll, ll> pii;const int maxn = 2e5 + 10;const int INF = 0x3f3f3f3f;const ...