标签：AtCoder ch Beginner fa int sum 288 read dp

A - Many A+B Problems

签到

#include <bits/stdc++.h>
using namespace std;

#define int long long

int32_t main() {
    int n ;
    cin >> n;
    for( int a , b ; n ; n -- ){
        cin >> a >> b;
        cout << a + b << "\n";
    }
    return 0;
}

B - Qualification Contest

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n , k; cin >> n >> k;
    vector<string> s(k);
    for( auto & i : s ) cin >> i;
    sort( s.begin() , s.end() );
    for( auto i : s ) cout << i << "\n";
    return 0;
}

C - Don’t be cycle

要想不成环，就用并查集维护一下连通性，如果边连接的两点已经联通就删除掉

#include <bits/stdc++.h>

using namespace std;

vector<int> fa;

int read(){
    int x = 0 , f = 1 , ch = getchar();
    while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
    if( ch == '-' ) f = -1 , ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x * f;
}

int getfa( int x ){
    if( fa[x] < 0 ) return x;
    return fa[x] = getfa(fa[x]);
}

void merge( int x , int y ){
    x = getfa(x) , y = getfa(y);
    if( x == y ) return;
    if( fa[x] > fa[y] ) swap( x , y );
    fa[x] += fa[y] , fa[y] = x;
}

bool check( int x , int y ){
    x = getfa(x) , y = getfa(y);
    return x == y;
}

int32_t main() {
    int n = read() , m = read() , cnt = 0;
    fa = vector<int>( n+1 , -1 ) , fa[0] = 0;
    for( int u , v ; m ; m -- ){
        u = read() , v = read();
        if( check( u , v ) ) cnt ++;
        else merge( u , v );
    }
    cout << cnt << "\n";
    return 0;
}

D - Range Add Query(补题)

假设\(n=6,k=3,a=\{x,0,0,0,0,0\}\)

第一次操作\(\{0,-x,-x,0,0,0\}\)

第二次操作\(\{0,0,0,x,0,0\}\)

因此可以总结出，每一个数都会加到后面的第k个数上，并且如果是good sequence，操作到最后的k个数一定相同。所以就是维护k个前缀和就好，赛时k个前缀和写的太复杂了，赛后发现Jiangly的写法很简单。

#include <bits/stdc++.h>

using namespace std;

int read(){
    int x = 0 , f = 1 , ch = getchar();
    while( (ch < '0' || ch > '9') && ch != '-' ) ch = getchar();
    if( ch == '-' ) f = -1 , ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x * f;
}

int32_t main(){
    int n = read() , k = read();
    vector<int> b(n+1);
    for( int i = 1 ; i <= n ; i ++ ){
        b[i] = read();
        if( i > k ) b[i] += b[i-k];
    }
    for( int l , r , q = read() ; q ; q -- ){
        l = read() , r = read();
        vector<int> c(k , 0 );
        for( int i = r ; i >= r - k + 1 ; i -- ) c[i%k] += b[i];
        for( int i = l-1 ; i >= max( l-k , 0 ) ; i -- ) c[i%k] -= b[i];
        if( c == vector<int>( k , c[0] ) ) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

F - Integer Division（补题）

用\(S[l,r]\)表示字符串中\([l,r]\)构成的十进制数，\(dp_i\)表示前i位分出来的和，我们只需要枚举最后一次是在那里分割的就好

所以\(dp_i=\sum_{j=0}^{i-1}dp_j\times S[j+1,i]\)

然后可以优化转移方程

\[dp_i =\sum_{j=0}^{i-1} dp_j\times S[j+1,i]\\ =\sum_{j=0}^{i-1} dp_j(10S[j+1,j-1] + S[i] )\\ = 10 dp_{i-1} + S[i] \times \sum_{j=0}^{i-1} dp_j \]

这样就可以实现\(O(1)\)的转移

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int mod = 998244353 , N = 2e5+5;

int dp[N] , sum = 0 , n;
string s;

int32_t main(){
    cin >> n >> s;
    dp[0] = 0 , sum = 1;
    for( int i = 1 ; i <= n ; i ++ )
        dp[i] = ( 10 * dp[i-1] + (s[i-1]-'0') * sum ) % mod , sum = ( sum + dp[i] ) % mod;
    cout << dp[n];
    return 0;
}

标签：AtCoder,ch,Beginner,fa,int,sum,288,read,dp
From： https://www.cnblogs.com/PHarr/p/17095818.html