首页 > 其他分享 >杭电多校第一场补题

杭电多校第一场补题

时间：2023-07-23 13:11:08浏览次数：44  
标签：tmp 杭电多校 return int ll tr while 补题 第一场

杭电多校第一场

1001 Hide-And-Seek Game

题意：给出一棵树，每次询问第一个人从Sa-Sb之间来回走，第二个人在Ta-Tb之间来回走，最早相遇的节点，如果无法相遇就输出-1

做法：由于数据量是1e3级别，因此对于每一条路径都可以使用暴力找祖先的方法求出路径，然后对于路径上的每一个节点，其出现的时间都是模上两倍路径长度后的某一个值或者某两个值，因此找到路径后问题就转换成x=a1(mod m1), x= a2(mod m2)的同余方程组的最小解问题，由于模m可能有两个值，因此最多有四个同余方程组，依次求解找最小值即可，求解可以使用扩展中国剩余定理。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 3e3 + 10;
int n, m;
ll ai[5], mi[5];
int dep[maxn];
int fa[maxn];
vector<int>edges[maxn];

ll exgcd(ll a, ll b, ll &x, ll &y){
	if(b == 0){
		x = 1, y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, y, x);
	y -= a/b * x;
	return d;
}

ll excrt(){
	ll x, y;
	ll m1 = mi[1], a1 = ai[1];
	ll ans = 0;
	ll a2 = ai[2], m2 = mi[2];
	ll a = m1, b = m2, c = (a2 - a1 % m2 + m2) % m2;
	ll d = exgcd(a , b, x , y);
	if(c % d != 0) return -1;
	x = x * (c / d) % (b / d);
	ans = a1 + x * m1;
	m1  = m2 / d  * m1;
	ans = (ans % m1 + m1) % m1;
	return ans;
}

ll lcm(ll a, ll b){
	return (a * b) / __gcd(a, b);
}

void dfs(int u, int fath){
	fa[u] = fath;
	dep[u] = dep[fath] + 1;
	for(auto v : edges[u]){
		if(v != fath){
			dfs(v, u);
		}
	}
}

int lca(int u, int v){
	if(dep[u] > dep[v]) swap(u, v);
	while(dep[v] != dep[u]) v = fa[v];
	if(u == v) return u;
	while(fa[u] != fa[v]){
		u = fa[u];
		v = fa[v];
	}
	return fa[u];
}


void solve(){
	cin>>n>>m;
	for(int i = 0; i <= n; i++) edges[i].clear();
	for(int i = 1; i <= n - 1; i++){
		int u, v;
		cin>>u>>v;
		dep[i] = 0;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	dep[n] = 0;
	dfs(1, 0);

	while(m--){
		int sa, sb, ta, tb;
		cin>>sa>>sb>>ta>>tb;
		vector<int>path1;
		vector<int>path2;
		vector<int>tmp;

		int u = lca(sa, sb);
		while(sa != u){
			path1.push_back(sa);
			sa = fa[sa];
		}
		path1.push_back(u);
		while(sb != u){
			tmp.push_back(sb);
			sb = fa[sb];
		}
		reverse(tmp.begin(), tmp.end());
		for(auto x : tmp){
			path1.push_back(x);
		}	
		tmp.clear();


		u = lca(ta, tb);
		while(ta != u){
			path2.push_back(ta);
			ta = fa[ta];
		}
		path2.push_back(u);
		while(tb != u){
			tmp.push_back(tb);
			tb = fa[tb];
		}
		reverse(tmp.begin(), tmp.end());
		for(auto x : tmp){
			path2.push_back(x);
		}

		tmp.clear();
		tmp = path1;
		reverse(tmp.begin(), tmp.end());
		int len = tmp.size();
		for(int i = 1; i < len - 1; i++) path1.push_back(tmp[i]);

		tmp.clear();
		tmp = path2;
		reverse(tmp.begin(), tmp.end());
		len = tmp.size();
		for(int i = 1; i < len - 1; i++) path2.push_back(tmp[i]);



		
		ll mod1 = path1.size();
		ll mod2 = path2.size();

		map<int ,int>mp[3];

		for(int i = 0; i < mod1; i++){
			if(!mp[1][path1[i]]) mp[1][path1[i]] = (i + 1) % mod1;
			else mp[2][path1[i]] = (i + 1) % mod1;
		}

		ll mina = 1e16;
		int ans = -1;
		for(int i = 0; i < mod2; i++){
			int a = (i + 1) % mod2;
			if(mp[1].count(path2[i])){
				ai[1] = mp[1][path2[i]];
				mi[1] = mod1;
				ai[2] = a;
				mi[2] = mod2;
				ll res = excrt();
				if(res != -1){
					if(res == 0){
						res = lcm(mod1, mod2);
					}

					if(res < mina){
						mina = res;
						ans = path2[i];
					}
				}
			}
			if(mp[2].count(path2[i])){
				ai[1] = mp[2][path2[i]];
				mi[1] = mod1;
				ai[2] = a;
				mi[2] = mod2;
				ll res = excrt();
				if(res != -1){
					if(res == 0){
						res = lcm(mod1, mod2);
					}

					if(res < mina){
						mina = res;
						ans = path2[i];
					}
				}
			}
		}

		cout<<ans<<"\n";

	}
}

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

	return 0;
}

1005 Cyclically Isomorphic

题意：给n个长度为m的字符串，给出q个询问，每次询问第x和第y个字符串是否能够通过循环右移相等

做法：用最小表示法求循环右移过程中字典序最小的字符串，然后比较这些字符串是否相等即可

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int n, m, q;
string s[maxn];


string getmin(string x){
	string res;
	int n = x.size();
	x = x + x;
	int i = 0, j = 1;
	int len = x.size();
	while(j < n){
		int k = 0;
		while(k < n - 1 && x[i + k] == x[j + k]){
			k++;
		}

		if(x[i + k] > x[j + k]){
			i += k + 1;
		}
		else{
			j += k + 1;
		}
		if(i == j) j++;
		if(i > j) swap(i, j);
	}

	for(int p = i; p <= i + n - 1; p++){
		res += x[p];
	}
	return res;
}

void solve(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++){
		cin>>s[i];
		s[i] = getmin(s[i]);
	}

	cin>>q;
	while(q--){
		int x, y;
		cin>>x>>y;
		if(s[x] == s[y]) cout<<"Yes\n";
		else cout<<"No\n";
	}
}

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

1009 Assertion

题意：鸽巢原理

做法：判断m *(d - 1)和n的大小关系即可

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void solve(){
	ll n, m, d;
	cin>>n>>m>>d;
	if((d - 1)  * n < m){
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
}

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

1010 Easy problem I

题意：给n个数，有m次询问，有两种操作，第一种将[l,r]上的每个a[i]，让a[i] = abs(a[i] - x)，第二种则是询问[l,r]的区间和。并且x的给出是递增的。

做法：可以发现，对于每个a[i]，假设当前为x[i], a[i] = x[i] - a[i] < x[i] < x[i + 1]，因此当一个数小于给出的x之后，每次对这个数的操作都是乘上-1再加上x，否则就是每次都减去x，可以考虑建两棵线段树，第一棵树用来维护x < a[i]的情况，第二棵用来维护x > a[i]的情况，并且由于从第一棵树转到第二棵树之后的不可能再转回来，因此考虑在第二棵树上单点修改暴力转移，复杂度O(nlogn)，剩下的部分就是线段树的区间加、区间乘和单点改的操作。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 10;
const  ll inf = 1e16;
int n, m;
ll a[maxn];


struct info1{
	ll sum, mn, cnt;//通过最小值来对点进行分类
};

struct info2{
	ll sum, cnt;
};


struct tag2{
	ll mul, add;
};

info2 operator+(info2 a, info2 b){
	return info2{
		a.sum + b.sum,
		a.cnt + b.cnt
	};
}

info2 operator+(info2 a, tag2 tag){
	return info2{
		a.sum * tag.mul + a.cnt * tag.add,
		a.cnt
	};
}

tag2 operator+(tag2 a, tag2 b){
	return tag2{
		a.mul * b.mul,
		a.add * b.mul + b.add
	};
}

info1 operator+(info1 a, info1 b){
	return info1{
		a.sum + b.sum,
		min(a.mn, b.mn),
		a.cnt + b.cnt
	};
}

info1 operator+(info1 a, int tag){
	return info1{
		a.sum + tag * a.cnt,
		a.mn + tag,
		a.cnt
	};
}


struct tree2{
	struct node{
		int l, r;
		info2 info;
		tag2 tag;
	}tr[maxn * 4];



	void pushtag(int p, tag2 tag){
		tr[p].info = tr[p].info + tag;
		tr[p].tag = tr[p].tag + tag;
	}

	void pushdown(int p){
		if(tr[p].tag.mul != 1 || tr[p].tag.add != 0){
			pushtag(p << 1, tr[p].tag);
			pushtag((p << 1) + 1, tr[p].tag);
			tr[p].tag = {1, 0};
		}
	}


	void build(int p, int l, int r){
		tr[p] = {l, r};
		tr[p].info = {0, 0};
		tr[p].tag = {0, 0};
		if(l == r) return;
		int mid = (l + r) >> 1;
		build(p << 1, l, mid);
		build((p << 1) + 1, mid + 1, r);
	}

	void update(int p, int pos, ll val){
		if(tr[p].l == tr[p].r){
			tr[p].info = {val, 1};
			return;
		}
		pushdown(p);
		int mid = (tr[p].l + tr[p].r ) >> 1;
		if(pos <= mid) update(p << 1, pos, val);
		else update((p << 1) + 1, pos , val);
		tr[p].info = tr[p << 1].info + tr[(p << 1) + 1].info;
	}

	info2 query(int p, int ql, int qr){
		if(tr[p].l >= ql && tr[p].r <= qr) return tr[p].info;
		pushdown(p);
		int mid = (tr[p].l + tr[p].r) >> 1;
		if(qr <= mid) return query(p << 1, ql, qr);
		if(ql > mid) return query((p << 1) + 1, ql, qr);
		return query(p << 1, ql, qr) + query((p << 1) + 1, ql, qr);
	}

	void modify(int p, int l, int r, ll mul, ll add){
		if(tr[p].l >= l && tr[p].r <= r){
			pushtag(p, tag2{mul, add});
			return;
		}
		pushdown(p);
		int mid = (tr[p].l + tr[p].r) >> 1;
		if(l <= mid) modify(p << 1, l, r, mul, add);
		if(r > mid) modify((p << 1) + 1, l, r, mul, add);
		tr[p].info = tr[p << 1].info + tr[(p << 1) + 1].info;
	}
}t2;

struct tree1{
	struct node{
		int l, r;
		info1 info;
		ll tag;
	}tr[4 * maxn];


	void pushtag(int p, ll tag){
		tr[p].info = tr[p].info + tag;
		tr[p].tag += tag;//标记叠加
	}

	void pushdown(int p){
		if(tr[p].tag){
			pushtag(p << 1, tr[p].tag);
			pushtag((p << 1) + 1, tr[p].tag);
			tr[p].tag = 0;
		}
	}

	void build(int p, int l, int r){
		tr[p] = {l, r};
		tr[p].tag = 0;
		if(l == r){
			tr[p].info = {a[l], a[l], 1};
			return;
		}

		int mid = (l + r) >> 1;
		build(p << 1, l, mid);
		build((p << 1) + 1, mid + 1, r);
		tr[p].info = tr[p << 1].info + tr[(p << 1) + 1].info;
	}

	void update(int p, int l, int r, ll val){
		if(tr[p].l >= l && tr[p].r <= r){
			//如过当前区间的最小值大于要减的值，那么就等价于当前区间减去val
			if(tr[p].info.mn > val){
				pushtag(p, -val);
				return;
			}
			//执行以下程序说明最小值小于要减去的值，那么此时就会涉及到区间部分值需要取反
			if(tr[p].l == tr[p].r){
				t2.update(1, tr[p].l, val - tr[p].info.mn);
				tr[p].info = {0, inf, 0};
				return;
			}

			pushdown(p);
			update(p << 1, l, r, val);
			update((p << 1) + 1, l, r, val);
			tr[p].info = tr[p << 1].info + tr[(p << 1) + 1].info;
			return;
		}

		pushdown(p);
		int mid = (tr[p].l + tr[p].r) >> 1;
		if(l <= mid) update((p << 1), l, r, val);
		if(r > mid) update((p << 1) + 1, l, r, val);
		tr[p].info = tr[p << 1].info + tr[(p << 1) + 1].info;
	}

	info1 query(int p, int ql, int qr){
		if(tr[p].l >= ql && tr[p].r <= qr) return tr[p].info;
		pushdown(p);
		int mid = (tr[p].l + tr[p].r) >> 1;
		if(qr <= mid) return query(p << 1, ql, qr);
		if(ql > mid) return query((p << 1) + 1, ql, qr);
		return query(p << 1, ql, qr) + query((p << 1) + 1, ql, qr);
	}
}t1;

void solve(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
	}

	t1.build(1, 1, n);
	t2.build(1, 1, n);
	while(m--){
		int op;
		cin>>op;
		if(op == 1){
			int l, r, x;
			cin>>l>>r>>x;
			t2.modify(1, l, r, -1, x);
			t1.update(1, l, r, x);
		}
		else{
			int l ,r;
			cin>>l>>r;
			ll ans = t1.query(1, l, r).sum + t2.query(1, l, r).sum;
			cout<<ans<<"\n";
		}
	}
}

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

标签：tmp,杭电多校,return,int,ll,tr,while,补题,第一场
From： https://www.cnblogs.com/pang-bai/p/17574902.html

相关文章

  • 2023牛客暑期多校训练营2 补题
    D.TheGameofEating题意：有n个人和m道菜，每个人对每个菜的都有一个喜好度a[i][j]，所有人都知道其他人的喜好度，现在需要上k道菜，从1，2...，n，1，2.....的顺序来选，如果每个人都只考虑自己的喜好，问最后哪些菜会被端上来Solution我们考虑到所有人都知道其他人的喜好度，也就是说，假设当前要选......
  • 2023牛客多校7.21补题
    D-TheGameofEating题意：一共有m道菜，n个人轮流点一道菜，一共点k道。第i个人对第j道菜的喜爱程度\(A_{i,j}\)对所有人公开，一个人点了菜所有人都可以吃到。每个人都希望最大化自己的喜爱程度之和，求最终的点菜集合。分析：很容易想到每个人点菜时都点当前剩下的菜中自己最喜爱的，但是......
  • Codeforces Round 886 (Div. 4)补题
    CodeforcesRound886(Div.4)A~D://A:boolsolve(){ cin>>a[1]>>a[2]>>a[3]; sort(a+1,a+4); returna[2]+a[3]>=10?1:0;}//B:voidsolve(){ intn; cin>>n; intmaxa=0; intnum=0; intx,y; for(inti=1;i<=n;i++){cin>......
  • 暑假补题记2
     题解：主要是对于炸弹时间的处理，直接让时间赋值给数组，进行判断即可，跑一遍bfs的板子就可以了。#include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<cmath>//#defineintlonglongu......
  • 2023杭电多校第二场
    目录1009StringProblem比赛地址：传送门这回过了三个题，后面4个小时都在坐牢~1009StringProblem题意：给你一个字符串，让你找成对不相交的子串，每个子串仅由一个字符组成，其对于答案的贡献为子串长度-1，问你最大化贡献。思路：就是判断是否有相邻位均为同一字符串，如果则++ans......
  • 2023杭电多校第二场
    1001求个SG然后打表发现$SG=0$的点满足$t=k_1*(4*K+2)+(K+1)$#include<bits/stdc++.h>usingnamespacestd;intT,N;intmain(){cin>>T;while(T--){intN,K;cin>>K>>N;if(N<=K)cout<<&......
  • 2023牛客多校7.17补题
    当时就做了两道签到题DJ，这两天补了四道简单题HKLMD-Chocolate题意：\(n×m\)的巧克力，Kelin先手，WalkAlone后手，每人每次拿走一块左下角为\((1,1)\)的子矩形的巧克力，谁拿走\((n,m)\)处的巧克力谁输。分析：这是一道结论题，只有\(1×1\)的时候后手赢，其余情况下都是先手赢。证明......
  • 牛客暑假多校 2023 第一场
    目录写在前面LH写在前面比赛地址：https://ac.nowcoder.com/acm/contest/57355。官方题解写得太好了都感觉没有自己整理的必要。简单写写有启发性的东西。我是垃圾。L发现进行三次操作后有：\[(x,y,z)\rightarrow(a_{b_{c_x}},b_{c_{a_{y}}},c_{a_{b_{z}}})\]每个位置仅......
  • HDU 暑假多校 2023 第一场
    目录写在前面72837279727672757284写在最后写在前面补题地址：HDUOJ题库第63页，题号7275~7286。以下题号以题库中题号为准。题目选补，按照个人认为题目难度排序，因为我是菜狗。打这场看到马娘题目直接整个人兴奋，于是推了3h推不出来滚粗了。以为是手玩题没想到是正统博弈论呃......
  • 【游记】2023杭电多校
    前言组队情况：team943wsyear-chengcheng567-ShaoJiaDay1赛果：solved10/12,rank4,1firstblood赛前约定ShaoJia开前\(4\)题，chengcheng567开中间\(4\)题，我开后\(4\)题。于是开场先看1009，一眼签到，直接过了，但是差\(5\)秒一血（但阻止不了我拿另一个一血）......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99