HDU 4655 Cut Pieces
假设n个数构成的总数都分成了n段，总数是n*a1*a2*...*an。但是答案显然不会那么多。
对于相邻的两个ai,ai+1，如果选择相同的颜色，那么就减少了a1*a2*...*ai-1*min(ai,ai+1)*ai+2*ai+3*...*an。
不妨假设n=3，三个数分别是a，b，c。且a<b<c。
对于所有的排列，只有a,c,b是最优的，结果是3*a*b*c-a*b-b。
当n>3的时候同样可以得到结论：a1,an,a2,an-1...使得总的段数最多。
#include<cstdio>
#include<algorithm>
#include<iostream>
typedef long long LL;
#define MOD 1000000007
#define MAXN 1000010
using namespace std;
int arr[MAXN];
int tmp[MAXN];
LL ext_gcd(LL a, LL b, LL &x, LL &y) {
LL 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;
}
LL invmod(LL a, LL n = MOD) {
LL x, y;
if (ext_gcd(a, n, x, y) != )
return -;
return (x % n + n) % n;
}
int main() {
int T;
int n;
int i;
LL ans;
LL res;
LL mul;
int l, r;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
ans = n;
mul = ;
for (i = ; i < n; i++) {
scanf("%d", &arr[i]);
mul *= arr[i];
mul %= MOD;
}
ans *= mul;
ans %= MOD;
sort(arr, arr + n);
for (l = , r = n - , i = ; l <= r; l++, r--) {
if (l == r) {
tmp[i++] = arr[l];
} else {
tmp[i++] = arr[l];
tmp[i++] = arr[r];
}
}
for (i = ; i <= n; i++) {
res = mul * invmod(tmp[i] * (LL) tmp[i - ]);
res %= MOD;
res *= min(tmp[i], tmp[i - ]);
ans -= res % MOD;
ans = (ans % MOD + MOD) % MOD;
}
cout << ans << endl;
}
return ;
}
HDU 4661 Message Passing
由于消息传递的次数要求最少，则一个节点将收集所有它的子树的消息之后，再往父节点传递。
因此，有一个节点将收到所有消息。而发送消息是收集消息的逆过程，总的答案=收集消息的方案数*发送消息的方案数=收集消息的方案数2。
dp[i]表示以i为根的子树，收集到它子孙所有消息的方案数。
size[i]表示以i为根的子树的节点总数。
f[i]表示以i为根的树，收集到它子孙所有消息的方案数。
fac[i]表示i的阶乘。
dp[i]=fac[size[i]-1]。
dp[i]/=fac[size[j]]，（j是i的儿子）。
dp[i]*=dp[j]，（j是i的儿子）。
#pragma comment(linker,"/STACK:102400000,102400000")
#include<cstdio>
#include<cstring>
typedef long long LL;
#define MAXN 1000010
#define MAXM 2000010
#define MOD 1000000007
int n;
LL fac[MAXN];
LL invfac[MAXN];
int first[MAXN], next[MAXM], v[MAXM], e;
bool vis[MAXN];
LL dp[MAXN];
LL f[MAXN];
int size[MAXN];
LL ext_gcd(LL a, LL b, LL &x, LL &y) {
LL 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;
}
LL invmod(LL a, LL n = MOD) {
LL x, y;
if (ext_gcd(a, n, x, y) != )
return -;
return (x % n + n) % n;
}
void init() {
int i;
fac[] = ;
for (i = ; i < MAXN; i++) {
fac[i] = fac[i - ] * i;
fac[i] %= MOD;
}
for (i = ; i < MAXN; i++) {
invfac[i] = invmod(fac[i]);
}
}
inline void addEdge(int x, int y) {
v[e] = y;
next[e] = first[x];
first[x] = e++;
}
void getSize(int x) {
vis[x] = true;
size[x] = ;
for (int i = first[x]; i != -; i = next[i]) {
int y = v[i];
if (!vis[y]) {
getSize(y);
size[x] += size[y];
}
}
}
void dfs(int x) {
vis[x] = true;
dp[x] = fac[size[x] - ];
for (int i = first[x]; i != -; i = next[i]) {
int y = v[i];
if (!vis[y]) {
dfs(y);
dp[x] *= invfac[size[y]];
dp[x] %= MOD;
dp[x] *= dp[y];
dp[x] %= MOD;
}
}
}
void search(int x, int pre) {
vis[x] = true;
if (pre != -) {
f[x] = fac[n - ]; f[x] *= invfac[n - size[x]];
f[x] %= MOD;
LL tmp = f[pre];
tmp *= invfac[n - ];
tmp %= MOD;
tmp *= fac[n - - size[x]];
tmp %= MOD;
tmp *= fac[size[x]];
tmp %= MOD;
tmp *= invmod(dp[x]);
tmp %= MOD;
f[x] *= tmp;
f[x] %= MOD;
for (int i = first[x]; i != -; i = next[i]) {
int y = v[i];
if (!vis[y]) {
f[x] *= invfac[size[y]];
f[x] %= MOD;
f[x] *= dp[y];
f[x] %= MOD;
}
}
}
for (int i = first[x]; i != -; i = next[i]) {
int y = v[i];
if (!vis[y]) {
search(y, x);
}
}
}
int main() {
int T;
int i;
int x, y;
int ans;
init();
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
e = ;
memset(first, -, sizeof(first));
for (i = ; i < n; i++) {
scanf("%d%d", &x, &y);
addEdge(x, y);
addEdge(y, x);
}
memset(vis, false, sizeof(vis));
getSize();
memset(vis, false, sizeof(vis));
dfs();
memset(vis, false, sizeof(vis));
f[] = dp[];
search(, -);
ans = ;
for (i = ; i <= n; i++) {
ans += (f[i] * f[i]) % MOD;
ans %= MOD;
}
printf("%d\n", ans);
}
return ;
}
HDU 4662 MU Puzzle
从给定的字符串变成MI需要反着操作。
（1）将U替换成III。
（2）添加x个UU，即添加x个IIIIII。
假设有cnt个I，添加x个UU，那么一共有cnt+6x个I，又要满足cnt+6x=2y。判断是否存在这样的x满足方程即可。
#include<cstdio>
#include<cstring>
#define MAXN 1000010
char str[MAXN];
bool isOK(int len) {
if (str[] != 'M') {
return false;
}
for (int i = ; i < len; i++) {
if (str[i] == 'M') {
return false;
}
}
return true;
}
int main() {
int T;
int len;
int cnt;
int i;
scanf("%d", &T);
while (T--) {
scanf(" %s", str);
len = strlen(str);
if (isOK(len)) {
cnt = ;
for (i = ; i < len; i++) {
if (str[i] == 'U') {
cnt += ;
} else {
cnt++;
}
}
if (len == && str[] == 'I') {
puts("Yes");
} else if (cnt % == || cnt % == ) {
puts("Yes");
} else {
puts("No");
}
} else {
puts("No");
}
}
return ;
}
HDU 4664 Triangulation
SG打表找规律。
mex是不属于这个集合的最少非负整数。
sg(x)是mex{sg(y)|y是x的后继状态}。
游戏和的SG函数值是它的所有子游戏SG函数值的异或。
n个游戏的异或和为0，先手必败。
#include<cstdio>
#include<cstring>
#define MAXN 1010
int sg[MAXN];
bool vis[MAXN];
int SG(int n) {
if (n == ) {
sg[n] = ;
} else if (n == ) {
sg[n] = ;
} else if (n == ) {
sg[n] = ;
} else if (n == ) {
sg[n] = ;
} else if (sg[n] == -) {
int i;
memset(vis, false, sizeof(vis));
for (i = ; i <= n - ; i++) {
vis[SG(i) ^ SG(n - i - )] = true;
}
for (i = ;; i++) {
if (!vis[i]) {
break;
}
}
sg[n] = i;
}
return sg[n];
}
void init() {
int i;
memset(sg, -, sizeof(sg));
for (i = ; i < MAXN; i++) {
sg[i] = SG(i);
}
}
int getSG(int n) {
if (n < MAXN) {
return sg[n];
} else {
return sg[n % + * ];
}
}
int main() {
int T;
int n;
int tmp;
int res;
init();
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
res = ;
while (n--) {
scanf("%d", &tmp);
res ^= getSG(tmp);
}
if (res) {
puts("Carol");
} else {
puts("Dave");
}
}
return ;
}
HDU 4665 Unshuffle
若一个数只出现两次，则第一个数属于0，第二个数属于1。
若一个数出现了四次，则第一个数属于0，第四个数属于1，其他两个都有可能。
#include<cstdio>
#include<cstring>
#include<vector>
#define MAXN 2010
using namespace std;
int arr[MAXN];
char str[MAXN];
bool flag;
int idx[MAXN];
int cnt[MAXN];
int st[][MAXN];
int belong[MAXN];
int n;
vector<int> pos[MAXN];
void dfs(int x, int p1, int p2) {
if (x > n) {
flag = true;
}
if (flag) {
return;
}
if (p1 > && p2 >
&& arr[st[][min(p1, p2)]] != arr[st[][min(p1, p2)]]) {
return;
}
if (belong[x] == ) {
st[][p1 + ] = x;
dfs(x + , p1 + , p2);
} else if (belong[x] == ) {
st[][p2 + ] = x;
dfs(x + , p1, p2 + );
} else {
st[][p1 + ] = x;
belong[pos[arr[x]][]] = ;
dfs(x + , p1 + , p2); if (!flag) {
st[][p2 + ] = x;
belong[pos[arr[x]][]] = ;
dfs(x + , p1, p2 + ); belong[pos[arr[x]][]] = -;
}
}
}
int main() {
int T;
int i;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
memset(idx, , sizeof(idx));
memset(cnt, , sizeof(cnt));
for (i = ; i <= n; i++) {
scanf("%d", &arr[i]);
cnt[arr[i]]++;
idx[i] = cnt[arr[i]];
pos[arr[i]].clear();
}
memset(belong, -, sizeof(belong));
for (i = ; i <= n; i++) {
if (idx[i] == ) {
belong[i] = ;
} else if (idx[i] == && cnt[arr[i]] == ) {
belong[i] = ;
} else if (idx[i] == ) {
belong[i] = ;
}
pos[arr[i]].push_back(i);
}
flag = false;
dfs(, , );
for (i = ; i <= (n >> ); i++) {
str[st[][i]] = '';
str[st[][i]] = '';
}
for (i = ; i <= n; i++) {
putchar(str[i]);
}
putchar('\n');
}
return ;
}