2019中国大学生程序设计竞赛-女生专场(重现赛)-感谢南京晓庄学院 wu-kan

Ticket

#include <bits/stdc++.h>
using namespace std;
int main(void)
{
	double ans, tot, a;
	int n;
	scanf("%d", &n);
	while (n--)
	{
		scanf("%lf", &a);
		if (tot < 100)
		{
			tot += a;
		}
		else if (tot >= 100 && tot < 150)
		{
			tot += 0.8 * a;
		}
		else if (tot >= 150 && tot < 400)
		{
			tot += 0.5 * a;
		}
		else
			tot += a;
	}
	printf("%.2lf\n", tot);
}

Gcd

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Mod
{
	const ll M, SM;
	Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
	ll qadd(ll &a, ll b) const { return a += b, a >= M ? a -= M : a; } //??a+b<2*M,??????,????????
	ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); }	  //??a?b??????????????
																	   //	ll mul(ll a, ll b) const { return add(a * b, M); }
	ll inv(ll a) const { return pow(a, M - 2); }					   //??M???,??return pow(a, phi(M) - 1);
	ll pow(ll a, ll b) const
	{
		ll r = 1;
		/*
		if (b < 0)
			b = -b, a = inv(a);
		*/
		for (a = add(a, M); b; b >>= 1, a = mul(a, a))
			if (b & 1)
				r = mul(r, a);
		return r;
	}

	ll mul(ll a, ll b) const { return add(a * b, -M * (ll)((long double)a / M * b)); } //long double ????16~18?,???????!
																					   /*ll mul(ll a, ll b) const //Head??,???????????,??a*b???ll??a*b%M,??a<M?b<M,?????????
	{
		ll c = a / SM, d = b / SM;
		a %= SM, b %= SM;
		ll e = add(add(a * d, b * c), c * d / SM * (SM * SM - M));
		return add(add(a * b, e % SM * SM), add(c * d % SM, e / SM) * (SM * SM - M));
	}
	ll mul(ll a, ll b) const //???
	{
		ll r = 0;
		for (a %= M; b; b >>= 1, qadd(a, a))
			if (b & 1)
				qadd(r, a);
		return r;
	}
	ll inv(ll a) const //?m?a?????,?????-1(m????a??0????)
	{
		ll x, y, d = gcd(a, M, x, y);
		return d == 1 ? add(x, M) : -1;
	}
	vector<ll> sol(ll a, ll b) const //?????,??ax=b(mod M)???????
	{
		vector<ll> ans;
		ll x, y, d = gcd(a, M, x, y);
		if (b % d)
			return ans;
		ans.push_back(mul((b / d) % (M / d), x));
		for (ll i = 1; i < d; ++i)
			ans.push_back(add(ans.back(), M / d));
		return ans;
	}
	ll log(ll a, ll b) const
	{
		unordered_map<ll, ll> x;
		for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
			if (!x.count(e))
				x[e] = i;
		for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
			if (x.count(b))
				return i * SM + x[b];
		return -1;
	}
	*/
};
struct PollardRho
{
	bool isPrime(ll n, int S = 12) //MillerRabin????,S?????,??S??????,S=12???unsigned long long?????;n<2???
	{
		static ll d, u, t, p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
		for (d = n - 1; !(d & 1);)
			d >>= 1; //??0,1???!
		Mod mo(n);
		for (int i = 0; i < S; ++i)
		{
			if (!(n % p[i]))
				return n == p[i];
			for (t = mo.pow(p[i], u = d); t != n - 1 && t != 1 && u != n - 1;)
				t = mo.mul(t, t), u <<= 1;
			if (t != n - 1 && !(u & 1))
				return 0;
		}
		return 1;
	}
	void fac(ll n, vector<ll> &factor)
	{
		/*
		if (n < e.m.size()) //????????,??????????????
		{
			for (; n > 1; n /= e.m[n])
				factor.push_back(e.m[n]);
			return;
		}
		*/
		if (isPrime(n))
			return factor.push_back(n);
		Mod mo(n);
		for (ll c = 1;; ++c)
			for (ll i = 0, k = 1, x = rand() % (n - 1) + 1, y, p;;)
			{
				if (++i == k)
					y = x, k <<= 1;
				if (x = mo.add(mo.mul(x, x), c), p = __gcd(abs(x - y), n), p == n)
					break;
				if (p > 1)
					return fac(p, factor), fac(n / p, factor);
			}
	}
} pr;
ll n;
vector<ll> v;
int main(void)
{
	scanf("%lld", &n);
	n = n * (n + 1) / 2;
	pr.fac(n, v);
	ll m = 1e18;
	for (int i = 0; i < v.size(); i++)
		m = min(m, v[i]);
	printf("%lld\n", n / m);
}

Function

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct hs
{
	int x, a, b;
	bool operator<(const hs &h) const
	{
		return (2 * x + 1) * a + b > (2 * h.x + 1) * h.a + h.b;
	}
};
priority_queue<hs> pq;
int main(void)
{
	int n, m;
	scanf("%d%d", &n, &m);
	ll ans = 0;
	while (n--)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		ans += a + b + c;
		m--;
		pq.push({1, a, b});
	}
	while (m--)
	{
		hs tem = pq.top();
		//cout<<tem.x<<" "<<tem.a<<" "<<tem.b<<endl;
		pq.pop();
		ans += (2 * tem.x + 1) * tem.a + tem.b;
		tem.x++;
		pq.push(tem);
	}
	printf("%lld\n", ans);
}

Tree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 9, NPOS = -1;
struct SegmentTree
{
	struct Seg
	{
		int l, r;
		ll flag, sum;
		void upd()
		{
			sum = sqrt(sum);
			if (sum <= 1)
				flag = 1;
		}
		friend Seg operator+(const Seg &lc, const Seg &rc) { return {lc.l, rc.r, lc.flag && rc.flag, lc.sum + rc.sum}; }
	};
	struct Node : Seg
	{
		int lc, rc;
	};
	vector<Node> v;
	SegmentTree(int l, int r, const vector<ll> &a) { build(l, r, a); }
	void build(int l, int r, const vector<ll> &a)
	{
		int rt = v.size();
		v.push_back({});
		v[rt].Seg::operator=({l, r, a[l] <= 1, a[l]});
		v[rt].lc = v[rt].rc = NPOS;
		if (l < r)
		{
			int m = v[rt].l + (v[rt].r - v[rt].l >> 1);
			if (v[rt].lc == NPOS)
				v[rt].lc = v.size(), build(v[rt].l, m, a);
			if (v[rt].rc == NPOS)
				v[rt].rc = v.size(), build(m + 1, v[rt].r, a);
			v[rt].Seg::operator=(v[v[rt].lc] + v[v[rt].rc]);
		}
	}
	void upd(int l, int r, int rt = 0)
	{
		if (v[rt].flag)
			return;
		if (v[rt].l >= v[rt].r)
		{
			v[rt].upd();
			return;
		}
		if (r <= v[v[rt].lc].r)
			upd(l, r, v[rt].lc);
		else if (l >= v[v[rt].rc].l)
			upd(l, r, v[rt].rc);
		else
			upd(l, v[v[rt].lc].r, v[rt].lc), upd(v[v[rt].rc].l, r, v[rt].rc);
		v[rt].Seg::operator=(v[v[rt].lc] + v[v[rt].rc]);
	}
	Seg ask(int l, int r, int rt = 0)
	{
		if (l <= v[rt].l && v[rt].r <= r)
			return v[rt];
		if (r <= v[v[rt].lc].r)
			return ask(l, r, v[rt].lc);
		if (l >= v[v[rt].rc].l)
			return ask(l, r, v[rt].rc);
		return ask(l, v[v[rt].lc].r, v[rt].lc) + ask(v[v[rt].rc].l, r, v[rt].rc);
	}
};
struct Graph
{
	struct Vertex
	{
		vector<int> o, i;		//相关出边和入边编号
		int siz, dep, top, dfn; //æ ‘é「¾å‰–分中使ç」¨ï¼Œä¾æ¬¡ä»£è¡¨å­æ ‘节点数、深度、所在é「¾çš„顶端节点、dfs序
	};
	typedef pair<int, int> Edge;
	vector<Vertex> v; //点集
	vector<Edge> e;   //边集
	Graph(int n) : v(n) {}
	void add(const Edge &ed)
	{
		v[ed.first].o.push_back(e.size());
		v[ed.second].i.push_back(e.size());
		e.push_back(ed);
	}
	int ch(int u, int i = 0) { return e[v[u].o[i]].second; } //u的第i个孩子节点
	int fa(int u, int i = 0) { return e[v[u].i[i]].first; }  //u的第i个父节点
};
ll a[N];
struct Diagram : Graph
{
	SegmentTree data;
	Diagram(const Graph &g, int root) : Graph(g.v.size()), data(0, 0, {0})
	{
		build(root, g);
		int cnt = v[root].dfn = v[root].dep = 1;
		dfs(v[root].top = root, cnt);
		vector<ll> b(cnt + 1);
		for (int i = 0; i < v.size(); ++i)
			b[v[i].dfn] = a[i];
		data = SegmentTree(1, cnt, b);
	}
	void build(int u, const Graph &g) //æ— å‘å›¾dfså»ºæ ‘ï¼Œä¸」重边在最前,uä¸ºæ ¹èŠ‚ç‚¹
	{
		v[u].siz = 1;
		for (int i = 0, k, to; i < g.v[u].o.size(); ++i)
			if (k = g.v[u].o[i], to = g.e[k].second, !v[to].siz) //没访问过的点siz默认0
			{
				build(to, g);
				v[u].siz += v[to].siz;
				Graph::add(g.e[k]);
				if (v[ch(u)].siz < v[to].siz) //重边移到最前
					swap(v[u].o.front(), v[u].o.back());
			}
	}
	void dfs(int u, int &cnt)
	{
		for (int i = 0, to; i < v[u].o.size(); ++i)
		{
			v[to = ch(u, i)].dfn = ++cnt;
			v[to].top = i ? to : v[u].top;
			v[to].dep = v[u].dep + 1;
			dfs(to, cnt);
		}
	}
	ll ask(int x, int y)
	{
		ll ans = 0;
		for (; v[x].top != v[y].top; x = fa(v[x].top))
		{
			if (v[v[x].top].dep < v[v[y].top].dep)
				swap(x, y);
			ans += data.ask(v[v[x].top].dfn, v[x].dfn).sum;
		}
		if (v[x].dep < v[y].dep)
			swap(x, y);
		return ans += data.ask(v[y].dfn, v[x].dfn).sum;
	}
	void upd(int x, int y)
	{
		for (; v[x].top != v[y].top; x = fa(v[x].top))
		{
			if (v[v[x].top].dep < v[v[y].top].dep)
				swap(x, y);
			data.upd(v[v[x].top].dfn, v[x].dfn);
		}
		if (v[x].dep < v[y].dep)
			swap(x, y);
		data.upd(v[y].dfn, v[x].dfn);
	}
};
int main()
{
	int n, q;
	scanf("%d%d", &n, &q);
	for (int i = 0; i < n; ++i)
		scanf("%lld", &a[i]);
	Graph g(n);
	for (int i = 1, u, v; i < n; ++i)
	{
		scanf("%d%d", &u, &v);
		g.add({u - 1, v - 1});
		g.add({v - 1, u - 1});
	}
	Diagram t(g, 0);
	for (int i = 0, o, u, v; i < q; ++i)
	{
		scanf("%d%d%d", &o, &u, &v);
		if (o)
			printf("%lld\n", t.ask(u - 1, v - 1));
		else
			t.upd(u - 1, v - 1);
	}
}

Checkout

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 9;
struct Vefaex
{
	vector<int> g;
	int a, fa;
	unordered_map<int, ll> mp;
} v[N];
int n, m;
ll sum = 0, ans[N];
void dfs1(int u)
{
	for (auto to : v[u].g)
		if (to != v[u].fa)
		{
			v[to].fa = u;
			sum += v[u].mp[v[to].a]++ + (v[to].a == v[u].a);
			dfs1(to);
		}
}
void dfs2(int u)
{
	for (auto to : v[u].g)
		if (to != v[u].fa)
			dfs2(to);
	int fa = v[u].fa;
	if (fa)
	{
		ll res = sum - v[fa].mp[v[fa].a];
		--v[fa].mp[v[u].a];
		for (auto tp : v[u].mp)
			res += tp.second * v[fa].mp[tp.first];
		++v[fa].mp[v[u].a];
		ans[fa] = max(ans[fa], res);
	}
	if (v[u].g.size() < 2 && v[u].fa)
	{
		ans[u] = sum - v[fa].mp[v[u].a] + 1;
		if (v[fa].a == v[u].a)
			--ans[u];
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &v[i].a);
	for (int i = 1, x, y; i < n; ++i)
	{
		scanf("%d%d", &x, &y);
		v[x].g.push_back(y);
		v[y].g.push_back(x);
	}
	dfs1(1);
	dfs2(1);
	for (int i = 1; i <= n; ++i)
		printf("%lld%c", ans[i], i < n ? ' ' : '\n');
}

String

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

const int maxn = 1e5 + 10;
int n, L, t;
int f[maxn][11][27], Min1[maxn][11], Min2[maxn][11], M1[maxn][11], M2[maxn][11];
char ch[maxn];

int main()
{
	scanf("%d%d%d", &n, &L, &t);
	scanf("%s", ch);

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= t; j++)
			for (int k = 0; k <= 26; k++)
				f[i][j][k] = n;
	memset(M1, -1, sizeof(M1));
	memset(M2, -1, sizeof(M2));

	int par = 1;
	f[0][par][ch[0] - 'a'] = 0;
	for (int i = 1; i < n; i++)
	{
		if (ch[i] != ch[i - 1])
			par++;
		if (par > t)
			break;
		f[i][par][ch[i] - 'a'] = 0;
	}
	for (int i = 0; i < n; i++)
		for (int k = 1; k <= t; k++)
		{
			for (int a = 0; a < 26; a++)
			{
				if (i > 0 && a == ch[i] - 'a')
					f[i][k][a] = min(f[i][k][a], f[i - 1][k][a]);
				if (i - L < 0)
					f[i][k][a] = min(f[i][k][a], 1);
				else
				{
					if (a != M1[i - L][k - 1] && M1[i - L][k - 1] != -1)
						f[i][k][a] = min(f[i][k][a], Min1[i - L][k - 1] + 1);
					if (a != M2[i - L][k - 1] && M2[i - L][k - 1] != -1)
						f[i][k][a] = min(f[i][k][a], Min2[i - L][k - 1] + 1);
					if (a == M1[i - L][k] && M1[i - L][k] != -1)
						f[i][k][a] = min(f[i][k][a], Min1[i - L][k] + 1);
					if (a == M2[i - L][k] && M2[i - L][k] != -1)
						f[i][k][a] = min(f[i][k][a], Min2[i - L][k] + 1);
				}
			}

			Min1[i][k] = n + 1;
			Min2[i][k] = n + 1;
			for (int a = 0; a < 26; a++)
			{
				if (Min1[i][k] > f[i][k][a])
				{
					Min1[i][k] = f[i][k][a];
					M1[i][k] = a;
				}
				else if (Min2[i][k] > f[i][k][a])
				{
					Min2[i][k] = f[i][k][a];
					M2[i][k] = a;
				}
			}
		}

	int ans = n;
	for (int k = 1; k <= t; k++)
		for (int a = 0; a < 26; a++)
			ans = min(ans, f[n - 1][k][a]);
	printf("%d\n", ans);
}

Circle

#include <bits/stdc++.h>
#define ld double
using namespace std;
ld a, x, ans;
int n;
const ld pi = acos(-1.0);
int main(void)
{
	while (cin >> n)
	{
		a = 2 * pi / n;
		ans = n * sin(a) / 2;
		x = sin(a / 4);
		ans += x * x * 2 * sin(a / 2);
		printf("%.6lf\n", ans);
	}
}

Clock

#include <bits/stdc++.h>
#define maxn 2000004
using namespace std;
int n, a, b, c, now;
int d[maxn];
int main(void)
{
	scanf("%d", &n);
	scanf("%d%d%d", &a, &b, &c);
	a %= 12;
	now = a * 3600 + 60 * b + c;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		a %= 12;
		int val = a * 3600 + b * 60 + c;
		d[i] = val;
	}
	d[0] = now;
	sort(d, d + n + 1);
	n = unique(d, d + 1 + n) - d - 1;
	int loc = lower_bound(d, d + n + 1, now) - d;
	//cout<<n<<" "<<loc<<endl;
	for (int i = n + 1; i <= 2 * n + 1; i++)
		d[i] = d[i - n - 1] + 43200;
	//for(int i=0;i<=2*n+1;i++)cout<<i<<" "<<d[i]<<endl;
	int dns = 0x3f3f3f3f;
	for (int i = 0; i <= n; i++)
	{
		if (i == 0)
		{
			dns = min(dns, min(d[loc] - d[0], d[n] - d[loc]) + d[n] - d[0]);
		}
		else if (i <= loc)
		{
			//cout<<d[i-1]<<endl;
			dns = min(dns, min(d[loc] - d[i], d[i - 1 + n + 1] - d[loc]) + 43200 - d[i] + d[i - 1]);
		}
		else if (i > loc)
		{
			dns = min(dns, min(d[i - 1] - d[loc], d[loc + n + 1] - d[i]) + 43200 - d[i] + d[i - 1]);
		}
	}
	printf("%.2lf\n", dns * 6.0);
}

Union

#include <bits/stdc++.h>
#define mod 1000000007
#define inv6 166666668
#define inv2 500000004
#define ll long long
ll c[100], jc[100], jcn[100];
ll ksm(ll a, ll b)
{
	ll ret = 1, tem = a;
	while (b)
	{
		if (b & 1)
			ret = ret * tem % mod;
		tem = tem * tem % mod;
		b >>= 1;
	}
	return ret;
}
using namespace std;
int main(void)
{
	int k, a1, a2, a3, a4, a5, a6, a7, n;
	scanf("%d%d%d%d%d%d%d%d%d", &n, &k, &a1, &a2, &a3, &a4, &a5, &a6, &a7);
	jc[0] = jcn[0] = c[0] = 1;
	for (int i = 1; i <= k; i++)
	{
		jc[i] = jc[i - 1] * i % mod;
		jcn[i] = ksm(jc[i], mod - 2);
		c[i] = c[i - 1] * (n - i + 1) % mod;
	}
	ll ans = 0;
	for (int s = a7; s <= k; s++)
	{
		for (int b1 = 0; b1 <= s - a5; b1++)
		{
			for (int b2 = 0; b2 * 2 + b1 <= k; b2++)
			{
				for (int b3 = 0; b3 * 3 + b2 * 2 + b1 <= k; b3++)
				{
					for (int b4 = max(a1 - b1 - b2 - b3, 0); b4 * 2 + b3 * 3 + b2 * 2 + b1 <= k; b4++)
					{
						for (int b5 = 0; b5 <= s - a6 && b5 + b4 * 2 + b3 * 3 + b2 * 2 + b1 <= k; b5++)
						{
							for (int b6 = max(a2 - b2 - b3 - b5, 0); b6 * 2 + b5 + b4 * 2 + b3 * 3 + b2 * 2 + b1 <= k; b6++)
							{
								//for(int b7=max(a3-b3-b4-b6-b7,0);b7+b6*2+b5+b4*2+b3*3+b2*2+b1<=k&&b7<=s-a4;b7++){
								int b7 = s - b1 - b2 - b3 - b4 - b5 - b6;
								int s1 = b1 + b2 + b3 + b4, s2 = b2 + b3 + b5 + b6, s3 = b3 + b4 + b6 + b7;
								if (b7 <= s - a4 && k - (b6 * 2 + b5 + b4 * 2 + b3 * 3 + b2 * 2 + b1) == b7 && b7 >= a3 - b3 - b4 - b6 - b7)
								{
									//if(b3==s)ans=(ans+(ll)c[s]*inv6%mod)%mod;
									//else if(b2+b3==s1&&b2+b3==s2)ans=(ans+(ll)c[s]*inv2%mod)%mod;
									//else if(b6+b3==s2&&b6+b3==s3)ans=(ans+(ll)c[s]*inv2%mod)%mod;
									//else if(b4+b3==s1&&b4+b3==s3)ans=(ans+(ll)c[s]*inv2%mod)%mod;
									ans = (ans + c[s] * jcn[b1] % mod * jcn[b2] % mod * jcn[b3] % mod * jcn[b4] % mod * jcn[b5] % mod * jcn[b6] % mod * jcn[b7] % mod) % mod;
									//puts("");
									//cout<<b1<<" "<<b2<<" "<<b3<<" "<<b4<<" "<<b5<<" "<<b6<<" "<<b7<<endl;
									//cout<<b1+b2+b3+b4<<" "<<b2+b3+b5+b6<<" "<<b3+b4+b6+b7<<" "<<s-b7<<" "<<s-b5<<" "<<s-b1<<" "<<s<<endl;;
								}
							}
						}
					}
				}
			}
		}
	}
	printf("%lld\n", ans);
}

Tangram

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

LL n;

int main()
{
	while (scanf("%lld", &n) != EOF)
	{
		if (n == 0)
			printf("7\n");
		else
			printf("%lld\n", 7ll + (6ll + (6ll + (n - 1ll))) * n / 2ll);
	}
}

Tetris

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

const int a[4][4] = {1, 1, 1, 3, 2, 1, 3, 3, 2, 2, 4, 3, 2, 4, 4, 4};
int n, m;

int main()
{
	while (~scanf("%d%d", &n, &m))
	{
		if (n % 4 != 0 || m % 4 != 0)
			printf(" no response\n");
		else
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < m; j++)
					printf("%d", a[i % 4][j % 4]);
				printf("\n");
			}
	}
}