四题签到 RK72 提前滚了…

Polynomial

洛必达定理搞一搞…

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int t, n;
	for (scanf("%d", &t); t--;)
	{
		scanf("%d", &n);
		vector<int> f, g;
		for (int i = 0, t; i < n; ++i)
			scanf("%d", &t), f.push_back(t);
		while (!f.back())
			f.pop_back();
		for (int i = 0, t; i < n; ++i)
			scanf("%d", &t), g.push_back(t);
		while (!g.back())
			g.pop_back();
		if (f.size() != g.size())
			printf(f.size() < g.size() ? "0/1\n" : "1/0\n");
		else
		{
			int gcd = __gcd(f.back(), g.back());
			printf("%d/%d\n", f.back() / gcd, g.back() / gcd);
		}
	}
}

Game

一开始没有看到依次处理然后 WA 了两发…

#include <bits/stdc++.h>
#define L first
#define R second
#define IN(x, p) (p.L <= x && x <= p.R)
#define INS(q, p) (IN(q.L, p) || IN(q.R, p) || IN(p.L, q) || IN(p.R, q))
using namespace std;
typedef pair<int, int> pii;
int main()
{
	int t, n;
	for (scanf("%d", &t); t--;)
	{
		scanf("%d", &n);
		vector<pii> v;
		for (int i = 0, a, b; i < n; ++i)
		{
			scanf("%d%d", &a, &b);
			v.push_back(make_pair(a, b));
		}
		int ans = 0;
		for (pii st(1, 1000000); !v.empty(); v.pop_back())
		{
			if (INS(st, v.back()))
			{
				st.L = max(st.L, v.back().L);
				st.R = min(st.R, v.back().R);
			}
			else if (st.R < v.back().L)
			{
				if (v.back().L < v.back().R)
				{
					if ((v.back().L - st.R) % 2 == 0)
					{
						ans += (v.back().L + 1 - st.R) / 2;
						st.L = st.R = v.back().L;
					}
					else
					{
						if (st.L < st.R)
						{
							ans += (v.back().L + 1 - st.R) / 2;
							st.R = v.back().L + 1;
							st.L = v.back().L;
						}
						else
						{
							ans += (v.back().L + 1 - st.R) / 2;
							st.R = v.back().L + 1;
							st.L = v.back().L;
						}
					}
				}
				else
				{
					ans += (v.back().L + 1 - st.R) / 2;
					st.L = st.R = v.back().L;
				}
			}
			else
			{
				swap(st.L, st.R), st.L = -st.L, st.R = -st.R;
				swap(v.back().L, v.back().R), v.back().L *= -1, v.back().R *= -1;
				if (v.back().L < v.back().R)
				{
					if ((v.back().L - st.R) % 2 == 0)
					{
						ans += (v.back().L + 1 - st.R) / 2;
						st.L = st.R = v.back().L;
					}
					else
					{
						if (st.L < st.R)
						{
							ans += (v.back().L + 1 - st.R) / 2;
							st.R = v.back().L + 1;
							st.L = v.back().L;
						}
						else
						{
							ans += (v.back().L + 1 - st.R) / 2;
							st.R = v.back().L + 1;
							st.L = v.back().L;
						}
					}
				}
				else
				{
					ans += (v.back().L + 1 - st.R) / 2;
					st.L = st.R = v.back().L;
				}
				swap(st.L, st.R), st.L = -st.L, st.R = -st.R;
			}
		}
		printf("%d\n", ans);
	}
}

Mindis

离散化成$4\times n^4$个点之后建图跑最短路即可。

#include <bits/stdc++.h>
using namespace std;
typedef double ll;
const ll INF = 1e18;
const int N = 255;
struct Ranker : vector<int>
{
	void init() { sort(begin(), end()), resize(unique(begin(), end()) - begin()); }
	int ask(int x) const { return lower_bound(begin(), end(), x) - begin(); }
};
struct Graph
{
	struct Vertex
	{
		vector<int> o;
	};
	struct Edge
	{
		int first, second;
		ll len;
	};
	vector<Vertex> v;
	vector<Edge> e;
	Graph(int n) : v(n) {}
	void add(const Edge &ed)
	{
		v[ed.first].o.push_back(e.size());
		e.push_back(ed);
	}
};
struct Dijkstra : Graph
{
	vector<ll> d;
	vector<int> p;
	Dijkstra(int n) : Graph(n) {}
	void ask(int s)
	{
		d.assign(v.size(), INF);
		p.assign(v.size(), e.size());
		priority_queue<pair<ll, int>> q;
		for (q.push(make_pair(d[s] = 0, s)); !q.empty();)
		{
			ll dis = -q.top().first;
			int u = q.top().second;
			if (q.pop(), d[u] < dis)
				continue;
			for (int i = 0, k, to; i != v[u].o.size(); ++i)
				if (k = v[u].o[i], to = e[k].second,
					d[to] > d[u] + e[k].len)
				{
					d[to] = d[u] + e[k].len, p[to] = k;
					q.push(make_pair(-d[to], to));
				}
		}
	}
	void add(Edge ed)
	{
		Graph::add(ed);
		swap(ed.first, ed.second);
		Graph::add(ed);
	}
};
int main()
{
	int t, n, x1[N], y1[N], x2[N], y2[N];
	for (scanf("%d", &t); t--;)
	{
		Ranker rx, ry;
		scanf("%d", &n);
		for (int i = 0; i <= n; ++i)
		{
			scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
			rx.push_back(x1[i]);
			rx.push_back(x2[i]);
			ry.push_back(y1[i]);
			ry.push_back(y2[i]);
		}
		rx.init();
		ry.init();
		vector<vector<int>> v(rx.size(), vector<int>(ry.size()));
		for (int i = 0; i <= n; ++i)
		{
			x1[i] = rx.ask(x1[i]);
			x2[i] = rx.ask(x2[i]);
			y1[i] = ry.ask(y1[i]);
			y2[i] = ry.ask(y2[i]);
			if (i < n)
				for (int x = x1[i]; x < x2[i]; ++x)
					for (int y = y1[i]; y < y2[i]; ++y)
						++v[x][y];
		}
		Dijkstra g(rx.size() * ry.size());
#define P(i, j) ((i) * (int)ry.size() + j)
		for (int i = 1; i < rx.size(); ++i)
			for (int j = 1; j < ry.size(); ++j)
			{
				double lx = rx[i] - rx[i - 1], ly = ry[j] - ry[j - 1];
				lx /= v[i - 1][j - 1] + 1, ly /= v[i - 1][j - 1] + 1;
				g.add({P(i - 1, j - 1), P(i, j - 1), lx});
				g.add({P(i - 1, j - 1), P(i - 1, j), ly});
				g.add({P(i, j - 1), P(i, j), ly});
				g.add({P(i - 1, j), P(i, j), lx});
			}
		g.ask(P(x1[n], y1[n]));
		printf("%.5f\n", g.d[P(x2[n], y2[n])]);
	}
}

Seq

六个一组愉快找规律…

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 31;
ll t, n, k, b;
int main()
{
	for (scanf("%I64d", &t); t--;)
	{
		scanf("%I64d", &n);
		k = n / 6, b = n % 6;
		printf("%I64d\n", b == 1 ? k * 4 + 1 : b == 2 ? k * 3 + 1 : b == 3 ? k : b == 4 ? 6 * k + 3 : b == 5 ? k : k * 3);
	}
}