近期所学
最长上升子序列nlogn的做法
思路：维护一个递增数组，长度相同的LIS只存终点的最小值
1
2
3
4
5
6
7
8
9
10
11
12
| int lengthOfLIS(vector<int>& nums){
int n=nums.size();
vector<int> vec;
for(int i=0;i<n;i++){
int p=lower_bound(vec.begin(),vec.end(),nums[i])-vec.begin();
if(p==vec.size())
vec.push_back(nums[i]);
else
vec[p]=nums[i];
}
return vec.size();
}
|
同类问题：给出一个由字符 ‘0’ 和 ‘1’ 组成的字符串 S，我们可以将任何 ‘0’ 翻转为 ‘1’ 或者将 ‘1’ 翻转为 ‘0’，返回使 S 单调递增的最小翻转次数
最近接触了很多可以转换成lis问题的dp题，感觉很神奇，就比如牛客的一道叫免费馅饼的题，可以通过旋转坐标轴，求新的x,y变量的lis（具体在cometoj)
容斥定理
规律奇加偶减
求[a,b]中与n互素的个数(co-prime)
思路：1~100中与30不互素的有是2，3，5倍数的-即是2又是3倍数的-即是2又是5倍数的-即是3又是5倍数的<3,5是两个数即为偶数>+即是2又是3又是5倍数的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| bool bprime[N];
LL prime[N],cnt, factor[N],num;
void isprime() {
cnt=0;
memset(bprime,false,sizeof(bprime));
for(LL i=2; i<N; i++) {
if(!bprime[i]) {
prime[cnt++]=i;
for(LL j=i*i; j<N; j+=i)
bprime[i]=true;
}
}
}
void getFactor(int n){
num=0;
for(LL i=0; prime[i]*prime[i]<=n&&i<cnt; i++) {
if(n%prime[i]==0) {
factor[num++]=prime[i];
while(n%prime[i]==0)
n/=prime[i];
}
}
if(n!=1)
factor[num++]=n;
}
LL calculate(LL m,LL num) {
LL res=0;
for(LL i=1; i<(1<<num); i++) {
LL sum=0;
LL temp=1;
for(LL j=0; j<num; j++) {
if(i&(1<<j)) {
sum++;
temp*=factor[j];
}
}
if(sum%2)
res+=m/temp;
else
res-=m/temp;
}
return res;
}
int main() {
isprime();
LL a,b,n;
scanf("%lld%lld%lld",&a,&b,&n);
getFactor(n)
LL res=(b-(a-1)-calculate(b,num))+calculate(a-1,num);
printf("%lld\n",res);
return 0;
}
|
求[1,n]中能/不能被m个数整除的个数
思路：sum=从 m 中选 1 个数得到的倍数的个数-从 m 中选 2 个数得到的倍数的个数 + 从 m 中选 3 个数得到的倍数的个数 - 从 m 中选 4 个数得到的倍数的个数……
能被整除的个数就是 sum，不能被整除的个数就是 n-sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| LL GCD(LL a,LL b){
return !b?a:GCD(b,a%b);
}
LL LCM(LL a,LL b){
return a/GCD(a,b)*b;
}
LL a[N];
int main(){
LL n;
int m;
scanf("%lld%d",&n,&m);
for(int i=0;i<m;i++)
scanf("%lld",&a[i]);
LL sum=0;
for(int i=0;i<(1<<m);i++){
LL lcm=1;
LL cnt=0;
for(int j=0;j<m;j++){
if(i&(1<<j)){
lcm=LCM(lcm,a[j]);
cnt++;
}
}
if(cnt!=0){
if(cnt&1)
sum+=n/lcm;
else
sum-=n/lcm;
}
}
printf(%lld "%lld\n",sum,n-sum);
return 0;
}
|
给出一串数，要求出删去最少个数字，使这串数的gcd增大
思路：只要gcd变大就行，至于删多少数字，先将所有数的公共gcd除去，然后分解质因数找最大数量(cnt)的因子,每轮对n-cnt取最小或者对cnt取最大
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include <stdio.h>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 15000000;
int vis[maxn],a[maxn],flag[maxn];
int gcd(int a,int b)
{
return b == 0 ? a : gcd(b,a % b);
}
int main()
{
memset(flag,0,sizeof(flag));
memset(vis,0,sizeof(vis));
int n;
int gc = 0;
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
vis[a[i]]++;
if(!gc)
gc = a[i];
else
gc = gcd(gc,a[i]);
}
int ans = 0;
for(int i = gc + 1;i <= maxn;i++)
{
if(!flag[i])
{
int cnt = 0;
for(int j = i; j <= maxn; j += i)
{
cnt += vis[j];
flag[j] = 1;
}
ans = max(ans,cnt);
}
}
if(ans > 0) printf("%d\n",n - ans);
else printf("-1\n");
return 0;
}
|
一些关于质数和整除的小规律
任何一个合数n必定包含一个不超过sqrt(n)的质因子
区间筛是在l~r区间内筛prime[sqrt(r)]以内]的倍数
N!中的每个质因子都不会超过N
gcd(a,b)=gcd(a,b-a)=gcd(a,b mod a)
c|a,c|b,则c|sa+tb
