整理组合数
https://www.acwing.com/blog/content/406/
倍增
P3406 海底高铁
/*
reference:
translation:
给定n个区间，所以对于每一段(i,i+1)经过了x次吧，我们可以用树状数组来维护每段区间经过的次数
对于每一段(i,i+1)，可以选择买c[i]的劵，每次只花b[i]元，也可以每次都花a[i]元。贪心一下就好啦
solution:
trigger:
区间修改，单点查询
note:
*为什么右端点不用+1……？……
record:
1 way ac
date:
2019.09.02
*/
#define N 100010
int n,m,ans;
int tr[N],p[N];
inline void add(int x,int k){
for(int i=x;i<=n;i+=(-i)&i)
tr[i]+=k;
}
inline int query(int x){
int res=0;
for(int i=x;i;i-=(-i)&i)
res+=tr[i];
return res;
}
#undef int
int main(){
#define int long long
#ifdef WIN32
freopen("motorway.txt","r",stdin);
#endif
rd(n),rd(m);
rep(i,1,m){
rd(p[i]);
}
rep(i,1,m-1){
if(p[i]<p[i+1])
add(p[i],1),add(p[i+1],-1);
else if(p[i]>p[i+1])
add(p[i+1],1),add(p[i],-1);
rep(i,1,n)
printf("%d ",tr[i]);
puts("");
}
rep(i,1,n)
printf("%lld
",query(i));
rep(i,1,n-1){
int a,b,c;rd(a),rd(b),rd(c);
int cnt=query(i);
ans+=min(cnt*b+c,cnt*a);
}
printf("%lld",ans);
return 0;
}
/*
9 10
3 1 4 1 5 9 2 6 5 3
200 100 50
300 299 100
500 200 500
345 234 123
100 50 100
600 100 1
450 400 80
2 1 10
*/
//6394
【unordered_map】870. 约数个数
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
对于本题：
1≤ai≤2e9
用x/ln(x)大致可判断有1e8左右的质数，开数组根本开不下，而且质数之间的间隔又会拉低效率，有没有什么容器不用遍历无效信息呢？
map；
而且是unordered_map(其实map也可以啦)
那么就很裸了
#define mod 1000000007
#define N 10000010
int n,tot,ans=1,maxx;
unordered_map<int,int> p;
inline void count(int x){
for(int i=2;i*i<=x;++i){
while(x%i==0){
p[i]++;
x/=i;
}
}
if(x>1)p[x]++;
}
#undef int
int main(){
#define int long long
//freopen("yueshu.txt","r",stdin);
rd(n);
while(n--){
int x;rd(x);
count(x);
}
int res=1;
for(unordered_map<int,int>::iterator it=p.begin();it!=p.end();it++){
res=res*(it->second+1)%mod;
}
printf("%lld",res%mod);
return 0;
}
约数之和
同样是unordered_map的应用
您的秦九昭突然出现
#define mod 1000000007
#define N 10000010
int n,tot,ans=1,maxx;
unordered_map<int,int> p;
inline void count(int x){
for(int i=2;i*i<=x;i++){
while(x%i==0){
x/=i;
p[i]++;
}
}
if(x>1) p[x]++;
}
#undef int
int main(){
#define int long long
int n;rd(n);
while(n--){
int x;rd(x);
count(x);
}
int res=1;
for(unordered_map<int,int>::iterator it=p.begin();it!=p.end();++it){
int p=it->first,a=it->second;
int t=1;
while(a--)
t=(t*p+1)%mod;//您的秦九昭突然出现
res=res*t%mod;
}
printf("%lld",res);
}
【双指针算法】799. 最长连续不重复子序列
/*
#define N 100010
int n,ans=INT_MIN;
int a[N];
unordered_map<int,int>mp;
int main(){
#ifdef WIN32
freopen("","r",stdin);
#endif
rd(n);
rep(i,1,n)rd(a[i]);
for(int i=1,j=1;i<=n;++i){
//i为快指针，j为慢指针，i扫描序列，j及时更新
mp[a[i]]++;
while(j<i && mp[a[i]]>1){
mp[a[j]]--;
j++;
}
//因为i移动一次后a[i]出现的次数大于1了，j前进直到i对应值出现次数变为1，j移动时候对应元素出现次数--
ans=max(ans,i-j+1);
}
printf("%d",ans);
return 0;
}
【双指针||map】800. 数组元素的目标和
使用双指针的前提：快指针变化的同时，慢指针根据一定条件变化而且j指针不会回退！；
例如本题，两个序列都单调递增，
if(a[i]+b[j]>x)的时候，j不可能++，只能--；
/*
int n,m,x;
#define N 100010
int a[N],b[N];
map<int,int>mpb;
#undef int
int main(){
#define int long long
rd(n),rd(m),rd(x);
rep(i,1,n){
rd(a[i]);
}
rep(i,1,m){
rd(b[i]);
mpb[b[i]]=i;
}
//sort(a+1,a+n+1);
//sort(b+1,b+m+1);
rep(i,1,n){
if(mpb[x-a[i]]){
printf("%lld %lld
",i-1,mpb[x-a[i]]-1);
break;
}
}
return 0;
}*/
#define N 100010
int n,m,x;
int a[N],b[N];
#undef int
int main(){
#define int long long
rd(n),rd(m),rd(x);
rep(i,1,n)rd(a[i]);
rep(i,1,m)rd(b[i]);
for(int i=1,j=m;i<=n;++i){
while(j>=1 && a[i]+b[j]>x)
j--;
if(j>=1 && a[i]+b[j]==x)
printf("%lld %lld
",i-1,j-1);
}
return 0;
}
/*
4 5 6
1 2 4 7
3 4 6 8 9
*/
//1 1
//数组下标从0开始
回文日期（80 pts）
#define N
int st,ed,s,t;
int ans;
bool check(int x){
int ge=x%10;
x/=10;
int shi=x%10;
x/=10;
int bai=x%10;
x/=10;
int qian=x%10;
x/=10;
swap(ge,qian);
swap(shi,bai);
int day=shi*10+ge;
int month=qian*10+bai;
bool feb=0;
if((x%400==0 || (x%4 && x%400))&& month==2)feb=1;
if(month>12 || !month)return 0;
if(!day || day>31)return 0;
if(feb && day>29)return 0;
if(!feb && day>28)return 0;
if((month==4 || month==6 || month==9 || month==11) && day>30)return 0;
if((month==1 || month==3 ||month==5 ||month==7 ||month==8 ||month==10 ||month==12) && day>31)return 0;
return 1;
}
int reverss(int x){
int ge=x%10;
x/=10;
int shi=x%10;
x/=10;
int bai=x%10;
x/=10;
int qian=x%10;
x/=10;
swap(ge,qian);
swap(shi,bai);
return qian*1000+bai*100+shi*10+ge;
}
int main(){
#ifdef WIN32
freopen("nianfen.txt","r",stdin);
#endif
rd(st),rd(ed);
s=st/10000,t=ed/10000;
//printf("%d %d
",s,t);
rep(i,s,t){
int now=reverss(i);
if(i==s && now<st%10000)continue;
if(i==t && now>ed%10000)continue;
if(check(i)){
ans++;
//printf("%d ",i);
//printf("%0*d
",4,now);
}
}
printf("%d",ans);
return 0;
}