2019 杭电多校 第六场

2019 Multi-University Training Contest 6

补题链接：2019 Multi-University Training Contest 6

1002 Nonsense Time (HDU 6635)

题意

给定包含 (n) 个不同数字的排列 (p)。一开始所有数字都冻住。再给出一个长度为 (n) 的数组 (k)，(k[i]) 表示 (p[k[i]]) 在第 (i) 时刻解冻。输出 (n) 个数，表示第 (i) 个时刻数组 (p) 中解冻的数字的最长上升子序列的长度。

题解

思维 LIS

倒过来考虑 (时光倒流)。一开始所有数都是解冻的，一个一个开始冰冻。每冰冻一个数字，判断是否在当前最长上升子序列内，如果不在就输出当前最长上升子序列的长度，否则重新计算最长上升子序列。

由于给定的排列是随机的，随机排列的期望 (LIS) 的长度是 (O(sqrt{n}))，一个数在最长上升子序列内的概率为 (1 / sqrt{n})，那么期望删除 (O(sqrt{n})) 个数才会修改 (LIS)。期望时间复杂度为 (O(nsqrt{n}logn))。

1008 TDL (HDU 6641)

(solved by zmz)

题意

定义 (f(n, m)) 为第 (m) 小的整数 (x) 满足 (x>n) 并且 (gcd(x,n)=1)。给定 (m) 和 (k)，求满足 ((f(n,m)-n)⊕n=k) 的最小正整数 (n)。((⊕) 代表按位异或)

题解

质数的密度分布

(f(n,m)-n) 不会超过第 (m) 个与 (n) 互质的质数，(m) 是比较小的

#pragma GCC optimize(2)

#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <iomanip>
#include <set>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    ll k, m;
    int T;
    scanf("%d", &T);
    while (T--) {
//        cout << 1 << endl;
        cin >> k >> m;
        ll left = k - 1000;
        if (left < 0)left = 1;
        ll right = k + 1000;
        int flag = 0;
        for (ll i = left; i <= right; i++) {
            ll cnt = 0, tmp = i + 1;
            while (cnt < m) {
                if (gcd(tmp, i) == 1) {
                    cnt++;
//                    cout << i << " " << tmp << endl;
                }
                tmp++;
            }
//            cout << i << endl;
//            cout << "tmp:" << tmp << endl;
            if ((k ^ i) == tmp - i - 1) {
                flag = 1;
                cout << i << endl;
                break;
            }
        }
        if (!flag)cout << -1 << endl;
    }
    return 0;
}

1012 Stay Real (HDU 6645)

题意

给定一个小根堆，两个人每次从叶子节点取出一个数累加到自身的分数，堆为空时游戏结束，两个人选择最优策略。求两个人最终的分数。

题解

贪心 排序

两个人每次取最大的值，因此直接排序后间隔着累加就行，也可以使用优先队列。时间复杂度 (O(nlogn))。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
typedef long long ll;

ll a[maxn];

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%lld", &a[i]);
        }
        sort(a, a + n);
        ll s1 = 0, s2 = 0;        
        for(int i = n - 1; i >= 0; --i) {
            if((n - i) % 2) s1 += a[i];
            else s2 += a[i];
        }
        printf("%lld %lld
", s1, s2);
    }
    return 0;
}