数轴上有n个点，第i个点的坐标为xi，权值为wi。两个点i，j之间存在一条边当且仅当$abs(x_{i}-x_{j})>=w_{i}+w{j}$，求这张图的最大团的点数（团就是两两之间有边的顶点集合）
1<=n<=2e5,0<=|xi|,wi<=1e9
根据qjx学姐上次考试讲的那道题的启发，可以知道两个有边就是他们的区间不相交（可以有一点相交），那么我们选出一些互不相交的区间，就代表这些区间形成团，
那么问题就变成了，给出n个区间要求选最多的区间且他们互不相交。这个就贪心就好了，按右端点排序，遍历一遍就好了。
不过结果只有90pts，因为w可以为0，那么就可能有这样两个区间(1,2),(2,2)，本来两个都可以取到，但如果(2,2)在前面那么就只能取一个。这是因为这道题并不是严格不相交
#include<bits/stdc++.h> using namespace std; const int maxn=200005; int n; struct point{ int l,r; }a[maxn]; template<class T>inline void read(T &x){ x=0;int f=0;char ch=getchar(); while(!isdigit(ch)) {f|=(ch==‘-‘);ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x= f ? -x : x ; } bool cmp(point a,point b){ if(a.r!=b.r) return a.r<b.r; return a.l<b.l; } int main(){ freopen("clique.in","r",stdin); freopen("clique.out","w",stdout); read(n); for(int i=1;i<=n;i++){ int x,w; read(x);read(w); a[i]=(point){x-w,x+w}; } sort(a+1,a+n+1,cmp); int ans=1,now=a[1].r; for(int i=2;i<=n;i++) if(now<=a[i].l){ ans++; now=a[i].r; } printf("%d",ans); }
给出一个序列，有三种操作：将[l,r]的数对x取模，求[l,r]的区间和，将a[x]改成y
1<=n,m<=1e5,0<=a[i],x,y<=1e9
要求区间和就用线段树维护即可。取模直接暴力，对于需要取模的地方单点修改，需要修改的地方就是值大于x的地方。操作3就单链修改。
考虑为什么暴力对：一个数取一次模至少减小一半，如果mod<x/2，那么取模之后x<mod<x/2；如果mod>x/2，那么x=x-mod<x/2。
所以一个数最多被修改log次，而且我可以通过区间最大值判断去掉不必要的取模。
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=200005; int n,m,cnt,a[maxn]; int root,ls[maxn<<1],rs[maxn<<1],mx[maxn<<1]; ll sum[maxn<<1]; template<class T>inline void read(T &x){ x=0;int f=0;char ch=getchar(); while(!isdigit(ch)) {f|=(ch==‘-‘);ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x= f ? -x : x ; } void update(int rt){ sum[rt]=sum[ls[rt]]+sum[rs[rt]]; mx[rt]=max(mx[ls[rt]],mx[rs[rt]]); } void build(int &rt,int l,int r){ rt=++cnt; if(l==r){ sum[rt]=mx[rt]=a[l]; return ; } int mid=(l+r)>>1; build(ls[rt],l,mid); build(rs[rt],mid+1,r); update(rt); } ll query(int rt,int l,int r,int a_l,int a_r){ if(a_l<=l&&r<=a_r) return sum[rt]; int mid=(l+r)>>1; ll ret=0; if(a_l<=mid) ret+=query(ls[rt],l,mid,a_l,a_r); if(mid<a_r) ret+=query(rs[rt],mid+1,r,a_l,a_r); return ret; } void modifymod(int rt,int l,int r,int a_l,int a_r,int mod){ if(mx[rt]<mod) return ; if(l==r){ mx[rt]=sum[rt]=mx[rt]%mod; return ; } int mid=(l+r)>>1; if(a_l<=mid) modifymod(ls[rt],l,mid,a_l,a_r,mod); if(mid<a_r) modifymod(rs[rt],mid+1,r,a_l,a_r,mod); update(rt); } void modify(int rt,int l,int r,int pos,int val){ if(l==r){ mx[rt]=sum[rt]=val; return ; } int mid=(l+r)>>1; if(pos<=mid) modify(ls[rt],l,mid,pos,val); else modify(rs[rt],mid+1,r,pos,val); update(rt); } int main(){ freopen("mod.in","r",stdin); freopen("mod.out","w",stdout); read(n);read(m); for(int i=1;i<=n;i++) read(a[i]); build(root,1,n); while(m--){ int opt; read(opt); if(opt==1){ int l,r; read(l);read(r); printf("%lld\n",query(1,1,n,l,r)); } else if(opt==2){ int l,r,mod; read(l);read(r);read(mod); modifymod(1,1,n,l,r,mod); } else{ int pos,val; read(pos);read(val); modify(1,1,n,pos,val); } } }
给定 整数 m,k,求出正整数n使得 n+1,n+2,...,2n中恰好有中恰好有m个数在二进制下恰好有k个1。有多组数据。有多组数据。
每组数据输出一行两个整数 ，第一个整数表示longlong范围内任意一个满足条件的满足条件的n，第二个数表示满足条件的n的个数 无穷多用-1表示）。保证 10^18以内存在满足条件的n。
对于100%的数据，t<= 2000 ，0<=m <=10^18 ,1<=k<=64。
首先可以打表看出随着n的增大，有k的1的数是不减的。
设f(n,k)为0-n之间二进制下有k个1的数的个数，那么n+1,...2*n中有k个1的数个数就是f(2*n,k)-f(n,k)。
将1-n的数都*2，这时这些数的1的个数不会改变，那么f(2*n,k)-f(n,k)= 0-2*n之间满足条件的奇数，因为偶数都被d(n,k)抵消了。（对于每一个满足条件的偶数/2都在0-n那么他们就在f(n,k)中）
对于单调性的证明:从刚才的结论继续，这些奇数-1后再/2那么就有k-1个1，而且都在0-n-1,因为奇数最多在2*n-1，那么f(2*n,k)-f(n,k)=f(n-1,k)，这个显然不递减。
有单调性又因为恰有k个所以满足条件的一定在一段连续区间，就分别二分求出两个边界。
考虑check，f(n,k)是从0-n判断，考虑像数位DP那样dfs，不过我们可以用组合数优化，我们保持一直处于压位状态，那么如果当前位能填1就dfs(pos-1,k-1)+c[pos][k]，c[pos][k]就是从后面pos位选k个填1.注意这里pos记为当前位后面有多少位。
还有二分边界要注意。
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=63; int t,k; ll m; ll c[66][66]; void init(){ c[0][0]=1; for(int i=1;i<=maxn;i++){ c[i][0]=c[i][i]=1; for(int j=1;j<i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1]; } } ll dfs(ll x,int pos,int kk){//pos:这位后面还有多少位 在任何时刻保持压位 if(!kk) return 1; if(pos<0) return 0; int p=(x>>pos)&1; if(p) return dfs(x,pos-1,kk-1)+c[pos][kk];//c:当这位填0从后面pos位中选kk位为1 else return dfs(x,pos-1,kk); } ll get(ll x){ return dfs(2*x,maxn,k)-dfs(x,maxn,k); } void cx(){ ll l=1,r=2e18,ans1,ans2; while(l<=r){ ll mid=(l+r)>>1; if(get(mid)>=m) r=mid-1,ans1=mid; else l=mid+1; } l=1,r=2e18; while(l<=r){ ll mid=(l+r)>>1; if(get(mid)<=m) l=mid+1,ans2=mid; else r=mid-1; } printf("%lld %lld\n",ans1,ans2-ans1+1); } int main(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout); init(); scanf("%d",&t); while(t--){ scanf("%lld%d",&m,&k); if(m==0){printf("1 %lld\n",((ll)1<<(k-1))-1);continue;} if(k==1) {printf("4 -1\n");continue;} cx(); } }
原文：https://www.cnblogs.com/sto324/p/11432033.html
