19th Polish Olympiad in Informatics - Gemini Boy - ACM之路~
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;
}
评论 (0)