cCodeforces Round #286 (Div. 2)

A题。。暴力枚举在每个位置添加字符，然后检查一下是不是回文串

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

#define LL long long
#define eps 1e-8
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
#define mnx 31000

char s[20], ch[20];
bool check(){
    int n = strlen( ch );
    for( int i = 0, j = n-1; i <= j; ++i, --j ){
        if( ch[i] != ch[j] ) return false;
    }
    return true;
}
int main(){
    scanf( "%s", &s );
    int n = strlen( s );
    for( int i = 0; i <= n; ++i ){
        for( int j = 'a'; j <= 'z'; ++j ){
            for( int k = 0, m = 0; k <= n; ++k ){
                if( i == k )
                    ch[k] = (char)j;
                else
                    ch[k] = s[m++];
            }
            ch[n+1] = '\0';
            if( check() ){
                printf( "%s\n", ch );
                return 0;
            }
        }
    }
    puts( "NA" );
    return 0;
}

B题。。也是暴力枚举每种颜色，dfs算一下就好

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

#define LL long long
#define eps 1e-8
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
#define mnx 500

int fst[mnx], nxt[mnx], vv[mnx], col[mnx], e, ans;
void add( int u, int v, int c ){
    vv[e] = v, col[e] = c, nxt[e] = fst[u], fst[u] = e++;
}
bool vis[mnx], ok;
void dfs( int u, int gg, int vol ){
    if( u == gg ){
        ans++; ok = 1; return ;
    }
    if( vis[u] ) return ;
    vis[u] = 1;
    for( int i = fst[u]; i != -1; i = nxt[i] ){
        if( ok ) return ;
        int v = vv[i], c = col[i];
        if( c != vol ) continue;
        dfs( v, gg, vol );
    }
}
int main(){
    int n, m, q;
    scanf( "%d %d", &n, &m );
    memset( fst, -1, sizeof( fst ) );
    for( int i = 0; i < m; ++i ){
        int u, v, c;
        scanf( "%d %d %d", &u, &v, &c );
        add( u, v, c );
        add( v, u, c );
    }
    scanf( "%d", &q );
    while( q-- ){
        int u, v;
        scanf( "%d%d", &u, &v );
        ans = 0;
        for( int i = 1; i <= m; ++i ){
            memset( vis, 0, sizeof( vis ) );
            ok = 0;
            dfs( u, v, i );
        }
        cout << ans << endl;
    }
    return 0;
}

C题。。比赛的时候想不出来，看了题解才知道 第二维的状态最多不超过500。。因为你1+2+...+250 > 3w，这样每次步数减一或者加一的总的状态不会超过500，所以dp[30000][600]就够了， 把第二维300当做第一次的步数d，然后每次有可能走 d+j-n - 1, d+j-n, d+j-n+1步，感觉看代码容易理解一些。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

#define LL long long
#define eps 1e-8
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
#define mnx 31000

const int N = 300;
int dp[mnx][700], val[mnx];
int main(){
    int n, m;
    while( scanf( "%d%d", &n, &m ) != EOF ){
        memset( val, 0, sizeof val );
        memset( dp, 0, sizeof dp );
        for( int i = 0; i < n; ++i ){
            int x;
            scanf( "%d", &x );
            val[x]++;
        }
        dp[m][N] = val[m] + val[0] + 1;
        int ans = 0;
        for( int i = m; i < mnx; ++i ){
            for( int j = 0; j < 600; ++j ){
                if( !dp[i][j] ) continue;
                int l = m + j - N;
                ans = max( dp[i][j] - 1, ans );
                if( i + l >= mnx ) continue;
                if( l > 0 )
                    dp[i+l][j] = max( dp[i+l][j], dp[i][j] + val[i+l] );
                if( l > 1 )
                    dp[i+l-1][j-1] = max( dp[i+l-1][j-1], dp[i][j] + val[i+l-1] );
                if( l >= 0 )
                    dp[i+l+1][j+1] = max( dp[i+l+1][j+1], dp[i][j] + val[i+l+1] );
            }
        }
        cout << ans << endl;
    }
    return 0;
}

D题。。好像是B的加强版，用并查集搞。。明天再看看