首页 > 其他分享 >SMU 2024 ptlks的周报Week 9 (7.15-7.21)

SMU 2024 ptlks的周报Week 9 (7.15-7.21)

时间：2024-07-21 18:52:02浏览次数：9  
标签：Week 7.15 cnt return int SMU long ll define

这周学了启发式合并，prim算法，对图有了进一步的理解。

树

题意：给一棵根为 1 的有根树，点 i 具有一个权值 \(A_i\)定义一个点对的值 f(u,v)=max(\(A_u\),\(A_v\))×∣\(A_u\)-\(A_v\)∣ 。你需要对于每个节点 i ，计算 \(ans_i=\displaystyle\sum_{u,v∈subtree(i)}f(u,v)\) ，其中 subtree(i) 表示 i 的子树。请你输出 ⊕($ans_i\ mod\ 2^{64}) $ ，其中 ⊕ 表示 XOR。

思路：树上启发式合并+线段树

代码

#include <bits/stdc++.h>
#define int unsigned long long
#define ll unsigned long long
#define mod 1000000007
#define PII pair<int,int>
#define PIII pair<PII,int>
#define double long double
#define endl '\n'
#pragma GCC optimize(3,"Ofast","inline")

using namespace std;

const int N = 1e6 + 5, SZ = N << 2;

ll a[N];
int c[N], vis[N];
vector<int>g[N];
int dp[N][2];
int s1, s2;
int mn =0, mx, sum, ss2;
int n, k, m;
set<PII>qqq;
int qpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1)ans = (ans * x) % mod;
		x = (x * x) % mod;
		y >>= 1;
	}
	return ans;
}

int pos[N];
struct data {
	int tad,cnt;
	ll sum,sum2;
	ll max, min;
} t[N << 2];

void push_up(int u) {
	t[u].cnt = (t[u << 1].cnt + t[u << 1 | 1].cnt);
	t[u].sum = (t[u << 1].sum + t[u << 1 | 1].sum);
	t[u].sum2 = (t[u << 1].sum2 + t[u << 1 | 1].sum2);
	t[u].max = max(t[u << 1].max, t[u << 1 | 1].max);
	t[u].min = min(t[u << 1].min, t[u << 1 | 1].min);
}



void build(int u = 1, int l = 1, int r = N) {
	if (l == r) {
		pos[l] = u;
		t[u].cnt=c[l];
		t[u].sum=l*c[l];
		t[u].sum2=l*l*c[l];
		t[u].max = l;
		t[u].min = l;
		return;
	}
	int mid = (l + r) >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	push_up(u);
}

void add(int p) {
	int u = pos[p];
	t[u].cnt++;
	t[u].max = p;
	t[u].min = p;
	t[u].sum+=p;
	t[u].sum2+=p*p;
	while (u >>= 1)push_up(u);
}

void del(int p) {
	int u = pos[p];
	t[u].cnt--;
	t[u].sum-=p;
	t[u].sum2-=p*p;
	if (!t[u].cnt) {
		t[u].max = 0;
		t[u].min=1e9;
	}
	while (u >>= 1)push_up(u);
}

ll qmax(int L, int R, int u = 1, int l = 1, int r = N) {
	if (R < l || r < L) return 0;
	if (L <= l && r <= R) return t[u].max;
	int mid = (l + r) >> 1;
	return max(qmax(L, R, u << 1, l, mid) , qmax(L, R, u << 1 | 1, mid + 1, r));
}

ll qsum(int L, int R, int u = 1, int l = 1, int r = N) {
	if (R < l || r < L) return 0;
	if (L <= l && r <= R) return t[u].sum;
	int mid = (l + r) >> 1;
	return (qsum(L, R, u << 1, l, mid) + qsum(L, R, u << 1 | 1, mid + 1, r));
}

ll qsum2(int L, int R, int u = 1, int l = 1, int r = N) {
	if (R < l || r < L) return 0;
	if (L <= l && r <= R) return t[u].sum2;
	int mid = (l + r) >> 1;
	return (qsum2(L, R, u << 1, l, mid) + qsum2(L, R, u << 1 | 1, mid + 1, r));
}

ll qcnt(int L, int R, int u = 1, int l = 1, int r = N) {
	if (R < l || r < L) return 0;
	if (L <= l && r <= R) return t[u].cnt;
	int mid = (l + r) >> 1;
	return (qcnt(L, R, u << 1, l, mid) + qcnt(L, R, u << 1 | 1, mid + 1, r));
}

ll qmin(int L, int R, int u = 1, int l = 1, int r = N) {
	if (R < l || r < L) return 1e9;
	if (L <= l && r <= R) return t[u].min;
	int mid = (l + r) >> 1;
	return min(qmin(L, R, u << 1, l, mid) , qmin(L, R, u << 1 | 1, mid + 1, r));
}

int sz[N], big[N], L[N], R[N], Node[N], totdfn;
int cnt[N], totColor;
ll ans[N];

void dfs0(int u, int p) {
	L[u] = ++totdfn;
	Node[totdfn] = u;
	sz[u] = 1;
	for (int v : g[u])
		if (v != p) {
			dfs0(v, u);
			sz[u] += sz[v];
			if (!big[u] || sz[big[u]] < sz[v]) big[u] = v;
		}
	R[u] = totdfn;
}

void dfs1(int u, int p, bool keep) {
	for (int v : g[u])
		if (v != p && v != big[u]) {
			dfs1(v, u, false);
		}
	if (big[u]) {
		dfs1(big[u], u, true);
	}
	for (int v : g[u])
		if (v != p && v != big[u]) {
			for (int i = L[v]; i <= R[v]; i++) {
				ans[u]+=2*qcnt(1,a[Node[i]])*a[Node[i]]*a[Node[i]];
//				cout<<qcnt(1,a[Node[i]])*a[Node[i]]*a[Node[i]]<<endl;
				ans[u]+=2*qsum2(a[Node[i]]+1,N);
//				cout<<qsum2(a[Node[i]]+1,N)<<endl;
				ans[u]-=2*qsum(1,N)*a[Node[i]];
//				cout<<qsum(1,N)*a[Node[i]]<<endl;
				add(a[Node[i]]);
//				cout<<a[Node[i]]<<endl;
//				for (int l = 1; l <= 10; l++) {
//					cout<<qsum(l,l)<<" \n"[l==10];
//				}
			}
		}
	
	ans[u]+=2*qcnt(1,a[u])*a[u]*a[u];
//	cout<<qcnt(1,a[u])*a[u]*a[u]<<endl;
	ans[u]+=2*qsum2(a[u]+1,N);
//	cout<<qsum2(a[u]+1,N)<<endl;
	ans[u]-=2*qsum(1,N)*a[u];
//	cout<<qsum(1,N)*a[u]<<endl;
	add(a[u]);
//	cout<<"ans"<<u<<' '<<ans[u]<<endl;
//	cout<<a[u]<<endl;
//	for (int i = 1; i <= 10; i++) {
//		cout<<qsum(i,i)<<" \n"[i==10];
//	}
	if (keep == false) {
		for (int i = L[u]; i <= R[u]; i++) {
			del(a[Node[i]]);
		}
	}else{
		ans[p]+=ans[u];
	}
}


void solve() {
	int s;
	cin >> n ;
	
	for (int i = 1; i < n; i++) {
		int u, v, x;
		cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
//	for (int i = 1; i <= 10; i++) {
//		cout<<qcnt(i,i)<<" \n"[i==10];
//	}
	build();
	dfs0(1, 0);
	dfs1(1, 0, false);
	ll Ans=0;
	for (int i = 1; i <= n; i++) {
		Ans^=ans[i];
//		cout<<ans[i]<<" \n"[i==n];
	}
	cout<<Ans<<endl;

}

int32_t main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

MST公司

题意：你面对的是一个加权无向图，它包含n顶点 和m没有任何自环的边缘。Sajin 呈现q查询。对于每个顶点集S是给出的。您的目标是确定S并找到其最小生成树的权重。最小生成树 （MST） 是连接的边加权图的边的子集，它以尽可能小的总边权重将所有顶点连接在一起，无需任何循环。在图论的数学领域中，图的诱导子图是另一个图，由图的顶点子集和原始图中的所有边组成，连接该子集中的顶点对。如果诱导子图S已断开连接，输出 -1。

思路：根号分治+prim算法

代码

#include <bits/stdc++.h>
#define ll long long
//#define int long long
#define mod 1000000007
#define PII pair<int,ll>
#define PIII pair<PII,int>
#define double long double
#define endl '\n'
#pragma GCC optimize(3,"Ofast","inline")

using namespace std;

const int N = 1e5 + 5, SZ = N << 2;

int k;
int n, m, h[N], cnte;
int a[N], b[N];
vector<PII>g[N], G[N];
struct S {
	int u;
	ll d;
};

bool operator<(const S &x, const S &y) {
	return x.d > y.d;
}

priority_queue<S> q;
ll dis[N];
bool vis[N];

ll res = 0, cnt = 0;

void Prim(int x) {
	res = 0, cnt = 0;
	for (int i = 0; i < k; i++) {
		dis[b[i]] = 1e18;
		vis[b[i]] = 0;
	}
	dis[x] = 0;
	while (q.size())q.pop();
	q.push({x, 0});
	while (!q.empty()) {
		if (cnt >= n) break;
		int u = q.top().u, d = q.top().d;
//		cout << u << ' ' << d << endl;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		++cnt;
		res += d;
		for (auto[v,w] : g[u]) {
//			cout << v << ' ' << w << 'x' << endl;
			if (w < dis[v] && a[v]) {
				dis[v] = w, q.push({v, w});
			}
		}
	}
}

void Prim1(int x) {
	res = 0, cnt = 0;
	for (int i = 0; i < k; i++) {
		dis[b[i]] = 1e18;
//		cout<<' '<<b[i]<<endl;
		vis[b[i]] = 0;
	}
	dis[x] = 0;
	while (q.size())q.pop();
	q.push({x, 0});
	while (!q.empty()) {
		if (cnt >= n) break;
		int u = q.top().u, d = q.top().d;
		
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		++cnt;
		res += d;
//		cout << u << ' ' << d <<' '//<<res<< endl;
		for (auto[v, w] : G[u]) {
//			cout << v << ' ' << w << 'y' << endl;
//			cout<< dis[v] <<' '<<a[v]<<endl;
			
			if (w < dis[v] && a[v]) {
//				cout<<'t'<<endl;
				dis[v] = w, q.push({v, w});
			}
		}
	}
}

void solve() {
	int q;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		int u, v, x;
		cin >> u >> v >> x;
		g[u].push_back({v,x});
		g[v].push_back({u,x});
	}
	for(int i=1;i<=n;i++){
		sort(g[i].begin(),g[i].end());
	}
	int nn = 3e2;
	
	for (int i = 0; i < q; i++) {
		cin >> k;
		for (int j = 0; j < k; j++) {
			int x;
			cin >> x;
			a[x] = 1;
			b[j] = x;
		}
		if (k < nn) {
			for (int j = 0; j < k; j++) {
				for (int l = 0; l < k; l++) {
					if(j==l)continue;
					PII op={b[l],0};
					int pp=lower_bound(g[b[j]].begin(),g[b[j]].end(),op)-g[b[j]].begin();;
					if(pp<g[b[j]].size()&&a[g[b[j]][pp].first]){
						
						//cout<<g[b[j]][pp].first<<' '<<g[b[j]][pp].second<<endl;
						G[b[j]].push_back(g[b[j]][pp]);
					}
					
				}
			}
		}
		if (k < nn) {
			Prim1(b[0]);
			for (int i = 0; i < k; i++) {
				G[b[i]].clear();
			}
		} else {
			Prim(b[0]);
		}
		for (int j = 0; j < k; j++) {
			a[b[j]]=0;
		}
		if (cnt == k)cout << res << endl;
		else cout << -1 << endl;
//		cout << endl;
	}
	
}

int32_t main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	//cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

标签：Week,7.15,cnt,return,int,SMU,long,ll,define
From： https://www.cnblogs.com/ptlks/p/18314829

相关文章

  • 暑期ACM-Week1（7.15-7.21）
    文章目录知识点基础程序设计技巧万能[头文件](#C++中的输入输出)while执行多次输入循环退出scanf，printf&cin,coutint初定义开数组一般大小：布尔型（bool）基本数据类型取值范围文件输入输出操作浮点数陷阱C++中的输入输出递归案例1：设计一个求阶乘的递归函数案例2：设计一个......
  • 大创项目个人周报（2024.7.15—2024.7.21）
    一、搭建开发环境1.下载AndroidStudio2.运行第一个程序二、入门Kotlin语言1.打印语句的操作，用println()函数funmain(){println("HelloWorld!")}2.变量的定义：在Kotlin中定义变量只有以如下两种方式定义var[变量名称]:[数据类型]val[变量名称]:[数据类型......
  • 大创项目个人周报（24.7.15-24.7.21）
    本周主要利用B站学习Kotlin语言一、完成环境的配置和软件的下载1、开发环境配置安装Java8环境2、IDEA安装与使用熟悉IDEA软件3、熟悉简单代码vara:Int//println("KFCvivo50")二、变量与基本类型1、变量的声明与使用var[变量名称]:[数据类型]例：funmain(......
  • 暑假第三周总结(7.15-7.20)
    这周做了什么继续学习JAVA,做出了城堡游戏点击查看代码//RoompackagecastleV3;importjava.util.HashMap;publicclassRoom{ privateStringdescription;privateHashMap<String,Room>exits=newHashMap<String,Room>();publicRoom(String......
  • SMU Summer 2024 Contest Round 5
    SMUSummer2024ContestRound5RobotTakahashi思路按照Wi......
  • 7.15 ~ 7.19
    7.15~7.17这几天干什么了？放假了，回了趟家。不过在家也没干啥有用的。“我感觉我不适合放两天假，第二天都不知道干啥。”说的挺对。7.18回校第一天，搬到了西扩宿舍，食堂也在西扩。但机房仍然在老校区，路程大概要5~10min。建议延长到位时间，虽然现在来得及但是会很紧。......
  • SMU Summer 2024 Contest Round 5
    ARobotTakahashi思路：将所有数排序，枚举孩子成人的分解点X，同时根据s的标识维护正真的孩子成人的个数voidsolve(){intn;cin>>n;strings;cin>>s;intsum=0;for(inti=0;i<s.size();++i){if(s[i]=='1')sum++;......
  • 7.15 树论
    MilkVisitsG自己做出来哒！先考虑是一条链时怎么做。很显然，用set维护每种奶的位置，然后lowerbound查找\(l\)再判断是否合法即可。那么再放到树上来做，显然，直接树链剖分就可以把树转化成链。于是做完力！点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN......
  • SMU Summer 2024 Contest Round 4
    1.HandV原题链接：http://162.14.124.219/contest/1008/problem/B二进制枚举行列即可查看代码#include<bits/stdc++.h>#defineintlonglong#definePIIpair<int,int>usingnamespacestd;intn,m,k;chara[10][10];signedmain(){ios::sync_with_stdio(fals......
  • 2024.7.15 近期练习
    P3488[POI2009]LYZ-IceSkates我们对于鞋码为\(x\)的人，贪心地，显然先把鞋小的给他穿。所以就有了一个暴力的检验方法：从左往右扫，并对应修改。但是这样太慢。这是一个二分图匹配问题，考虑Hall定理。对于任意\(1\lel\ler\len\)，当\(sum(a_l\sima_r)\le(r-l+1+d)k\)时合......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99