既然是ABC就只看DEF了….
D.- Leaping Tak
我们用推的方法可以发现我们对于每个位置$i$,可以枚举每个$i$能到的位置然后$dp$转移.
然后发现对于每次转移,等价与将$k$段连续区间的$dp$值加一个相同的数.然后我们最后要的就是$dp_n$.
对于这种区间修改单点求值的问题我们显然可以用树状数组来维护.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
using namespace std;
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;
}
const int N = 2e5 + 10;
const int HA = 998244353;
int n , k;
long long tree[N];
struct Seq {
int ll , rr;
} se[15];
inline int lowbit ( int x ) {
return x & -x;
}
inline void add ( int pos , int v ) {
while ( pos <= n ) {
tree[pos] = ( tree[pos] + v + HA ) % HA;
pos += lowbit ( pos );
}
return;
}
inline long long query ( int pos ) {
long long tmp = 0;
while ( pos ) {
tmp = ( tmp + tree[pos] + HA ) % HA;
pos -= lowbit ( pos );
}
return tmp % HA;
}
int main ( void ) {
n = read () , k = read ();
for ( int i = 1 ; i <= k ; i++ ) {
se[i].ll = read ();
se[i].rr = read ();
}
tree[1] = 1;
for ( int i = 1 ; i <= n ; i++ ) {
for ( int j = 1 ; j <= k ; j++ ) {
int l = i + se[j].ll , r = i + se[j].rr;
add ( l , query ( i ) );
add ( r + 1 , -query ( i ) );
}
}
// for ( int i = 1 ; i <= n ; i++ )
// printf ( "%d " , tree[i] );
printf ( "%lld\n" , query ( n ) % HA );
return 0;
}
E.Sequence Sum
我们发现$n$的值很大,所以不能直接去算.但是我们发现$M$的值只有$1e5$的级别.所以我们由抽屉原理可知,我们至多只需要枚举$m+1$个数字,就一定可以找到一个和之前重复的数字,而假设我们现在枚举到的重复的位置为$j$,这个数字之前出现过的位置为$i$,那么剩余的数字一定都是位置$i$到位置$j$的数字的重复.
1 |
|
F. Simplified Reversi
发现$n$和$q$都是$2 \times 10^5$级别,所以直接模拟显然不太核里…
发现每一次操作都最多只会删掉一行最靠左上的部分.我们设现在的最左上方的长宽分别为$c$和$k$.
刚开始的时候$c=k=n-2$,我们进行任何一次操作之后黑色棋子的个数都会减掉$n-2$.假设我们进行了$1$操作在坐标为$(1,xx)$的位置,那么我们在(1,xx)以后的位置再进行一次一操作的话,黑色棋子的个数都一定会只减少$n-2$.
所以我们对于列的情况,对于刚开始的$n-2$列,我们把这$n-2$列的值都设为$n-2$,表示对这$n-2$列操作时,都会将黑色棋子的个数减少$$n-2$.然后在进行某一次$2$操作时,假设进行的$2$操作是第$yy$行,那么我们发现,从第$yy$行往下的所有白棋子都不会再被$1$操作所染白. 而从左到第一个$1$操作的所有列上再进行$1$操作都会只染白$[2,yy)$这个区间的棋子
那么解法就很显然了:我们对于行和列,分别去维护$1$和$2$操作能减少的黑色棋子个数即可.
1 |
|
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想