1. 首页
  2. 文章中心
  3. sdnu

SDNU_Winter_Practice_2_20230104「思维」「构造」「二分」「递推数列」「判断存在同构树」C.Problem - 1496D - CodeforcesF.Problem - 1496E - Codeforces G.B - Light It Up (atcoder.jp) H.Problem - 1496C - Codeforces K.E - Lucky Numbers (atcoder.jp)L.F - Pre-order and In-order (atcoder

89 阅读 0 评论
我是靠谱客的博主 贪玩水杯，最近开发中收集的这篇文章主要介绍SDNU_Winter_Practice_2_20230104「思维」「构造」「二分」「递推数列」「判断存在同构树」C.Problem - 1496D - CodeforcesF.Problem - 1496E - Codeforces G.B - Light It Up (atcoder.jp) H.Problem - 1496C - Codeforces K.E - Lucky Numbers (atcoder.jp)L.F - Pre-order and In-order (atcoder，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

6/13 发现其实我也不是很擅长思维，这不是我笨拙的大脑能想出来的东西

C.Problem - 1496D - Codeforces

思路： 

Q若要赢需满足以下几个条件：

  • Q必须选山顶，否则D可以直接堵死。
  • 当Q/D相向而行时，必须保证Q -> D之间的点数必为奇数（但是在选x时无法保证该点于是必须强制D无法如此选择），否则Q将会在自己轮次中无路可走。
  • Q所在山顶通向两边的路必须最大且唯二，否则D会走那条/其他最大路且二人无法相遇，此时D必胜。
  • Q所在山顶通向两遍的路必须相等：
    • 证明：若不等：1.长路为偶数，Q走短路输，Q走长路与D相向也输。2.长路为奇数，Q走短路输，Q走长路时D将选择长路山脚倒数第二点，迫使该路为偶数，Q仍输。由于长路>短路，故长路-1>=短路，等号成立时Q先手Q也先面临无路可走局面，可保证D的永远可选。

总结：Q赢的唯一可能是处于唯二最长路间的山峰，且该最长路为奇数。

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
#define inf 0x3f3f3f3f3f3f3f3f
const int N = 3e5 + 50;
int arr[N], l[N], r[N];

void work() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i];
	}
//刷新从左/从右的上升序列长度，类似oj上前两年的结训赛题_远足
	for (int i = 1; i <= n; i++) {
		if (arr[i] > arr[i - 1])
			l[i] = l[i - 1] + 1;
		else
			l[i] = 1;
	}
	for (int i = n; i >= 1; i--) {
		if (arr[i] > arr[i + 1])
			r[i] = r[i + 1] + 1;
		else
			r[i] = 1;
	}
	int maxx = -1, cnt = 0;
	bool flag = 0;
	for (int i = 1; i <= n; ++i) {
		if (maxx < max(l[i], r[i])) {
			maxx = max(l[i], r[i]);
			flag = 0, cnt = 0;
			if (l[i] == r[i] && l[i] % 2 != 0) {
				flag = 1;
				cnt++;
			}
		} else if (maxx == max(l[i], r[i])) {
			cnt++;
		}
	}
	if (flag && cnt == 1) {
		cout << "1n";
		return;
	}
	cout << "0n";
}

signed main() {
	io;
	work();
	return 0;
}

F.Problem - 1496E - Codeforces

思路：

构造。

  • 题面中一个非常重要的条件是：any two empty cells have no common points (neither edges nor corners)  ，无共边和共角，即在初始图中任一九宫格内最多只有一个X【*】

我们可以将1，4，7…列直接变为X，这样能保证对于每中间两列都可以使任一X可联通。接下来处理各列的联通，我开了一个bool数组，将遍历每中间两列时遇到的第一个X作为桥梁，记录下该两列已存在桥梁。接下来特判m%3是否为0，即最右侧两列是否都不是全X列，若是则使最后列每一个X都与主体联通。最后判断1~m/3+1中是否存在vis=0的情况，即是否存在两列全为 . ，若存在则将该两列的第一行作为桥梁。

注意：遇到需要取模的东西，数组还是从0开始写吧，这坑也太多了点（真的很难一次写对

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
#define inf 0x3f3f3f3f3f3f3f3f
const int N = 3e5 + 50;
char arr[505][505];

void work() {
	int n, m;
	cin >> n >> m;
	bool vis[m / 3 + 5];
	mem(vis, 0);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> arr[i][j];
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (j % 3 == 1)
				arr[i][j] = 'X';
			else if (!vis[(j + 2) / 3] && (j % 3 == 0) && arr[i][j] == 'X') {
				arr[i][j - 1] = 'X';
				vis[(j + 2) / 3] = 1;
			} else if (!vis[(j + 2) / 3] && (j % 3 == 2) && arr[i][j] == 'X') {
				arr[i][j + 1] = 'X';
				vis[(j + 2) / 3] = 1;
			}
		}
	}
	if (m % 3 == 0) {
		for (int i = 1; i <= n; ++i) {
			if (arr[i][m] == 'X') {
				arr[i][m - 1] = 'X';
				//cout << i << m << " ";
			}
		}
	}
	for (int i = 1; i < m / 3 + 1; ++i) {
		if (!vis[i]) {
			arr[1][i * 3 - 1] = 'X';
			arr[1][i * 3] = 'X';
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cout << arr[i][j] ;
			if (j == m)
				cout << "n";
		}
	}
}

signed main() {
	io;
	int t;
	cin >> t;
	while (t--) {
		work();
	}
	return 0;
}

 G.B - Light It Up (atcoder.jp)

思路：

暴力即可。

让每一个不发光的点找到离自己最近的发光点，记录距离，找出最大距离。 

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
#define inf 0x3f3f3f3f3f3f3f3f
const int N = 3e5 + 50;
struct node {
	int x, y;
	double dis = 1.0 * inf;
} arr[N];

double get_dis(node a, node b) {
	double ans = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
	ans = sqrt(ans);
	return ans;
}

void work() {
	int n, k;
	cin >> n >> k;
	vector<int> b(k + 1);
	bool vis[N];
	for (int i = 1; i <= k; ++i) {
		cin >> b[i];
		vis[b[i]] = 1;
	}
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i].x >> arr[i].y;
	}
	double ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (vis[i] == 1)
			continue;
		for (int j = 1; j <= k; ++j) {
			int t = b[j];
			arr[i].dis = min(arr[i].dis, get_dis(arr[i], arr[t]));
		}
		ans = max(ans, arr[i].dis);
	}
	printf("%.8lfn", ans);
}

signed main() {
	io;
	work();
	return 0;
}

 H.Problem - 1496C - Codeforces

思路：

任何两条有交叉的连线一定比没有交叉的连线和长，最优时不让任意两线交叉，排序两个数组逐个计算距离即可。

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
#define inf 0x3f3f3f3f3f3f3f3f
const int N = 3e5 + 50;

double dis(int a, int b) {
	double ans = a * a + b * b;
	ans = sqrt(ans);
	return ans;
}

void work() {
	int n;
	cin >> n;
	vector<int>x, y;
	for (int i = 1; i <= 2 * n; ++i) {
		int a, b;
		cin >> a >> b;
		if (a == 0) {
			if (b < 0)
				b = -b;
			y.pb(b);
		} else {
			if (a < 0)
				a = -a;
			x.pb(a);
		}
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	double ans = 0.0;
	for (int i = 0; i < n; ++i) {
		ans += dis(y[i], x[i]);

	}
	printf("%.12lfn", ans);
}

signed main() {
	io;
	int t;
	cin >> t;
	while (t--) {
		work();
	}
	return 0;
}

 K.E - Lucky Numbers (atcoder.jp)

思路：

思维（递推数列。 

a[i]=a[1]*(-1)^(i+1)+b[i]

b[i]=s[i-1]-b[i-1]

a[1]=(a[i]-b[i])*(-1)^(i+1)

令a[i]=x[j]时，可以求出a[1]=(x[j]-b[i])*(-1)^(i+1)，用map记录下每个a[1]出现的次数，代表当前数作为a[1]时，a[i]=x[j]的不同个数。

  • 推荐一个本题讲的很清楚的博客AtCoder Beginner Contest 255 部分题解_marvel121的博客-CSDN博客
#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
#define inf 0x3f3f3f3f3f3f3f3f
const int N = 3e5 + 50;
int s[N], x[N], b[N];

void work() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i < n; ++i) {
		cin >> s[i];
	}
	for (int i = 1; i <= m; ++i) {
		cin >> x[i];
	}
	for (int i = 1; i <= n; ++i) {
		b[i] = s[i - 1] - b[i - 1];
	}
	map<int, int>mp;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (i % 2 == 1) {
				mp[x[j] - b[i]]++;
			} else {
				mp[b[i] - x[j]]++;
			}
		}
	}
	map<int, int>::iterator i = mp.begin();
	int ans = 0;
	for (i; i != mp.end(); ++i) {
		ans = max(ans, (*i).second);
	}
	cout << ans << 'n';
}

signed main() {
	io;
	work();
	return 0;
}

L.F - Pre-order and In-order (atcoder.jp)

思路：

巧妙的二分。

我个人认为这个做法最大的妙点在于：dfs（或者说二分）搜索的顺序和先序排列的顺序相同

在中序排列中，对于每一个根节点，他的左子孙都在自己左边，右子孙都在自己右边，于是我们在找当前节点时，可以用他在中序中的位置作为左右区间的分界。

在开始二分的时候，我们就可以把1~n的数列看作以1为树根的树，只不过二分端点代表的也是区间而不一定是儿子&&不一定是某一点，但是在每一步操作中，我们可以将每个区间继续二分直到确定到一个叶节点。

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
#define inf 0x3f3f3f3f3f3f3f3f
const int N = 3e5 + 50;
int a[N], id[N], b[N], L[N], R[N];
int tot, flag = 1;

void dfs(int cur, int l, int r) { //根节点（当前节点），根的左右叶节点（不一定是儿子）
	int mid = id[cur]; //当前节点在中序排列的位置
	if (l > mid || r < mid) {
		cout << "-1n";
		flag = 0;
		exit(0);//return跳出函数，exit退出程序
	}
//当mid==l||mid==r时即表示mid没有这个儿子
	if (l < mid) {
		L[cur] = a[++tot]; //由于dfs深搜特性，搜索顺序与先序排列的顺序是相同的
		dfs(a[tot], l, mid - 1); //当前节点变为cur的左儿子
                                 //左儿子的最左子孙是l，最右子孙是mid-1
	}
	if (r > mid) {
		R[cur] = a[++tot];
		dfs(a[tot], mid + 1, r);//这里注意一下
    //不同于普通二分，由于在树种根节点在左右儿子中间，即l<mid<r,所以在找儿子时要空出根的位置
	}
}

void work() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; ++i) {
		cin >> b[i];
		id[b[i]] = i;//记录b[i]在中序排列中的位置
	}
	if (a[1] != 1) {
		cout << "-1n";
		return;
	}
	dfs(a[++tot], 1, n);
	if (!flag)
		return;
	for (int i = 1; i <= n; ++i) {
		cout << L[i] << " " << R[i] << "n";
	}
}

signed main() {
	io;
	work();
	return 0;
}

 M.Problem - 902C - Codeforces

思路：

 只要出现连续两层节点数大于1就会存在同构。

需要注意的几点：

  • 输出的层数是n+1
  • 可以输出上层倒数第二个节点（同构）的条件是本层和上层的节点数都不为1
#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
#define int ll
#define pb push_back
#define mem(a,b) memset(a,b,sizeof a)
#define inf 0x3f3f3f3f3f3f3f3f
const int N = 3e5 + 50;
int arr[N];

void work() {
	int n;
	cin >> n;
	bool flag = 0;
	for (int i = 0; i <= n; ++i) {
		cin >> arr[i];
		if (arr[i] > 1 && arr[i - 1] > 1)
			flag = 1;
	}
	if (!flag) {
		cout << "perfectn";
		return;
	}

	cout << "ambiguousn";
	int root = 0;
	for (int i = 0; i <= n; ++i) {
		for (int j = 1; j <= arr[i]; ++j) {
			cout << root << " ";
		}
		root += arr[i];
	}
	cout << 'n';
	root = 0;
	for (int i = 0; i <= n; ++i) {
		if (arr[i] != 1 && arr[i - 1] != 1) {
			for (int j = 1; j <= arr[i] - 1; ++j) {
				cout << root << " ";
			}
			cout << root - 1 << " ";
			root += arr[i];
		} else {
			for (int j = 1; j <= arr[i]; ++j) {
				cout << root << " ";
			}
			root += arr[i];
		}
	}
	cout << 'n';
}

signed main() {
	io;
	work();
	return 0;
}

下班！

最后

以上就是贪玩水杯为你收集整理的SDNU_Winter_Practice_2_20230104「思维」「构造」「二分」「递推数列」「判断存在同构树」C.Problem - 1496D - CodeforcesF.Problem - 1496E - Codeforces G.B - Light It Up (atcoder.jp) H.Problem - 1496C - Codeforces K.E - Lucky Numbers (atcoder.jp)L.F - Pre-order and In-order (atcoder的全部内容，希望文章能够帮你解决SDNU_Winter_Practice_2_20230104「思维」「构造」「二分」「递推数列」「判断存在同构树」C.Problem - 1496D - CodeforcesF.Problem - 1496E - Codeforces G.B - Light It Up (atcoder.jp) H.Problem - 1496C - Codeforces K.E - Lucky Numbers (atcoder.jp)L.F - Pre-order and In-order (atcoder所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(59)

相关文章

AGC002 D Stamp Rally 整体二分 并查集 整体二分学习笔记
AGC002 D Stamp Rally 整体二分 并查集 整体二分学习笔记
欧几里德 与 扩展欧几里得 学习笔记欧几里得算法扩展欧几里得算法
欧几里德 与 扩展欧几里得 学习笔记欧几里得算法扩展欧几里得算法
深度学习优化器中的变形金刚：Ranger21
深度学习优化器中的变形金刚：Ranger21
@Kubernetes（k8s）安装与集群服务部署详解
@Kubernetes（k8s）安装与集群服务部署详解
SDNU_Winter_Practice_2_20230104「思维」「构造」「二分」「递推数列」「判断存在同构树」C.Problem - 1496D - CodeforcesF.Problem - 1496E - Codeforces G.B - Light It Up (atcoder.jp) H.Problem - 1496C - Codeforces K.E - Lucky Numbers (atcoder.jp)L.F - Pre-order and In-order (atcoder
SDNU_Winter_Practice_2_20230104「思维」「构造」「二分」「递推数列」「判断存在同构树」C.Problem - 1496D - CodeforcesF.Problem - 1496E - Codeforces G.B - Light It Up (atcoder.jp) H.Problem - 1496C - Codeforces K.E - Lucky Numbers (atcoder.jp)L.F - Pre-order and In-order (atcoder
Kubernetes（k8s）安装与集群服务部署详解
Kubernetes（k8s）安装与集群服务部署详解
AGC 010 B Boxes 思维题
AGC 010 B Boxes 思维题
【思维题】【图论】AGC011 C——Squared Graph
【思维题】【图论】AGC011 C——Squared Graph

评论列表共有 0 条评论

立即
投稿
返回
顶部