原题：Widespread 原题大意一条线上有N个怪兽，第i个怪兽有hi格血条，我们每次可以对其中一个怪发动攻击，使他损失A格血，同时，除他以外的怪兽要损失B格血（A>B），问最少攻击几次使得怪兽全部gg。 算法分析贪心的想，每次让血最多的怪受到直接攻击，直到所有怪都完蛋，下面考虑优化，每次攻击每个怪都会受到B的伤害，其中被直接攻击到的还要受到（A—B）的额外伤害，假设攻击次数为t，enough(t) = yes / no 为（t次攻击成功消灭怪兽）答案。t为单调函数，可以二分来做，t次攻击的额外伤害次数应该等于t，即为 ∑⌈(hi −B ×T)/(A−B)⌉ = t。 程序代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+5; int n; ll a, b; ll h[maxn]; ll check(ll m){ ll ans = 0; for(int i = 1; i <= n; i++){ i ...

原题：UCloud 的安全秘钥 原题大意对长度为n的数字组成的串，进行m次询问，询问的长度为k，求原串（长度为k）的字串与询问串近似匹配（可以理解成两个集合相同）的个数。 算法分析对于n<=50000，m <= 100000，以及询问串的总长度不超过200000的数据来说，通过hash给每个元素赋值，然后按长度将询问的字串分组，并且按hash的和排序，可由双指针完成计数。 https://www.jisuanke.com/article/9v3lgyb4 程序代码#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 200050; struct E{ int l; int p; int v; bool friend operator <(E ob1, E ob2){ return ob1.l == ob2.l ? ob1.v < ob2.v : ob1.l < ob2.l; ...

原题：3N Numbers 原题大意给3n个数，要求去掉n个数，使得剩下的2n个数里，前n个数减后n个数的值最大，求最大值。 算法分析将球分为三种颜色，被取走的标为黑色，剩下的前n个为红色，后n个为蓝色，所以观察后发现，红色一定只出现在前面，蓝色一定只出现在后面，红色的最后一个位置是n~2n，蓝色的第一个位置一定是n+1~2n+1。设k为分界线，红球从前k个里面取，蓝球从后3*n-k里面取，k的取值为(n<=k<=2n)，枚举k的取值，用优先队列维护最优值。 程序代码#include<stdio.h> #include<string.h> #include<algorithm> #include<stdlib.h> #include<iostream> #include<queue> using namespace std; priority_queue<int>QD;//大根堆 priority_queue<int,vector<int>,greater<int& ...

原题：OR 原题大意给出n个数A1, A2…,AN, 任意选择两个数i,j(1 <= i < j <= N),问Ai|Aj的期望值是多少。以既约分数的形式输出。 算法分析如果暴力需要n^2，会超时，所以考虑每一位，前i-1个数里，第j位是0的个数为cnt，如果第i个数的第j位是1，那么贡献为(1 << j) (i-1)，否则贡献为cnt (1 << j)。如果直接算出分子除以分母会爆long long int，所以记录余数然后两次gcd求出结果。 程序代码#include <bits/stdc++.h> #define mem(a,b) memset(a, b, sizeof(a)) using namespace std; typedef long long ll; int T; ll cnt[40]; ll x, y, n; ll gcd(ll a, ll b){ return b == 0 ? a : gcd(b, a % b); } int main(){ ios::sync_with_stdio(fa ...

原题：Factorial Modulo 原题大意给出两个数a, b,问有多少i使得i!能被a整除，而不能被b整除。 算法分析对于一个数字n， 如果x!是可以被它整除的第一个数，那么x之后的数都能整除。将x计作 f（n），答案就是max(0, f(b)-f(a))。对于f的计算，就是对于n分解质因数，然后对于每一个因数算出要满足这个因数所需要的x，取max即为f。 程序代码#include <bits/stdc++.h> #define mem(a,b) memset(a, b, sizeof(a)) using namespace std; typedef long long ll; int a, b; //得到能被x^cnt整除的最小阶乘n！，n一定是x的整数倍。 int get(int x, int cnt){ int t = 1; //如果能将cnt个x整除完 while(cnt){ int tmp = t*x; while(tmp % x == 0 && cnt){ t ...