比赛链接 / 官方题解链接
A. Fast Food Restaurant
Solution
最多最多就 $7$ 种搭配，$a,b,c,ab,ac,bc,abc$，从大到小依次去满足即可。
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
| #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...);}
int T, a, b, c;
int main(){
read(T);
while(T--){
int ans = 0;
read(a, b, c);
if(a < b) swap(a, b); if(a < c) swap(a, c); if(b < c) swap(b, c);
if(a) a--, ans++; if(b) b--, ans++; if(c) c--, ans++;
if(a && b) a--, b--, ans++; if(a && c) a--, c--, ans++; if(b && c) b--, c--, ans++;
if(a && b && c) a--, b--, c--, ans++;
printf("%d\n", ans);
}
return 0;
}
|
B. Different Rules
卡了好久……好歹把式子弄出来了，差点以为要挂在 B 题上……
看到官方题解也是庞大的一坨，我就放心了（雾
Solution
不失一般性，假设 $x\leq y$. 下面的图中，第一列代表第一轮，第二列代表第二轮，每一行代表一个人的得分。
我们首先看一种大家“皆大欢喜”的情况——所有人总得分都一样，第一轮得了 $i$ 分，第二轮就得 $n+1-i$ 分（图1）。接下来分情况讨论：
- $x+y\leq n$：此时图1中第二列的 $y$ 在第一列的 $x$ 下方（图2-1），已知条件是，第二列的这个 $y$ 往上跑到和第一列的 $x$ 同一层去了。
- 最小排名：交换第二列的 $y$ 和与第一列的 $x$ 同一层的那个元素，显然就是第1名了（图2-2）；
- 最大排名：$y$ 往上跑了 $(n-y+1)-x$ 层导致了 $x+y$ 变小了，于是其他人很不爽，也想把第二轮的得分变小且变小到总分与 $x+y$ 相等就够了，于是大家都往上移 $(n-y+1)-x$ 层，总体上来看第二列往上“滚”（第 $i$ 层到第 $i-1$ 层，第 $1$ 层到最后一层）了 $(n-y+1)-x$ 层（图2-3）。从上面滚到下面去了的有 $(n-y+1)-x$ 个，这些分事实上变大了，不计入答案，所以最大排名是 $n-[(n-y+1)-x]=x+y-1$.
- $x+y>n$：此时图1中第二列的 $y$ 在第一列的 $x$ 上方（图3-1），已知条件是，第二列的这个 $y$ 往下跑到和第一列的 $x$ 同一层去了。
- 最大排名：交换第二列的 $y$ 和与第一列的 $x$ 同一层的那个元素，显然就是第 $n$ 名了（图3-2）；
- 最小排名：$y$ 往下跑了$x-(n-y+1)$ 层导致了 $x+y$ 变大了，其他人都很关心它，想把第二轮得分变大，于是大家都往下移 $x-(n-y+1)$ 层，总体上来看第二列往下“滚”了 $x-(n-y+1)$ 层，可惜还不够，为使 $x+y$ 排名更小，其他元素还得再往下移一层（图3-3）。从下面滚到上面去了的有 $\min\{n-1,x-(n-y+1)+1\}$ 个（小心 $x=y=n$ 的特殊情况），这些分事实上变小了，不计入答案，所以最小排名是 $\min\{n-1,x-(n-y+1)+1\}+1=\min\{n,x+y-n+1\}$.
把上面两种情况整合起来，最小排名 $=\max(\min(n,x+y+1-n),1)$，最大排名 $=\min(x+y-1,n)$.
Code
>folded1
2
3
4
5
6
7
8
9
10
11
12
| #include<algorithm>
#include<cstdio>
using namespace std;
int T, n, x, y;
int main(){
scanf("%d", &T);
while(T--){
scanf("%d%d%d", &n, &x, &y);
printf("%d %d\n", max(min(n, x + y + 1 - n), 1), min(x + y - 1, n));
}
return 0;
}
|
C1. Skyscrapers (easy version)
Solution
依次枚举每一个元素作为最高点，然后向左右两边暴力扩展即可。
复杂度：$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
41
| #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 = 1005;
int n;
LL m[N], f[N], rec[N], ans[N];
int main(){
read(n);
for(int i = 1; i <= n; i++) read(m[i]);
for(int i = 1; i <= n; i++){
LL res = m[i];
rec[i] = m[i];
for(int j = i - 1; j >= 1; j--){
LL now = min(m[j], rec[j+1]);
res += now;
rec[j] = min(m[j], rec[j+1]);
}
for(int j = i + 1; j <= n; j++){
LL now = min(m[j], rec[j-1]);
res += now;
rec[j] = min(m[j], rec[j-1]);
}
if(ans[0] < res){
ans[0] = res;
for(int j = 1; j <= n; j++) ans[j] = rec[j];
}
}
for(int i = 1; i <= n; i++)
printf("%lld ", ans[i]);
return 0;
}
|
C2. Skyscrapers (hard version)
唉，比赛时在正解的边缘疯狂试探，然后逐渐偏离正解，用分治解出了最大值，突然想起题目要求的是方案，结果复杂度降不下来了……
Solution
预处理每一个元素左右最近的小于它的元素位置（设为 $L_i,R_i$），然后就可以递推了：
- 设 $f_i$ 是以第 $i$ 个元素结尾的最大上升序列的值，那么 $f_i=f_{L_i}+m_i\cdot(i-L_i)$.
- 设 $g_i$ 是以第 $i$ 个元素开头的最大下降序列的值，那么 $g_i=g_{R_i}+m_i\cdot(R_i-i)$.
然后枚举每一个点作为最大值，第 $i$ 个点作为最大值时的答案就是 $f_i+g_i-m_i$ 了。靠 $L$ 和 $R$ 数组也能够线性地把方案解出来。
怎么预处理呢？我的方法是 ST 表+二分查找（说实话有点奇怪……毕竟以前从来没有在 ST 表上二分过……）
复杂度：$O(n\lg n)$
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #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 = 500005;
int n, L[N], R[N];
LL m[N], f[N], g[N], h[N], ans;
int lg[N];
LL rmq[N][20];
void pre(){
lg[1] = 0, lg[2] = 1;
for(int i = 3; i <= n; i++)
lg[i] = lg[i/2] + 1;
}
void init(){
for(int i = 1; i <= n; i++) rmq[i][0] = m[i];
for(int j = 1; (1 << j) <= n; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++)
rmq[i][j] = min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
}
int query(int l, int r){
int k = lg[r - l + 1];
return min(rmq[l][k], rmq[r-(1<<k)+1][k]);
}
inline void find(int x){
int l = 0, r = x - 1;
while(l < r){
int mid = (l + r) >> 1;
if(query(mid + 1, r) < m[x]) l = mid + 1;
else r = mid;
}
L[x] = l;
l = x + 1, r = n + 1;
while(l < r){
int mid = (l + r) >> 1;
if(query(l, mid) < m[x]) r = mid;
else l = mid + 1;
}
R[x] = r;
}
int main(){
read(n);
for(int i = 1; i <= n; i++) read(m[i]);
pre(); init();
for(int i = 1; i <= n; i++) find(i);
for(int i = 1; i <= n; i++) f[i] = f[L[i]] + m[i] * (i - L[i]);
for(int i = n; i >= 1; i--) g[i] = g[R[i]] + m[i] * (R[i] - i);
int mark = 0;
for(int i = 1; i <= n; i++){
if(ans < f[i] + g[i] - m[i]){
ans = f[i] + g[i] - m[i];
mark = i;
}
}
int now = mark;
while(now){
for(int i = L[now] + 1; i <= now; i++) h[i] = m[now];
now = L[now];
}
now = mark;
while(now <= n){
for(int i = now; i <= R[now] - 1; i++) h[i] = m[now];
now = R[now];
}
for(int i = 1; i <= n; i++) printf("%lld ", h[i]);
return 0;
}
|
D. Happy New Year
留坑……
