ABC179

既然是ABC就只看DEF了….

D.- Leaping Tak

我们用推的方法可以发现我们对于每个位置$i$,可以枚举每个$i$能到的位置然后$dp$转移.
然后发现对于每次转移,等价与将$k$段连续区间的$dp$值加一个相同的数.然后我们最后要的就是$dp_n$.
对于这种区间修改单点求值的问题我们显然可以用树状数组来维护.

#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$的数字的重复.

#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$级别,所以直接模拟显然不太核里…

发现每一次操作都最多只会删掉一行最靠左上的部分.我们设现在的最左上方的长宽分别为$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$操作能减少的黑色棋子个数即可.

#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;
}

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想