牛客-DongDong数颜色 及其相似题
2024-09-08 16:04:59
大佬博客
ps:在牛客上做到这题不会,学会之后补了两道相关题。顺便记录一下。
牛客-DongDong数颜色
sol:dfs序+莫队,先把树上的点标上dfs序,因为子树的dfs序是连续的,所以子树可以表示为id[x]到id[x] + size[x] + 1,然后就是序列上莫队了(引用自官方题解)
- dfs序 + 莫队
#include "bits/stdc++.h"
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 1e5 + ;
int c1[MAXN], c2[MAXN], c3[MAXN];
vector<int> edge[MAXN];
PII node[MAXN];
int pos, size;
int ans[MAXN];
struct Query {
int l, r;
int index;
} q[MAXN];
void dfs(int u, int f) {
c2[++pos] = c1[u];
node[u].first = pos;
for (int i = ; i < edge[u].size(); i++) {
int v = edge[u][i];
if (v == f) continue;
dfs(v, u);
}
node[u].second = pos;
}
bool cmp(Query a, Query b) {
if ((a.l - ) / size != (b.l - ) / size)
return (a.l - ) / size < (b.l - ) / size;
return a.r < b.r;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
size = sqrt(n);
for (int i = ; i <= n; i++)
scanf("%d", &c1[i]);
for (int i = ; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(, -);
for (int i = ; i <= m; i++) {
int x;
scanf("%d", &x);
q[i].l = node[x].first;
q[i].r = node[x].second;
q[i].index = i;
}
sort (q + , q + + m, cmp);
int l = , r = , k = ;
for (int i = ; i <= m; i++) {
while (r < q[i].r) if (++c3[c2[++r]] == ) k++;
while (l > q[i].l) if (++c3[c2[--l]] == ) k++;
while (r > q[i].r) if (--c3[c2[r--]] == ) k--;
while (l < q[i].l) if (--c3[c2[l++]] == ) k--;
ans[q[i].index] = k;
}
for (int i = ; i <= m; i++)
printf("%d\n", ans[i]);
return ;
}
ps:由于我菜,官方题解上的另外两种解法没补出来,但是去网上看了其他博主的博客发现可以用树状数组代替莫队的功能,效率更高。数组数组为n*log(n),莫队为n*sqrt(n)
HDU-3333-Turing Tree
sol:离线处理,优先处理右区间在前的,不断更新每个颜色下标位置,从而在权值树状数组上统计总和;
- 树状数组
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + ;
struct Query {
int l, r;
int index;
} q[MAXN];
int a[MAXN], pre[MAXN];
LL c[MAXN], ans[MAXN];
map<int, int> mp;
bool cmp(Query a, Query b) {
return a.r < b.r;
}
int lowbit(int i) {
return i & (-i);
}
void add(int i, int k) {
while (i < MAXN) {
c[i] += k;
i += lowbit(i);
}
}
LL sum(int i) {
LL res = ;
while (i > ) {
res += c[i];
i -= lowbit(i);
}
return res;
}
int main() {
int t, n, m;
scanf("%d", &t);
while (t--) {
memset(c, , sizeof(c));
mp.clear();
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]);
scanf("%d", &m);
for (int i = ; i <= m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].index = i;
}
sort(q + , q + + m, cmp);
int r = ;
for (int i = ; i <= m; i++) {
while (r < q[i].r) {
++r;
add(r, a[r]);
if (mp.count(a[r])) add(mp[a[r]], -a[r]);
mp[a[r]] = r;
}
ans[q[i].index] = sum(q[i].r) - sum(q[i].l - );
}
for (int i = ; i <= m; i++)
printf("%lld\n", ans[i]);
}
return ;
}
ps:按难易程度这题应该排在上一题上面,完全就是上一题的阉割版。上一题用莫队来写了这一题就用来练树状数组的方法了,不过这题用莫队不一定能过,这份数组数组的代码都跑了468ms,莫队可能会比较极限,没有尝试过。
CF-703D-Mishka and Interesting sum
sol:把区间所以数异或起来根据相同数字异或为0的原理得到的就是所有出现次数为奇数的数的异或值,那么联系上面两题,只要把区间内不重复出现的数都异或一遍在和区间内所有数异或一下就是我们的结果了。因为异或和加减法具有同样的一些性质也可以用树状数组来解决。
- 树状数组+位运算
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e6 + ;
int a[MAXN], b[MAXN], c[MAXN];
map<int, int> mp;
int ans[MAXN];
struct Query {
int l, r;
int index;
} q[MAXN];
bool cmp(Query a, Query b) {
return a.r < b.r;
}
int lowbit(int i) {
return i & (-i);
}
void add(int i, int k) {
while (i < MAXN) {
c[i] ^= k;
i += lowbit(i);
}
}
int sum(int i) {
int _xor = ;
while (i > ) {
_xor ^= c[i];
i -= lowbit(i);
}
return _xor;
}
int main() {
int n, m;
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i] ^ b[i - ];
}
scanf("%d", &m);
for (int i = ; i <= m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].index = i;
}
sort(q + , q + + m, cmp);
int r = ;
for (int i = ; i <= m; i++) {
while (r < q[i].r) {
r++;
add(r, a[r]);
if (mp.count(a[r]))
add(mp[a[r]], a[r]);
mp[a[r]] = r;
}
ans[q[i].index] = (sum(q[i].r) ^ sum(q[i].l - )) ^ (b[q[i].r] ^ b[q[i].l - ]);
}
for (int i = ; i <= m; i++)
printf("%d\n", ans[i]);
return ;
}
ps:这题我尝试了莫队,超时了,卡在第14组数据,莫队能过1e5的数据,这题n最大值为1e6。莫队比较好写,但还是树状数组比较快。
dfs序+莫队,先把树上的点标上dfs序,因为子树的dfs序是连续的,所以子树可以表示为id[x]到id[x]+size[x]+1id[x]到id[x]+size[x]+1,然后就是序列上莫队了
最新文章
- [ACM训练] 算法初级 之 数据结构 之 栈stack+队列queue (基础+进阶+POJ 1338+2442+1442)
- Laravel 校验规则之字段值唯一性校验
- Android之jni入门
- mysql 外连接总结
- andorid 进度条
- Thread多线程stopSleep顺序问题
- linux 文件类型
- ECSTORE验证码优化
- centos 下 安装mysql
- 从0开始的LeetCode生活—001-Two Sum
- eclipse创建maven——初学
- java生成UUID
- 【Core】.NET Core 部署在Linux
- python文件的基础操作
- Android-ProgressDialog点击对话框外部是不让其消失
- 可视化并理解CNN
- String.valueOf 的坑
- mysql 内置功能 存储过程 创建有参存储过程
- VIPServer:阿里智能地址映射及环境管理系统详解
- git ——本地项目上传到git
热门文章
- Vue.js——1.初识Vue
- Python说文解字_杂谈08
- Is the MIME type &#39;image/jpg&#39; the same as &#39;image/jpeg&#39;?
- 面试必问之http以及浏览器相关知识
- 框架-Spring容器
- Linux-竟态初步引入
- 获取文件MD5值(JS、JAVA)
- UEFI启动(翻译)
- 吴裕雄--天生自然 JAVA开发学习:接口
- F - kebab HDU - 2883 (最大流构图)