HDU 4632 Palindrome subsequence
dp[x][y]表示区间[x,y]构成回文串的方案数。
若str[x]==str[y]，dp[x][y]=dp[x+1][y]+dp[x][y-1]-dp[x+1][y-1]+(dp[x+1][y-1]+1)=dp[x+1][y]+dp[x][y-1]+1。
若str[x]!=str[y]，dp[x][y]=dp[x+1][y]+dp[x][y-1]-dp[x+1][y-1]。
#include<cstdio>
#include<cstring>
#define MAXN 1010
#define MOD 10007
char str[MAXN];
int dp[MAXN][MAXN];
int dfs(int x, int y) {
if (dp[x][y] == -) {
if (str[x] != str[y]) {
dp[x][y] = dfs(x + , y) + dfs(x, y - ) - dfs(x + , y - );
} else {
dp[x][y] = dfs(x + , y) + dfs(x, y - ) + ;
}
}
dp[x][y] %= MOD;
return dp[x][y];
}
int main() {
int T;
int ca = ;
int len;
int i;
scanf("%d", &T);
while (T--) {
memset(dp, -, sizeof(dp));
scanf(" %s", str);
len = strlen(str);
for (i = ; i < len; i++) {
dp[i][i] = ;
}
for (i = ; i < len; i++) {
if (str[i] == str[i - ]) {
dp[i - ][i] = ;
} else {
dp[i - ][i] = ;
}
}
printf("Case %d: %d\n", ca++, (dfs(, len - ) + MOD) % MOD);
}
return ;
}
HDU 4633 Who's Aunt Zhang
由Polya得到：
本身到本身的置换有1种，k8+12+54。
沿着一个面的中心旋转90度有3种，k(1+1+3)*(1+1+3)+1+9。
沿着一个面的中心旋转270度有3种，k(1+1+3)*(1+1+3)+1+9。
沿着一个面的中心旋转180度有3种，k(2+2+5)*(2+2+5)+2+18。
沿着正方体的两个对顶点旋转120度有4种，k2+2+9+9+2+2。
沿着正方体的两个对顶点旋转240度有4种，k2+2+9+9+2+2。
沿着正方体的中心，与正方体任意两条对边的中点旋转180度有6种，k4+8+18+8。
#include<cstdio>
#define MOD 10007
int powmod(int a, int b) {
int ans;
for (ans = ; b; b >>= ) {
if (b & ) {
ans *= a;
ans %= MOD;
}
a *= a;
a %= MOD;
}
return ans;
}
int ext_gcd(int a, int b, int &x, int &y) {
int t, d;
if (b == ) {
x = ;
y = ;
return a;
}
d = ext_gcd(b, a % b, x, y);
t = x;
x = y;
y = t - a / b * y;
return d;
} int Invmod(int a, int n) {
int x, y;
if (ext_gcd(a, n, x, y) != )
return -;
return (x % n + n) % n;
}
int main() {
int T;
int ca = ;
int n;
int ans;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
ans = powmod(n, + + );
ans += * powmod(n, );
ans += * powmod(n, );
ans += * powmod(n, );
ans += * powmod(n, );
printf("Case %d: %d\n", ca++, ans % MOD * Invmod(, MOD) % MOD);
}
return ;
}
HDU 4638 Group
询问区间最少可以组成多少段，连续的数可以组成一段。
若x+1与x-1已经出现了，则加入x使得段数-1。
若x+1与x-1都没有出现，则加入x使得段数+1。
其他情况段数不变。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 100010
using namespace std;
int n, m;
bool vis[MAXN];
int arr[MAXN];
int tree[MAXN];
int res[MAXN];
int pos[MAXN];
struct Ask {
int x, y;
int idx;
friend bool operator<(Ask a, Ask b) {
return a.x < b.x;
}
} ask[MAXN];
inline int lowbit(int x) {
return x & -x;
}
void update(int x, int val) {
for (; x < MAXN; x += lowbit(x)) {
tree[x] += val;
}
}
int sum(int x) {
int ans;
for (ans = ; x > ; x -= lowbit(x)) {
ans += tree[x];
}
return ans;
}
int main() {
int T;
int i, j;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (i = ; i <= n; i++) {
scanf("%d", &arr[i]);
pos[arr[i]] = i;
}
for (i = ; i < m; i++) {
scanf("%d%d", &ask[i].x, &ask[i].y);
ask[i].idx = i;
}
sort(ask, ask + m);
memset(tree, , sizeof(tree));
memset(vis, false, sizeof(vis));
for (i = ; i <= n; i++) {
vis[arr[i]] = true;
if (vis[arr[i] - ] && vis[arr[i] + ]) {
update(i, -);
}
if (!vis[arr[i] - ] && !vis[arr[i] + ]) {
update(i, );
}
}
for (i = , j = ; i < m; i++) {
for (; j < ask[i].x; j++) {
if (vis[arr[j] + ]) {
update(pos[arr[j] + ], );
}
if (vis[arr[j] - ]) {
update(pos[arr[j] - ], );
}
vis[arr[j]] = false;
}
res[ask[i].idx] = sum(ask[i].y) - sum(ask[i].x - );
}
for (i = ; i < m; i++) {
printf("%d\n", res[i]);
}
}
return ;
}
HDU 4639 Hehe
dp[i]表示以i结尾的方案数。
dp[i]=dp[i-1]。
若替换“hehe”，dp[i]+=dp[i-4]。
#include<cstdio>
#include<cstring>
#define MAXN 100010
#define MOD 10007
int dp[MAXN];
char str[MAXN];
int main() {
int T;
int ca = ;
int len;
int i;
scanf("%d", &T);
while (T--) {
scanf(" %s", str + );
len = strlen(str + );
dp[] = ;
for (i = ; i <= len; i++) {
dp[i] = dp[i - ];
if (i > && str[i - ] == 'h' && str[i - ] == 'e'
&& str[i - ] == 'h' && str[i] == 'e') {
dp[i] += dp[i - ];
}
dp[i] %= MOD;
}
printf("Case %d: %d\n", ca++, dp[len]);
}
return ;
}
dp[i][j]表示访问了的地点压缩成i，最后访问的是j，它的最小花费。
f[i][j]表示i个人，共同访问的地点压缩成j，它的最小花费。
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define MAXN 17
#define MAXM 3
#define oo 987654321
using namespace std;
int g[MAXN + ][MAXN + ];
int dis[MAXN + ][MAXN + ];
int dp[ << MAXN][MAXN];
int f[MAXM + ][ << MAXN];
vector<int> island;
void floyd(int n) {
for (int k = ; k < n; k++) {
for (int i = ; i < n; i++) {
for (int j = ; j < n; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
}
bool getHelp() {
for (int i = ; i < (int) island.size(); i++) {
if (dis[][island[i]] >= oo) {
return false;
}
}
return true;
}
queue<pair<int, int> > q;
int main() {
int T;
int ca = ;
int n, m, p;
int x, y, val;
int i, j, k;
int vis;
int ans;
pair<int, int> head, tmp;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof(g));
memset(dis, 0x3f, sizeof(dis));
for (i = ; i < m; i++) {
scanf("%d%d%d", &x, &y, &val);
x--;
y--;
g[x][y] = min(g[x][y], val);
dis[x][y] = dis[y][x] = g[y][x] = g[x][y];
}
island.clear();
scanf("%d", &p);
for (i = ; i < p; i++) {
scanf("%d", &x);
x--;
island.push_back(x);
}
floyd(n);
if (getHelp()) {
memset(dp, 0x3f, sizeof(dp));
dp[][] = ;
q.push(make_pair(, ));
while (!q.empty()) {
head = q.front();
q.pop();
for (i = ; i < n; i++) {
tmp.first = head.first | ( << i);
tmp.second = i;
if (dp[tmp.first][tmp.second]
> dp[head.first][head.second]
+ g[head.second][tmp.second]) {
dp[tmp.first][tmp.second] = dp[head.first][head.second]
+ g[head.second][tmp.second];
q.push(tmp);
}
}
}
memset(f, 0x3f, sizeof(f));
f[][] = ;
for (i = ; i < ( << n); i += ) {
for (j = ; j < n; j++) {
f[][i] = min(f[][i], dp[i][j]);
}
}
for (i = ; i <= MAXM; i++) {
for (j = ; j < ( << n); j += ) {
for (k = j; k >= ; k = k ? (k - ) & j : -) {
f[i][j] = min(f[i][j],
max(f[i - ][k | ], f[][(j ^ k) | ]));
}
}
}
vis = ;
for (i = ; i < (int) island.size(); i++) {
vis |= << island[i];
}
ans = oo;
for (i = ; i < ( << n); i++) {
if ((i & vis) == vis) {
ans = min(ans, f[][i]);
}
}
} else {
ans = -;
}
printf("Case %d: %d\n", ca++, ans);
}
return ;
}
HDU 4642 Fliping game
若右下角的数为1，则Alice必胜。Alice先把右下角变为0，无论Bob如何操作右下角的数都会变为1。
若右下角的数为0，则Alice必败。Alice会把右下角的数变为1。
#include<cstdio>
int main() {
int T;
int n, m;
int i, j, k;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (i = ; i < n; i++) {
for (j = ; j < m; j++) {
scanf("%d", &k);
}
}
if (k) {
puts("Alice");
} else {
puts("Bob");
}
}
return ;
}