首页 > 其他分享 >20230821比赛

20230821比赛

时间：2023-08-21 20:11:25浏览次数：348  
标签：return 比赛 20230821 ll int && ans hp

20230821比赛

T1 【佛山市选2013】树环转换 GMOJ 3230

Description

给定一棵N个节点的树，去掉这棵树的一条边需要消耗值1，为这个图的两个点加上一条边也需要消耗值1。树的节点编号从1开始。在这个问题中，你需要使用最小的消耗值（加边和删边操作）将这棵树转化为环，不允许有重边。

环的定义如下：

（1）该图有N个点，N条边。

（2）每个顶点的度数为2。

（3）任意两点是可达的。

树的定义如下：

（1）该图有N个点，N-1条边。

（2）任意两点是可达的。

Input

第一行是一个整数N代表节点的个数。

接下来N-1行每行有两个整数U, V（1 ≤ U, V ≤ N），表示双向边（U, V）

Output

输出把树转化为环的最小消耗值。

Sample Input

4
1 2
2 3
2 4

Sample Output

3

Data Constraint

对于20%的数据，有1≤N≤10。

对于100%的数据，有1≤N≤1000000。

题目大意：求把一棵树转为一个环的最小操作次数

比赛的想法：这不就是求树的直径嘛。对于一棵树，我们可以求出最长的直径 \(d\) ，然后用总边数 \(t = n - 1\) 得到要操作的边为：

\[2\times (t - d)+1 \]

但是这个是错误的，因为有的边可能会多算——删掉自己又加上自己还不如不操作。

正解：不会dp，所以：

我们求出子树有多少条未解决的链，然后删去大于2条链的子树之间的联系（断边）。我们看作ans。最后记得输出 \(2\times ans + 1\) 因为要记录删掉和补上，最后还有一个成环的边。

#include <cstdio>
#define ll int									// 这告诉我们，交之前记得算一下时空复杂度 
ll n;

ll ans;

ll q[1000010][3];

ll head[1000010];
ll nxt[5000010];
ll to[5000010];
ll cnt;

void addEdge(ll u, ll v) {
	++cnt;
	to[cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
}

ll dfs(ll u, ll fa) {
	ll size = 0;								// 子树链的数量 
	for(ll i = head[u]; i; i = nxt[i]) {
		ll v = to[i];
		if(v == fa) continue;
		size += dfs(v, u);
	}
	if(size < 2) return 1;						// 没有链或只有一个链 
	if(fa == 0) {								// 为根节点 
		ans += size - 2;
	} else {
		ans += size - 2 + 1;					// 包括父节点 
	}
	return 0;
}

int main() {
	scanf("%d", &n);
	for(ll i = 1; i < n; i++) {
		ll u, v;
		scanf("%d %d", &u, &v);
		addEdge(u, v);
		addEdge(v, u);
	}
	
	dfs(1, 0);
	
	printf("%d", 2 * ans + 1);
	
	return 0;
}

T2 【佛山市选2013】海明距离 GMOJ 3231

Description

对于二进制串a，b，他们之间的海明距离是指两个串异或之后串中1的个数。异或的规则为：

0 XOR 0 = 0

1 XOR 0 = 1

0 XOR 1 = 1

1 XOR 1 = 0

计算两个串之间的海明距离的时候，他们的长度必须相同。现在我们给出N个不同的二进制串，请计算出这些串两两之间的最短海明距离。

Input

第一个数字是整数T（T≤10），代表数据的组数。

接下来有T组数据，每组数据的第一行是一个正整数N，代表不同的二进制串的个数。接下来是N行，每行都是一个二进制串(长度是5)。我们用数字(0-9)和字符(A-F)来表示这个二进制串。它代表这个二进制串的16进制码。例如，“12345”代表的二进制串为“00010010001101000101”。

Output

对于每个数据，请输出一个整数，即答案值。

Sample Input

2
2
12345
54321
4
12345
6789A
BCDEF
0137F

Sample Output

6
7

Data Constraint

对于30%的数据有1≤N≤100

对于全部数据，有1≤N≤100000

先是打了暴力，然后因为之前做过一道二进制的题目——腿部挂件。题目是可持久化01Trie。

那么这道题会不会也是这个呢？后来发现并不是，所以我打了一个暴力——先枚举 \(1\) 个数字作为基准，然后dfs跑一遍 01Trie ，然后就行了。

后面发现不行，会TLE，怎么办呢？于是我加了一个剪枝——如果当前答案大于最小值就不遍历了。

成功AC。但是我感觉这不应该是正解。

正解应该是什么呢？应该是模拟退火，而且是LBSA（堆优化模拟退火）

下面我附上LBSA和我的代码：

我的暴力：

#include <cstdio>
#include <cstring>
#define ll long long
ll t, n;
bool a[100010][30];
ll son[700010][2];
ll cnt;
ll ans = 1e15;
inline ll min(ll x, ll y) {
	return x > y ? y : x;
}
void dfs(ll x, ll p, ll r, ll tot) {
	if(tot >= ans) return;
	if(x == 20) {
		if(tot == 0) return;
		ans = min(ans, tot);
		return;
	}
	
	if(a[r][x + 1] == 0) {
		if(son[p][1]) {
			dfs(x + 1, son[p][1], r, tot + (a[r][x + 1] != 1));
		}
		if(son[p][0]) {
			dfs(x + 1, son[p][0], r, tot + (a[r][x + 1] != 0));
		}
	}
	if(a[r][x + 1] == 1) {
		if(son[p][0]) {
			dfs(x + 1, son[p][0], r, tot + (a[r][x + 1] != 0));
		}
		if(son[p][1]) {
			dfs(x + 1, son[p][1], r, tot + (a[r][x + 1] != 1));
		}
	}
}
inline char get() {
	static char buf[10000000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,10000000,stdin),p1 == p2) ? EOF : *p1 ++;
}
inline ll read() {
	ll x = 0;
	char c = '.';
	while(c < '0' || c > '9') c = get();
	while(c >= '0' && c <= '9') {
		x = (x << 1) + (x << 3) + (c ^ '0');
		c = get();
	}
	return x;
}
inline ll readHex() {
	ll x = 0;
	char c = '.';
	while(!((c >= '0' && c <= '9') || (c >='A' && c <= 'F'))) c = get();
	while((c >= '0' && c <= '9') || (c >='A' && c <= 'F')) {
		if(c >= '0' && c <= '9') x = (x << 4) + (c ^ '0');
		else x = (x << 4) + (c - 'A' + 10);
		c = get();
	}
	return x;
}
int main() {
//	freopen("data.in", "r", stdin);
	t = read();
	while(t--) {
		memset(son, 0, sizeof(son));
		ans = 1e15;
		cnt = 0;
		n = read();
		for(ll i = 1; i <= n; i++) {
			ll x;
			x = readHex();
			for(ll j = 20; j >= 1; j--) {
				a[i][j] = x&1;
				x >>= 1;
			}
			ll p = 0;
			for(ll j = 1; j <= 20; j++) {
				if(!son[p][a[i][j]]) {
					son[p][a[i][j]] = ++cnt;
				}
				p = son[p][a[i][j]];
			}
		}
		for(ll i = 1; i <= n; i++) {
			dfs(0, 0, i, 0);
		}
		printf("%lld\n", ans);
	}
}

LBSA：

#include<cstdio>
#include<random>
#include<algorithm>
#include<ctime>
#include<cmath>
#define f(x) calc(a[x]^a[v])
using namespace std;
const int N = 1e5 + 2, P = 1 << 20, L = 100 + 2, K = 10, M = 10;
const double RND_MAX = 1ll << 32;
mt19937 rnd(time(NULL));
int T,tt,n,i,a[N],hs,f[P],ans;
double hp[L];
double RND() {
	return rnd()/RND_MAX;
}
int calc(int x) {
	if(f[x]<ans)
		ans=f[x];
	return f[x];
}
int Num(int x) {
	return x<1?1:x>n?n:x;
}
void put(double x) {
	hp[++hs]=x;
	int k=hs;
	while(k>1&&hp[k]>hp[k/2]) {
		swap(hp[k],hp[k/2]);
		k/=2;
	}
	return ;
}
double pop() {
	double ret=hp[1];
	hp[1]=hp[hs--];
	int k=1;
	while(k*2<=hs&&hp[k*2]>hp[k]||k*2+1<=hs&&hp[k*2+1]>hp[k]) {
		int kk=k*2;
		if(kk+1<=hs&&hp[kk+1]>hp[kk])
			++kk;
		swap(hp[k],hp[kk]);
		k=kk;
	}
	return ret;
}
void LBSA(int v) {
	hs=0;
	int x=Num(v+rnd()%11-5);
	double r=0.7;
	for(int i=1; i<L; ++i) {
		int y=Num(x+rnd()%11-5);
		if(f(y)<f(x))
			x=y;
		put(-abs(f(y)-f(x))/log(r));
	}
	x=Num(v+rnd()%11-5);
	for(int k=1; k<=K; ++k) {
		double t=0,temp=hp[1];
		int c=0;
		for(int m=1; m<=M; ++m) {
			int y=Num(x+rnd()%11-5);
			if(f(y)<f(x))
				x=y;
			else {
				double r=RND();
				if(exp(-(f(y)-f(x))/temp)>r) {
					t+=-(f(y)-f(x))/log(r);
					++c;
					x=y;
				}
			}
			if(ans==1) return ;
		}
		if(c) {
			pop();
			put(t/c);
		}
	}
}
int main() {
	f[0]=0;
	for(i=1; i<P; ++i)
		f[i]=f[i&(i-1)]+1;
	f[0]=20;
	scanf("%d",&T);
	for(tt=1; tt<=T; ++tt) {
		scanf("%d",&n);
		for(i=1; i<=n; ++i)
			scanf("%X",&a[i]);
		stable_sort(a+1,a+n+1);
		ans=20;
		for(i=1; i<=n&&ans>1&&(double)clock()/CLOCKS_PER_SEC<0.998/T*tt; ++i)
			LBSA(i);
		printf("%d\n",ans);
	}
	return 0;
}

T3 【佛山市选2013】排列 GMOJ 3232

Description

一个关于n个元素的排列是指一个从{1, 2, …, n}到{1, 2, …, n}的一一映射的函数。这个排列p的秩是指最小的k，使得对于所有的i = 1, 2, …, n，都有p(p(…p(i)…)) = i（其中，p一共出现了k次）。

例如，对于一个三个元素的排列p(1) = 3, p(2) = 2, p(3) = 1，它的秩是2，因为p(p(1)) = 1, p(p(2)) = 2, p(p(3)) = 3。

给定一个n，我们希望从n!个排列中，找出一个拥有最大秩的排列。例如，对于n=5，它能达到最大秩为6，这个排列是p(1) = 4, p(2) = 5, p(3) = 2, p(4) = 1, p(5) = 3。

当我们有多个排列能得到这个最大的秩的时候，我们希望你求出字典序最小的那个排列。对于n个元素的排列，排列p的字典序比排列r小的意思是：存在一个整数i，使得对于所有j < i，都有p(j) = r(j)，同时p(i) < r(i)。对于5来说，秩最大而且字典序最小的排列为：p(1) = 2, p(2) = 1, p(3) = 4, p(4) = 5, p(5) = 3。

Input

输入的第一行是一个整数T（T <= 10），代表数据的个数。

每个数据只有一行，为一个整数N。

Output

对于每个N，输出秩最大且字典序最小的那个排列。即输出p(1), p(2),…,p(n)的值，用空格分隔。

Sample Input

2
5
14

Sample Output

2 1 4 5 3
2 3 1 5 6 7 4 9 10 11 12 13 14 8

Data Constraint

对于40%的数据，有1≤N≤100。

对于所有的数据，有1≤N≤10000。

不会

T4 【佛山市选2013】排列 GMOJ 3229

Description

回文序列是指左右对称的序列。例如1 2 3 2 1是回文序列，但是1 2 3 2 2就不是。我们会给定一个N×M的矩阵，你需要从这个矩阵中找出一个P×P的子矩阵，使得这个子矩阵的每一列和每一行都是回文序列。

Input

第一行有两个正整数N, M。

接下来是n行，代表一个N×M的矩阵，矩阵的每个元素都是值不超过31415926的正整数。

Output

输出符合条件的子矩阵的最大大小P。

Sample Input

5 10
1 2 3 3 2 4 5 6 7 8
1 2 3 3 2 4 5 6 7 8
1 2 3 3 2 4 5 6 7 8
1 2 3 3 2 4 5 6 7 8
1 2 3 9 10 4 5 6 7 8

Sample Output

4

Data Constraint

对于20%数据 1 ≤ N, M ≤ 10

对于所有数据 1 ≤ N, M ≤ 300

正如我想，暴力跑一遍即可。

数据太水啦！

所以正解是什么呢？我觉得是马拉车这位(\(n^2\log n\))。

我的暴力：

#include <cstdio>
#define ll long long
using namespace std;
ll n, m, ans;
ll a[310][310];
inline ll min(ll x, ll y) {
	return x < y?x:y;
}
inline ll read() {
	ll x = 0;
	char c = '.';
	while(c < '0' || c > '9')
		c = getchar();
	while(c >= '0' && c <= '9') {
		x = (x << 1) + (x << 3) + (c ^ '0');
		c = getchar();
	}
	return x;
}
int main() {
	n = read(), m = read();
	for(ll i = 1; i <= n; i++) {
		for(ll j = 1; j <= m; j++) {
			a[i][j] = read();
		}
	}
	for(ll p = min(n, m); p >= 1; p--) {
		for(ll i = 1; i <= n - p + 1; i++) {
			for(ll j = 1; j <= m - p + 1; j++) {
				bool flag = true;
				for(ll x = 1; x <= p; x++) {
					for(ll y = 1; y <= p / 2; y++) {
						if(a[i + x - 1][j + y - 1] != a[i + x - 1][j + p - y] || a[i + y - 1][j + x - 1] != a[i + p - y][j + x - 1]) {
							flag = false;
							break;
						}
					}
					if(!flag) break;
				}
				if(flag) {
					printf("%lld", p);
					return 0;
				}
			}
		}
	}
	printf("%lld", ans);
}

标签：return,比赛,20230821,ll,int,&&,ans,hp
From： https://www.cnblogs.com/znpdco/p/test20230821.html

相关文章

  • 20230819比赛
    T1无聊的草稿GMOJ1752Description图中有N个点，每两点间只有唯一的路径，对于这样一个给定的图，最大的“毛毛虫”会有多大。毛毛虫包含一条主链，毛毛虫中的节点，要不在主链上，要么和主链上某节点相邻，如下图所示有两只合法的毛毛虫，点数越多，毛毛虫越大。Input输入......
  • C++项目实战之演讲比赛流程管理系统
    演讲比赛流程管理系统1.演讲比赛程序需求1.1比赛规则学校举行一场演讲比赛，共有12个人参加。比赛共两轮，第一轮为淘汰赛，第二轮为决赛每名选手都有对应的编号，如10001~10012比赛方式：分组比赛，每组6个人第一轮分为两个小组，整体按照选手编号进行抽签后顺序演讲10个......
  • 20230818比赛
    T1休息(rest)Description休息的时候，可以放松放松浑身的肌肉，打扫打扫卫生，感觉很舒服。在某一天，某LMZ开始整理他那书架。已知他的书有n本，从左到右按顺序排列。他想把书从矮到高排好序，而每一本书都有一个独一无二的高度Hi。他排序的方法是：每一次将所有的书划分为尽量少的连续部......
  • 比赛策略分析
    CSP-S时长为4小时，需要将4小时灵活分配在4道题上，以拿到最高的分。整体策略考试开始时先将所有题全部浏览一遍（大约\(20min\)）切掉快速能切的题。然后就开始磕。每道题一次磕的时间不要太短，大约\(30min\)比较合适。磕不出来就换下一道。在思维间隔期间养成习惯留意自己......
  • 智能照明控制系统在体育馆乒乓球比赛场地中的设计与应用
    未晓妃安科瑞电气股份有限公司上海嘉定201801摘要：在早期的体育建设中，大多较为注重体育赛场的规糢形式，随着体育建筑的不断发展，人们对体育场地的功能性、设备情况、安全舒适程度和绿色环保情况越来越重视。智能系统开始在体育场馆建设中应用，而智能照明是智能系统的重要组成部分。在......
  • 20230816比赛
    T1矩形Description现在我们在一个平面上画了n个矩形。每一个矩形的两边都与坐标轴相平行，且矩形定点的坐标均为整数。现我们定义满足如下性质的图形为一个块：每一个矩形都是一个块；如果两个块有一段公共的部分，那么这两个块就会形成一个新的块，否则这两个块就是不同的。示......
  • 【比赛】8.16
    Ⅰ.LYKlovesstring通过限定元素的先后可以将\(10^10\)优化成\(10!\)，再加一些剪枝就可以过了。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintmod=1e9+7;intread(){ intx=0,f=1;charch=getchar(); while(ch<'0'||......
  • 【比赛】8.14
    Ⅰ.妹子第一题考虑被包含的矩阵需不需要旋转，如上图，我们可以枚举\(x\)来判断是否可行。#include<bits/stdc++.h>#definedbdouble#defineeqs1e-6usingnamespacestd;intread(){ intx=0,f=1;charch=getchar(); while(ch<'0'||ch>'9'){if(ch==......
  • 某谷 Rated 比赛泛做
    P9535「YsOI2023」连通图计数非常好题目，爱来自湖南。\(m=n-1\)等价于给定度数求树的个数，这是一个经典题，在「HNOI2004」树的计数有描述，即利用Prufer序列得到答案为\(\binom{n-2}{(d_1-1)(d_2-1)\ldots(d_n-1)}\)。\(m=n\)即基环树，对于整个大环建立一个虚点，该点向环上的所......
  • 【比赛】8.13
    Ⅰ.波状数列考试时想到的是用\(f_{i,0/1}\)表示用了前\(i\)个数，其中第一个数是山峰还是山谷。比较麻烦。之前看题解做的时候，用\(f_{i,j}\)表示用了前\(i\)个数，其中第一个数是\(j\)，滚动数组优化一下。点击查看代码#include<bits/stdc++.h>#defineintlonglongc......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99