2019-10-26测试总结
Eqvpkbz's Site

2019-10-26测试总结

$tournament$

作为一个熟练的算法竞赛选手,$Dove$非常喜爱打比赛。近期 $Dove$ 被邀请参加「算法带师」比赛。这个比赛的目的选拔出水平最高的算法竞赛选手,比赛以这样的流程进行:比赛总共有$2^n$个人参加,对于第 $i$ 个人,他的能力评分为$a_i \in [1, 2^n ]$,且保证任意两个人的能力评分不同。在两个人的比拼中,能力评分较高的那个人获胜。比赛一共将进行 $n$ 场,对于第 $i$ 场比赛,相邻两个人进行比拼,获胜者将进入下一轮比赛,每场比赛中保证所有人的相对位置保持一致。对于每个人来说,我们定义他参加比赛的愉悦度为他参与并获胜的比赛数目,$Dove$想知道,对于能力评分为 $i$ 的人来说,如果允许他和任意一个人交换位置,那么他能获得的愉悦度的最大值是多少

考场上没想出来

中间上厕所的时候稍稍想了一下,任何一个数字换了位置的愉悦度的最大值都大于等于比它小的数字的不换位置的愉悦度

然后自认为复杂度是错的,于是就指望着枚举 + 线段树能过然后理所当然的挂了

考完出来发现人均$A$$T1???$

nmdwsm

正确思想: 就是我上厕所想的和我考场上真正打了的部分的结合体

需要线段树然后$DFS$,考虑维护一个最大值和次大值,并不需要排序(然而std排了序),再结合之前的思想就$A$

我调了两个小时的线段树发现在updatequery的时候把查询的区间端点改了

标程:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<algorithm>
using namespace std;
#define file(SSS) freopen(SSS".in","r",stdin),freopen(SSS".out","w",stdout)
#define file_close fclose(stdin),fclose(stdout)

#define ll long long
#define MAXN 300005
int n,m,cnt,a[MAXN],ans[MAXN];
struct SegmentTree{int deep;ll MAX,Max;}t[MAXN << 2];
void build(int d,int i,int l,int r)
{
    t[i].deep = d;if(l == r){t[i].MAX = a[l],t[i].Max = 0;return ;}
    int mid = (l+r)>>1;build(d-1,i<<1,l,mid),build(d-1,(i << 1) + 1,mid+1,r);
    t[i].MAX = max(t[i<<1].MAX,t[(i << 1) + 1].MAX);
    t[i].Max = max(t[i << 1].Max,t[(i << 1) + 1].Max);
    t[i].Max = max(t[i].Max,min(t[i << 1].MAX,t[(i << 1) + 1].MAX));
    return ;
}
void solve()
{
    for(int i=1;i<=(m << 1) - 1;i++)
    {
        while(cnt > t[i].Max && cnt)
            ans[cnt --]=t[i].deep;
        if(cnt==1) return ;
    }
    return ;
}
int main()
{
    file("tournament");
    scanf("%d",&n),cnt = m = 1 << n;
    for(int i=1;i<=m;i++) scanf("%d",&a[i]);
    build(n,1,1,m),solve();
    for(int i=1;i<=m;i++)
        printf("%d ",ans[i]);
    file_close;
    return 0;
}

$run$

作为一个熟练的算法竞赛选手,$Cicada$ 跑的比谁都快 $(?)$$Cicada$$Dove$ 所在的高中最近要举办一个运动会,作为好朋友,$Cicada$$Dove$ 一块参加了接力跑项目。接力跑项目一共有 $n + 1$ 个人参加,其中 $Dove$ 作为最后一个接棒人,并不参与实际的跑步,所以总共有 $n$ 个人可能参与跑步,接力棒最多会被交接 $n$ 次,每个人都有一定的身高,对于第 $i$ 个人,他的身高为 $h_i$ 。特别的,一个人的接力棒并不是一定要传给相邻的人,当经过一个人时,他可以自行选择是将接力棒传递给这个人还是继续走向下一个人。但是,如果当前持棒人的身高小于当前接棒人的身高时,那么他就必须交接接力棒。因为一些奥妙重重的原因,参加接力跑的所有人的速度都是相近的,并且任意相邻两个人之间的距离也是相近的。所以我们定义一个时间单位为接力棒从一个人手里传到下一个人手里在路上需要经历的时间。同时,对于每个人来说,他参加接力跑有一定的厌烦度,对于第 $i$ 个人,他的厌烦度为 $c_i$ ,如果第 $i$ 个人被传递了接力棒,那么整场比赛的无聊度就会增加 $c_i$,特别的,$Cicada$ 作为第一个人,是组织者,他的厌烦度是 $0$。为了让比赛尽可能好看,$Cicada$ 向指定一个传棒方案,使得正常比赛的无聊度与消耗时间的和尽可能低。因为 $Cicada$ 还要肝 $DDL$,所以这个锅就甩给你了。

$dp$

考场上没仔细看(一直在调T1)

现在还没搞懂,所以就贴一下出题人的代码和题解

$f_i$表示传到第 $i$ 个人的最小花费,我们维护一个单调队列,可以发现此时单调队列的长度期望是 $log n$ 级别的,并且可以发现有效的转移只会发生在队列里,暴力转移即可,这个相比线段树的 $log$ 常数较小,可以通过$10^6$,观察到每次转移实际上是在队列里分前缀和后缀转移,而我们每次加入新元素弹出旧元素的时候恰好会访问到边界。因此我们维护一个前缀最小值来辅助转移即可,时间复杂度为 $O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>

#define up(__i,__start,__end) for (int __i = (__start); __i <= (__end); __i++)
#define down(__i, __start,__end) for (int __i = (__start); __i >= (__end); __i--)
#define fi first
#define se second
#define bin(__o) (1 << (__o))
#define bug(x) std::cerr<<"[ "<<(#x)<<":  "<<x<<" ]"<<std::endl
#define bugline std::cerr<<"Passing:  "<<__LINE__<<std::endl
#define bugm(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

template<typename T> inline T max(T a, T b) {return a > b ? a : b;}
template<typename T> inline T min(T a, T b) {return a < b ? a : b;}
template<typename T> inline bool cmax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<typename T> inline bool cmin(T &a, T b) {return a > b ? a = b, 1 : 0;}

const int maxn = 1e6 + 5;

int n, h[maxn], c[maxn], q[maxn], top;

ll pre[maxn], f[maxn];

inline void push(int o) {
    q[++top] = o;
    pre[top] = min(pre[top - 1], h[o] + f[o]);
}

#define FILE "run"

inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while ('0' > ch || ch > '9') {if (ch == '-') f = -1; ch = getchar(); }
    while ('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main() {

    freopen(FILE".in", "r", stdin);
    freopen(FILE".out", "w", stdout);

    scanf("%d", &n);
    up (i, 1, n) h[i] = read();
    up (i, 2, n) c[i] = read();
    pre[0] = 1e18;
    f[1] = 0;
    push(1);
    up (i, 2, n) {
        f[i] = 1e18;
        while (top >= 1 && h[i] > h[q[top]]) {
            cmin(f[i], f[q[top]] + h[i] - h[q[top]] + c[i]);
            top--;
        }
        cmin(f[i], pre[top] - h[i] + c[i]);
        push(i);
    }
    ll ans = 1e18;
    up (i, 1, top) cmin(ans, f[q[i]] + n);
    printf("%lld\n", ans);

    return 0;
}

$magnet$

没人$A$(包括一个点超时得90分的std)

给定一个长度为 $n$ 的序列,对于每个位置,询问所有数和他的异或值中 $1$ 的数量

现在都还是不会

把出题人的题解和代码放上来吧

不妨假设 $m$ 是偶数,如果 $m$ 是奇数我们将 $m + 1$ 即可,这不会影响我们的计算,另取 $h = \frac{m}{2}$

我们考虑动态维护一个函数$f(pp, qq, c)$,表示当前数集中所有前 $h$ 位的状态为 $pp$,后$h$ 位与 $qq$ 的异或和中 $1$ 的数量为 $c$ 的数的个数。

对于 $i$,假设我们现在以及维护了前 $i − 1$ 个数的 $f$,那么我们只需要暴力枚举 $a_i$$h$位的所有可能的状态即可。考虑如何更新 $f$,因为前 $h$ 位的状态是固定的,因此我们只需要枚举后 $h$ 位的状态即可,这个复杂度与询问时一致的。$m$复杂度$O(n2^{\frac{m}{2}})$,期望得分 100pts

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

#define up(__i,__start,__end) for (int __i = (__start); __i <= (__end); __i++)
#define down(__i, __start,__end) for (int __i = (__start); __i >= (__end); __i--)
#define fi first
#define se second
#define bin(__o) (1 << (__o))
#define bug(x) std::cerr<<"[ "<<(#x)<<":  "<<x<<" ]"<<std::endl
#define bugline std::cerr<<"Passing:  "<<__LINE__<<std::endl
#define chkloop assert(false)
#define bugm(__x) std::cerr<<(#__x)<<std::endl

typedef long long ll;
typedef unsigned long long ull;
typedef double db;

template<typename T> inline T max(T a, T b) {return a > b ? a : b;}
template<typename T> inline T min(T a, T b) {return a < b ? a : b;}
template<typename T> inline bool cmax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<typename T> inline bool cmin(T &a, T b) {return a > b ? a = b, 1 : 0;}

const int maxn = 2e5 + 5;
const int maxs = (1 << 16);

int n, m, a[maxn], f[maxs >> 8][maxs >> 8][9], bc[maxs], ans[17], hash = 0;

#define FILE "magnet"

int main() {

    freopen(FILE".in", "r", stdin);
    freopen(FILE".out", "w", stdout);

    scanf("%d%d", &n, &m);  
    int mm = m;
    m += m % 2;
    int all = 1 << m, hf = all >> (m / 2);
    up (ss, 1, all - 1) bc[ss] = bc[ss >> 1] + (ss & 1);
    up (i, 1, n) scanf("%d", &a[i]);
    up (i, 1, n) {
        std::memset(ans, 0, sizeof(ans));
        int app = a[i] >> (m / 2), aqq = a[i] & (hf - 1), m2 = m / 2;
        up (pp, 0, hf - 1) up (cnt, 0, m2) ans[bc[pp ^ app] + cnt] += f[pp][aqq][cnt];  
        up (qq, 0, hf - 1) f[app][qq][bc[qq ^ aqq]]++;
        up (j, 0, mm) hash ^= (ans[j] + i + j);
    }
    printf("%d\n", hash);

    return 0;

}