Codeforces Round #612 (Div. 2)
2024-10-08 04:03:04
https://codeforces.com/contest/1287/
A - Angry Students
题意：求A后面的P最长连续有几个？
题解：？
int n;
char s[200005];
void test_case() {
scanf("%d%s", &n, s + 1);
int cnt = 0, ans = 0;
int b = 1;
while(b <= n && s[b] == 'P')
++b;
for(int i = b; i <= n; ++i) {
if(s[i] == 'P')
++cnt;
else {
ans = max(ans, cnt);
cnt = 0;
}
}
ans = max(ans, cnt);
printf("%d\n", ans);
}
一种不需要判断结尾的思路是，一边统计cnt，一边尝试更新ans。
B - Hyperset
题意：每个属性只有3种值。定义三张牌是一个SET，当他们每个属性要么全等要么两两不同。
题解：枚举两张牌，可以确定第三张牌。
注：原来没有重复的牌的啊，这个constraint完全没必要啊，把这题变成一个送分题了。
struct TrieNode {
int data;
int nxt[3];
void Init() {
data = 0;
memset(nxt, 0, sizeof(nxt));
}
};
struct Trie {
static const int MAXN = 45000;
TrieNode tn[MAXN + 5];
int root, top;
int NewNode() {
tn[++top].Init();
return top;
}
void Init() {
top = 0;
root = NewNode();
}
void Insert(int *a, int len, int data) {
int cur = root;
for(int i = 1; i <= len; ++i) {
int &nxt = tn[cur].nxt[a[i]];
if(!nxt)
nxt = NewNode();
cur = nxt;
}
tn[cur].data += data;
}
int Query(int *a, int len) {
int cur = root;
for(int i = 1; i <= len; ++i) {
int &nxt = tn[cur].nxt[a[i]];
if(!nxt)
return 0;
cur = nxt;
}
return tn[cur].data;
}
} trie;
int n, k;
char s[35];
int st[128], t[1505][35], r[35];
void test_case() {
st['S'] = 0;
st['E'] = 1;
st['T'] = 2;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
for(int j = 1; j <= k; ++j)
t[i][j] = st[s[j]];
trie.Insert(t[i], k, 1);
}
ll sum = 0;
for(int i1 = 1; i1 <= n; ++i1) {
for(int i2 = i1 + 1; i2 <= n; ++i2) {
int ty = 1;
for(int j = 1; j <= k; ++j) {
r[j] = (3 - (t[i1][j] + t[i2][j]) % 3) % 3;
if(r[j] != t[i1][j])
ty = 0;
}
if(ty == 0)
sum += trie.Query(r, k);
else
sum += trie.Query(r, k) - 2;
}
}
printf("%lld\n", sum / 3);
}
map<ll, int> M;
int n, k;
char s[35];
int st[128], t[1505][35];
ll val[1505];
void test_case() {
st['S'] = 0;
st['E'] = 1;
st['T'] = 2;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
ll r = 0;
for(int j = 1; j <= k; ++j) {
t[i][j] = st[s[j]];
r = 3 * r + t[i][j];
}
M[r]++;
val[i] = r;
}
ll sum = 0;
for(int i1 = 1; i1 <= n; ++i1) {
for(int i2 = i1 + 1; i2 <= n; ++i2) {
ll r = 0;
for(int j = 1; j <= k; ++j) {
int tmp = (3 - (t[i1][j] + t[i2][j]) % 3) % 3;
r = 3ll * r + tmp;
}
auto it = M.find(r);
if(it != M.end()) {
if(r != val[i1])
sum += it->second;
else
sum += (it->second) - 2;
}
}
}
printf("%lld\n", sum / 3);
}
unordered_map<ll, int> M;
int n, k;
char s[35];
int st[128], t[1505][35];
ll val[1505];
void test_case() {
M.reserve(3000);
st['S'] = 0;
st['E'] = 1;
st['T'] = 2;
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) {
scanf("%s", s + 1);
ll r = 0;
for(int j = 1; j <= k; ++j) {
t[i][j] = st[s[j]];
r = 3 * r + t[i][j];
}
M[r]++;
val[i] = r;
}
ll sum = 0;
for(int i1 = 1; i1 <= n; ++i1) {
for(int i2 = i1 + 1; i2 <= n; ++i2) {
ll r = 0;
for(int j = 1; j <= k; ++j) {
int tmp = (3 - (t[i1][j] + t[i2][j]) % 3) % 3;
r = 3ll * r + tmp;
}
auto it = M.find(r);
if(it != M.end()) {
if(r != val[i1])
sum += it->second;
else
sum += (it->second) - 2;
}
}
}
printf("%lld\n", sum / 3);
}
Trie最快，但是一开始开太紧空间WA了一发。事实上真的没必要省空间，有多大开多大。
C - Garland
这个怎么贪心的啊？得看看别人怎么搞。
题意：给一列数字，是一个自然数的排列，假如是0表示待填。填上这个序列使得复杂度最小。每个相邻的奇偶对贡献1复杂度。
题解：dp，由于奇数之间是等价的，偶数之间也是等价的，每种填法对后面的影响也是只有最后一位数字。设dp[i][j][0/1]为前i个位置填了j个奇数，并且最后一位的奇偶性为0/1的最小复杂度。
int a[105];
int dp[105][105][2];
void test_case() {
int n;
scanf("%d", &n);
int cnt1 = (n + 1) / 2;
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
if(a[i]) {
if(a[i] & 1)
--cnt1;
}
}
memset(dp, INF, sizeof(dp));
dp[0][0][0] = 0;
dp[0][0][1] = 0;
for(int i = 1; i <= n; ++i) {
if(a[i]) {
int t = a[i] & 1;
for(int j = 0; j <= cnt1; ++j) {
dp[i][j][t] = dp[i - 1][j][t];
dp[i][j][t] = min(dp[i][j][t], dp[i - 1][j][1 - t] + 1);
}
} else {
for(int j = 1; j <= cnt1; ++j) {
dp[i][j][1] = dp[i - 1][j - 1][1];
dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][0] + 1);
}
for(int j = 0; j <= cnt1; ++j) {
dp[i][j][0] = dp[i - 1][j][1] + 1;
dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0]);
}
}
/*for(int j = 0; j <= cnt1; ++j) {
for(int t = 0; t <= 1; ++t)
printf("dp[%d][%d][%d]=%d\n", i, j, t, dp[i][j][t]);
}
puts("");*/
}
printf("%d\n", min(dp[n][cnt1][0], dp[n][cnt1][1]));
}
int a[105];
int dp[105][105][2];
void test_case() {
int n, c;
scanf("%d", &n);
c = (n + 1) / 2;
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
memset(dp, INF, sizeof(dp));
dp[0][0][0] = 0;
dp[0][0][1] = 0;
for(int i = 1; i <= n; ++i) {
if(a[i]) {
int t = a[i] & 1;
for(int j = 0; j <= c; ++j) {
dp[i][j + t][t] = dp[i - 1][j][t];
dp[i][j + t][t] = min(dp[i][j + t][t], dp[i - 1][j][1 - t] + 1);
}
} else {
for(int j = 1; j <= c; ++j) {
dp[i][j][1] = dp[i - 1][j - 1][1];
dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][0] + 1);
}
for(int j = 0; j <= c; ++j) {
dp[i][j][0] = dp[i - 1][j][1] + 1;
dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][0]);
}
}
/*for(int j = 0; j <= cnt1; ++j) {
for(int t = 0; t <= 1; ++t)
printf("dp[%d][%d][%d]=%d\n", i, j, t, dp[i][j][t]);
}
puts("");*/
}
printf("%d\n", min(dp[n][c][0], dp[n][c][1]));
}
贪心的解法复杂度低一个层次。
D - Numbers on Tree
题意：给一棵n<=2000的有根树，规定每个数的子树中有多少个节点的val比根节点的严格小。给这棵树填上任意一种合法的val（每个值都在[1,10^9]且满足上一句话）或报告不存在。
题解：树的这类问题可能都是先往递归的方向考虑，假如是叶子，不用多说之间返回1，否则是中间节点。假如中间节点只有一棵子树，而且子树中的值是相异的，那么随便插进去然后把后面的数往后面挤，得到的也还是值全部相异的树。否则至少有两棵子树，假如他们的值也都是相异的也可以仿照上面解决，可惜搞不得，有可能不存在一个位置刚好满足要求。
这时候很显然的子树之间是没有关系的，可以给一棵子树的值整体提高一个水平，使得得到的值也是相异的，最简单的是加上上一棵子树的最大值（而不一定是size，假如没有进行算不并列的排名的话）。
事实上并不一定需要同一棵子树占据同一段连续的位置，直接全部混在一起算不并列的排名也可以。
int n, root;
int c[2005];
vector<int> G[2005];
vector<pii> vec[2005];
void dfs(int u) {
for(auto &v : G[u]) {
dfs(v);
for(auto &j : vec[v])
vec[u].push_back(j);
}
if(c[u] > vec[u].size()) {
puts("NO");
exit(0);
}
sort(vec[u].begin(), vec[u].end());
for(int i = 0; i < vec[u].size(); ++i)
vec[u][i].first = i + 1;
vec[u].insert(vec[u].begin() + c[u], {c[u] + 1, u});
for(int i = c[u] + 1; i < vec[u].size(); ++i)
++vec[u][i].first;
}
void test_case() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
int p;
scanf("%d%d", &p, &c[i]);
if(p)
G[p].push_back(i);
else
root = i;
}
dfs(root);
for(auto &j : vec[root])
swap(j.first, j.second);
sort(vec[root].begin(), vec[root].end());
puts("YES");
for(auto &j : vec[root])
printf("%d ", j.second);
puts("");
}
注意vector中insert是一个迭代器，而且确实可以在 for auto 中进行交换（应该在遍历中不会改变其他元素的操作都可以吧？）
最新文章
- grunt 入门学习
- 判断iframe是否加载完成的完美方法
- SE1-soc入手又有的东西可以玩了
- mysql内存使用以及优化中需要的几点注意
- AloneJs.msgbox() —— 弹出消息框
- createjs mask 填坑过程
- This version of MySQL doesn’t yet support ‘LIMIT & IN/ALL/ANY/SOME 错误解决
- Chrome插件开发 尝试1
- PowerShell官方的MSDN
- Oracle Hint用法总结
- String类之indexOf--->查找某字对应的位置
- Python实战：爬虫的基础
- away 3d的一些问题
- 小程序之Tab切换（二）
- WEB 前端开发插件整理
- 【翻译】Context should go away for Go 2
- rTorrent + ruTorrent 安装和配置
- SVN基本命令总结
- java web mysql.jar java.lang.ClassNotFoundException: com.mysql.jdbc.Driver
- html中去掉文本框(input type="text")的边框或只显示下边框