WORIA

https://codeforces.com/contest/1366 D. Two Divisors   题意：给定一个数，要求找出它的两个因子 d1,d2，且他们的和与这个数互质。多次询问。 设 x=p1k1⋅p2k2⋯pmkmx=p_1^{k_1}\cdot p_2^{k_2}\cdots p_m^{k_m}x=p1k1​​⋅p2k2​​⋯pmkm​​，则构造出第一个因子为 p1p_1p1​，第二个因子为 p2k2⋯pmkmp_2^{k_2}\cdots p_m^{k_m}p2k2​​⋯pmkm​​。 假设 gcd(d1+d2,x)≠1gcd(d1+d2,x)\neq 1gcd(d1+d2,x)=1，则 gcd 一定是 x 的某个因子，则一定有一个 x 的质因子整除 gcd，设为 p，则一定有 (d1+d2)%p=0(d1+d2)\% p=0(d1+d2)%p=0 ，即 (p1+p2k2⋯pmkm)%p=0(p_1+p_2^{k_2}\cdots p_m^{k_m})\%p=0(p1​+p2k2​​⋯pmkm​​)%p=0，其中 p 是 p1,p2,⋯ ,pmp_1,p_2, ...

https://codeforces.com/contest/1359 C. Mixing Water   题意：给定热水和冷水的温度分别是h，c，按照一杯热水，一杯冷水，一杯热水，一杯冷水······的顺序倒入一个桶里，温度为平均值，问最少倒多少杯后温度与给定温度差值最小。 有两种情况：冷水数=热水数；热水数=冷水数+1。 先考虑第二种，冷水数为0时，温度就是热水，随着冷水数增加，温度逐渐趋近两者的平均值，把式子列出来就可以证明是单调递减的了，类似双曲线。 第一种情况，温度就是两者的平均值，也就是双曲线的渐进线。 所以温度随着杯数递减，趋近平均值，且杯数为1和杯数为2是两个极端，极端外的结果就是极端的值。 而对于范围内的，由于单调，所以可以直接求出给定温度所在位置的杯数，可能在坐标中间，有两个整点，比较一下大小即可。 还要注意精度，最好要把分数比较化成整数比较。 12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;#define ll long longconst in ...

https://codeforces.com/contest/1354 C2. Not So Simple Polygon Embedding 题意：一个正 2n 变形，求它的最小外接正方形边长，n为奇数。 正弦定理 asin⁡A=bsin⁡B=csin⁡C=2r=d\frac{a}{\sin A}=\frac{b}{\sin B}=\frac{c}{\sin C}=2r=d sinAa​=sinBb​=sinCc​=2r=d 做完C1就应该猜到C2里正方形一定是卡在某个点上的，所以直接画图。 以上面n=7时的正14边形为例。 先在小三角形里用正弦定理求得 x；再在a1，x所在的三角形里用正弦定理求得a1；最后在a2，x所在的三角形同理求得a2。结果就是a1+a2. 主要是要知道角P，即正方形卡在哪个点，画出n=5，7的图应该能发现n=5时共10个小角t，1/4个正方形占了10/4个t，而卡在的点又在1/4个正方形中间位置，所以猜P=n/4个t，然后发现要取整，那么再画出n=7，发现一个下取整一个上取整，所以就要找最近的整数，就是四舍五入了。 12345678910111213141 ...

https://codeforces.com/contest/1334 D. Minimum Euler Cycle   题意：一个n阶有向完全图，求出一个环经过每条边一次，且路径的字典序最小。要求输出路径的L到R段。 模拟 显然把小点先走完是最优解。 假设有5个点。则12131415232425343545. 那么难点就在输出了，先找到L在哪个大段，再确定小段，再加到R，加的时候注意跳段。 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const ll inf = 1e18;const int N = 3e5 + 10;int T;ll n, l, r;int main() { scanf("%d", &T); while (T--) { ...

https://codeforces.com/contest/1327 D. Infinite Path   题意：定义排列的乘法：c=a×b  ⟹  c[i]=b[a[i]]c = a \times b\implies c[i] = b[a[i]]c=a×b⟹c[i]=b[a[i]]。定义一种特殊路径：i,p[i],p[p[i]],p[p[p[i]]]…i, p[i], p[p[i]], p[p[p[i]]] \dotsi,p[i],p[p[i]],p[p[p[i]]]…，且路径上所有点颜色相同。给定排列 ppp，求最小的 kkk 使得 pkp^kpk 中存在一条这样的特殊路径。 容易想到转成有向图，每个点出度入度都为1，一定是几个不相交的环。然后根据离散数学的知识，或者画图看出来， pkp^kpk 就是把 ppp 中 uuu 指向 vvv 的边变成 uuu 指向 vvv 顺时针后 kkk 位的点。 那么就是要找到最小的 kkk ，使得在原图上的某个环里，存在一个公差为 kkk 的等差数列，且数列里的所有点颜色相同。 最关键的一点是， kkk 一定是最终答案所在环的长度的因数，因为如 ...

https://codeforces.com/contest/1312 D. Count the Arrays   题意：要求构造一个长为n的数列，每个数在1到m，且是单峰（左升右降），且有且仅有一个数出现了两次。问方案数。 转化为找一个长度为n-1的单调递增的数列，然后最大值作为峰值，再考虑左右分别放哪些数，再确定一个数让它重复两次。以上再用乘法原理乘起来。 123456789101112131415161718192021222324252627282930313233343536#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 2e5 + 10;const int INF = 0x3f3f3f3f;const ll mod = 998244353;ll ans;ll n, m;ll P[N];ll Pow(ll a, ll b) { ll res = 1; while (b) { if (b & 1)res = res * a%mod; ...

http://codeforces.com/contest/1303 D. Fill The Bag   题意：给出了一些物品，每个大小都为2的幂次，有一个已知大小的背包。每个物品可以分裂成两个大小都为原来一半的物品。问最少分裂几次能恰好装满背包？ 贪心 从大到小遍历所有物品，如果能放下就直接放，否则判断如果剩下的物品能放满背包，这个物品就不要了。否则就分裂，再把得到的两个物品和其他的一起再继续判断。 如果大物品并不是必须的，那么用小物品分裂放满背包是比分裂大物品更优的。 显然还需要的物品的2进制分布是确定的，现在就是需要把每一位需要的都凑出来，而同样是为了凑出某一位，用大的至少比小的多分裂1次。并且用幂次拼出更大的幂次也不存在需要先分裂再拼的情况，且既然总和足够，任何一位一定都是能拼出来的。所以用小的一定更优。 1234567891011121314151617181920212223#include<bits/stdc++.h>using namespace std;long long t, s, n, m, x, ans;int main() { cin & ...

http://codeforces.com/contest/1295 B. Infinite Prefixes   题意：给定一个01串s，构造出一个由s不断重复得到的无限长度的新串，问新串有几个前缀的0的个数减1的个数等于x。 如果s串的01差值等于0，则可以不断像前面插入s而不影响，所以此时如果s中有前缀01值等于x，就有无限多，否则永远不会有。 否则，可以发现s串的每个前缀最多作为答案出现1次，所以可以枚举前缀，判断前缀加k个s串是否能等于x。 1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<ll, ll> pii;const int maxn = 2e5 + 10;const int INF = 0x3f3f3f3f;int T, n, x;char s[maxn];int sum[maxn];map<int, int>cnt;in ...

http://codeforces.com/contest/1288 B. Yet Another Meme Problem   题意：找到给定范围 1≤a≤A,1≤b≤B1≤a≤A, 1≤b≤B1≤a≤A,1≤b≤B 中满足下图所示的数对个数。 a⋅b+a+b=a⋅10p+ba\cdot b+a+b=a\cdot 10^p +ba⋅b+a+b=a⋅10p+b，其中 ppp 为 bbb 的十进制下位数。 得到 b=10p−1b=10^p-1b=10p−1 ，即 bbb 为 9,99,999⋯9,99,999\cdots9,99,999⋯， aaa 任意。 12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int maxn = 1e5 + 10;int T;ll a, b;int main() { scanf("%d", &T) ...

http://codeforces.com/contest/1279 B. Verse For Santa   题意：规定从前往后处理n个物品，中间允许跳过1次，限制在s时间内，要处理最多的物品，问如果要跳过，跳过哪一个。 模拟题。 从前往后遍历，如果和大于s，则试着跳过，由于之前可能已经跳过一次了，所以要重新选最大的跳过，如果跳过后能小于等于s，则更新答案。 注意当和即使跳过也无法小于等于s时，不能直接break，类似s=100，a=[111，1]的答案就是如此。只有当以上情况且之前已经跳过了才可以break。当然也可以一直循环下去。 1234567891011121314151617181920212223242526272829#include<bits/stdc++.h>using namespace std;#define ll long longtypedef pair<int, int> pii;const int INF = 0x3f3f3f3f;const int maxn = 1e6 + 10;int T;int a[maxn];int ma ...