给定一个排列,每次插入
,查询最长上升子序列长度.
由于数据随机,每次只要标记其中能构成最长上升的元素,然后暴力找.
#include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const long long mod=1e9+7; const int oo=0x7fffffff; const int sup=0x80000000; typedef long long ll; typedef unsigned long long ull; template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");} template <typename it> string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;} template <typename it>int o(it a){cout<<a<<endl;return 0;} ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;} ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;} int n; int p[N],k[N]; int dp[N],len; bool vis[N],f[N]; void cal(){ me(vis,0); len=0; vector<int>pos(n+2); for(int i=1;i<=n;i++){ if(f[p[i]])continue; if(len==0||dp[len]<p[i])dp[++len]=p[i],pos[i]=len; else{ int x=lower_bound(dp+1,dp+1+len,p[i])-dp; dp[x]=p[i]; pos[i]=x; } } int t=len; for(int i=n;i>=1;i--){ if(f[p[i]])continue; if(pos[i]==t)vis[p[i]]=1,t--; } } int main(){ int t;cin>>t; while(t--){ me(f,0); sc("%d",&n); for(int i=1;i<=n;i++)sc("%d",p+i); for(int i=1;i<=n;i++)sc("%d",k+i); cal(); vector<int>ans(n+2,0); for(int i=n;i>=1;i--){ ans[i]=len; f[p[k[i]]]=1; if(!vis[p[k[i]]])continue; cal(); } for(int i=1;i<=n;i++)printf("%d%c",ans[i]," \n"[i==n]); } }
在二维坐标系中给定个点,每个点有权值,找最大子矩阵和.
先离散化坐标,变成一个二维稀疏矩阵,因为有效点的数量最多是,所以可以在每一行建立一颗线段树,把所有的点
插入进去,每插入一行,查询最大字段和.复杂度
#include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const long long mod=1e9+7; const long long mod2=998244353; const int oo=0x7fffffff; const int sup=0x80000000; typedef long long ll; typedef unsigned long long ull; template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");} template <typename it> string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;} template <typename it>int o(it a){cout<<a<<endl;return 0;} ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;} ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;} int n,nx,my; int a[N],b[N]; bool f[2005][2005]; ll mp[2005][2005]; struct node{ int x,y,w; bool friend operator <(node a,node b){ return a.x<b.y; } }nd[N]; ll suf[N],pre[N],sum[N],MAX[N]; int pos[N]; void tree(int l=1,int r=my,int rt=1){ MAX[rt]=suf[rt]=pre[rt]=sum[rt]=0; if(l>=r){ pos[l]=rt; return; } int mid=l+r>>1; tree(l,mid,rt<<1); tree(mid+1,r,rt<<1|1); } void up(int pt,ll val){ int rt=pos[pt]; sum[rt]+=val;MAX[rt]+=val;suf[rt]+=val;pre[rt]+=val; while(rt>1){ rt>>=1; MAX[rt]=max((max(MAX[rt<<1],MAX[rt<<1|1])),suf[rt<<1]+pre[rt<<1|1]); suf[rt]=max(suf[rt<<1]+sum[rt<<1|1],suf[rt<<1|1]); pre[rt]=max(sum[rt<<1]+pre[rt<<1|1],pre[rt<<1]); sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } } int main(){ int t;cin>>t; while(t--){ me(mp,0); sc("%d",&n); for(int i=1;i<=n;i++){ sc("%d%d%d",&nd[i].x,&nd[i].y,&nd[i].w); a[i]=nd[i].x; b[i]=nd[i].y; } sort(b+1,b+1+n);sort(a+1,a+1+n); nx=unique(a+1,a+1+n)-a-1; my=unique(b+1,b+1+n)-b-1; for(int x=1;x<=n;x++){ int i=lower_bound(a+1,a+1+nx,nd[x].x)-a; int j=lower_bound(b+1,b+1+my,nd[x].y)-b; mp[i][j]+=nd[x].w; } vector<pair<ll,int> >nod[nx+5]; for(int i=1;i<=nx;i++) for(int j=1;j<=my;j++)if(mp[i][j]!=0)nod[i].push_back({mp[i][j],j}); ll ans=0; for(int i=1;i<=nx;i++){ tree(); for(int j=i;j<=nx;j++){ for(pair<ll,int>x:nod[j]){ up(x.second,x.first); } if(ans<MAX[1])ans=MAX[1]; } } printf("%lld\n",ans); } }
给出个方程组,
,求
解的数量.
首先去绝对值会分成 个区域,比如
时,假设
在某一个区域中,枚举其中的所有点进行判断。因为
,
的余数肯定会在
以内,所以分别计算每个区域合法的个数.
#include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const long long mod=1e9+7; const long long mod2=998244353; const int oo=0x7fffffff; const int sup=0x80000000; typedef long long ll; typedef unsigned long long ull; template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");} template <typename it> string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;} template <typename it>int o(it a){cout<<a<<endl;return 0;} ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;} ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;} int n,m; int X[N],Y[N]; struct node{ int x,y,k,t; }a[15]; inline bool ck(int x,int y){ for(int i=1;i<=n;i++)if((abs(x-a[i].x)+abs(y-a[i].y))%a[i].k!=a[i].t)return false; return true; } inline int cal(int l,int r){ if(r-1-l<0)return 0; return 1LL+(r-l-1)/60; } int main(){ int ti;cin>>ti; while(ti--){ sc("%d%d",&n,&m); X[0]=0,Y[0]=0;X[n+1]=m+1,Y[n+1]=m+1; for(int i=1;i<=n;i++){ sc("%d%d%d%d",&a[i].x,&a[i].y,&a[i].k,&a[i].t); X[i]=a[i].x;Y[i]=a[i].y; } sort(X+1,X+n+1);sort(Y+1,Y+n+1); ll ans=0; for(int i=0;i<n+1;i++){ if(X[i]<X[i+1]){ for(int j=0;j<n+1;j++){ if(Y[j]<Y[j+1]){ for(int x=0;x<60;x++){ for(int y=0;y<60;y++){ if(ck(X[i]+x,Y[j]+y)){ ans+=1LL*cal(X[i]+x,X[i+1])*cal(Y[j]+y,Y[j+1]); } } } } } } }printf("%lld\n",ans); } }
给定,找出最小的
满足
,
表示大于
的第
个与
互质的数.
根据质数分布密度可以判断很小,对于满足条件的
大概在1000以内所以枚举就行.
#include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const long long mod=1e9+7; const long long mod2=998244353; const int oo=0x7fffffff; const int sup=0x80000000; typedef long long ll; typedef unsigned long long ull; template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");} template <typename it> string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;} template <typename it>int o(it a){cout<<a<<endl;return 0;} ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;} ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;} int main(){ //freopen("in.txt","r",stdin); int t;cin>>t; while(t--){ ll k;int m; sc("%lld%d",&k,&m); bool BOOl=0;ll ans=1e18+9; for(ll f=1;f<=1000;f++){ ll n=f^k; if(n<1)continue; if(__gcd(n,n+f)!=1)continue; itn ti=0;ll y=0; for(ll x=n+1;;x++){ if(__gcd(n,x)==1)ti++; if(ti==m){y=x;break;} } if(y-n==f){ ans=min(ans,n); BOOl=1; } } if(!BOOl)o(-1); else o(ans); } }
给定一个小根堆,个人轮流玩游戏每一次只能从叶子取最大数,求
人的最大和.
最底层的一定是最大的数,依次取最大就行.
#include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const long long mod=1e9+7; const long long mod2=998244353; const int oo=0x7fffffff; const int sup=0x80000000; typedef long long ll; typedef unsigned long long ull; template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");} template <typename it> string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;} template <typename it>int o(it a){cout<<a<<endl;return 0;} ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;} ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;} ll h[N]; int main(){ //freopen("in.txt","r",stdin); int t;cin>>t; while(t--){ int n;sc("%d",&n); for(int i=1;i<=n;i++)sc("%lld",&h[i]); ll S=0,E=0; sort(h+1,h+1+n); int x=0; for(int i=n;i>=1;i--){ if(x+1&1)S+=h[i]; else E+=h[i]; x^=1; } printf("%lld %lld\n",S,E); } }