[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 0;
}

1474 : 拆字游戏

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

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

char map[505][505];
int n,m,top,bottom,Left,Right;
int value[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};

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

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

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 = 1e9 + 7;
int dp[110000];
int sum[110000];

int main(){
while( scanf( "%d", &N ) != EOF ){
        sum[0] = 0;
for( int i = 1; i <= N; i++ ){
scanf( "%d", &sum[i] );
            sum[i] += sum[i-1];
        }
map<int,int> mp;
        mp.clear();
        mp[0] = 1;
int cnt = 1;
for( int i = 1; 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 0;
}