CF 191 div2

A. 데이터량이 적어서 바로 폭발적으로 한다.
 

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstring>

#include <queue>

#include <set>

#include <vector>

#include <stack>

#include <map>

#include <iomanip>

#define PI acos(-1.0)

#define Max 2505

#define inf 1<<28

#define LL(x) ( x << 1 )

#define RR(x) ( x << 1 | 1 )

#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )

#define ll long long

#define mem(a,b) memset(a,b,sizeof(a))

#define mp(a,b) make_pair(a,b)

#define PII pair<int,int>

using namespace std;



int a[111] ;

int num[11111] ;

int main() {



    int n ;

    cin >> n ;

    int ans = 0 ;

    for (int i = 1 ; i <= n ;i ++ ){

        cin >> a[i] ;

        num[i] = num[i - 1] + a[i] ;

    }

    ans = num[n] - 1 ;

     for(int i = 1; i <= n; ++i ){

        for(int j = 1; j <= i; ++ j){

            int sum = num[n] - 2 * ( num[i] - num[j-1] ) + ( i - j + 1  );

            ans = max(sum ,ans) ;

        }

     }

    cout << ans << endl;





    return 0 ;

}

B, 바로 소수표를 치고 앞의 N개의 소수를 출력하면 됩니다.
 
 

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstring>

#include <queue>

#include <set>

#include <vector>

#include <stack>

#include <map>

#include <iomanip>

#define PI acos(-1.0)

#define Max 2505

#define inf 1<<28

#define LL(x) ( x << 1 )

#define RR(x) ( x << 1 | 1 )

#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )

#define ll long long

#define mem(a,b) memset(a,b,sizeof(a))

#define mp(a,b) make_pair(a,b)

#define PII pair<int,int>

using namespace std;



bool flag[11111111] ;

void prime(){

    flag[0] = 1 ;

    flag[1] = 1 ;

    flag[2] = 0 ;

    for (int i = 2 ;i <= 1300000 ; i ++ ){

        if(!flag[i]){

            for (int j = 2 * i ;j <= 1300000 ;j += i){

                flag[j] = 1 ;

            }

        }

    }

}

int a[111] ;

int num[1111111] ;

int main() {

    prime() ;

    int nn = 0 ;

    for (int i = 2 ;i <= 1300000 ;i ++ ){

        if(!flag[i])num[nn ++ ] = i ;

    }

    int n ;

    cin >> n ;

    cout << num[0] ;

    for (int i = 1 ;i < n ;i ++ ){

        printf(" %d",num[i]) ;

    }

    cout << endl;

    return 0 ;

}

C, k개의 연속 문자열은 등비 수열의 관계를 충족시키는 것으로 내놓을 수 있다.
그래서 우리는 a1과 비례q만 내면 된다.
수상은 문자열이 하나일 때 모든 삭제의 총체이다.
q는 Pow(2,l)이고 l은 문자열의 길이입니다.
등비수열구와 공식 (a1 * (q ^ n - 1)/(q - 1)%MOD.먼저 a1을 밖으로 내보내고 계산에 참여하지 않습니다.우리는 q^n-1을 a, q-1을 b로 설정합니다.그러면 식은 a/b%MOD가 됩니다.이것은 매우 익숙한 유클리드를 넓히는 것이 되었다. 먼저 b% MOD의 역원 x를 구한다.x * b% MOD = 1 그러면 (a/b)%MOD * (x * b)% MOD의 값이 변하지 않으면 식을 (a * x)% MOD로 간략화할 수 있습니다.
마지막으로 a1을 곱하면 됩니다.
 

#define MOD 1000000007



char a[111111] ;



inline ll extend_gcd(ll a ,ll b , ll& x , ll& y){

    ll ans , t ;

    if(b == 0){

        x = 1 ;

        y = 0 ;

        return a ;

    }

    ans = extend_gcd(b , a % b ,x ,y ) ;

    t = x ;

    x = y ;

    y = t - (a / b) * y ;

    return ans ;

}





ll quick_pow(ll a ,ll b , ll M){

    ll ret = 1 ;

    ll temp = a ;

    while(b){

        if(b & 1){

            ret = (ret * temp) % M ;

        }

        temp = (temp * temp) % M  ;

        b >>= 1 ;

    }

    return ret ;

}

int main(){

    cin >> a ;

    int k ;

    cin >> k ;

    int l = strlen(a) ;

    ll a1 = 0 ;

    REP(i , 0 ,l - 1 ){

         if(a[i] == '0' || a[i] == '5'){

            a1 = (a1 + quick_pow(2 ,i ,MOD)) % MOD ;

        }

    }

    ll a = quick_pow(2 , l ,MOD) ;

    ll aa = (a - 1 + MOD) % MOD ;

    ll x , y ;

    extend_gcd(aa ,MOD , x ,y) ;

    x = (x + MOD) % MOD ;

    ll c = (quick_pow(a , k  ,MOD) - 1) * x % MOD ;

    ll ans = c * a1 % MOD ;

    cout << ans << endl;

    return 0 ;

}

 
 
D, DFS는 매번 공터에 들어갈 때마다 먼저 그를 파란색으로 만든 다음에 네 방향으로 DFS를 만든다. 마지막에 거슬러 올라갈 때 이 파란색 건물을 뜯어서 빨간색으로 만든다. 물론 첫 번째 진입점은 빨간색으로 만들 수 없다.
이것은 하나의 연결 블록 안에 틀림없이 하나는 파란색이고 다른 것은 모두 빨간색이라는 것을 증명하기 쉽다.

int n , m ;

char op[11111111] ;

int xx[11111111] ;

int yy[11111111] ;

int ss[555][555] ;

char Map[555][555] ;

int num = 0 ;

void dfs(int x ,int y ,int first ) {

    if(x < 1 || x > n || y < 1 || y > m)return ;

    op[num] = 'B' ;

    xx[num] =  x ;

    yy[num] = y ;

    num ++ ;

    ss[x][y] = 0 ;

    if(ss[x - 1][y])dfs(x - 1 ,y , 1) ;

    if(ss[x][y - 1])dfs(x ,y - 1 ,1 ) ;

    if(ss[x + 1][y])dfs(x + 1 ,y , 1) ;

    if(ss[x][y + 1])dfs(x ,y + 1 ,1 ) ;

    if(first) {

        op[num] = 'D' ;

        xx[num] = x ;

        yy[num] = y ;

        num ++ ;

        op[num] = 'R' ;

        xx[num] = x ;

        yy[num] = y ;

        num ++ ;

    }

}

int main() {

    cin >> n >> m ;

    for (int i = 1 ; i <= n ; i ++ ) {

        for (int j = 1 ; j <= m ; j ++ ) {

            cin >> Map[i][j] ;

            if(Map[i][j] == '.') {

                ss[i][j] = 1 ;

            }

        }

    }

    for (int i = 1 ; i <= n ; i ++ ) {

        for (int j = 1 ; j <= m ; j ++ ) {

            if(ss[i][j]) {

                dfs(i ,j , 0 ) ;

            }

        }

    }

    cout << num << endl;

    for (int i = 0 ; i < num ; i ++ ) {

        cout << op[i] << " " << xx[i] << " " << yy[i] << endl;

    }

    return 0 ;

}

E.상태 압축 DP.
 
매거 1<<24의 상태.
 

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <string>

#include <cmath>

#include <cstring>

#include <queue>

#include <set>

#include <vector>

#include <stack>

#include <map>

#include <iomanip>

#define PI acos(-1.0)

#define Max 2505

#define inf 1<<28

#define LL(x) ( x << 1 )

#define RR(x) ( x << 1 | 1 )

#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )

#define ll long long

#define mem(a,b) memset(a,b,sizeof(a))

#define mp(a,b) make_pair(a,b)

#define PII pair<int,int>

using namespace std;



#define MOD 1000000007



inline void RD(int &ret) {

    char c;

    do {

        c = getchar();

    } while(c < '0' || c > '9') ;

    ret = c - '0';

    while((c=getchar()) >= '0' && c <= '9')

        ret = ret * 10 + ( c - '0' );

}



int a[111111] ;

int sum[1 << 24] ;

int dp[1 << 24] ;

int k[11] ;



int main(){



    int n ;

    cin >> n  ;

    for (int i = 0 ;i < n ; i ++ ){

        RD(a[i]) ;

    }



    int m ;

    cin >> m ;

    for (int i = 0 ;i < m ;i ++ ){

        RD(k[i]) ;

    }

    dp[0] = 1 ;

    for (int i = 1 ;i < (1 << n) ; ++ i){//      

        int pos ;

        bool flag = 0 ;

        sum[i] = 0 ;

        for (int j = 0 ;j < n ;j ++ ){

            if(i & (1 << j)){//i   j    1 ，       sum[i]   T。O(2 ^ 24 *  n）

                pos = j ;//       sum[i] += a[j] ; T 

                break ;

            }

        }

        sum[i] = sum[i ^ (1 << pos)] + a[pos] ;//i        。

        for (int j = 0 ; j < m ;j ++ ){//i          。

            if(sum[i] == k[j]){

                dp[i] = 0 ;

                flag = 1 ;

                break ;

            }

        }

        if(flag)continue ;

        dp[i] = 0 ;

        for (int j = 0 ;j < n ;j ++ ){

            if(i & (1 << j)){//i      i ^ (1 << j )      。

                dp[i] = (dp[i] + dp[i ^ (1 << j)]) ;

                if(dp[i] >= MOD)dp[i] -= MOD ;

            }

        }

    }



    cout << dp[(1 << n) - 1] << endl;

    return 0 ;

}