D. Dima and Hares

problem

输入n (1 ≤ n ≤ 3000) a1 a2 ... an.
  b1, b2, ..., bn.
  c1, c2, ..., cn. 

n只兔子，每只兔子喂一遍，abc分别是旁边两只都饿着一直饿着一直饱着两只都饱着的joy值，按照某种顺序喂，求最大joy和。

think

两边的情况太模糊。。我纠结了很久。。

dp[i][0]表示喂完前i-1只第i只在第i-1只之后喂

dp[i][1]表示喂完前i-1只第i只在第i-1只之前喂

答案就是dp[n+1][0]

code  

int a[N], b[N], c[N], dp[N][2];

int main ()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    for(int i = 1; i <= n; ++i) scanf("%d", &c[i]);
    dp[1][0] = -100000;
    for(int i = 1; i <= n; ++i){
        dp[i+1][0] = max(dp[i][0] + b[i], dp[i][1] + a[i]);
        dp[i+1][1] = max(dp[i][0] + c[i], dp[i][1] + b[i]);
    }
    cout<<dp[n+1][0]<<endl;
    return 0;
}

E. Dima and Kicks

problem

输入n m 和一个n*m的01矩阵，问是否存在“一笔画”，并且中间每笔的长度一样并且大于1

think

先判断是否有

11

11这样的，因为这样不能大于1

还有判断是否联通，还有基数点的个数最多2

code

int a[1111][1111];
int vis[1111][1111];
int ans[1111];
int dx[] = {0, 0, 1, -1};
int dy[] = {-1, 1, 0, 0};
int n, m, amount;

int gcd(int x, int y){
    return (x==0 ? y : gcd(y % x, x));
}

int cal(int x, int y){
    int ans = 0;
    if(x > 1 && a[x-1][y]) ++ans;
    if(x < n && a[x+1][y]) ++ans;
    if(y > 1 && a[x][y-1]) ++ans;
    if(y < m && a[x][y+1]) ++ans;
    return ans;
}

bool sq(){
    for(int i = 1; i < n; ++i)
        for(int j = 1; j < m; ++j){
            if(a[i][j]==1 && a[i+1][j]==1 && a[i][j+1]==1 && a[i+1][j+1]==1) return true;
        }
    return false;
}

int dfs(int i,int j){
    if(i<1 || i>n || j<1 || j>m) return 0;
    if(!a[i][j] || vis[i][j]) return 0;
    vis[i][j]=true;
    return  dfs(i+1,j) + dfs(i-1,j) + dfs(i,j+1) + dfs(i,j-1) + 1;
}

bool ou(){
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(a[i][j]==1){
                if(dfs(i, j)==amount) return true;
                else return false;
            }
        }
    }
}

int solve(){
    memset(vis, 0, sizeof(vis));
    memset(ans, 0, sizeof(ans));
    int odd = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(a[i][j]){
                int num = cal(i, j);
                odd += (num&1);
                if(odd >= 3) return 0;
                if(num == 2 && ((a[i+1][j]==1 && a[i-1][j]==1) || (a[i][j+1]==1 && a[i][j-1]==1))) continue;
                vis[i][j] = 1;
            }
        }
    }
    int gg = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; ++j) if(vis[i][j]){
            for(int d = 0, k; d < 4; ++d){
                for(k = 1; a[i+dx[d]*k][j+dy[d]*k] && !vis[i+dx[d]*k][j+dy[d]*k]; ++k);
                if(k > 1){
                    ans[k] = 1;
                    gg = k;
                }
            }
        }
    }

    for(int k = max(n, m); k > 1; --k)
    if(ans[k]) gg = gcd(gg, k);
    return gg;
}

int main(){
    amount = 0;
    scanf("%d%d", &n, &m);
    memset(a, 0, sizeof(a));
    for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; amount += a[i][j], ++j) scanf("%d", &a[i][j]);
    if(sq() || !ou()){
        puts("-1");
        return 0;
    }
    int res = solve();
    if(res < 2) puts("-1");
    else{
        for(int i = 2; i < res; ++i){
            if(res % i == 0) printf("%d ", i);
        }
        printf("%d\n", res);
    }
    return 0;
}