Jeopardy!

题目大意 ：

给定一个长度为 $n$ 的数组 $a=[a_{1},a_{2},\dots,a_{n}]$ ，其中 $m$ 个元素是特殊元素。你可以任意排列这 $n$ 个元素的顺序。初始化总和为 $s=0$。

如果当前元素是普通元素，则

$$s \leftarrow s+a_{i}$$

如果当前元素是特殊元素，且 $s\geq a_{i}$，你可以令 $a_{i}=s$

$$s \leftarrow s + s$$

思路

很明显，这 n - m 个普通元素的值一定会被累加。不妨把这个累加和称之为 base。剩下的就只要分情况讨论。这里记 max 为 m 个特殊元素中的最大值。

1. $base \geq max$ ，这个时候所有的特殊元素都可以改动。贪心球求得累加和肯定最大。$ans = base * (1 \ll m)$

2. $base< max$ ，这个时候，必须起码要从特殊元素中选择一个($a_{i} \in a_{m}$)，把它当成普通元素处理。做 $base \leftarrow base +a_{i}$。这个时候，只有 $a_{i}=max$ 的时候，是贪心最优解。此时有

   $$m -= 1, \quad ans = base * (1 \ll m)$$

The child and Toy

很简单，不多说。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void solve() {
    int n ,m;
    cin >> n >> m;
    std::vector<int> arr(n);
    for(int &i : arr) cin >> i;
    
    i64 ans = 0;
    while(m --) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        ans += std::min(arr[l], arr[r]);
    }

    cout << ans << nl;
}

Three displays

思路

如果以 $i$ 或者 $k$ 为 $point$ 展开，整个的时间复杂度是 $O(N^3)$ 。这个时候，我们转换思维，以 $j$ 为基准，整个问题就迎刃而解。

Divide by three, multiply by two

思路

注意到题目对一个 $num$ 的处理只有 ×3 ÷2 这两种操作，这说明最终的排序和这个数字里面 2 和 3 的因数个数有关。于是按照 2 从小到大，3 从大到小这样排序就是最终答案。

btw，最开始我乱搞过了这题。但是那个方法我现在觉得能过简直是奇迹。

Iva & Pav

思路

这个题我学了两种方法。一种是哥哥的方法，思维量较大但是非常快。一种是参考答案，只要想到了前缀和就很简单。

两个方法都没有利用 与 这个运算本身特殊的性质，而是采用了暴力运算。

$I$

先转化思考，如果这个 f 代表的不是区间与，而是区间加法。那么这个题我该怎么写？答案是前缀和 + 二分。这个不难想到。

从这里入手，回到题目。但是区间与并没有类似 ^ + 这样的性质，也就是说，使用不了前缀和。重点就是，怎样转化到前缀和。

注意到，如果我把每个数字的二进制写出来，对应的位数中如果存在连续的 1 ，就会满足区间和等于端点值相减 + 1。如此，问题就迎刃而解。

1
2
3
4
5
6
7
8
9

for(int i = 0; i < n; ++i) {
    for(int j = 0; j < 30; ++j) {
        if(arr[i] >> j & 1) {
            pref[i + 1][j] = pref[i][j] + 1;
        } else {
            pref[i + 1][j] = pref[i][j];
        }
    }
}

$II$

1
2
3
4
5
6
7
8

for(int i = n - 1; i >= 0; --i) {
	nxt[i] = nxt[i + 1];
	for(int j = 30; j >= 0; --j) {
		if(~arr[i] >> j & 1) {
			nxt[i][j] = i;
		}
	}
}

哥哥的代码采用了类似填表的思路，但是是从后往前填的，$nxt[i][j]$ 代表 idx 为 i 的数字二进制第 j 位存在连续的 1 直到 $nxt[i][j]$ 这个 idx 为止。

1
2
3
4
5
6
7
8
9

for(int i = 30; i >= 0; --i) {
	if(k >> i & 1) {
		max = std::min(max, nxt[l][i]);
	} else {
		pos = std::max(pos, std::min(max, nxt[l][i]));
	}
}

int ans = std::max(max, pos);

max 代表绝对上界，也就是说当 k 在这一位为 1 的时候， 你构成的这个数，起码要是 1 才能满足条件。

pos 就是潜在的最大值，也就是说，当 k 和 f(l, r) 逐位比较的时候，如果在某一位 k = 0， 此时 f(l, r) 是可为 0， 可为 1 的。比如当你这个位为 0 的时候，你可以保存一个很大的 pos，但是下一个位 k 为 1，不巧你的绝对上界在这个位被压缩的很小。但是最终答案是在 pos , max 里面取的。其实就是这种例子：$k = ***11001111, f(l, r) = ***11100000$ 。

Phoenix and Beauty

思路

注意到—任意长度为 k 的序列重复一次，在区间长度为 k 的和都相等—这个性质就行。

Rotation Matching

思路

注意到，如果两个序列中某个元素可以旋转到相同位置，说明这两个元素的相对位置是一样的。排序计算相对位置即可。

Epic Transformation

思路

摩尔投票问题，这篇文章 讲的很好。

当存在绝对众数的时候，最终剩下的结果一定是绝对众数。

当不存在绝对众数的时候， 最终的结果一定是 0 或者 1。

可以在奇数和偶数的时候用数学归纳法证明。

另解：注意到数学归纳中的规律，使用优先队列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int ans = n;
while(q.size() >= 2) {
	auto [cnt1, val1] = q.top();
	q.pop();
	auto [cnt2, val2] = q.top();
	q.pop();

	cnt1-- , cnt2--;

	ans -= 2;
	if(cnt1 > 0) {
		q.push({cnt1, val1});
	}
	if(cnt2 > 0) {
		q.push({cnt2, val2});
	}

}

Element Extermination

思路

只有在 $a_{1} < a_{n}$ 的时候有解。易证。

Team

思路

很典的题了。先看出无解情况，特判特殊解，然后就是尽可能的放 110 就行。

Find The Array

思路

两种解法。

一种是 偶数个数全为 $a_{i}$ ，奇数为1；或者奇数 $a_{i}$ ，偶数为1。这种方法一定存在一种满足题意。

可以用这个放缩证明

着重讲一下第二种解法。

不妨设 $a_{i}>b_{i}$ ，且把约束加强到 $i$ ，有 $b_{i} > \frac{a_{i}}{2}$ 也就是 $a_{i} > b_{i} > \frac{a_{i}}{2}$ 。我们知道 $\left[ \frac{a_{i}}{2}, a_{i} \right]$ 之间一定存在一个 $2^k$ 。就有如下代码

1
2
3
4
5
6

for(int &i : arr) {
	while(i - lowbit(i) != 0) {
		i -= lowbit(i);
	}
	cout << i << " \n"[&i == &arr.back()];
}

Game With Array

思路

这个题也有两种解法。一种是填 2 ， 一种是填 1.我估计这两个方法没有什么本质上的区别。

$1,1,1,\dots,k$ 只要证明这种方法的产生数是最多的就行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void solve() {
    int n , s;
    cin >> n >> s;
    if(s / 2 + 1 <= n) {
        cout << "NO" << nl;
        return ;
    }

    cout << "YES" << nl;
    for(int i = 0; i < n - 1; ++i) {
        cout << 1 << " ";
    }

    cout << s - (n - 1) << nl;
    cout << s / 2 << nl;
}

Quasi Binary

思路

注意到整个过程中所使用的 $Quasi Binary$ 最多九个

Composite Coloring

思路

注意到题目限制的 11 和 1000 肯定是 1000 以内的合数最大的因子不会超过第 11 个质数。由于不存在质数，由唯一分解定理可知，只需从小到大把所有的数筛一遍就行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

int cnt = 0;
for(int i = 0; i < n; ++i) {
	for(int j = 0; j < 11; ++j) {
		if(arr[i] % prime[j] == 0) {
			if(choice[j] == 0) {
				choice[j] = ++cnt;
			}
			ans[i] = choice[j];
			break;
		}
	}
}