http://codeforces.com/contest/1287
B. Hyperset
题意：给出n个字符串，要求若三个字符串每一列的三个字母都不同或者都相同，则可以放一起，求最多凑出几个集合。
若已知两个字符串，则第三个字符串就是确定的。map找到即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n, k;
map<string,int>mp;
string s[maxn];
int ans;
int vis[30];
char oth(char a, char b) {
int x = 'S' - 'A', y = 'E' - 'A', z = 'T' - 'A';
vis[x] = vis[y] = vis[z] = 0;
vis[a - 'A'] = 1; vis[b - 'A'] = 1;
if (!vis[x])return 'S';
else if (!vis[y])return 'E';
else return 'T';
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
cin >> s[i];
mp[s[i]] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
string tmp;
for (int p = 0; p < k; p++) {
if (s[i][p] == s[j][p])tmp.push_back(s[i][p]);
else tmp.push_back(oth(s[i][p], s[j][p]));
}
if (mp.count(tmp) && mp[tmp] > j)ans++;
}
}
printf("%d\n", ans);
return 0;
}
|
C. Garland
题意：给定一个排列，其中有一些缺失了。要求填入，使得相邻奇偶性不同的数对个数最少。输出最少对数。
dp
dp[i] [j] [k] 表示第 i 个，到第 i 个共有 j 个奇数，第 i 个数是奇数/偶数。
则分原排列中第 i 个是否已经确定讨论。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n;
int a[maxn];
int dp[110][110][110];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
memset(dp, 0x3f, sizeof(dp));
if (a[1] == 0)dp[1][0][0] = dp[1][1][1] = 0;
else dp[1][(a[1] & 1)][(a[1]) & 1] = 0;
for (int i = 2; i <= n; i++) {
if (a[i] == 0) {
for (int j = 1; j <= i; j++)
dp[i][j][1] = min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][0] + 1);
for (int j = 0; j <= i; j++)
dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1] + 1);
}
else {
if (a[i] & 1) {
for (int j = 1; j <= i; j++)
dp[i][j][1] = min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][0] + 1);
}
else {
for (int j = 0; j <= i; j++)
dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1] + 1);
}
}
}
printf("%d\n", min(dp[n][n / 2 + (n & 1)][0], dp[n][n / 2 + (n & 1)][1]));
return 0;
}
|
D. Numbers on Tree
题意：给定一棵树，构造结点值。满足结点的子树中结点值小于该结点的结点个数等于规定值。
dfs
后序遍历，保证先处理完子节点。
每次直接把当前节点插入到规定位置，这样做是可行的。因为属于不同的子树中的结点被处理时会先用自己的子树把vector更新，使得vector的最前面一串一定都是自己的子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n;
int p[maxn], c[maxn];
int sz[maxn];
vector<int>G[maxn];
int rt;
vector<int>vc;
void dfs(int u) {
sz[u] = 1;
for (int v : G[u]) {
dfs(v);
sz[u] += sz[v];
}
if (sz[u] <= c[u]) {
puts("NO");
exit(0);
}
vc.insert(vc.begin() + c[u], u);
}
int ans[maxn];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &p[i], &c[i]);
if (p[i] == 0)rt = i;
else G[p[i]].push_back(i);
}
dfs(rt);
puts("YES");
for (int i = 0; i < n; i++) {
ans[vc[i]] = i + 1;
}
for (int i = 1; i <= n; i++)printf("%d ", ans[i]);
printf("\n");
return 0;
}
|
