比赛链接 / 官方题解链接
A. Even Subset Sum Problem
Solution
找一个偶数或两个奇数即可。
Code
>folded1
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
| #include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 105;
int T, n, a[N];
int main(){
read(T);
while(T--){
read(n);
int mark = 0, mark1 = 0, mark2 = 0;
for(int i = 1; i <= n; i++){
read(a[i]);
if(a[i] % 2 == 0) mark = i;
else if(mark1 == 0) mark1 = i;
else mark2 = i;
}
if(mark){
printf("1\n%d\n", mark);
continue;
}
if(mark1 && mark2)
printf("2\n%d %d\n", mark1, mark2);
else puts("-1");
}
return 0;
}
|
B. Count Subrectangles
Solution
枚举矩形边长，分别数 $a$ 和 $b$ 数组中有多少能构成边长的连续 $1$，答案加上二者乘积。
复杂度：$O(n\cdot r(k))$，其中 $r(k)$ 表示 $k$ 的约数个数。
Code
>folded1
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
| #include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 40005;
int n, m, k, a[N], b[N];
int dpa[N], dpb[N];
LL ans = 0;
int main(){
read(n, m, k);
for(int i = 1; i <= n; i++){
read(a[i]);
if(a[i] == 1) dpa[i] = dpa[i-1] + 1;
else dpa[i] = 0;
}
for(int i = 1; i <= m; i++){
read(b[i]);
if(b[i] == 1) dpb[i] = dpb[i-1] + 1;
else dpb[i] = 0;
}
vector<int> vec;
for(int r = 1; r * r <= k; r++)
if(k % r == 0)
vec.push_back(r);
for(auto r: vec){
LL cnt1 = 0, cnt2 = 0;
for(int i = 1; i <= n; i++) cnt1 += (dpa[i] >= r);
for(int i = 1; i <= m; i++) cnt2 += (dpb[i] >= (k / r));
ans += cnt1 * cnt2;
if(r * r == k) continue;
cnt1 = cnt2 = 0;
for(int i = 1; i <= n; i++) cnt1 += (dpa[i] >= (k / r));
for(int i = 1; i <= m; i++) cnt2 += (dpb[i] >= r);
ans += cnt1 * cnt2;
}
printf("%lld\n", ans);
return 0;
}
|
C. Unusual Competitions
Solution
比赛时猜的结论：顺序遍历字符串，当 ( 和 ) 相等时，若没有构成合法序列，就 reorder 一次。
Intuitive proof：画一个折线图，遇到 ( 就往上画，遇到 ) 就往下画，然后我们需要把基准线以下的部分翻转到上面去，图参看官方题解。
Code
>folded1
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
| #include<algorithm>
#include<cstdio>
#include<stack>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 1000005;
int n, cnt[2][N], ans;
char s[N];
int main(){
read(n);
scanf("%s", s+1);
for(int i = 1; i <= n; i++){
if(s[i] == '(')
cnt[0][i] = cnt[0][i-1] + 1, cnt[1][i] = cnt[1][i-1];
else
cnt[0][i] = cnt[0][i-1], cnt[1][i] = cnt[1][i-1] + 1;
}
if(cnt[0][n] != cnt[1][n]) return puts("-1"), 0;
stack<int> sta;
int pre = 0;
for(int i = 1; i <= n; i++){
if(s[i] == ')' && !sta.empty() && sta.top() == '(')
sta.pop();
else sta.push(s[i]);
if(cnt[0][i] == cnt[1][i]){
if(!sta.empty()){
ans += i - pre;
while(!sta.empty()) sta.pop();
}
pre = i;
}
}
printf("%d\n", ans);
return 0;
}
|
D. Present
Solution
答案的第 $i$ 位为 $1$ 当且仅当存在奇数个数对 $(j,k)$ 满足 $a_j+a_k$ 的第 $i$ 位为 $1$。
依次考虑答案的每一位（从 $0$ 开始），在考虑第 $i$ 位时，由于更高位对答案没有影响，我们先去掉更高位的数字，形成新的数列 $b[]$，那么现在每个数的取值范围是 $[1,2^{i+1}-1]$，两个数的和的范围是 $[2,2^{i+2}-2]$. 于是，若数对 $(j,k)$ 满足 $b_j+b_k$ 的第 $i$ 位为 $1$，那么 $b_j+b_k\in[2^i,2^{i+1}-1]\cup[2^{i+1}+2^i,2^{i+2}-2]$（草纸上举举例就知道了）。枚举 $b_j$，排序后分别在两个区间二分查找就可以数出数对 $(j,k)$ 的数量。
复杂度：$O(n\lg n\lg10^7)$
Code
>folded1
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
| #include<algorithm>
#include<cstdio>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 400005;
int n, a[N], b[N], ans;
int main(){
read(n);
for(int i = 1; i <= n; i++) read(a[i]);
for(int i = 0; i <= 24; i++){
for(int j = 1; j <= n; j++)
b[j] = a[j] & ((1 << (i+1)) - 1);
sort(b+1, b+n+1);
LL cnt = 0;
for(int j = 1; j <= n; j++){
int l = lower_bound(b+1, b+j, (1<<i) - b[j]) - b;
int r = upper_bound(b+1, b+j, (1<<(i+1))-1 - b[j]) - b;
cnt += r - l;
l = lower_bound(b+1, b+j, (1<<i)+(1<<(i+1)) - b[j]) - b;
r = upper_bound(b+1, b+j, (1<<(i+2))-2 - b[j]) - b;
cnt += r - l;
}
if(cnt & 1) ans |= (1 << i);
}
printf("%d\n", ans);
return 0;
}
|
E. Instant Noodles
Solution
容易知道，把右边邻域相同的点合并为一个点（权值相加）后答案不变。结论：合并后答案就是右边所有点的权值 $gcd$.
证明：设左边点 $a$ 在右边的邻域的权值和为 $A$，左边点 $b$ 在右边的邻域的权值和为 $B$，那么 $a,a\cup b$ 是两个子集，选出这两个子集时，$gcd(A,A+B)=gcd(A,B)$. 扩展到所有子集，答案就是右边所有点的 $gcd$.
Code
>folded1
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
| #include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 500005;
LL gcd(LL a, LL b){ return b == 0 ? a : gcd(b, a % b); }
int T, n, m;
LL c[N];
vector<int> edge[N];
int main(){
read(T);
while(T--){
read(n, m);
for(int i = 1; i <= n; i++) edge[i].clear();
for(int i = 1; i <= n; i++) read(c[i]);
for(int i = 1; i <= m; i++){
int u, v; read(u, v);
edge[v].emplace_back(u);
}
map<vector<int>, LL> a;
for(int i = 1; i <= n; i++){
if(edge[i].empty()) continue;
sort(edge[i].begin(), edge[i].end());
a[edge[i]] += c[i];
}
LL ans = 0;
for(auto x: a) ans = gcd(x.second, ans);
printf("%lld\n", ans);
}
return 0;
}
|
F. Reality Show
Solution
把输入颠倒一下顺序，则原题可转化为：求不降序列使得合并后收益最大。
设 $dp[i][j][k]$ 表示考虑前 $i$ 个数，最大值小于等于 $j$ 且有 $k$ 个值等于 $j$ 的最大收益，则若选择第 $i$ 个数，$dp[i][l_i][k]$ 可从 $dp[i-1][l_i][k-1]$ 转移而来；另外，不断地两两合并，有 $dp[i][j][k]$ 可以从 $dp[i][j-1][2k]$ 和 $dp[i][j-1][2k+1]$ 转移而来，一共合并 $O(\lg n)$ 次。
实现时 $dp$ 数组第一维滚动，则时间复杂度 $O(n^2\lg n)$，空间 $O(n^2)$.
Code
>folded1
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<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 2005;
const int INF = 1e9;
int n, m, l[N], s[N], c[N<<1];
int dp[N<<1][N], ans = -INF;
int main(){
read(n, m);
for(int i = n; i >= 1; i--) read(l[i]);
for(int i = n; i >= 1; i--) read(s[i]);
for(int i = 1; i <= n + m; i++) read(c[i]);
memset(dp, -0x7f, sizeof dp);
for(int i = 1; i <= n + m; i++) dp[i][0] = 0;
for(int i = 1; i <= n; i++){
int pos = l[i];
for(int j = i; j >= 1; j--)
dp[pos][j] = max(dp[pos][j], dp[pos][j - 1] + c[l[i]] - s[i]);
for(int k = pos + 1, t = i / 2; k <= n + m; k++, t >>= 1){
for(int j = t; j >= 0; j--){
dp[k][j] = max(dp[k][j], dp[k-1][j<<1] + j * c[k]);
dp[k][j] = max(dp[k][j], dp[k-1][j<<1|1] + j * c[k]);
}
}
}
for(int i = 1; i <= n + m; i++) ans = max(ans, max(dp[i][0], dp[i][1]));
printf("%d\n", ans);
return 0;
}
|