从这种开始训练量要降下来了，因为要期末考试了
这周就周一到周四训练吧
目标每天一道cf D题或者E题
搞起
12.28 周一
E. Water Level
一个下午就做了这道题，还是看题解的
挑的对我来说有点难了，我理解题解到ac花了蛮长时间的
这是一道比较复杂比较绕的思维题
我卡在怎么跳是最优的
首先要分类讨论
分x > y和 x<= y的情况
x > y的话整体是一直往左的，所以挺好判断
注意一开始不一定能加水，处理一下
这里有一点，官方的ac代码是不能往右跳就先往左跳一步
问题是会不会往左跳了一次之后还是不能往右跳。不应该写if应该写个while我觉得
而题目是没有这组数据的，if能过
但如果写while，是可以构造k很大，x很小而超时的
x<=y的话
其实我当时自己想的时候一直卡住就是要因为不知道每一步要怎么判断
也就是怎么样加水是最优的，最避免超出范围的
比如当前要不要选择加水
后来我发现，其实这种加水存在等价性
很多情况下这一步加水和下一步加水情况是一样的
等到要小于l再加水和中间过程加水更优，因为保证了当前水尽可能小而尽量不会加过头
然后这里还有个判断循环的问题
显然出现相同的k就循环了
而k改变只有两种方式，一种是减x，一种是先加y后减x
处理的时候我们是一次性减去很多个x，没有到中间过程
因此可以用k%x或者最靠近l的k来一次性代表这一类情况
而每一次y变化都会改变k%x和最靠近l的k
所以每一次都要只加一次y
具体实现的时候可以用最靠近l的k来判断循环，效果一样的。
最后发现其实这个加水思路在样例有体现
所以认真琢磨样例，样例是怎么操作的可以给我们启发
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
ll k, l, r, t, x, y;
unordered_map<ll, bool> vis;int main()
{scanf("%lld%lld%lld%lld%lld%lld", &k, &l, &r, &t, &x, &y);if(y < x){while(k + y > r) k -= x, t--;//直接从时间t减少去操作 if(k < l || t <= 0 || (k - l) / (x - y) < t) return puts("No"), 0;//输出Yes和No可以这么写 else return puts("Yes"), 0;}else{while(1){ ll n = (k - l) / x;k -= n * x;t -= n;if(t <= 0) return puts("Yes"), 0;if(vis[k]) return puts("Yes"), 0;vis[k] = true;if(k + y <= r) {k += y - x;if(--t <= 0) return puts("Yes"), 0; } else return puts("No"), 0; } } return 0;
}
这样，我接下来做cf1800左右的题，来它个50道
rating比较靠谱
12.29 周二
今天刚一道题，没做出来，明天补题
12.30 周三
复习欧拉筛模板
复习欧拉筛，O（n）
学算法要理解原理，理解才深刻，打模板才容易
欧拉筛的核心是每个数只被它的最小质因子筛去
i是作为倍数，prime[j]是作为最小质因子
为了保证一定是最小质因子，要加上如果i % p[j] == 0就break
详情可以看这个博客欧拉筛
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e2 + 10;
bool vis[MAXN];
vector<int> p;void get_prime()
{vis[0] = vis[1] = true;REP(i, 2, MAXN){if(!vis[i]) p.push_back(i);REP(j, 0, p.size()){if(i * p[j] >= MAXN) break;vis[i * p[j]] = true;if(i % p[j] == 0) break; } }
} int main()
{get_prime();REP(i, 0, p.size()) printf("%d ", p[i]);return 0;
}A. Enlarge GCD（欧拉筛拓展）
这道题还是很有收获的
独立做不出来，看题解发现要用欧拉筛
首先新的gcd一定是原来gcd的倍数
设新的gcd为y，原来gcd为x
则gcd（y,x） = x
所以y是x的倍数
那么一开始就可以先除去gcd
然后就找一个不为1的最多的数的公因数
那么怎么找就是这个题的难点
首先可以只考虑这个公因数是质数
因为公因数是合数的话可以用它的因子来代替，也就可以由其质因子来代替
那么先预处理质数
这个时候把每一个数质因数分解，试除法会超时
那么这里就需要优化
欧拉筛的核心是每一个数只被其最小质因子去除
因此我们可以在欧拉筛的过程中记录每个数的最小质因子，质因数分解时直接除去其最小质因子
不过空间开销挺大
一个int4个字节（B） 算一下发现空间不会超
8位一字节，一位（比特）是 0/1
char 一个字节 int4个，float4个，double8个 long long 8个 bool一个
#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1.5e7 + 10;
bool vis[MAXN];
vector<int> p;
int k[MAXN], a[MAXN], n;
unordered_map<int, int> cnt;void get_prime()
{vis[1] = vis[0] = true;REP(i, 2, MAXN){if(!vis[i]) p.push_back(i), k[i] = i;REP(j, 0, p.size()){if(i * p[j] >= MAXN) break;vis[i * p[j]] = true;k[i * p[j]] = p[j];if(i % p[j] == 0) break; } }
} int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }int main()
{get_prime();int g;scanf("%d", &n);_for(i, 1, n){scanf("%d", &a[i]); if(i == 1) g = a[i];else g = gcd(g, a[i]);} int ans = 0;_for(i, 1, n){a[i] /= g;while(a[i] > 1){int t = k[a[i]];ans = max(ans, ++cnt[t]);while(t == k[a[i]]) a[i] /= t;}}printf("%d\n", n - ans == n ? -1 : n - ans);return 0;
}