Fork me on GitHub

ABC179

既然是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
#include <bits/stdc++.h>

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
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
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const ll MX = 1e6;

ll n, x, m;
bool inCycle;
int endi, starti, cstart;
ll sum, cycle[MX];
set<ll> found;

int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> x >> m;
cycle[0] = x;
found.insert(x);
rep(i, 1, MX) {
ll nxt = cycle[i - 1] * cycle[i - 1] % m;
if (found.find(nxt) != found.end()) {
cstart = nxt;
endi = i - 1;
break;
} else {
cycle[i] = nxt;
found.insert(nxt);
}
}
rep(i, 0, endi + 1) {
if (cycle[i] == cstart) {
starti = i;
break;
} else if (n) {
sum += cycle[i];
--n;
}
}
int cycleLen = endi - starti + 1;
rep(i, 0, cycleLen)
sum += max(0ll, (ll)ceil((n - i) / (long double)cycleLen) * cycle[i + starti]);

cout << sum;
}

F. Simplified Reversi

发现$n$和$q$都是$2 \times 10^5$级别,所以直接模拟显然不太核里…

1601267501205

发现每一次操作都最多只会删掉一行最靠左上的部分.我们设现在的最左上方的长宽分别为$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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,x,y,q,op,k;
int r[N],c[N];
int main ( void ) {
cin>>n>>q;
x=y=n;
ll ans=(n-2LL)*(n-2LL);
while ( q-- ) {
cin>>op>>k;
if(op==1) {
if (k < y) {
ans -= x - 2;
while (y > k)
c[y--] = x - 2;
}
else
ans -= c[k];
}
else{
if (k < x) {
ans -= y - 2;
while (x > k)
r[x--] = y - 2;
}
else
ans -= r[k];
}
}
cout<<ans<<endl;
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:ABC179

文章作者:兮水XiShui丶

发布时间:2020年10月08日 - 12:10

最后更新:2020年10月09日 - 18:10

原始链接:http://krrrr.top/2020/10/08/ARC179/

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