Fork me on GitHub

校内ACM赛题解选讲

校内题目就不公开题面啦x

数学

首先我们用二项式定理展开一下式子.

有因为$x$是一个常数,则$E(x)=x$,那么显然$E^{k-i}(x)={(\dfrac{1}{2})}^{k-i}$,那么问题就只剩下了$E(x^i)$怎么求了.
而对于$E(x^i)$,我们可以设函数$f(x)=x^i$,然后考虑它的图像.因为$x^i$的期望对应的就是图像中的$y$,所以有$1 \times E(x^i) = S$.
所以我们要计算的就只剩下函数$f(x)=x^i$在$[0,1]$上的图像的面积了.然后这个东西….可以用积分去求得:

计算出$E(x^i)$后,将表达式带回原式后得到

英语

发现直接做的话貌似没什么思路….
显然这道题可以先把询问离线出来,然后有一个显然错误的贪心就是每次选一个叶子节点的值(指从根节点到某个叶子的前缀和)最大的.
这样做显然错误,因为每个点对答案的贡献只能被统计一次,所以我们要考虑怎么调整这个贪心的思路.通过观察发现,对于某一个点$i$,它的值只能被计算到它所有的儿子中边权权重求大的那个儿子,而对于它其他的儿子,它的贡献为$0$.
所以我们的思路类似重链剖分中的寻找重儿子,我们对于每个非叶节点$p$,都在它的子树中找到一个权重最大的子树,然后把它的边权加入到它的重儿子中即可.
听说这东西叫做长链剖分

政治

看完题之后首先想到的就是对于每个犯罪团伙两两考虑包含关系然后再统计答案,但是这样的话时间复杂度上界是$O(2^{40})$,无法通过本题.
然后我们发现村庄的数量只有$20$个,而且显然如果有两个团伙,他们的控制的村庄的状态一样,那么这两个团伙的收入和支出也一定是一样的.那么我们可以考虑根据每个团伙的控制村庄的二进制开桶,然后根据$S_i$统计每个团伙的答案.
不难发现,对于某三个团伙(我们设他们控制的村庄的二进制表示分别为$i,j,k$),那么如果有$i \subsetneqq j , j \subsetneqq k$,那么一定有$i \subsetneqq k$.而如果一个集合$i$是$j$的子集的话,那么必要条件即在二进制表示下$i$中$1$的个数小于等于二进制表示下$j$中$1$的个数.
那么我们如果考虑按照二进制表示下$1$的个数来划分集合的$rank$的话,那么显然某一个状态$i$一定会被所有的二进制下$1$的个数小于它的子集转移到,但是这样直接枚举的话是$3^n$的.所以我们考虑到可以用$FMT$优化.
因为$FMT$为高维前缀和,我们每一次对于某一个状态$j$,显然$inn_j=inn_j+=inn_{j xor ( 1 << i )} ((1<<i) and j==1)$.
而对于支出的情况.可以发现,对于某个状态$i$,它的支出次数即为包含它的集合的个数,而包含它的集合的个数显然也可以用$FMT$去求解(但是注意转移的时候是由它转移到它的子集)即在进行$FMT$时要用异或之后的状态去更新之前的状态.

音乐

首先发现直接使用区间的最大值去减去区间的最小值去更新答案的话显然是不对的,考虑怎么去调整.
发现如果我们使用线段树的话,那么对于某个非叶节点,那么它的答案可能是它左子树的答案,也有可能是它右子树的答案.但是对于合并的话貌似直接不能两边的答案取一个$max$.
我们发现,对于这个节点左子树中的每一个值,那么右子树中的任何一个比左子树中某一个值大的节点都可以去更新这一个节点.所以,我们直接去用右子树中的任何一个节点,去更新左子树中的任何一个节点是没有问题的.
那么我们就可以分别使用左子树中的最小值和右子树中的最大值去维护这个两颗子树合并时的答案.而对于左子树的答案或者右子树的答案可能会大于左右两颗子树合并时的答案的情况,我们可以对于左子树的答案,右子树的答案和右子树的最大值-左子树的最小值去取一个$max$即为这个节点的$ans$值.
所以我们需要维护一颗线段树,分别维护区间最大/最小值以及我们要求的答案即可简单线段树练习题.

体育

我们发现无解的情况只存在于起点会重复的情况,但是题目中明确给出了起点和终点的坐标不会重复,所以没有无解的情况.而且ACM你只判无解也没分
然后我们发现,如果我们把起点和终点都按照坐标从小到大排序之后,我们用最小的起点去对应最小的终点的话,发现这个起点是最小的,那么坐标比它大的点到这些点的终点的路径中一定有一段路程不会被包含,对于终点来说同理(如下图)
显然的结论

所以我们可以直接排完序之后找答案即可.

美术

显然,我们可以设$f_{i,j,01}$表示现在以及考虑了$i$个格子,其中有$j$个格子的颜色和这个格子的上一个的颜色不一样,并且这个格子的颜色和它的上一个的颜色一不一样.
那么如果这个格子的颜色和之前的一样的话,就只能继承前$i-1$个格子的答案,而如果这个格子和这个格子的前一个格子的颜色不一样的话,那么这个格子就有$m-1$种涂色方案.
根据上边所说的,状态转移方程就很明显了:

听说还有组合数学的做法,但是我不会

生物

首先发现这道题的数据范围非常的迷惑,因为$n$只有$26$而且$a,b,c$只有$9$,所以只要$v$大于$26 \times 9$,我们就不妨钦定$v=26 \times 9$.
这样之后发现混乱度可以直接用一维表示出来,所以我们考虑一下$DP$.直觉$DP$的话可以设$f_{i,j}$表示已经考虑了前$i$种相对性状,此时的混乱度是$j$的时候的方案数.但是这样的话我们会发现一个问题,就是我们可能会把同一种基因型在父本的贡献和在母本的贡献算重,而且也不好去重.
所以我们考虑加一维状态:我们设$f_{i,j,k}$表示已经考虑了前$i$种相对性状,其中父本贡献的混乱度为$j$,母本贡献的混乱度为$k$时的方案数,在转移的时候直接考虑父本的性状已经母本的性状即可.

信息

看上去不好写实际上还挺简单的模拟我不管这道题我一定要放代码(其实是为了凑字数)

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cctype>
#include <ctime>
#include <vector>
#include <cstdlib>
#include <stack>
#define ll long long
#define pii std::pair<int,int>
#define pll std::pair<ll,ll>
#define MP std::make_pair
#define fi first
#define se second
#define oo 2147483647
#define PI 3.141592653590
#define rint register int
#define F(i,a,b) for(rint i=a;i<=b;i++)
#define D(i,a,b) for(rint i=a;i>=b;i--)
#define G(i,num,b,c) for(rint num=head[b];num;num=c[num].next)

inline int _read () {int s = 0 , w = 1;char ch = getchar ();while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}return s * w;}
template < class T > inline void read ( T &x ) {T s = 0 , w = 1;char ch = getchar ();while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}x = s * w;return;}
template < class T , typename ...Argc > inline void read ( T &x , Argc &...Args ) {read ( x );read ( Args... );return;}
template < class T > inline T max ( T x , T y ) {return x > y ? x : y;}
template < class T > inline T min ( T x , T y ) {return x < y ? x : y;}
template < class T > inline void abs ( T x ) {return x > 0 ? x : -x;}
template < typename T > void write ( T x ) {if ( x < 0 ) x = -x , putchar ( '-' );if ( x > 9 ) write ( x / 10 );putchar ( x % 10 + 48 );return;}
template < typename T > void writeln ( T x ) {write ( x ); printf ("\n"); }
template < class T > inline T gcd ( T x , T y ) {if ( x < y ) swap ( x , y );if ( !y ) return x;return gcd ( y , x % y );}
template < class T > inline T ksm ( T x , T y , T Mod ) {T tmp = 1;while ( y ) {if ( y % 2 == 1 ) tmp = ( tmp * x % Mod );x = ( x * x ) % Mod;y >>= 1;}return tmp;}

/**********************************************************************************************************************************************************************************************************************************************************************/

const int N = 1005;

int n , m , sx , sy;
int indeque[N][N];
char mp[N][N] , operation[N];

inline void init () {
read ( n , m );
F ( i , 1 , n )
scanf ( "%s" , mp[i] + 1 );
F ( i , 1 , n )
F ( j , 1 , m )
if ( mp[i][j] == '@' ) {
mp[i][j] = '.';
sx = i , sy = j;
break;
}
scanf ( "%s" , operation + 1 );
return;
}
inline void FindDir ( int &dx , int &dy , char op ) {
if ( op == 'W' )
dx = -1 , dy = 0;
else if ( op == 'A' )
dx = 0 , dy = -1;
else if ( op == 'S' )
dx = 1 , dy = 0;
else if ( op == 'D' )
dx = 0 , dy = 1;
return;
}

struct Node {
int x , y;
}qu[ ( N * N )*6];
int hea = N * N , tail = ( N * N ) - 1;

void Debug () {
F ( i , 1 , n ) {
F ( j , 1 , m )
if ( indeque[i][j] ){
if(indeque[i][j] == hea )
printf("%c",'@');
else
printf("%c",'X');
}
else
printf ( "%c",mp[i][j] );
puts ( "" );
}
puts ( "" );
return;
}

inline void work () {
qu[++tail] = ( Node ) { sx , sy };
indeque[sx][sy] = tail;
int len = strlen ( operation + 1 );
F ( T , 1 , len ) {
char op = operation[T];
int dx , dy;
FindDir ( dx , dy , op );
int nx = qu[hea].x , ny = qu[hea].y;
int tx = qu[tail].x , ty = qu[tail].y;
if ( mp[nx + dx][ny + dy] == '.' && !indeque[nx + dx][ny + dy] ) {
qu[--hea] = ( Node ) { nx + dx , ny + dy };
indeque[nx + dx][ny + dy] = hea;
indeque[tx][ty] = 0;
tail--;
}
else if ( mp[nx + dx][ny + dy] == 'o' ) {
qu[--hea] = ( Node ) { nx + dx , ny + dy };
indeque[nx + dx][ny + dy] = hea;
mp[nx + dx][ny + dy] = '.';
}
else if ( indeque[nx + dx][ny + dy] ) {
int start = indeque[nx + dx][ny + dy];
for ( int i = start ; i <= tail ; i++ ) {
int xx = qu[i].x , yy = qu[i].y;
indeque[xx][yy] = 0;
}
while ( tail >= start )
tail--;
qu[--hea] = ( Node ) { nx + dx , ny + dy };
indeque[nx + dx][ny + dy] = hea;
}
else if ( nx + dx > m || ny + dy > n || nx + dx <= 0 || ny + dy <= 0 || mp[nx + dx][ny + dy] == '#' ) {
puts ( "-1" );
exit ( 0 );
}
//Debug ();
}
return;
}
inline void print () {
F ( i , 1 , n )
F ( j , 1 , m )
if ( mp[i][j] == '#' || mp[i][j] == 'o' )
continue;
else
mp[i][j] = '.';
int xx = qu[hea].x , yy = qu[hea].y;
mp[xx][yy] = '@';
hea++;
while ( hea <= tail ) {
xx = qu[hea].x , yy = qu[hea].y;
mp[xx][yy] = 'X';
hea++;
}
F ( i , 1 , n ) {
F ( j , 1 , m )
printf ( "%c" , mp[i][j] );
puts ( "" );
}
return;
}

int main ( void ) {
init ();
work ();
print ();
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:校内ACM赛题解选讲

文章作者:KRrrrrrrrr

发布时间:2019年10月30日 - 16:10

最后更新:2019年11月05日 - 09:11

原始链接:http://krrrr.xyz/2019/10/30/校内ACM赛题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。