[Offer收割]程式設計練習賽8

1473 : 小Ho的強迫症

題解

在mod L的情況下每次加D，最終相鄰點的距離一定為__gcd(L,D)，然後隻需要判斷是否大于腳長F即可

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int main(){
    int T;
    cin >> T;
    while( T-- ){
        int a, b, c;
        cin >> a >> b >> c;
        int x = __gcd( a, c );
        if( x >= b ){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
    return ;
}
           

1474 : 拆字遊戲

#include <iostream>
#include <stdio.h>
using namespace std;

#pragma comment(linker, "/STACK:1024000000,1024000000")

char map[][];
int n,m,top,bottom,Left,Right;
int value[][] = {{,},{,},{-,},{,-}};

void DFS(int y,int x){
    map[y][x] = -;
    if(y<top) top = y;
    if(y>bottom) bottom = y;
    if(x>Right) Right = x;
    if(x<Left) Left = x;
    for(int i=;i<;i++){
        int xx = x + value[i][];
        int yy = y + value[i][];
        if(xx>= && xx<m && yy>= && yy<n && map[yy][xx]=='1') DFS(yy,xx);
    }
}

int main(){
    int i,j,k,l;
    while(cin>>n>>m){
        for(i=;i<n;i++) cin>>map[i];
        for(i=;i<m;i++){
            for(j=;j<n;j++){
                if(map[j][i] == '1'){
                    top = j;
                    bottom = j;
                    Left = i;
                    Right = i;
                    DFS(j,i);
                    printf("%d %d\n",bottom-top+,Right-Left+);
                    for(k=top;k<=bottom;k++){
                        for(l=Left;l<=Right;l++){
                            if(map[k][l] == -){
                                printf("1");
                                map[k][l] = '0';
                            }
                            else printf("0");
                        }
                        printf("\n");
                    }
                }
            }
        }
    }
    return ;
}
           

1475 : 數組分拆

題解

dp[i]表示到i的所有可能

那麼dp【i】 = sum（dp【k】）其中：（1<= k <= i - 1 && num【k+1】 +…+num【i】 !=0）

= sum( dp【1】+ … + dp【i-1】) - sum( dp【x】 ) 其中：( num【x+1】 +…+num【i】 ==0 )

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;

int N;
const int MOD =  + ;
int dp[];
int sum[];

int main(){
    while( scanf( "%d", &N ) != EOF ){
        sum[] = ;
        for( int i = ; i <= N; i++ ){
            scanf( "%d", &sum[i] );
            sum[i] += sum[i-];
        }
        map<int,int> mp;
        mp.clear();
        mp[] = ;
        int cnt = ;
        for( int i = ; i <= N; i++ ){
            dp[i] = ( cnt - mp[sum[i]] + MOD ) % MOD;
            cnt = ( cnt + dp[i] ) % MOD;
            mp[sum[i]] = ( mp[sum[i]] + dp[i] ) % MOD;
        }
        printf( "%d\n", dp[N] );
    }
    return ;
}