HDU-6635 Nonsense Time



给定一个排列,每次插入,查询最长上升子序列长度.



由于数据随机,每次只要标记其中能构成最长上升的元素,然后暴力找.


#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]);
    }
}

HDU-6638 Snowy Smile



在二维坐标系中给定个点,每个点有权值,找最大子矩阵和.



先离散化坐标,变成一个二维稀疏矩阵,因为有效点的数量最多是,所以可以在每一行建立一颗线段树,把所有的点
插入进去,每插入一行,查询最大字段和.复杂度图片说明


#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);
    }
}

HDU-6639 Faraway



给出个方程组, ,求解的数量.



图片说明
首先去绝对值会分成 个区域,比如时,假设在某一个区域中,枚举其中的所有点进行判断。因为 ,的余数肯定会在以内,所以分别计算每个区域合法的个数.


#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);
    }
}

HDU-6641 TDL



给定,找出最小的满足,表示大于的第个与互质的数.



根据质数分布密度可以判断很小,对于满足条件的大概在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);
    }
}

HDU-6645 Stay Real



给定一个小根堆,个人轮流玩游戏每一次只能从叶子取最大数,求人的最大和.



最底层的一定是最大的数,依次取最大就行.


#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);
    }
}