A
题目大意：两个矩形拼在一起，上面的矩形宽度小于下面的矩形，求离这两个矩形最近的方块个数（不包含矩形本身）。
模拟。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int ww1, hh1, ww2, hh2;
void init(){
ww1 = read(), hh1 = read(), ww2 = read(), hh2 = read();
}
void solve(){
cout << ww1 + hh1 + hh1 + hh2 + ww2 + hh2 + ww1 - ww2 + 4 << endl;
}
int main(){
init();
solve();
return 0;
}
B
题目大意：有两个队伍比赛，某一个时候比分为$a: b$，那么某一队得分之后就可能变为$a+1: b$或者$a: b+1$。按时间顺序给出一系列时间点的比分，问最多可能有多少个时刻，满足两队比分相同（包含$0: 0$）。
模拟，但是情况比较繁琐。按照前后两个时刻$a>b, a=b, a< b$讨论。虽然这样就有9种情况，但有些情况是对称的。
数学上分析的话有更简单的做法：设前后两个时刻的比分分别是$a: b$和$c: d$，那么如果形如$x: x$的平局出现就有$a\le x \le c, b \le x \le d\implies \max\lbrace a, b\rbrace \le x \le \min \lbrace c, d \rbrace$。但不能立即得出$x$有$\min \lbrace c, d \rbrace - \max\lbrace a, b\rbrace + 1$个，因为如果$a=b=c=d$就会出现重复计算的情况，因此这种情况还要特殊考虑。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, a[10005], b[10005];
void init(){
n = read();
}
void solve(){
for(int i = 1; i <= n; ++i)
a[i] = read(), b[i] = read();
a[0] = b[0] = 0;
int ans = 1;
for(int i = 1; i <= n; ++i){
if(a[i - 1] == b[i - 1]){
if(a[i] == b[i]) ans += b[i] - b[i - 1];
else if(a[i] < b[i]) ans += a[i] - a[i - 1];
else ans += b[i] - b[i - 1];
}else if(a[i - 1] < b[i - 1]){
if(a[i] == b[i]) ans += b[i] - b[i - 1] + 1;
else if(a[i] < b[i]) ans += max(a[i] - b[i - 1] + 1, 0);
else ans += b[i] - b[i - 1] + 1;
}else if(a[i - 1] > b[i - 1]){
if(a[i] == b[i]) ans += a[i] - a[i - 1] + 1;
else if(a[i] < b[i]) ans += a[i] - a[i - 1] + 1;
else ans += max(b[i] - a[i - 1] + 1, 0);
}
}
printf("%d\n", ans);
}
int main(){
init();
solve();
return 0;
}
C
题目大意：给定一个长度为$n$的数列$a$，将其重排使得最小。
可能容易根据数据猜出来当呈现“山峰型”排列（也就是先对数列排序，然后前半部分：正着排列奇数位置元素，后半部分：倒着排列偶数位置元素）时该值达到最小。确实如此，不过我们需要一个证明。
D
题目大意：给定两组菜，第一组有$n$道菜，第二组有$m$道菜，给定这两组菜之间每一对菜的美味程度相比关系（前者大于，小于或等于后者），共$nm$对。要求对每一个菜赋予一个美味值，要求是正整数，且每一对菜美味值的关系和美味程度的关系相符合，且最大的美味值最小。如果无法赋予，输出No。
缩点+拓扑排序。将关系是等于的两个菜之间连一条无向边，否则从美味程度低的菜连一条边到美味程度高的菜。然后缩点，按拓扑序分配美味值。最后再检查，如果分配的美味值和所给信息相矛盾就输出No。
上面的缩点可以改成并查集。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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
struct Edge{
int v, nxt;
};
Edge e[2000005], e_[2000005];
int at[2005] = {0}, n, m, cnt = 0;
int at_[2005] = {0}, cnt_ = 0;
int dfn[2005] = {0}, low[2005], D = 0, in[2005] = {0};
int st[2005], top = 0, du[2005] = {0};
int repre[2005] = {0}, rk[2005];
int que[2005], hd = 0, tl = 0;
char mat[1005][1005];
void addEdge(int u, int v){
e[++cnt].v = v;
e[cnt].nxt = at[u], at[u] = cnt;
}
void addEdge_(int u, int v){
e_[++cnt_].v = v;
e_[cnt_].nxt = at_[u], at_[u] = cnt_;
}
void tarjan_scc(int id){
dfn[id] = low[id] = ++D;
in[id] = true;
st[top++] = id;
int i = at[id], vv;
while(i){
vv = e[i].v;
if(!dfn[vv])
tarjan_scc(vv), low[id] = min(low[id], low[vv]);
else if(in[vv])
low[id] = min(low[id], dfn[vv]);
i = e[i].nxt;
}
if(dfn[id] == low[id]){
for(; ; ){
top--;
in[st[top]] = false;
repre[st[top]] = id;
if(st[top] == id)
break;
}
}
}
void getDu(){
for(int i = 1; i <= n + m; ++i){
for(int j = at[i]; j; j = e[j].nxt){
if(repre[i] == repre[e[j].v]) continue;
addEdge_(repre[i], repre[e[j].v]);
du[repre[e[j].v]]++;
}
}
for(int i = 1; i <= n + m; ++i){
if(repre[i] != i) continue;
if(!du[i]) rk[i] = 1, que[tl++] = i;
}
while(tl > hd){
int id = que[hd++];
for(int i = at_[id]; i; i = e_[i].nxt){
du[e_[i].v]--;
if(!du[e_[i].v]) rk[e_[i].v] = rk[id] + 1, que[tl++] = e_[i].v;
}
}
for(int i = 1; i <= n + m; ++i)
rk[i] = rk[repre[i]];
}
void init(){
n = read(), m = read();
for(int i = 1; i <= n; ++i){
scanf("%s", &mat[i][1]);
for(int j = 1; j <= m; ++j){
if(mat[i][j] != '<') addEdge(n + j, i);
if(mat[i][j] != '>') addEdge(i, n + j);
}
}
}
void solve(){
for(int i = 1; i <= n + m; ++i)
if(!dfn[i]) tarjan_scc(i);
getDu();
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
if((mat[i][j] == '<' && rk[i] >= rk[j + n]) || (mat[i][j] == '=' && rk[i] != rk[j + n]) || (mat[i][j] == '>' && rk[i] <= rk[j + n]))
goto label;
}
}
printf("Yes\n");
for(int i = 1; i < n; ++i) printf("%d ", rk[i]);
printf("%d\n", rk[n]);
for(int i = 1; i < m; ++i) printf("%d ", rk[i + n]);
printf("%d\n", rk[m + n]);
return ;
label:
printf("No\n");
}
int main(){
init();
solve();
return 0;
}
E
我们按不同的字母考虑，对每一个字母都求一个最长子串。
对于一个字母，可以发现$s\cdot t$的最长子串长度只取决于$s$和$t$的最长子串长度。因此，我们不需要算出具体的$s\cdot t$，只需要根据当前字符串$t$和之前处理过的$s$算出结果即可。这样就可以按照字符串连乘的顺序，一步一步推出最终答案。
设$f(s, a)$为串$s$中字母$a$构成的最长子串长度。对$t$分类讨论：
- $t$是纯字符串，即本身只由一个字母构成。那么设$t$中只有字母$a$，则$f(s\cdot t, a) = (f(s, a) + 1)\left| t \right| +f(s, a)$。对其他字母$b$有$f(s\cdot t, b) = \max(\min(f(s, b), 1), 0)$。
- $t$的第一个字母和最后一个字母相同。设其前后
1 |
|
F
这题比D和E简单了一倍。。。
由于答案任意，完全可以用一个链表来维护数之间的顺序，每次操作$(a, b)$就是把$b$所在链表连在$a$之后。不过这需要更新链表的头节点和尾节点，用并查集可以做到。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
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, hd[160005], nxt[160005], tl[160005];
int Findh(int x){
if(x == hd[x]) return x;
return hd[x] = Findh(hd[x]);
}
int Findt(int x){
if(x == tl[x]) return x;
return tl[x] = Findt(tl[x]);
}
void init(){
n = read();
for(int i = 1; i <= n; ++i){
hd[i] = tl[i] = i, nxt[i] = 0;
}
}
void solve(){
int a, b;
for(int i = 1; i < n; ++i){
a = read(), b = read();
int tla = Findt(a), tlb = Findt(b);
int hda = Findh(a), hdb = Findh(b);
hd[hdb] = hda, tl[tla] = tlb;
nxt[tla] = hdb;
}
int root;
for(int i = 1; i <= n; ++i){
if(hd[i] == i){
root = i;
break;
}
}
for(int cur = root; cur; cur = nxt[cur])
printf("%d ", cur);
}
int main(){
init();
solve();
return 0;
}
G
DP。