欧拉函数裸题。能看见就必须满足前面没有在同一斜率上的点，即，而且，所以只需要算一半*2即可。对于每一个i，的数的个数其实就是它的欧拉函数值..但是注意n不要算以及还有3个点最后要加就行了 #include <bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f #define il inline namespace io { #define in(a) a=read() #define out(a) write(a) #define outn(a) out(a),putchar('\n') #define I_int ...

因为前个素数乘积大于,也大于。所以反素数分解质因数后一定是在前个素数，而且指数不超过.一定在前个素数。证明：如果有一个反素数质因数不在这个素数，那么一定有一个这个素数内的没有被用到，那么我们可以把这个反素数改一下(设为n),变成，那么这样约数个数相同，但是变完后这个数更小，不符合反素数的定义，所以这个数一定不是反素数，所以反素数分解质因数后一定是在前10个素数里面。而且必须是指数不升的，这个根据前面那个交换指数也可以证明。所以只需要搜索前10个素数的指数，然后判定即可，有前面三个判定条件以及它不能超过n，实际搜索量非常小。 #include <bits/stdc++.h> #def...

题解 题意即为 根据的求解方式可以得到 于是我们可以枚举的约数，这样可以得到50分 增加一个小小的优化，就可以得到100分了。容易知道的是，当时，所以枚举在范围内的约数，得到另一个约数即可于是只需要特判一下的情况即可 #include <bits/stdc++.h> int T, a0, a1, b0, b1; int gcd(int a, int b) { if(b == 0) return a; return gcd(b, a % b); } int lcm(int a, int b) { return a / gcd(a , b) * b; } int main() { sc...

挺水的一题...了解阶乘的定义就可以做了。因为阶乘是连着乘下去的，所以对于一个，它的出现次数就是，对于，的出现次数是，不过有一半的数在处被算过了那个不能乘上去。将枚举到即可。效率是的注意开long long #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int p[N], vis[N], cnt, n; int main() { scanf("%d", &n); for(int i = 2; i <= n; ++i) { if(!vis[i]) p[++cnt] = i; f...

引理：对于一个合数，一定有一个不超过的质因数。注意到所以只需要预处理出素数，对所有的素数标记它在之间的倍数，之后扫一遍只要没有被标记的就一定是素数。直接存入数组判断相邻的素数即可。复杂度是 #include <iostream> #include <cstring> #include <cstdio> using namespace std; #define N 2000100 #define ll long long #define inf 2147483647 int l, r, p[N], m, f[N]; bool vis[N]; int main(...

不难发现三个LCA一定有两个重合，且一定是深度小的，但是深度大的那个点会更优（有两个点到它那里最优），那么找出深度大的那个lca就好了，它一定是公共点...，距离预处理深度即可。 #include <bits/stdc++.h> #define ll long long #define il inline const ll inf = 1e18; namespace io { #define in(a) a = read() #define out(a) write(a) #define outn(a) out(a), putchar('\n') #define I_int ll ...

本blog有所有部分分的解法 Description 小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。天天爱跑步是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。 这个游戏的地图可以看作一一棵包含 N个结点和N-1 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从1到N的连续正整数。 现在有个玩家,第个玩家的起点为Si ,终点为Ti 。每天打卡任务开始时,所有玩家在第0秒同时从自己的起点出发, 以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去, 跑到终点后该玩家就算完成了打卡任务。 (由于地图是一棵树, 所以每个人的路径是...

有向无环图是个很好的性质。因为期望dp都是逆推，所以可以建反图，然后在反图上拓扑排序来递推。设表示点到终点的期望路径长度，有,为点的度数。答案为 #include <bits/stdc++.h> using namespace std; const int N = 100010; double f[N]; int n, m, du[N], in[N]; int cnt, head[N], q[N]; struct edge {int to, nxt, v;} e[N]; void ins(int u, int v, int w) { e[++cnt] = (edge) {v, he...

选取的概率为，选取的概率为分别考虑三种运算并按位考虑，考虑第位：对于的情况显然贡献为，为第位为的数的个数。（三种运算的情况都一样）对于和，记录前面连续的个数，那么当前位置作为右端点，对期望的贡献为对于和，记录前面第一个有的位置，那么当前位置作为右端点，对期望的贡献为对于和，记录前缀和，并维护和两个桶。当当前为时，对期望的贡献为；当当前为时，对期望的贡献为。这题有点卡精度...要用long double并将除法运算挪到适当的位置... #include <bits/stdc++.h> using namespace std; #define double long double co...

搜索+大模拟。不过思路明确后还是可以写的。搜索树每一层代表移动了几次。每次枚举移动哪个位置，以及可以写个两个函数，一个来处理每一列的下降（移动或消除），第二个将每次可消的方块标记出来，然后再次下降（注意一次移动可能会导致多次消除，所以得重复判断），以及每次要记得把原数组copy了以便回溯。复杂度上界应该是35^7。但是跑不满（中间跑出解了）。 #include <bits/stdc++.h> using namespace std; bool vis[10][10]; int st[10][4], top = 0; int a[10][10]; int n; bool flag =...

能整合的操作大部分都整合了...所以这是个毒瘤题（码农题），不过维修序列貌似比这题更恐怖。这题要求资瓷区间加，区间反转，区间旋转（其实就是从中间断开然后左右交换位置），单点插入，单点删除，区间查询最小值。这些都能用fhqtreap解决。区间加（和线段树），区间反转（^=1，交换左右子树）都打标记就行了，分裂合并的时候下传标记。其实就是码码码，没有别的...然后注意一个坑就是poj的g++不资瓷time函数，我因为这个查了1h一直以为哪里写挂了，然后换成某八位质数就过了...(换成c++提交也没事...) #include <cstdio> #include <algorith...

和蒲公英差不多的套路，预处理整块的答案，查询的时候分类讨论，如果一个数在整段中是偶数次，在中间的整块是奇数次那么，在整段是奇数次在中间的整块是偶数次就。效率是。必须O2+优秀的块的大小才可以卡过去。注意不要用memset，每次处理过后for一遍清空就好，memset是对整个数组清空. #include <bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f #define il inline namespace io { #define debug_ puts("debuging ... ") ; #define in...

很有意思的一道题。对于每秒的增长，因为是个定值，所以显然可以打标记处理，记录每只蚯蚓被切断的时间，那么这只增长量就是，可以利用一个堆来维护当前的最大长度，那么可以做到，这样子已经可以通过5分了（卡常卡的好一点就85）。这题最有意思的地方就是按题目规则切出来的蚯蚓都是有单调性的。对于当前切出来的两只蚯蚓，长的那一条一定比后面切出来的长的蚯蚓长，短的同理（因为增长量是一样的，而当前找的又是最长的那条来切），所以可以维护三个队列，一个放原来的蚯蚓，一个放切出来的长的蚯蚓，一个放切出来的短的蚯蚓，然后每次选一个最长的那个出来切。然后第二次输出的时候类似归并排序那样两个指针扫一扫，就能合并三个队列，于是...

考虑先离散化，那么点的个数只会有个最多。于是复杂度里面就可以有一个.考虑构造矩阵表示经过一条边的最短路，那么就会是输入进来的边。那么表示经过条边的最短路，则有;然后就可以处理出次方的所有矩阵，然后得到最终矩阵的答案了。这个算法叫做倍增floyd  #include <cstdio> #include <algorithm> #include <cstring> #define ll long long #define inf 0x3f3f3f3f #define il inline namespace io { #define in(a) a = read(...