2019 Multi-University Training Contest 6

2019.11.22

2019 Multi-University Training Contest 6

A B C D E F G H I J K L
× × × × × × ×

A – Salty Fish

B – Nonesense Time

T(1 \le T \le 3)组数据。给出长为n(1 \le n \le 50000)的序列p_1,p_2,\cdots,p_nk_1,k_2,\cdots k_n,开始时序列全部被划去,第i次恢复p_{k_i},维护LIS。(数据随机)

因为LIS不唯一,按题意每次插入一个数来维护LIS复杂度很高。但是正难则反,如果改成每次删除一个元素,就只用考虑这个元素在不在当前维护的LIS里面。又因为随机数据,期望LIS长度为O(\sqrt{n}),每次删除当前LIS里的元素后用O(n \log n)的算法重新找出LIS。时间复杂度O(n \sqrt{n} \log n)

//code by cwz
#include<bits/stdc++.h>
using namespace std;
int n,ans,tot;
int f[234234],from[234234],b[234234],a[234234],k[234234],ANS[234234];

struct SS {
    int num,wz;
} F[234234],S[234234];

bool cmp(SS t1,SS t2) {
    return t1.num<t2.num;
}

void Add(int x,int y) {
    int tt=x;
    while(x<=n) {
        if(y>F[x].num) F[x].num=y,F[x].wz=tt;
        x+=x&(-x);
    }
}

int getf(int x) {
    int asd=0,tt=x+1;
    while(x) {
        if(F[x].num>asd) asd=F[x].num,from[tt]=F[x].wz;
        x-=x&(-x);
    }
    return asd;
}

void gx(int up) {
    memset(f,0,sizeof(f));
    memset(b,0,sizeof(b));
    memset(from,0,sizeof(from));
    memset(F,0,sizeof(F));
    int i,t=0,tt=0;
    tot=0;
    for(i=1; i<=up; i++) S[++tot].wz=k[i],S[tot].num=a[k[i]];
    sort(S+1,S+1+tot,cmp);
    for(i=1; i<=tot; i++) {
        f[S[i].wz]=getf(S[i].wz-1)+1;
        Add(S[i].wz,f[S[i].wz]);
        if(f[S[i].wz]>t) t=f[S[i].wz],tt=S[i].wz;
    }
    ans=t;
    while(tt) b[tt]=1,tt=from[tt];
}

int main() {
    int i,T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        for(i=1; i<=n; i++) scanf("%d",&a[i]);
        for(i=1; i<=n; i++) scanf("%d",&k[i]);
        gx(n);
        for(i=n; i>=1; i--) {
            ANS[i]=ans;
            if(b[k[i]]) gx(i-1);
        }
        for(i=1; i<n; i++) printf("%d ",ANS[i]);
        printf("%d\n",ANS[i]);
    }
}

C – Milk Candy

D – Speed Dog

E – Snowy Smile

T(1 \le T \le 100)组数据。给出平面上n(1 \le n \le 2000,\sum n \le 10000)个点,第i个点有坐标(x_i,y_i)和权值w_i(-10^9 \le x_i,y_i,w_i \le 10^9)。找出一个矩形使得矩形内点的权值和最大,求最大权值。

离散化点坐标,横纵坐标不超过n,枚举矩形上下边界之后缩成一条线,线段树维护最大连续区间。时间复杂度O(n^2 \log n)

//code by me
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 2019;
ll ans;
int T, n, x[MAX], y[MAX], w[MAX], maxx, maxy;
int a[MAX], b[MAX], c[MAX], cnta, cntb, cntc;

struct seg {
    ll mxl[MAX << 2], mxr[MAX << 2], mx[MAX << 2], sum[MAX << 2];
    void clear(int x, int l, int r) {
        mxl[x] = mxr[x] = mx[x] = sum[x] = 0;
        if (l < r) {
            int mid = (l + r) >> 1;
            clear(x << 1, l, mid);
            clear(x << 1 | 1, mid + 1, r);
        }
    }
    void update(int x, int l, int r, int p, ll v) {
        if (l == r) {
            sum[x] += v;
            mx[x] = mxl[x] = mxr[x] = sum[x];
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(x << 1, l, mid , p, v);
        else update(x << 1 | 1, mid + 1, r, p, v);
        mxl[x] = max(mxl[x << 1], sum[x << 1] + mxl[x << 1 | 1]);
        mxr[x] = max(mxr[x << 1 | 1], sum[x << 1 | 1] + mxr[x << 1]);
        mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
        mx[x] = max(mx[x], mxr[x << 1] + mxl[x << 1 | 1]);
        sum[x] = sum[x << 1] + sum[x << 1 | 1];
    }
} sgt;


vector<int> v[MAX];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= 2000; i++)
            v[i].clear();
        ans = 0;
        cnta = cntb = cntc = 0;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d", &x[i], &y[i], &w[i]);
            a[++cnta] = x[i], b[++cntb] = y[i];
        }
        sort(a + 1, a + cnta + 1);
        sort(b + 1, b + cntb + 1);
        cnta = unique(a + 1, a + cnta + 1) - a - 1;
        cntb = unique(b + 1, b + cntb + 1) - b - 1;
        maxx = cnta, maxy = cntb;
        for (int i = 1; i <= n; i++) {
            x[i] = lower_bound(a + 1, a + cnta + 1, x[i]) - a;
            y[i] = lower_bound(b + 1, b + cntb + 1, y[i]) - b;
            v[x[i]].push_back(i);
        }
        for (int i = 1; i <= maxx; i++) {
            sgt.clear(1, 1, maxy);
            for (int j = i; j <= maxx; j++) {
                for (int k = 0; k < v[j].size(); k++) {
                    sgt.update(1, 1, maxy, y[v[j][k]], w[v[j][k]]);
                }
                ans = max(ans, sgt.mx[1]);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

F – Faraway

T(1 \le T \le 10)组数据。给出目标点的坐标(x_e,y_e),有n(1 \le n \le 10)个点,坐标满足(|x_i-x_e|+|y_i-y_e|) \bmod k_i = t_i(0 \le x_i,y_i \le m,1 \le m \le 10^9,2 \le k_i \le 5,0 \le t_i < k_i)给出n,m,x_i,y_i,k_i,t_i,求(x_e,y_e)有多少钟可能。

先把绝对值去掉,10个点最多把平面划分成121块,就能得到方程(x_e+y_e) \bmod k_i = t_i’(x_e-y_e) \bmod k_i = t_i’
2、3、4、5的最小公倍数是60,把横纵坐标都按模60的余数分类,得到3600种,每一种都代回方程验证。时间复杂度O(3600n^2)

//code by gzh
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int x[15],y[15],k[15],t[15],xx[15],yy[15];
int main() {
    int kase;
    cin>>kase;
    while(kase--) {
        cin>>n>>m;
        for(int i=1; i<=n; i++) {
            cin>>x[i]>>y[i]>>k[i]>>t[i];
            xx[i]=x[i];
            yy[i]=y[i];
        }
        sort(xx+1,xx+1+n);
        sort(yy+1,yy+1+n);
        xx[0]=yy[0]=0;
        xx[n+1]=yy[n+1]=m+1;
        long long dsy=0;
        for(int x1=0; x1<=n; x1++) {
            for(int y1=0; y1<=n; y1++) {
                int xl=xx[x1],xr=xx[x1+1]-1,yl=yy[y1],yr=yy[y1+1]-1;
                int cnt=0;
                for(int m1=0; m1<60; m1++) {
                    for(int m2=0; m2<60; m2++) {
                        int fg=1;
                        cnt++;
                        for(int i=1; i<=n; i++) {
                            int _x=x[i],_y=y[i],_k=k[i],_t=t[i] ,xe=m1 ,ye=m2;
                            if(xl>=x[i]) xe*=-1, _x*=-1;
                            if(yl>=y[i]) ye*=-1, _y*=-1;
                            int tp=_x%_k-xe%_k+_y%_k-ye%_k;
                            while(tp<0) tp+=_k;
                            if(tp%_k!=_t) {
                                fg=0;
                                break;
                            }
                        }
                        if(!fg) continue;
                        int kr=(xr-m1)/60, kl=(xl-m1)/60;
                        if(xr-m1<0) continue;
                        if((xl-m1)%60!=0 &&(xl>m1)) kl++;
                        int k1=kr-kl+1;
                        kr=(yr-m2)/60, kl=(yl-m2)/60;
                        if(yr-m2<0) continue;
                        if((yl-m2)%60!=0 &&(yl>m2)) kl++;
                        int k2=kr-kl+1;

                        ll tmp=(ll)k1*k2;

                        if(tmp==0) continue;
                        dsy+=tmp;
                    }
                }

            }
        }
        cout<<dsy<<endl;

    }
    return 0;
}

G – Support or Not

H – TDL

T(1 \le T \le 10)组数据。定义f(n,m)是大于n的第m个与n互质的数,给出k,m(1 \le k \le 10^{18},1 \le m \le 100),求最小的n满足(f(n,m)-n)\oplus n=k\oplus代表异或。

f(n,m)=n + k\oplus n

只要没有相同的质因子,两个数一定互质,所以比n大的第100个和他互质的数与n很接近,枚举k\oplus n的值,然后暴力验证这个n是否符合条件,取满足条件的最小n即可。

//code by me
#include <bits/stdc++.h>
using namespace std;
int T, m;
long long k, n, t, ans;
bool check(long long n) {
    t = (n ^ k) + n;
    if (__gcd(t, n) != 1) return 0;
    int cnt = 0;
    for (long long i = n + 1; i < t; i++) {
        if (__gcd(i, n) == 1) cnt++;
        if (cnt >= m) return 0;
    }
    if (cnt == m - 1) return 1;
    else return 0;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%d", &k, &m);
        ans = -1;
        for (long long i = m; i <= 1000; i++) {
            n = i ^ k;
            if (check(n)) {
                ans = (ans == -1 ? n : min(ans, n));
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

I – Three Investigators

J – Ridiculous Netizens

K – 11 Dimensions

//没有代码

L – Stay Real

小根堆中甲乙轮流取叶节点,双方按最优策略取使得权值和最大,求最终双方所取权值。

小根堆中子节点一定比父节点大,所以每次贪心在可选中取最大的。时间复杂度O(n\log n)

//code by cwz
#include<bits/stdc++.h>
using namespace std;
multiset<pair<int,int> > S;
long long ans[2];
int a[234234],lc[234234];
int T,n;

int main() {
    int i,j,t=0,tt;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n),ans[0]=ans[1]=0;
        for(i=1; i<=n; i++) {
            scanf("%d",&a[i]);
            if(i*2>n) S.insert(make_pair(a[i],i));
            lc[i/2]++;
        }
        while(!S.empty()) {
            multiset<pair<int,int> >::const_iterator cite = S.end();
            cite--;
            ans[t]+=cite->first;
            tt=(cite->second)/2;
            lc[tt]--;
            if(!lc[tt] && tt)  S.insert(make_pair(a[tt],tt));
            t^=1;
            S.erase(cite);
        }
        cout<<ans[0]<<' '<<ans[1]<<endl;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注