Powered by:AB_IN 局外人 我数论这学的是真烂啊。。。又得借练习赛补老番…… 任意一个大于0的正整数都能被表示成若干个素数的乘积且表示方法是唯一的。这就是唯一分解定理。 用于求 因子和 和 因子个数 。 求因子和 模板 //以线性筛为基础 int jet_num[N];//用来记录素数的幂是多少的 ll get_yin_zi_sum(ll n) { ll ans = 1; for(int i = 1; (ll) prime[i] * prime[i] <= n; i++){ if(!(n % prime[i])){ ...

Powered by:NEFU AB_IN 欧拉函数 定义：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。 欧拉函数通式： 其中为的所有质因数，。特别的。 所以根据通式可以直接求出一个数的欧拉值 ll euler(ll n){ ll ans = n; for(int i = 2; i * i <= n; i ++){ if(!(n % i)){ ans = ans / i * (i - 1); while(!(n % i)) n /= i; } } ...

Powered by:NEFU AB_IN 引入： 曼哈顿距离在一维空间下，曼哈顿距离定义如下：在二维空间下，曼哈顿距离定义如下： 货仓选址 题意：在一条数轴上有 家商店，它们的坐标分别为 ，求一个到每家商店的距离之和最小的值。 首先，最直接的思路就是枚举的每个点，求一遍距离，复杂度为 其实可以知道最优的方案，那就是取中位数，每一个点到中位数的距离，都是满足全局的最优性，而不是局部最优性。 先给出结论：取所有坐标中位数，如果n是奇数，那么中位数唯一；如果n是偶数，可以选中间两个数之间的任何一个位置 比如： 明显建在处最优。 比如： 可以看出建在处都可以，因为距离一样，可以通过画图求证出...

芜湖！

Powered by:AB_IN 局外人 B. 牛牛和网格三角形 先引进一下卡特兰数的概念： 卡特兰数又称卡塔兰数，英文名Catalan number，是组合数学中一个常出现于各种计数问题中的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)的名字来命名，其前几项为（从第零项开始） : 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24...

D. 夹缝中求和 的数据只能是以下的复杂度，排序已经到，那么查找数就得是或者为。 就是最容易想到的二分法，用STL的 和即可，不等式即为#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ll long long const int N = 1e5 + 10; ll n, cnt; ll x, y; ll a[N]; int main() { IOS; cin >> n >&...

C. 石头剪刀布 纯模拟，我想的应该是有点麻烦了。 先让牛牛的拳头碰剪刀，以此类推，先把赢了的赢了，但要注意拳头和剪刀的局数都得有值，这样每局得分。 再让牛牛的拳头碰拳头，以此类推，拳头和拳头的局数都得有值，这样每局得分。#include<bits/stdc++.h> using namespace std; int a[4],b[4]; int n, t, ans; #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int main() { IOS; cin >> n; for...

B. 移动撤销 栈的操作，当进栈时 而且 栈不为空时，就将栈顶的元素弹出，之后就模拟栈里的元素即可。 #include<bits/stdc++.h> using namespace std; string s; int n; #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int main() { IOS; cin >> n; cin >> s; int x = 0, y = 0; stack < char > s1; ...

A. 完全数 没想太多，看到求因子和就想到了唯一分解定理，写个线性筛，套个求因子和的函数即可。不懂的可以看一眼我之前的文章。-> 戳 #include <bits/stdc++.h> #define ll long long const int N=1e6+5; int cnt, prime[N], pre[N]; bool flag[N]; using namespace std; void init() { memset(flag,1,sizeof(flag)); flag[1]=cnt=0; for(int i=2;i<=N;i++) ...

D 自由世界 思路很简单，先给每个点跑一遍最短路，记录到的路径长度。再去管传送门，从每个传送门这跑一遍最短路，记录传送门到的路径，和取个最小值即可。 我一开始为了图个方便，把传送门和每个点都建了个边权为的边，导致凭空多出来至少条边，就T了，呜呜呜。。。 #include<bits/stdc++.h> using namespace std; #define ll long long const int N=1e6+10; const int inf=0x3f3f3f3f; struct sa{ int dis; int pos; }; bool operator &...

C 小球下落 想要代码量少，思维量一定要大。这个题可以用爆搜，但我太菜了写不出来 ，比赛时写了个只得了30分。赛后看了眼大佬们的代码，才发现是真的巧妙。 首先核心思想是贪心。反向输入图形，把第行当作第行，现在的目标就是尽可能的去让球去填满上面的空。但是，有三种情况是会封死路的 xx .xx. x..x 所以要分区。所以现在问题就转化成了，让球去尽量往上填这一分区的空。 先给出代码 #include<bits/stdc++.h> using namespace std; const int N = 3e5+10; int n , r , f , Q[N << 1]; ...

B 平面旅行 题意就是要从走到再走到，一直走到的最短距离，中间有设个传送点，可以使在任何地方都能到达传送点。 所以到最短路径无非就是两种情况： 第一种：直接过去 第二种：传送至传送门，从传送门直接过去。#include <bits/stdc++.h> using namespace std; const int N=5e3+10; struct sa { int x; int y; }a[N]; vector <int> v; int n,m,x,y,c,mn,ans; int main() { scanf("%d%d",&n,&m); ...

A 七七七七 打表出来二分即可，发现打表到6的时候，就已经超10000了，我其实打多了。 #include<bits/stdc++.h> using namespace std; int a[20],n,ans = 1,b[20]; int main() { cin >> n; for(int i = 1 ;i <= 10; i++){ a[i] = ans; ans *= 7; b[i] = a[i] + b[i-1]; } int id = lower_bound(b+1, b+...

C T3 最少移动 随机选两个相邻的数，一个加1，一个减1，最后要所有数都一样，那么就都是平均数。所以一开始想判断是否每个数都能变成相同。如果可以，就从尾到头遍历，和平均值比较，大了就减，然后前一个加。 for _ in range(int(input())): n = int(input()) lst = list(map(int , input().split())) if sum(lst) % len(lst) != 0 : print(-1) else: ans=0 ave = sum(lst) // le...