2024.7.8

2024.7.8 【追逐影子的人，自己就是影子 —— 荷马】

Monday 六月初三

---

讲的根本听不懂好吧！

目前只写了三道题（但是黑色

确实是没见过这么抽象的数据结构

Gregor and the Two Painters
Number of Components
Equal LCM Subsets

这个lcm确实让我印象深刻，

第一次把一个数学+数据结构写成这样

//2024.7.8
//by wite_ice
//Equal LCM Subsets
#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
typedef pair<int, int> p;
typedef __int128 ll;

int T, n, m;
int c[2], sz[2];
ll a[2][N], d[2][N];

inline ll read(){
ll ans = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9'){ans = ans * 10 + (ch ^ 48);ch = getchar();}
return ans;
}

void write(ll n){if (n >= 10) write(n / 10);putchar(n % 10 + '0');}

struct tree{
ll s[N * 4], sum;
void build(int x, int l, int r, ll a[]) {
if(l == r) {
s[x] = sum / __gcd(sum, a[l]);
return ;
}
int mid = (l + r) >> 1;
build(x << 1, l, mid, a);
build(x << 1 | 1, mid + 1, r, a);
s[x] = __gcd(s[x << 1], s[x << 1 | 1]);
}
void change(int x, int l, int r, int p) {
if(l == r) {
s[x] = 0;
return ;
}
int mid = (l + r) >> 1;
if(p <= mid) change(x << 1, l, mid, p);
else change(x << 1 | 1, mid + 1, r, p);
s[x] = __gcd(s[x << 1], s[x << 1 | 1]);
}
ll work() {return s[1];}
}t[2][N];

int main() {
cin >> T;
while(T--) {
cin >> n >> m;
for(int i = 1; i <= n; ++i)
    a[0][i] = read(), d[0][i] = 0;
for(int i = 1; i <= m; ++i)
    a[1][i] = read(), d[1][i] = 0;
c[0] = c[1] = 0, sz[0] = n, sz[1] = m;
queue <p> q;
for(int k = 0; k <= 1; ++k) 
for(int i = 1; i <= sz[k]; ++i) {
t[k][i].sum = a[k][i], t[k][i].build(1, 1, sz[k ^ 1], a[k ^ 1]);
if(t[k][i].work() > 1) q.push({k, i}), d[k][i] = 1, ++c[k];
}
while(q.size()) {
p x = q.front(); q.pop();
int f = (x.first) ^ 1;
for(int i = 1; i <= sz[f]; ++i) {
if(!d[f][i]) {
t[f][i].change(1, 1, sz[f ^ 1], x.second);
if(t[f][i].work() > 1) q.push({f, i}), d[f][i] = 1, ++c[f];
}
}
}
if(c[0] == sz[0] || c[1] == sz[1]) cout << "NO" << endl;
else {
cout << "YES" << endl << sz[0] - c[0] << ' ' << sz[1] - c[1] << endl;
for(int i = 1; i <= n; ++i) 
if(!d[0][i]) write(a[0][i]), putchar(' ');
cout << endl;
for(int i = 1; i <= m; ++i)
if(!d[1][i]) write(a[1][i]), putchar(' ');
cout << endl;
}
}
}

不过对线段树的理解加深了不少，理解了很多之前未曾设想的用法

理解了一些方法，比如钦定某个点为代表元，之后向四周遍历

或者使用类似染色的思想，简化问题

原文地址：https://blog.csdn.net/white__ice/article/details/140279474

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！