2019 HDU多校第六场

Nonsense Time

Time Limit: 14000/14000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

You a given a permutation p1,p2,…,pn of size n. Initially, all elements in p are frozen. There will be n stages that these elements will become available one by one. On stage i, the element pki will become available.

For each i, find the longest increasing subsequence among available elements after the first i stages. 
InputThe first line of the input contains an integer T(1≤T≤3), denoting the number of test cases.

In each test case, there is one integer n(1≤n≤50000) in the first line, denoting the size of permutation.

In the second line, there are n distinct integers p1,p2,…,pn(1≤pi≤n), denoting the permutation.

In the third line, there are n distinct integers k1,k2,…,kn(1≤ki≤n), describing each stage.

It is guaranteed that p1,p2,…,pn and k1,k2,…,kn are generated randomly. 
OutputFor each test case, print a single line containing n integers, where the i-th integer denotes the length of the longest increasing subsequence among available elements after the first i stages. 

Sample Input

1
5
2 5 3 1 4
1 4 5 3 2

Sample Output

1 1 2 3 3

考虑时间倒流,看作一个完整的排列按照一定顺序依次删除每个数,然后每次需要计算LIS 的长度。首先在 O(n log n) 的时间内求出 LIS,并找到一个 LIS。当删除 x 时,如果 x 不在之前找到的那个 LIS 中,那么显然 LIS 的长度是不会变化的,否则暴力重新计算出新的 LIS 即可。因为数据随机,因此 LIS 的期望长度是 O(√n),删除的 x 位于 LIS 中的概率是 √
111
n,也就是说期望删除 O(√n) 个数才会修改 LIS,那么 LIS 变化的次数不会很多。

#include<cstdio>
const int N=50010;
int Case,n,i,x,a[N],b[N],ans[N],pre[N],nxt[N],f[N],g[N],used[N],bit[N];
inline void up(int&a,int b){if(f[a]<f[b])a=b;}
inline void build(){
  int i,j,k;
  for(i=nxt[0];i<=n+1;i=nxt[i]){
    used[i]=0;
    k=0;
    for(j=a[i];j;j-=j&-j)up(k,bit[j]);
    f[i]=f[k]+1;
    g[i]=k;
    for(j=a[i];j<=n+2;j+=j&-j)up(bit[j],i);
  }
  for(i=nxt[0];i<=n+1;i=nxt[i])for(j=a[i];j<=n+2;j+=j&-j)bit[j]=0;
  for(i=n+1;i;i=g[i])used[i]=1;
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]),a[i]++;
    a[0]=1;
    a[n+1]=n+2;
    for(i=0;i<=n+1;i++)pre[i]=i-1,nxt[i]=i+1,bit[i]=used[i]=0;
    bit[n+2]=0;
    for(i=1;i<=n;i++)scanf("%d",&b[i]);
    build();
    for(i=n;i;i--){
      ans[i]=f[n+1]-1;
      x=b[i];
      pre[nxt[x]]=pre[x];
      nxt[pre[x]]=nxt[x];
      if(used[x])build();
    }
    for(i=1;i<=n;i++)printf("%d%c",ans[i],i<n?' ':'\n');
  }
}


Snowy Smile

Time Limit: 4000/4000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

There are n pirate chests buried in Byteland, labeled by 1,2,…,n. The i-th chest’s location is (xi,yi), and its value is wi, wi can be negative since the pirate can add some poisonous gases into the chest. When you open the i-th pirate chest, you will get wi value.

You want to make money from these pirate chests. You can select a rectangle, the sides of which are all paralleled to the axes, and then all the chests inside it or on its border will be opened. Note that you must open all the chests within that range regardless of their values are positive or negative. But you can choose a rectangle with nothing in it to get a zero sum.

Please write a program to find the best rectangle with maximum total value. 
InputThe first line of the input contains an integer T(1≤T≤100), denoting the number of test cases.

In each test case, there is one integer n(1≤n≤2000) in the first line, denoting the number of pirate chests.

For the next n lines, each line contains three integers xi,yi,wi(−109≤xi,yi,wi≤109), denoting each pirate chest.

It is guaranteed that ∑n≤10000. 
OutputFor each test case, print a single line containing an integer, denoting the maximum total value. 

Sample Input

2
4
1 1 50
2 1 50
1 2 50
2 2 -500
2
-1 1 5
-1 1 1

Sample Output

100
6

首先将纵坐标离散化到 O(n) 的范围内,方便后续的处理。将所有点按照横坐标排序,枚举矩形的上边界,然后往后依次加入每个点,这样就确定了矩形的上下边界。设 v[y] 表示矩形内部纵坐标为 y 的点的权值和,则答案为 v 的最大子段和,用线段树维护带修改的最大子段和即可。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
#define ls rt<<1
#define rs rt<<1|1
#define delf int mid=(l+r)>>1
typedef long long ll;
const int maxn=(int)2e3+10;
int num;
inline ll read(){
    ll sum=0,f=1;char ch=getchar();
    while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
    return f*sum;
}
ll tree[maxn<<2],ssum[maxn<<2],lsum[maxn<<2],rsum[maxn<<2];
void pushup(int rt){
    tree[rt]=tree[ls]+tree[rs];
    ssum[rt]=max(max(ssum[ls],ssum[rs]),rsum[ls]+lsum[rs]);
    lsum[rt]=max(lsum[ls],tree[ls]+lsum[rs]);
    rsum[rt]=max(rsum[rs],tree[rs]+rsum[ls]);
}
void build(int rt,int l,int r){
    if(l==r){
        ssum[rt]=lsum[rt]=rsum[rt]=tree[rt]=0;
        return;
    }
    delf;
    build(ls,l,mid); build(rs,mid+1,r);
    pushup(rt);
}
void update(int rt,int l,int r,int pos,ll val){
    if(l==pos&&r==pos){
        tree[rt]+=val; ssum[rt]=max(0ll,tree[rt]);
        lsum[rt]=max(0ll,tree[rt]); rsum[rt]=max(0ll,tree[rt]);
        return;
    }
    delf;
    if(pos<=mid) update(ls,l,mid,pos,val);
    else update(rs,mid+1,r,pos,val);
    pushup(rt);
}
struct P{
    int x,y;ll w;
    bool operator<(const P &b)const{
        return y<b.y;
    }
}p[maxn];
ll x,y,w,ans;
int b[maxn],c[maxn],n,m;
void solve(){
    scanf("%d",&num);
    n=0,m=0;ans=0;
    rep(i,1,num){
        p[i].x=read();p[i].y=read();p[i].w=read();
        b[i]=p[i].x; c[i]=p[i].y;
    }
    sort(b+1,b+1+num);
    sort(c+1,c+1+num);
    int sz1=unique(b+1,b+1+num)-b-1;
    int sz2=unique(c+1,c+1+num)-c-1;
    rep(i,1,num){
        p[i].x=lower_bound(b+1,b+1+sz1,p[i].x)-b;
        p[i].y=lower_bound(c+1,c+1+sz2,p[i].y)-c;
        n=max(n,p[i].x);m=max(m,p[i].y);
    }
    sort(p+1,p+1+num);
    rep(i,1,m){ //枚举下界 
        int pos=1,now=p[1].y;
        while(p[pos].y<i) pos++;
        now=i;
        build(1,1,n);
        while(1){
            while(p[pos].y==now){
                update(1,1,n,p[pos].x,p[pos].w);
                pos++;
            }
            ans=max(ans,ssum[1]);
            if(pos>num) break;
            now=p[pos].y;
        }
    }
    printf("%lld\n",ans);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}


Faraway

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

n soldiers are dispatched to somewhere in Byteland. These soldiers are going to set off now, but the target location is not so clear.

Assume the target location is at (xe,ye), it is clear that xe,ye are both non-negative integers within [0,m]. For the i-th soldier, the only thing he knows is that (|xi−xe|+|yi−ye|)modki=ti.

To find the correct target location, these soldiers are working on the information they have now. Please write a program to figure out the number of possible target locations. 
InputThe first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.

In each test case, there are two integers n,m(1≤n≤10,1≤m≤109) in the first line, denoting the number of soldiers and the upper bound of xe,ye.

For the next n lines, each line contains four integers xi,yi,ki,ti(0≤xi,yi≤m,2≤ki≤5,0≤ti<ki), denoting what each soldier knows. 
OutputFor each test case, print a single line containing an integer, denoting the number of possible target locations. 

Sample Input

2
2 5
1 2 4 2
3 1 2 1
2 5
1 2 4 2
1 2 4 3

Sample Output

10
0

将 |xi − xe| + |yi − ye| 的绝对值拆掉,则每个点 (xi, yi) 会将平面分割成 4 个部分,每个部分里距离的表达式没有绝对值符号,一共 O(n2) 个这样的区域。枚举每个区域,计算该区域中可能的终点数量。注意到 lcm(2, 3, 4, 5) = 60,所以只需要枚举 xe 和 ye 模 60 的余数,O(n) 判断是否可行,然后 O(1) 计算该区域中有多少这样的点即可。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=15,K=60;
int Case,n,m,x,y,i,j,ca,cb,a[N],b[N];long long ans;
struct E{int x,y,k,t;}e[N];
inline int abs(int x){return x>0?x:-x;}
inline bool check(int x,int y){
  for(int i=0;i<n;i++)if((abs(x-e[i].x)+abs(y-e[i].y))%e[i].k!=e[i].t)return 0;
  return 1;
}
inline int cal(int l,int r){
  r-=l+1;
  if(r<0)return 0;
  return r/K+1;
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    a[ca=1]=b[cb=1]=m+1;
    for(i=0;i<n;i++){
      scanf("%d%d%d%d",&e[i].x,&e[i].y,&e[i].k,&e[i].t);
      a[++ca]=e[i].x;
      b[++cb]=e[i].y;
    }
    sort(a+1,a+ca+1);
    sort(b+1,b+cb+1);
    ans=0;
    for(i=0;i<ca;i++)if(a[i]<a[i+1])for(j=0;j<cb;j++)if(b[j]<b[j+1])
      for(x=0;x<K;x++)for(y=0;y<K;y++)if(check(a[i]+x,b[j]+y))
        ans+=1LL*cal(a[i]+x,a[i+1])*cal(b[j]+y,b[j+1]);
    printf("%lld\n",ans);
  }
}


TDL

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

For a positive integer n, let’s denote function f(n,m) as the m-th smallest integer x that x>n and gcd(x,n)=1. For example, f(5,1)=6 and f(5,5)=11.

You are given the value of m and (f(n,m)−n)⊕n, where “⊕” denotes the bitwise XOR operation. Please write a program to find the smallest positive integer n that (f(n,m)−n)⊕n=k, or determine it is impossible. 
InputThe first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.

In each test case, there are two integers k,m(1≤k≤1018,1≤m≤100). 
OutputFor each test case, print a single line containing an integer, denoting the smallest n. If there is no solution, output “-𝟷” instead. 

Sample Input

2
3 5
6 100

Sample Output

5
-1

考虑枚举 f(n, m) − n 的值 t,则 n = t ⊕ k,O(tlog n) 检查这个 n 是否满足条件即可。注意到 t 显然不会超过第 m 个与 n 互质的质数,而 n 最多只有 O(log log n) < m = 100 个质数,根据质数密度可以得到 t 的一个比较松的上界 O(m log m)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll k,m;
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&k,&m);
        vector<ll> v;
        for(ll i=1;i<=3000;i++){
            ll n=i^k;
            int cnt=0;
            ll pt=0;
            if(n==0) continue;
            for(ll j=n+1;cnt<m;j++){
                if(gcd(j,n)==1){
                    cnt++;
                    pt=j;
                }
            }
            if(((pt-n)^n)==k){
                v.push_back(n);
            }
        }
        if((int)v.size()==0){
            printf("-1\n");
        }
        else{
            ll mi=v[0];
            for(int i=1;i<(int)v.size();i++){
                mi=min(mi,v[i]);
            }
            printf("%lld\n",mi);
        }
    }
    return 0;
}


Stay Real

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)

Problem Description

In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a min heap, for any given node C, if P is a parent node of C, then the key(the value) of P is less than or equal to the key of C. The node at the “top” of the heap(with no parents) is called the root node.

Usually, we may store a heap of size n in an array h1,h2,…,hn, where hi denotes the key of the i-th node. The root node is the 1-th node, and the parent of the i(2≤i≤n)-th node is the ⌊i2⌋-th node.

Sunset and Elephant is playing a game on a min heap. The two players move in turns, and Sunset moves first. In each move, the current player selects a node which has no children, adds its key to this player’s score and removes the node from the heap.

The game ends when the heap is empty. Both players want to maximize their scores and will play optimally. Please write a program to figure out the final result of the game. 
InputThe first line of the input contains an integer T(1≤T≤10000), denoting the number of test cases.

In each test case, there is one integer n(1≤n≤100000) in the first line, denoting the number of nodes.

In the second line, there are n integers h1,h2,…,hn(1≤hi≤109,h⌊i2⌋≤hi), denoting the key of each node.

It is guaranteed that ∑n≤106. 
OutputFor each test case, print a single line containing two integers S and E, denoting the final score of Sunset and Elephant. 

Sample Input

1
3
1 2 3

Sample Output

4 2

签到题

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+10;
int n,a[maxn];
void solve(){
    scanf("%d",&n);
    rep(i,1,n) scanf("%d",&a[i]);
    sort(a+1,a+1+n,greater<int>());
    ll ans1,ans2;
    int op=1;
    ans1=ans2=0;
    rep(i,1,n){
        if(op) ans1+=a[i];
        else ans2+=a[i];
        op^=1;
    }
    printf("%lld %lld\n",ans1,ans2);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

发表评论,支持MarkDown语法