第十七届浙大城市学院程序设计竞赛（同步赛）

A	Sumo and Keyboard-Ca t

题意：有一个键盘，一开始是大写，按一次capslock切换大小写，给出键盘输入的字符串，问最少按capslock的次数

做法：签到题，每次切换大小写贡献+1

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 5e5 + 5;
char s[MAXN];
int main()
{
	sc("%s", s);
	int len = strlen(s);
	int f = 1, ans = 0;
	for (int i = 0; i < len; i++)
	{
		if (islower(s[i]))
		{
			if (f == 1)
			{
				ans++;
				f = 0;
			}
		}
		else
		{
			if (f == 0)
			{
				ans++;
				f = 1;
			}
		}
	}
	pr("%d\n", ans);
}

B	Sumo and His Followers

题意：给出每个人花费的时间，同时只能有一个人问问题，求所有人问问题的最小等待时间

做法：等待时间等于 $\sum_{i=1}^n a[i]*(n-i-1)$ ，其中 a[i] 是第 i 个人花费的时间， n-i+1 是这个人后面人的个数，可以发现，只需要将 a 按照从小到大的顺序排序，即可使得最小等待时间最小

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 5e5 + 5;
int a[MAXN];
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n;
		sc("%d", &n);
		for (int i = 1; i <= n; i++)
			sc("%d", &a[i]);
		sort(a + 1, a + 1 + n);
		ll ans = 0;
		for (int i = 1; i <= n; i++)
		{
			a[i] += a[i - 1];
			ans += a[i - 1];
		}
		double res = 1.0 * ans / n;
		pr("%.2lf\n", res);
	}
}

C	Sumo and Virus

题意：按照题意模拟每天的疫情人数

做法：注意题目做的从第 8 天开始，这个人感染的人在第 8 天算作那个人的第一天，注意治愈的人不会再感染，所以我们只需要维护每天感染的人数和还能感染的人数即可，然后考虑每天感染的人数不能超过总人数减去治愈的人减去正在感染的人即可。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 5e5 + 5;
ll a[15];
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		memset(a, 0, sizeof(a));
		ll x, m, n, tot = 1;
		sc("%lld%lld%lld", &x, &m, &n);
		a[1] = 1;
		for (int i = 1; i < n; i++)
		{
			ll t = a[7] + a[8] + a[9] + a[10] + a[11] + a[12] + a[13];
			m -= a[14];
			tot -= a[14];
			for (int j = 14; j >= 2; j--)
				a[j] = a[j - 1];
			if (tot + t * x > m)
			{
				a[1] = m - tot;
				tot = m;
			}
			else
			{
				a[1] = t * x;
				tot += t * x;
			}
		}
		ll t = a[8] + a[9] + a[10] + a[11] + a[12] + a[13];
		pr("%lld\n", t);
	}
}

D	Sumo and Easy Sum

题意：已知 a 数组是斐波那契数列，给出 k，求 $S_n=\sum_{i=1}^{\infty}\frac{a_i}{k^i}$

做法：高中数学，求数列前 n 项和错位相减法（一般来说，错位相减法只能做等差数列乘等比数列的式子，但由于斐波那契数列存在 a[n-2]=a[n]-a[n-1]，所以也可以用错位相减）

$S_n=\sum_{i=1}^{\infty}\frac{a_i}{k^i}$ $S_n=\sum_{i=1}^{\infty}\frac{a_i}{k^i}$ $S_n=\sum_{i=1}^{\infty}\frac{a_i}{k^i}$ $S_n=\sum_{i=1}^{\infty}\frac{a_i}{k^i}$

$\frac{S_n}{k}=\sum_{i=1}^{\infty}\frac{a_i}{k^{i+1}}$

两式相减得到 $S_n-\frac{S_n}{k}=\frac{1}{k}+\sum_{i=1}^{\infty}\frac{a_{i-1}}{k^{i+1}}$

$S_n-\frac{S_n}{k}=\frac{1}{k}+\frac{S_n}{k^2}$

$S_n=\frac{k}{k^2-k-1}$

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
ll gcd(ll a, ll b)
{
	return b == 0 ? a : gcd(b, a % b);
}
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		ll k;
		sc("%lld", &k);
		ll ans1 = k, ans2 = k * k - k - 1;
		ll g = gcd(ans1, ans2);
		ans1 /= g;
		ans2 /= g;
		pr("%lld", ans1);
		if (ans2 != 1)
			pr("/%lld",ans2);
		pr("\n");
	}
}

F	Sumo and Luxury Car

题意：有 n 辆车，你每次选择若干辆车，然后再在你选择的车里面选出一辆，如果你选择的车不一样或者你最后选的一辆不一样则算作不同的情况，求有多少种情况

做法：先考虑最后一次取一辆车，然后剩下的 n-1 辆车是否在第一次取的车里面即可，所以最后答案是 $n*2^{n-1}$

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 5e5 + 5;
const ll mod = 1e9 + 7;
ll power(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    int T;
    sc("%d", &T);
    while (T--)
    {
        ll n, ans = 0;
        sc("%lld", &n);
        ans = n * power(2, n - 1) % mod;
        pr("%lld\n", ans);
    }
}

H	Sumo and Electricity(Easy)

题意：有 n 个核电站，每个核电站有一个耗电量，存在 m 条电缆，电缆的功率为两个核电站的耗电量的异或值，现在已知有一个核电站的耗电量未知，求在满足电缆的总功耗最低的前提下，核电站总耗电量最低，并输出这两个值。

做法：考虑到只有一个核电站的耗电量未知，并且只有和这个核电站连边的电缆功率未知，所以我们考虑将这个核电站的连边的点按位统计，如果出现 1 的次数大于 0 的次数，说明未知耗电量的核电站的耗电量的这一位是 1 的话，可以满足电缆总功耗最小，如果出现 1 的次数小于 0 的次数，那么这一位放 0 满足电缆总功耗最小，如果相等，考虑第二个条件，核电站的总功率最小，这时，我们这一位放 0。在知道了这个核电站耗电量的情况下，直接遍历即可算出题目所求的两个答案

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 5005;
struct edge
{
	int to;
	int nex;
}e[MAXN * 2];
int head[MAXN], tot;
void init()
{
	memset(head, -1, sizeof(head));
	tot = 1;
}
void add(int a, int b)
{
	e[tot] = edge{ b,head[a] };
	head[a] = tot++;
}
ll val[MAXN];
int wei[32][2];
int main()
{
	init();
	int n, m, rot = 0;
	sc("%d%d", &n, &m);
	ll ans1 = 0, ans2 = 0;
	for (int i = 1; i <= n; i++)
	{
		sc("%lld", &val[i]);
		if (val[i] == -1)
			rot = i;
		else
			ans2 += val[i];
	}
	while (m--)
	{
		int a, b;
		sc("%d%d", &a, &b);
		if (val[b] == -1)
			swap(a, b);
		if (val[a] != -1)
			ans1 += val[a] ^ val[b];
		add(a, b);
		add(b, a);
	}
	for (int i = head[rot]; i + 1; i = e[i].nex)
	{
		int v = e[i].to;
		for (int j = 0; j <= 30; j++)
		{
			if (val[v] & (1LL << j))
				wei[j][1]++;
			else
				wei[j][0]++;
		}
	}
	val[rot] = 0;
	for (int i = 0; i <= 30; i++)
	{
		if (wei[i][0] < wei[i][1])
			val[rot] += (1LL << i);
	}
	ans2 += val[rot];
	for (int i = head[rot]; i + 1; i = e[i].nex)
	{
		int v = e[i].to;
		ans1 += val[rot] ^ val[v];
	}
	pr("%lld\n%lld\n", ans1, ans2);
}

J	Sumo and Balloon

题意：有一个气球，你每秒能吹入一定单位的气体，气球可以看作一个球体，直径大于等于一定大小就会爆炸，问气球什么时候爆炸

做法：如果我们可以求出气球的体积，那么我们就可以算出气球爆炸的时间，那么我们只需要算出球的直径即可，点到直线的距离，列式子求出平面的一般式，然后直接套公式即可（直接上几何板子也行）

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
//三维几何
const double eps = 1e-8;
const double PI = acos(-1.0);
int sgn(double x) {
	if (fabs(x) < eps)return 0;
	if (x < 0)return-1;
	else return 1;
}
struct Point3 {
	double x, y, z;
	Point3(double _x = 0, double _y = 0, double _z = 0) {
		x = _x;
		y = _y;
		z = _z;
	}
	void input() {
		scanf("%lf%lf%lf", &x, &y, &z);
	}
	Point3 operator-(const Point3& b)const {
		return Point3(x - b.x, y - b.y, z - b.z);
	}
	Point3 operator +(const Point3& b)const {
		return Point3(x + b.x, y + b.y, z + b.z);
	}
	Point3 operator *(const double& k)const {
		return Point3(x * k, y * k, z * k);
	}
	Point3 operator /(const double& k)const {
		return Point3(x / k, y / k, z / k);
	}
	double operator *(const Point3& b)const {
		return x * b.x + y * b.y + z * b.z;
	}
	Point3 operator ^(const Point3& b)const {
		return Point3(y * b.z - z * b.y, z * b.x - x * b.z, x * b.y - y * b.x);
	}
};
struct Line3
{
	Point3 s, e;
	Line3() {}
	Line3(Point3 _s, Point3 _e)
	{
		s = _s;
		e = _e;
	}
};
struct Plane
{
	Point3 a, b, c, o;//平面上的三个点，以及法向量
	Plane() {}
	Plane(Point3 _a, Point3 _b, Point3 _c)
	{
		a = _a;
		b = _b;
		c = _c;
		o = pvec();
	}
	Point3 pvec()
	{
		return (b - a) ^ (c - a);
	}
	//平面和直线的交点，返回值是交点个数
	int crossline(Line3 u, Point3& p)
	{
		double x = o * (u.e - a);
		double y = o * (u.s - a);
		double d = x - y;
		if (sgn(d) == 0)return 0;
		p = ((u.s * x) - (u.e * y)) / d;
		return 1;
	}
	//点到平面最近点 (也就是投影)
	Point3 pointtoplane(Point3 p)
	{
		Line3 u = Line3(p, p + o);
		crossline(u, p);
		return p;
	}
};
int main()
{
	double l;
	sc("%lf", &l);
	Point3 o; o.input();
	Point3 a, b, c;
	a.input();
	b.input();
	c.input();
	Plane p = Plane(a, b, c);
	Point3 t = p.pointtoplane(o);
	double dis = sqrt((o.x - t.x) * (o.x - t.x) + (o.y - t.y) * (o.y - t.y) + (o.z - t.z) * (o.z - t.z));
	double r = dis / 2;
	double v = 4.0 / 3 * PI * r * r * r;
	double ans = v / l;
	pr("%.10lf\n", ans);
}

L	Sumo and Coins

题意：有 n 个硬币，a 个向上，b 个向下，每次可以翻转其中的 n-1 个硬币，问能不能全部朝上或者全部朝下

做法：如果 n 是偶数，那么每次翻转奇数个，一定会产生向上的个数和向下的个改变奇偶的情况，此时无论向上或者向下的数量，均可以达到 n 个。如果 n 是奇数，那么每次翻转偶数个，向上的个数和向下的个一定不会改变奇偶，所以有奇数个硬币的朝向可以达到 n 个

#include <bits/stdc++.h> #define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 5e5 + 5;
ll a[15];
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		int n, a, b;
		sc("%d%d%d", &n, &a, &b);
		if (n & 1)
		{
			if (a & 1)
				pr("UP\n");
			else if (b & 1)
				pr("DOWN\n");
		}
		else
			pr("ALL\n");
	}
}