BFS+DP先按照到达x节点的距离 ，将所有节点进行分类，求出每一类的节点的数量，用cnt数组存储；然后对cnt数组进行 dp , dp[ i ][ j ] 视作 当最大距离为 i 时，选取 j 个点，有多少种方案，则dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i-1 ][ j-1 ]*cnt[ i ] , 即考虑 选距离为i 的节点 和 不选距离为 i 的节点的方案和；另外 j = 0 时 dp[ i ][ j ] 恒为 1；  #include <bits/stdc++.h> using namespace std; #define dbg(x) c...

#include <bits/stdc++.h> using namespace std; #define int long long #define dbg(x) cout<<#x<<": "<<(x)<<endl; //n个糖果，m个同学，尝试每人分配cnt个，能否成功分配 int check(int n,int m,int cnt){ if(!m)return true; int rest=n-m*cnt; for(int i=62;i>=0;i--){ if(cnt&(1ll<<i...

void solve(){ int n;cin>>n; vector<int> a(n+1); for(int i=1;i<=n;i++)cin>>a[i]; int xor_sum=0; for(int i=1;i<=n;i++)xor_sum^=a[i]; int l_sum=0; int final_ans=xor_sum; for(int i=1;i<=n;i++){ l_sum^=a[i]; final_ans=max(final_ans,l_sum&(xor_sum^l_sum)); } cout<<fina...

#include<bits/stdc++.h> using namespace std; int main(){ int n;cin>>n; vector<int> a(n+1); for(int i=1;i<=n;i++)cin>>a[i]; sort(a.begin()+1,a.end()); deque<int> q; int ans=0; for(int i=1;i<=n;i++){ while(!q.empty()&&q.front()<a[i]-1)q.pop_front(); if(!q...

void solve(){ int n,k;cin>>n>>k; map<int,int> mp; for(int i=1;i<=n;i++){ int x;cin>>x; while(x<=k){ mp[x]++; x*=2; } } int sum=0,cnt=0; for(auto[x,xCnt]:mp){ if(sum>k)break; if(sum+x*xCnt<=k){ sum+=x*xCnt;cnt+=xCnt; }else{ int addCnt=(k-sum)/x; cnt+=addCnt; break;...

template<typename T> class ST{ public: vector<vector<T> > st; int sz; function<T(T,T)> op;//op can be max,min,gcd,lcm,&,|,etc. ST(vector<T>&x,function<T(T,T)> f) : op(std::move(f)){ sz=x.size(); int K=log2(sz); st.resize(sz,vector<T>(K+1)); for(int i...

bool check(int x,int k){ int cnt=(x/3+1)/2; int cnt5=(x/5+1)/2; cnt+=cnt5; if(cnt5>1)cnt-=((cnt5-1)+2)/3; return cnt<k; } void solve(){ int k;cin>>k; int l=1,r=1e18,mid; while(l<=r){ mid=(l+r)>>1; if(check(mid,k))l=mid+1; else r=mid-1; } cout<<l<<endl; } 二分+容斥原理二分最终答...

void solve(){ int q;cin>>q; int maxl=0; set<int> rec; auto find=[&](int l,int r){ auto eL=rec.lower_bound(l); if(eL==rec.end())return false; if(*eL<=r)return true; return false; }; for(int i=1;i<=q;i++){ int l,r;cin>>l>>r; if(!find(l,r)){ maxl=max(maxl,r-l+1); for(i...

string getMin(string s){ int n=s.size();s="!"+s; char minl='z'; for(int i=1;i<=n;i++)minl=min(minl,s[i]); if(s[1]==minl){ string tmp;tmp+=minl; return tmp; } string ans; for(int i=n;i>=1;i--){ if(s[i]==minl){ if(ans.empty())ans=s.substr(i,n-i+1); else ans=min(ans,s.substr(i,n-i+1)); ...

void solve(){ int a,b,x,y;cin>>a>>b>>x>>y; int ans=inf; for(int i=0;i<=20;i++){ for(int j=0;j<=20;j++){ int restA=a,restB=b,iNeed=0; restA-=j*y,restB-=j*y; if(restA>0)iNeed+=(restA+x-1)/x; if(restB>0)iNeed+=(restB+x-1)/x; if(iNeed<=i)ans=min(ans,i+j); } } cout&...

void solve(){ int n;cin>>n; vector<int> a(n+1); vector<int> v(n+1); for(int i=1;i<=n;i++)cin>>a[i]>>v[i]; stack<int> sk; vector<int> ans(n+1); for(int i=1;i<=n;i++){ while(!sk.empty()&&a[sk.top()]<=a[i])sk.pop(); if(!sk.empty())ans[sk.top()]...

#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define dbg(x) cout<<#x<<": "<<x<<endl; #define endl '\n' #define int long long const int N=1e7+1e5; vector<int> f; void init(){ f=vector<int>(...

#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define dbg(x) cout<<#x<<": "<<x<<endl; #define endl '\n' #define int long long const int inf=LLONG_MAX; void submit(int x){ cout<<"The shortest...

void solve(){ int n,k;cin>>n>>k; vector<int> a(n+1); for(int i=1;i<=n;i++)cin>>a[i]; sort(a.begin()+1,a.end()); int r=1; int ans=1; for(int i=1;i<=n;i++){ while(r<=n&&a[r]-a[i]<=k)r++; ans=max(ans,r-i); } cout<<ans<<endl; } 枚举每个数最为选择的最小数x，那么小于等...