2024/7/8 笔记

CF1656H
https://www.luogu.com.cn/problem/CF1656H
参考DaiRuiChen007的题解:

code:

using namespace std;
#define ll __int128_t
const int maxn = 1e3+10;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
const int N = 1024,N2 = N<<2;
struct stree{
	
	ll tree[N2];
	ll ls(int x){
		return x<<1;
	}
	ll rs(int x){
		return x<<1|1;
	}
	void init(){
		for(int i = 0;i < N2;i++){
			tree[i] = 0;
		}
	}
	void update(int x,ll v){
		for(tree[x+=N]=v,x>>=1;x;x>>=1){
			tree[x]=gcd(tree[x<<1],tree[x<<1|1]);
		}
	}  
	ll query() { return tree[1]; }
};//线段树 
const int maxb = 2e6+1e5;
char buf[maxb],*p1 = buf,*p2 = buf;
stree A[maxn],B[maxn];
ll a[maxn],b[maxn];
int n,m;
inline ll read() {
	ll x=0; char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+(c^48),c=getchar();
	return x;
}
inline void write(ll x) {
	if(x>=10) write(x/10);
	putchar((x%10)^48);
}
void run(){
	cin>>n>>m;
	vector <int> qa,qb;
	for(int i = 1;i <= n;i++){
		//cin>>a[i];
		a[i] = read();
		qa.push_back(i);
		A[i].init();
	}
	for(int i = 1;i <= m;i++){
		//in>>b[i];
		b[i] = read();
		qb.push_back(i);
		B[i].init();
	}
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			A[i].update(j,a[i]/gcd(a[i],b[j]));
			B[j].update(i,b[j]/gcd(a[i],b[j]));
		}
	}
	while(!qa.empty()&&!qb.empty()){
		for(auto it=qa.begin();it!=qa.end();++it){
			if(A[*it].query()>1) {
				for(int z:qb) B[z].update(*it,0);
				qa.erase(it);
				goto no;
			}//mythware_super_password
		}
		for(auto it=qb.begin();it!=qb.end();++it){
			if(B[*it].query()>1) {
				for(int z:qa) A[z].update(*it,0);
				qb.erase(it);
				goto no;
			}	
		}
		cout<<"YES"<<endl;
		cout<<(int)qa.size()<<" "<<(int)qb.size()<<endl;
		for(int i:qa){
			write(a[i]);
			cout<<" ";
		}//cout<<a[i]<<" ";
		cout<<endl;
		for(int i:qb){
			write(b[i]);
			cout<<" ";
		}//cout<<b[i]<<" ";
		cout<<endl;
		return;
		no:;
	}
	cout<<"NO"<<endl;
}
int main(){
	int t;
	cin>>t;
	while(t--) run();
	return 0;
}

T2

CF1209G2
https://www.luogu.com.cn/problem/CF1209G2
考虑每个颜色最左边出现的位置为L ，最右边的位置为R ，使用一数组c,对于每个颜色, 在L,R(左闭右开)区间内将c的每一个值+1;
最后结果如下:
a: 1 2 1 2 1 3 4 3 4 5
b: 1 2 2 1 0 1 2 1 0 0
很容易发现 ,每两个0之间都有一独立段,这个段中出现次数最多的ai就是要保留的,其余a中的元素需要更改, 最后统计结果;
考虑使用线段树维护a中区间最大值,b区间最小值,左边一段不含bi最小值的段中ai的最大值Lmx以及Rmx

第一次独立写这么难的题( 前前后后算是参考了不知道多少篇题解再结合上课讲的才勉强把思路理清