题解 - Gemini Boy - ACM之路~
Codeforces 291E. Tree-String Problem
链接：http://codeforces.com/problemset/problem/291/E
题意就是说给你一棵树，边权是字符串，然后从根节点到叶子节点的所有路径中，出现模板串的个数。
做法就是dfs+kmp，对目标串得到next数组，然后从根节点dfs，一边dfs一边跑kmp进行匹配。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int maxn = 100100;
struct Edge {
int to;
string s;
Edge() {}
Edge(int too, string str) {
to = too; s = str;
}
};
int n, ans = 0, next[maxn];
string t;
vector<Edge> edge[maxn];
void dfs(int u, int k) {
for (int l = 0; l < edge[u].size(); l++) {
int v = edge[u][l].to;
string str = edge[u][l].s;
int tmp = k, len = edge[u][l].s.size();
for (int i = 0, j = k; i < len; i++) {
while (j != -1 && str[i] != t[j+1])
j = next[j];
if (str[i] == t[j+1]) j++;
if (j + 1 == t.size()) {
j = next[j]; ans++;
}
tmp = j;
}
dfs(v, tmp);
}
}
void work() {
cin >> n;
for (int i = 2; i <= n; i++) {
int p;
string str;
cin >> p >> str;
edge[p].push_back(Edge(i, str));
}
cin >> t;
next[0] = -1;
for (int i = 1, j = -1; i < t.size(); i++) {
while (j != -1 && t[j+1] != t[i])
j = next[j];
if (t[j+1] == t[i]) {
next[i] = j + 1; j++;
} else {
next[i] = -1;
}
}
dfs(1, -1);
cout << ans << endl;
}
int main() {
work();
return 0;
}
SGU 499. Greatest Greatest Common Divisor
链接：http://acm.sgu.ru/problem.php?contest=0&problem=499
给出n(1<=n<=100000)个数，每个数的范围是1<=a[i]<=1000000，现在求n个数任意俩个数的gcd最大是多少。
做法是枚举答案，然后用类似于素数筛法的方法判定是否存在。复杂度O(n*logn)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 1000010;
int n, maxx, a[100100], pos[maxn];
void init() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
pos[a[i]] = i;
maxx = max(a[i], maxx);
}
maxx += 2;
}
bool check(int x) {
int res = 0;
for (int i = x; i < maxx; i += x) {
if (res > 1) break;
if (pos[i]) res++;
}
if (res > 1)
return true;
else
return false;
}
void work() {
for (int i = maxx - 2; i >= 1; i--) {
if (check(i) == true) {
printf("%d\n", i);
return ;
}
}
}
int main() {
init();
work();
}
矩阵连乘问题
POJ 1651：http://poj.org/problem?id=1651
n<=100个数，每次去掉一个数a[i]得到a[i-1]*a[i]*a[i+1]的分数，不能去掉首尾两端，求最小分数。
f(l, r) = min{f(l, k) + f(k+1, r) + a[i-1]*a[k]*a[j] : (l <= k < r)}
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int n, f[111][111], v[111];
int main() {
memset(f, 0, sizeof(f));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &v[i]);
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
f[i][j] = f[i][i] + f[i+1][j] + v[i-1]*v[i]*v[j];
for (int k = i + 1; k < j; k++) {
if (f[i][j] > f[i][k] + f[k+1][j] + v[i-1]*v[k]*v[j])
f[i][j] = f[i][k] + f[k+1][j] + v[i-1]*v[k]*v[j];
}
}
}
printf("%d\n", f[2][n]);
}
spoj MIXTURES：http://www.spoj.com/problems/MIXTURES/
n<=100个数，每次合并两个数a,b，得到新数(a+b)%100，代价是a*b，求并至1个数的最小代价
f(l, r) = min{f(l, k) + f(k+1, r) + mix(l, k)*mix(k+1, r) : l <= k < r} (合并k和k+1), mix(x, y) = (sum[y] - sum[x-1]) % 100;
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, sum[111], val[111], f[111][111];
int getSum(int l, int r) {
return (sum[r] - sum[l-1]) % 100;
}
int main() {
while (~scanf("%d", &n)) {
memset(sum, 0, sizeof(sum));
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
sum[i] = sum[i-1] + val[i];
}
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n - len + 1; i++) {
int j = i + len - 1;
f[i][j] = f[i][i] + f[i+1][j] + getSum(i, i) * getSum(i+1, j);
for (int k = i + 1; k < j; k++) {
if (f[i][j] > f[i][k] + f[k+1][j] + getSum(i, k) * getSum(k+1, j))
f[i][j] = f[i][k] + f[k+1][j] + getSum(i, k) * getSum(k+1, j);
}
}
}
printf("%d\n", f[1][n]);
}
}
19th Polish Olympiad in Informatics
链接：http://main.edu.pl/en/archive/oi/19
Festival(Stage I)：
Description
有n个正整数X1,X2,...,Xn，再给出m1+m2个限制条件，限制分为两类：
1. 给出a,b (1<=a,b<=n)，要求满足Xa + 1 = Xb
2. 给出c,d (1<=c,d<=n)，要求满足Xc <= Xd
在满足所有限制的条件下，求集合{Xi}大小的最大值。
Input
第一行三个正整数n, m1, m2 (2<=n<=600, 1<=m1+m2<=100,000)。
接下来m1行每行两个正整数a,b (1<=a,b<=n)，表示第一类限制。
接下来m2行每行两个正整数c,d (1<=c,d<=n)，表示第二类限制。
Output
一个正整数，表示集合{Xi}大小的最大值。
如果无解输出NIE。
Sample Input
4 2 2
1 2
3 4
1 4
3 1
Sample Output
3
Hint
X3=1, X1=X4=2, X2=3
这样答案为3。容易发现没有更大的方案。
做法就是类似于差分约束建图，然后在每个scc里判断是否满足限制条件。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int maxn = 1000;
const int inf = 1000000000;
struct Edge {
int v, w;
Edge() {}
Edge(int vv, int ww) {
v = vv; w = ww;
}
};
vector<Edge> adj[maxn*2];
int idx, size;
int n, m1, m2, a, b;
int dist[maxn][maxn];
int dfn[maxn], low[maxn], stk[maxn], id[maxn];
bool vis[maxn];
stack<int> S;
inline int Myabs(int x) {
if (x < 0)
x = -x;
return x;
}
void addEdge(int u, int v, int w) {
adj[u].push_back(Edge(v, w));
}
void tarjan(int u) {
dfn[u] = low[u] = ++idx;
S.push(u); vis[u] = true;
vector<Edge>::iterator it;
for (it = adj[u].begin(); it != adj[u].end(); it++) {
int v = it->v;
if (dfn[v] == -1) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
size++;
int v;
do {
v = S.top();
S.pop();
id[v] = size;
vis[v] = false;
} while (u != v);
}
}
void clearAll() {
for (int i = 0; i < maxn; i++)
adj[i].clear();
memset(dfn, -1, sizeof(dfn));
memset(low, -1, sizeof(low));
memset(vis, false, sizeof(vis));
memset(id, 0, sizeof(id));
memset(dist, 0, sizeof(dist));
while (!S.empty()) S.pop();
}
void init() {
scanf("%d %d %d", &n, &m1, &m2);
for (int i = 0; i < m1; i++) {
scanf("%d %d", &a, &b);
addEdge(a, b, 1);
addEdge(b, a, -1);
}
for (int i = 0; i < m2; i++) {
scanf("%d %d", &a, &b);
addEdge(a, b, 0);
}
void work() {
for (int i = 1; i <= n; i++) {
if (dfn[i] == -1)
tarjan(i);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j)
dist[i][j] = 0;
else
dist[i][j] = -inf;
}
}
for (int i = 1; i <= n; i++) {
vector<Edge>::iterator it;
for (it = adj[i].begin(); it != adj[i].end(); it++) {
int j = it->v;
if (id[i] == id[j])
dist[i][j] = max(dist[i][j], it->w);
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
if (dist[i][k] <= -inf)
continue;
for (int j = 1; j <= n; j++) {
if (dist[k][j] <= -inf)
continue;
if (dist[i][k] + dist[k][j] > dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
for (int i = 1; i <= n; i++) {
if (dist[i][i] > 0) {
puts("NIE");
return ;
}
}
int result = 0;
vector<int> ans;
memset(vis, false, sizeof(vis));
for (int i = 1; i <= n; i++) {
ans.clear();
if (vis[i] == true)
continue;
for (int j = 1; j <= n; j++) {
if (id[i] == id[j]) {
vis[j] = true;
ans.push_back(j);
}
}
int tmp = 0;
for (int j = 0; j < ans.size(); j++) {
for (int k = 0; k < ans.size(); k++) {
tmp = max(tmp, Myabs(dist[ans[j]][ans[k]])+1);
}
}
result += tmp;
}
printf("%d\n", result);
}
int main() {
clearAll();
init();
work();
return 0;
}
Letters(Stage I)：
Description
给出两个长度相同且由大写英文字母组成的字符串A、B，保证A和B中每种字母出现的次数相同。
现在每次可以交换A中相邻两个字符，求最少需要交换多少次可以使得A变成B。
Input
第一行一个正整数n (2<=n<=1,000,000)，表示字符串的长度。
第二行和第三行各一个长度为n的字符串，并且只包含大写英文字母。
Output
一个非负整数，表示最少的交换次数。
Sample Input
3
ABC
BCA
Sample Output
2
Hint
ABC -> BAC -> BCA
其实就是求逆序对。BIT维护。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1001000;
char str1[maxn], str2[maxn];
vector<int> adj1[maxn], adj2[maxn];
int len, sum[maxn], pos[maxn];
int main() {
scanf("%d %s %s", &len, str1, str2);
for (int i = 0; i < len; i++) {
adj1[str1[i]-'A'].push_back(i);
adj2[str2[i]-'A'].push_back(i);
}
for (int i = 0; i < 26; i++) {
for (int j = 0; j < adj1[i].size(); j++) {
pos[adj1[i][j]] = adj2[i][j];
}
}
long long ans = 0;
for (int i = len - 1; i >= 0; i--) {
for (int j = pos[i]; j; j -= j & -j)
ans += sum[j];
for (int j = pos[i] + 1; j <= len; j += j & -j)
sum[j]++;
}
printf("%lld\n", ans);
return 0;
}
2013 ACM/ICPC Asia Regional Online —— Warmup
A题(HDU 4706)：无意义的题，就贴个代码吧
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
void get(int x, int n) {
int y = x + 2 * (n - 1);
y %= 26;
for (int i = 1; i <= n; i++) {
printf("%c", 'a'+(x+i-1)%26);
for (int j = n-i-1; j >= 1; j--)
printf(" ");
if (i > 1 && i < n)
printf("%c", 'a'+(y+1-i+26)%26);
for (int j = 1; j <= i-2; j++)
printf(" ");
printf("%c\n", 'a'+(y+i-1)%26);
}
}
int main() {
int x = 0;
for (int i = 3; i <= 10; i++) {
get(x, i);
x = (x+2*i+i-2) % 26;
}
return 0;
}