给定一个排列,每次插入
,查询最长上升子序列长度.
由于数据随机,每次只要标记其中能构成最长上升的元素,然后暴力找.
#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);
}
}
京公网安备 11010502036488号