栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

ShanDong Multi-University Training #2(团队训练赛)

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

ShanDong Multi-University Training #2(团队训练赛)

除了敲代码啥也没干,哦还贡献了四发WA。。。我是fw

这次榜有点歪了似乎?

(题好难呐QWQ)

目录

B(思维)

J(数学,规律)

 D(简单计算几何)

L(思维,反向思考)

I(思维,最小生成树)

F(对数保精度)

G(高精度/Python解题,反素数)

B(思维)

找到相距最远的不同的数字。

思路:这个距离一定包括数组的第一个元素或者最后一个元素,这是可以证明的。基于这个思想,那就顺序扫一遍逆序扫一遍数组找到最大值即可。

AC Code:

#include 
#pragma GCC optimize(2)

template 
inline void read(T &x) {
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0', ch = getchar();
	}
	x *= f;
}

template 
void write(T x) {
	if (x < 0)
		putchar('-'), x = -x;
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

#define INF 0x3f3f3f3f
typedef long long ll;
typedef std::pair PII;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
int n;
int a[N];

int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cin >> n ;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}
	int max = -1;
	for (int i = 2; i <= n; i++) {
		if (a[i] != a[1])
			max = std::max(max, i - 1);
	}
	for (int i = n - 1; i >= 1; i--) {
		if (a[i] != a[n])
			max = std::max(max, n - i);
	}
	std::cout << max << 'n';
	return 0;
}

os:签到题我WA了四发QWQ

J(数学,规律)

给出n*m的矩阵,把所有的方格都翻动一遍,相邻被翻到的方格也会翻动一次,开始时方格全部向上问最后有多少方格向下。

思路:每个方格都会被翻动相邻的方格数+1,这样就可以找到规律了,特判n或m等于1的情况。

AC Code:

#include 
#pragma GCC optimize(2)

template 
inline void read(T &x) {
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0', ch = getchar();
	}
	x *= f;
}

template 
void write(T x) {
	if (x < 0)
		putchar('-'), x = -x;
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
ll n, m;

int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cin >> n >> m;
	if (n == 1 && m == 1) {
		std::cout << 1 << 'n';
	} else if (n == 1 || m == 1) {
		std::cout << std::max(m, n) - 2 << 'n';
	} else {
		std::cout << n *m - (2 * (m + n) - 4) << 'n';
	}
	return 0;
}

 D(简单计算几何)

给出一个半圆的圆心坐标和半径和一系列点的坐标,这个半圆可以绕圆心转动,问这个半圆可以同时包括多少点(边界上也算在其中)。

思路:数据范围较小,可以先把在圆内的点筛出来,枚举每个圆内的点的斜率,即这个点和圆心的连线把这个些圆内的点分成两个部分,取两部分的最大值即可,注意斜率不存在时特判,在边界上的点两部分都要算,具体怎样判断某个点在圆的哪个部分,可以将该点的x带入基准点和圆心的连线直线方程中,判断大于等于还是小于等于它本来的y值。

AC Code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
double a, b, r;
int n;
double x[N], y[N];

struct node {
	double x, y;
} e[N];

double getdis(double x, double y) {
	return sqrt((x - a) * (x - a) + (y - b) * (y - b));
}

int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	while (cin >> a >> b >> r) {
		if (r <= 0)
			break;
		cin >> n;
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			cin >> x[i] >> y[i];
			if (getdis(x[i], y[i]) <= r) {
				e[++cnt].x = x[i];
				e[cnt].y = y[i];
			}
		}
		int ans1 = 0, ans2 = 0, maxn = 0;
		for (int i = 1; i <= cnt; i++) {
			ans1 = 0, ans2 = 0;
			if (e[i].x == a) {
				for (int j = 1; j <= cnt; j++) {
					if (e[j].x <= a)
						ans1++;
					if (e[j].x >= a)
						ans2++;
				}
				maxn = max(maxn, max(ans1, ans2));
			} else {
				for (int j = 1; j <= cnt; j++) {
					if ((b - e[i].y) / (a - e[i].x) * (e[j].x - a) + b >= e[j].y)
						ans1++;
					if ((b - e[i].y) / (a - e[i].x) * (e[j].x - a) + b <= e[j].y)
						ans2++;
				}
				maxn = max(maxn, max(ans1, ans2));
			}
		}
		cout << maxn << 'n';
	}
	return 0;
}

os:POJ我是真的无语了,不支持万能头也不支持集合取最大值,仨人围着电脑交了三次CE,乐

L(思维,反向思考)

给出n个骰子,每个骰子可以显示1~d[i]的数字,问给出一个值A,若要用这些骰子组成的和等于A,则分别求每个骰子有几个数一定取不到。

思路:反向思考比较容易,对于第i个骰子,可以取到的最小值是A-(所有最大值的和-该数),可以取到的最小值是A-所有最小值的和+1,这样就可以很容易得到每个数的答案了。

AC Code:

#include 
#pragma GCC optimize(2)

template 
inline void read(T &x) {
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0', ch = getchar();
	}
	x *= f;
}

template 
void write(T x) {
	if (x < 0)
		putchar('-'), x = -x;
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

#define INF 0x3f3f3f3f
typedef long long ll;
typedef std::pair PII;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
int n;
ll k, sum;
ll a[N];

int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cin >> n >> k ;
	sum = 0;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
		sum += a[i];
	}
	for (int i = 1; i <= n; i++) {
		ll min = std::max((ll)1, k - (sum - a[i]));
		ll max = std::min(a[i], k - n + 1);
		ll ans = a[i] - (max - min + 1);
		std::cout << ans << " n"[i == n];
	}
	return 0;
}

os:这个题并不太难,但是一开始的几个小时没有人开这个题。。。

I(思维,最小生成森林)

给出两个字符串,最后是要把两个字符串变成一样的,每次可以选择两个字母任一互换,问最少经过几步使得达到目的。

思路:对于每一对相同位置字母不同,我们可以连一条边,这样就是把这些边连成一个连通图,即求最小生成树,该题是输出最小生成树的路径。

AC Code:

#include 
#pragma GCC optimize(2)

template 
inline void read(T &x) {
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0', ch = getchar();
	}
	x *= f;
}

template 
void write(T x) {
	if (x < 0)
		putchar('-'), x = -x;
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

#define INF 0x3f3f3f3f
typedef long long ll;
typedef std::pair PII;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 35;
int n;
int fa[N];
bool vis[N];
std::string a, b;

void init() {
	for (int i = 0; i < 26; i++)
		fa[i] = i;
}

int getfa(int x) {
	return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

void emerge(int x, int y) {
	int xx = getfa(x);
	int yy = getfa(y);
	fa[xx] = yy;
}

int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
	
	std::cin >> n >> a >> b;
	init();
	std::vectorvec[N];
	for (int i = 0; i < n; i++) {
		int x = a[i] - 'a', y = b[i] - 'a';
		if (x == y)
			continue;
		emerge(x, y);
		vis[x] = vis[y] = true;
	}
	std::vectorv;
	for (int i = 0; i < 26; i++) {
		vec[getfa(i)].push_back(i);
	}
	for (int i = 0; i < 26; i++) {
		if (vec[i].empty())
			continue;
		if (!vis[vec[i][0]])
			continue;
		for (int j = 0; j + 1 < vec[i].size(); j++) {
			v.emplace_back(vec[i][j], vec[i][j + 1]);
		}
	}
	std::cout << v.size() << 'n';
	for (auto u : v) {
		printf("%c %cn", u.first + 'a', u.second + 'a');
	}
	return 0;
}

F(对数保精度)

原来有pink的,要换成blue,问经过一系列变换后最多可以得到多少blue,最多是10,指若大于10则输出10。

思路:记录对于每个变换之前的状态,对于相同的变换取更大的变换,这里对精度要求较高,所以需要用对数将乘法变为加法,使得精度尽可能减少损失。

AC Code:

#include 
#pragma GCC optimize(2)

template 
inline void read(T &x) {
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0', ch = getchar();
	}
	x *= f;
}

template 
void write(T x) {
	if (x < 0)
		putchar('-'), x = -x;
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

#define INF 0x3f3f3f3f
typedef long long ll;
typedef std::pair PII;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
int n, idx;
std::string a, b;
double r;
double ans[N];

int main() {
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::mapmp;
	std::cin >> n ;
	mp["pink"] = ++idx;
	mp["blue"] = ++idx;
	ans[1] = log(1.0);
	ans[2] = -1.0 * INF;
	for (int i = 1; i <= n; i++) {
		std::cin >> a >> b >> r;
		if (!mp[a]) {
			mp[a] = ++idx;
			ans[mp[a]] = -1.0 * INF;
		}
		if (!mp[b]) {
			mp[b] = ++idx;
			ans[mp[b]] = -1.0 * INF;
		}
		ans[mp[a]] = std::max(ans[mp[a]], ans[mp[b]] + log(r));
	}
	ans[2] = std::max(0.0, exp(ans[2]));
	printf("%.15lfn", std::min(ans[2], 10.0));
	return 0;
}

 os:一开始师哥讲的是DP,这个非DP的方法是另一个队的同学想出来的,,,甚至可以想到用对数保精度,,唉差得太多了

G(高精度/Python解题,反素数)

 给出k,问有k个因数的最小值是多少。

思路:这里用到了一个之前我没见过的概念:反素数(详细解释)。

AC Code:

k = int(input())
lim = 1 << 1000
m = float('inf')
prim = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

def dfs(u, k, pv, res) :
    global m
    if u == 12 :
        if k == 1 :
            m = min(m, res)
        return
    now = 1
    for i in range(pv + 1) :
        if res * now > lim :
            break
        if k % (i + 1) == 0 :
            dfs(u + 1, k // (i + 1), i, res * now)
        now *= prim[u]

dfs(0, k, k, 1)
print(m)

os:代码是贴的师哥给的标解,这个题可以用Python也可以C++用高精度乘法,but。。不太会,,我学会了回来补C++代码

别的题补不动了QWQ我太菜了wwwww

若有错误请指教,谢谢!

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/892918.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号