ACM-ICPC 2018 焦作赛区网络预赛 wu-kan

Magic Mirror

#include <cstdio>
#include <cstring>
int T;
char s[20], a[20] = "JESSIE", b[20] = "jessie";
bool o;
int main()
{
	scanf("%d", &T);
	while (T--)
	{
		scanf("%s", s);
		if (strlen(s) != 6)
		{
			printf("Dare you say that again?\n");
			continue;
		}
		o = true;
		for (int i = 0; i < 6; i++)
			if ((s[i] != a[i]) && (s[i] != b[i]))
			{
				o = false;
				break;
			}
		if (o)
			printf("Good guy!\n");
		else
			printf("Dare you say that again?\n");
	}
}

Mathematical Curse

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int t, n, m, k;
long long a[1010];
char s[10];
long long mx[1010][10], mn[1010][10];
int main()
{
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d%d", &n, &m, &k);
		for (int i = 1; i <= n; i++)
			scanf("%lld", &a[i]);
		scanf("%s", s);
		memset(mx, 0, sizeof(mx));
		memset(mn, 0, sizeof(mn));
		mx[0][0] = mn[0][0] = k;
		for (int i = 1; i <= n; i++)
			for (int j = 1; (j <= m) && (j <= i); j++)
			{
				mx[i][0] = mn[i][0] = k;
				if (s[j - 1] == '+')
					mx[i][j] = mx[i - 1][j - 1] + a[i], mn[i][j] = mn[i - 1][j - 1] + a[i];
				else if (s[j - 1] == '-')
					mx[i][j] = mx[i - 1][j - 1] - a[i], mn[i][j] = mn[i - 1][j - 1] - a[i];
				else if (s[j - 1] == '*')
				{
					if (a[i] >= 0)
						mx[i][j] = mx[i - 1][j - 1] * a[i], mn[i][j] = mn[i - 1][j - 1] * a[i];
					else
						mx[i][j] = mn[i - 1][j - 1] * a[i], mn[i][j] = mx[i - 1][j - 1] * a[i];
				}
				else
				{
					if (a[i] >= 0)
						mx[i][j] = mx[i - 1][j - 1] / a[i], mn[i][j] = mn[i - 1][j - 1] / a[i];
					else
						mx[i][j] = mn[i - 1][j - 1] / a[i], mn[i][j] = mx[i - 1][j - 1] / a[i];
				}
				if (i > j)
					mx[i][j] = max(mx[i][j], mx[i - 1][j]), mn[i][j] = min(mn[i][j], mn[i - 1][j]);
			}
		printf("%lld\n", mx[n][m]);
	}
}

Password


Sequence


Jiu Yuan Wants to Eat

链剖+双标记维护区间和,区间取反操作等价于区间乘 -1 后区间加 -1 。 时限卡的有点紧,线段树用 vector 建的时候卡时限 2832ms/3000ms,改成数组也要跑 2448ms/3000ms。

#include <cstdio>
#include <vector>
using namespace std;
typedef unsigned long long ll;
const int N = 1e5 + 9;
struct Node
{
	int l, r;
	ll mul, add, sum;
	void upd(ll m, ll a)
	{
		mul *= m;
		add = add * m + a;
		sum = sum * m + a * (r - l + 1);
	}
	void up(const Node &lc, const Node &rc) { sum = lc.sum + rc.sum; }
	void down(Node &lc, Node &rc) { lc.upd(mul, add), rc.upd(mul, add), mul = 1, add = 0; }
} v[N << 2];
struct SegmentTree
{
	SegmentTree(int l, int r) { build(l, r); }
	void build(int l, int r, int rt = 1)
	{
		v[rt] = {l, r};
		if (l == r)
			return;
		int m = v[rt].r + v[rt].l >> 1;
		build(l, m, rt << 1), build(m + 1, r, rt << 1 | 1), v[rt].up(v[rt << 1], v[rt << 1 | 1]);
	}
	void upd(int l, int r, ll mul, ll add, int rt = 1)
	{
		if (l <= v[rt].l && v[rt].r <= r)
			return v[rt].upd(mul, add);
		v[rt].down(v[rt << 1], v[rt << 1 | 1]);
		int m = v[rt].r + v[rt].l >> 1;
		if (m >= r)
			upd(l, r, mul, add, rt << 1);
		else if (m < l)
			upd(l, r, mul, add, rt << 1 | 1);
		else
			upd(l, m, mul, add, rt << 1), upd(m + 1, r, mul, add, rt << 1 | 1);
		v[rt].up(v[rt << 1], v[rt << 1 | 1]);
	}
	Node ask(int l, int r, int rt = 1)
	{
		if (l <= v[rt].l && v[rt].r <= r)
			return v[rt];
		v[rt].down(v[rt << 1], v[rt << 1 | 1]);
		int m = v[rt].l + v[rt].r >> 1;
		if (m >= r)
			return ask(l, r, rt << 1);
		if (m < l)
			return ask(l, r, rt << 1 | 1);
		return v[0].up(ask(l, m, rt << 1), ask(m + 1, r, rt << 1 | 1)), v[0];
	}
};
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个父节点
};
struct Diagram : Graph
{
	SegmentTree data; //暂用树状数组作为默认数据结构
	Diagram(const Graph &g, int root) : Graph(g.v.size()), data(0, g.v.size() - 1)
	{
		build(root, g);
		int cnt = v[root].dfn = v[root].dep = 1;
		dfs(v[root].top = root, cnt);
	}
	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);
		}
	}
	Node ask(int x, int y)
	{
		Node ans;
		ans.sum = 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.up(ans, data.ask(v[v[x].top].dfn, v[x].dfn));
		}
		if (v[x].dep < v[y].dep)
			swap(x, y);
		return ans.up(ans, data.ask(v[y].dfn, v[x].dfn)), ans;
	}
	void upd(int x, int y, ll mul, ll add)
	{
		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, mul, add);
		}
		if (v[x].dep < v[y].dep)
			swap(x, y);
		data.upd(v[y].dfn, v[x].dfn, mul, add);
	}
};
int main()
{
	for (int n; ~scanf("%d", &n);)
	{
		Graph g(n + 1);
		for (int i = 2, b; i <= n; ++i)
			scanf("%d", &b), g.add({b, i});
		Diagram d(g, 1);
		scanf("%d", &n);
		for (int i = 0, u, v; i < n; ++i)
		{
			ll x;
			scanf("%llu%d%d", &x, &u, &v);
			if (x == 1)
				scanf("%llu", &x), d.upd(u, v, x, 0);
			else if (x == 2)
				scanf("%llu", &x), d.upd(u, v, 1, x);
			else if (x == 3)
				d.upd(u, v, -1, -1);
			else
				printf("%llu\n", d.ask(u, v).sum);
		}
	}
}

Modular Production Line

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N = 100009, NPOS = -1, INF = 1e18;
struct Ranker : vector<ll>
{
	void init()
	{
		sort(begin(), end()), resize(unique(begin(), end()) - begin());
	}
	int ask(ll x) const
	{
		return lower_bound(begin(), end(), x) - begin();
	}
};
struct Graph
{
	struct Vertex
	{
		vector<int> a /*,b*/; //相关出边和入边编号
							  //int siz,dep,top,dfn;//树链剖分中使用,依次代表子树节点数、深度、所在链的顶端节点、dfs序
	};
	struct Edge
	{
		int from, to;
		ll dist, cap; //边长、容量,图论算法使用
	};
	vector<Vertex> v; //点集
	vector<Edge> e;	  //边集
	Graph(int n) : v(n) {}
	void add(const Edge &ed)
	{
		if (ed.from == ed.to)
			return; //如果有需要请拆点
		v[ed.from].a.push_back(e.size());
		//v[ed.to].b.push_back(e.size());
		e.push_back(ed);
	}
};
struct EdmondKarp : Graph
{
	ll flow, cost;
	vector<ll> f;
	EdmondKarp(int n) : Graph(n) {}
	void add(Edge ed)
	{
		Graph::add(ed);
		swap(ed.from, ed.to), ed.cap = 0, ed.dist *= -1;
		Graph::add(ed);
	}
	void ask(int s, int t)
	{
		vector<int> p(v.size(), NPOS);
		for (f.assign(e.size(), flow = cost = 0);;)
		{
			vector<ll> d(v.size(), INF);
			vector<int> flag(v.size(), d[s] = 0);
			for (deque<int> q(flag[s] = 1, s); !q.empty(); q.pop_front())
				for (int u = q.front(), i = flag[u] = 0, k, to; i < v[u].a.size(); ++i)
					if (k = v[u].a[i], to = e[k].to,
						e[k].cap > f[k] && d[to] > d[u] + e[k].dist)
					{
						d[to] = d[u] + e[k].dist, p[to] = k;
						if (!flag[to])
							q.push_back(to), flag[to] = 1;
					}
			if (d[t] == INF)
				return;
			ll _f = INF;
			for (int u = t; u != s; u = e[p[u]].from)
				_f = min(_f, e[p[u]].cap - f[p[u]]);
			for (int u = t; u != s; u = e[p[u]].from)
				cost += _f * e[p[u]].dist, f[p[u]] += _f, f[p[u] ^ 1] -= _f;
			flow += _f;
		}
	}
};
int t, n, m, k, x[N], y[N], w[N];
int main()
{
	for (scanf("%d", &t); t--;)
	{
		Ranker rk;
		scanf("%d%d%d", &n, &k, &m);
		for (int i = 0; i < m; ++i)
		{
			scanf("%d%d%d", &x[i], &y[i], &w[i]);
			rk.push_back(x[i]);
			rk.push_back(++y[i]);
		}
		rk.init();
		EdmondKarp g(rk.size() + 2);
		for (int i = 0; i < rk.size(); ++i)
			g.add({i, i + 1, 0, k});
		for (int i = 0; i < m; ++i)
			g.add({rk.ask(x[i]), rk.ask(y[i]), -w[i], 1});
		g.add({rk.size() + 1, 0, 0, k});
		g.ask(rk.size() + 1, rk.size());
		printf("%lld\n", -g.cost);
	}
}

Give Candies

答案是$2^{n-2}$,用费马小定理把指数对 M-1 取模后进行运算避免更多的高精度运算。

#include <stdio.h>
#define mul(a, b, c) (1LL * (a) * (b) % (c))
typedef int ll;
const ll M = 1e9 + 7;
ll pow(ll a, ll b, ll m)
{
	ll r = 1;
	for (a %= m; b; b >>= 1, a = mul(a, a, m))
		if (b & 1)
			r = mul(r, a, m);
	return r;
}
char s[100009];
int t, n;
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%s", s);
		for (int i = n = 0; s[i]; ++i)
			n = mul(n, 10, M - 1) + s[i] - '0';
		printf("%d\n", pow(2, n + M - 2, M));
	}
}

String and Times

拉一个后缀数组的板子跑掉了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SufArr
{
	vector<int> sa, rk, h;
	SufArr(const vector<int> &s, int m) : sa(s.size(), 0), rk(s), h(s.size(), 0)
	{
		vector<int> cnt(s.size() + m, 0);
		for (int i = 0; i < s.size(); ++i)
			++cnt[rk[i]];
		for (int i = 1; i < m; ++i)
			cnt[i] += cnt[i - 1];
		for (int i = 0; i < s.size(); ++i)
			sa[--cnt[rk[i]]] = i;
		for (int k = 1, j = 0; k <= s.size() && j < s.size() - 1; k <<= 1)
		{
			for (int i = 0; i < s.size(); ++i)
			{
				if (j = sa[i] - k, j < 0)
					j += s.size();
				h[cnt[rk[j]]++] = j;
			}
			cnt[0] = sa[h[0]] = j = 0;
			for (int i = 1; i < s.size(); ++i)
			{
				if (rk[h[i]] != rk[h[i - 1]] || rk[h[i] + k] != rk[h[i - 1] + k])
					cnt[++j] = i;
				sa[h[i]] = j;
			}
			swap(rk, sa), swap(sa, h);
		}
		for (int i = 0, k = 0, j = rk[0]; i < s.size() - 1; ++i, ++k)
			for (; ~k && s[i] != s[sa[j - 1] + k]; j = rk[sa[j] + 1], --k)
				h[j] = k;
	}
};
struct SparseTable
{
	typedef int ll;
	vector<vector<ll>> f;
	SparseTable(const vector<ll> &a) : f(log2(a.size()) + 1, a)
	{
		for (int k = 0; k + 1 < f.size(); ++k)
			for (int i = 0; i + (1 << k) < a.size(); ++i)
				f[k + 1][i] = min(f[k][i], f[k][i + (1 << k)]);
	}
	ll ask(int l, int r)
	{
		int k = log2(r - l + 1);
		return min(f[k][l], f[k][r + 1 - (1 << k)]);
	}
};
ll cal(SufArr &sa, SparseTable &st, int k) //原串中至少出现k次的子串数量
{
	ll ans = 0;
	if (k > 1)
		for (int l = 2, r = k; r < sa.h.size(); ++l, ++r)
			ans += max(st.ask(l, r) - sa.h[l - 1], 0);
	else
		for (int i = 1; i < sa.h.size(); ++i)
			ans += sa.h.size() - 1 - sa.sa[i] - sa.h[i];
	return ans;
}
char s[2000009];
int main()
{
	for (int a, b; ~scanf("%s%d%d", s, &a, &b);)
	{
		SufArr sa(vector<int>(s, s + strlen(s) + 1), 'Z' + 1);
		SparseTable st(sa.h);
		printf("%lld\n", cal(sa, st, a) - cal(sa, st, b + 1));
	}
}

Save the Room

#include <stdio.h>
int main()
{
	for (int a, b, c; ~scanf("%d%d%d", &a, &b, &c);)
		printf(a % 2 && b % 2 && c % 2 ? "No\n" : "Yes\n");
}

Participate in E-sports

交了个高精度开根号上去。

#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
struct Wint : vector<int> //继承vector
{
	static const int width = 9, base = 1e9;
	Wint(unsigned long long n = 0) //普通初始化,当整型数和Wint同时运算时会提升至Wint
	{
		for (; n; n /= base)
			push_back(n % base);
	}
	explicit Wint(const string &s) //字符串初始化函数,未判断字符串合法情况
	{
		for (int len = int(s.size() - 1) / width + 1, b, e, i = 0; i < len; ++i)
			for (e = s.size() - i * width, b = max(0, e - width), push_back(0); b != e; ++b)
				back() = back() * 10 + s[b] - '0';
		trim(0);
	}
	Wint &trim(bool up = 1) //去前导0,是否需要进位,很常用的小函数,为方便返回自身
	{
		for (int i = 1; up && i < size(); ++i)
		{
			if ((*this)[i - 1] < 0)
				--(*this)[i], (*this)[i - 1] += base;
			if ((*this)[i - 1] >= base)
				(*this)[i] += (*this)[i - 1] / base, (*this)[i - 1] %= base;
		}
		while (!empty() && back() <= 0)
			pop_back();
		for (; up && !empty() && back() >= base; (*this)[size() - 2] %= base)
			push_back(back() / base);
		return *this;
	}
	friend istream &operator>>(istream &is, Wint &n)
	{
		string s; //懒
		return is >> s, n = Wint(s), is;
	}
	friend ostream &operator<<(ostream &os, const Wint &n)
	{
		if (n.empty())
			return os.put('0');
		os << n.back();
		char ch = os.fill('0');
		for (int i = n.size() - 2; ~i; --i)
			os.width(n.width), os << n[i];
		return os.fill(ch), os;
	}
	friend bool operator<(const Wint &a, const Wint &b)
	{
		if (a.size() != b.size())
			return a.size() < b.size();
		for (int i = a.size() - 1; ~i; --i)
			if (a[i] != b[i])
				return a[i] < b[i];
		return 0;
	}
	friend bool operator>(const Wint &a, const Wint &b)
	{
		return b < a;
	}
	friend bool operator<=(const Wint &a, const Wint &b)
	{
		return !(a > b);
	}
	friend bool operator>=(const Wint &a, const Wint &b)
	{
		return !(a < b);
	}
	Wint &operator+=(const Wint &b)
	{
		if (size() < b.size())
			resize(b.size()); //保证有足够的位数
		for (int i = 0; i < b.size(); ++i)
			(*this)[i] += b[i];
		return trim(); //单独进位防自运算
	}
	friend Wint operator+(Wint a, const Wint &b)
	{
		return a += b;
	}
	Wint &operator++() //前置版本
	{
		return *this += 1; //懒
	}
	Wint operator++(int) //后置版本
	{
		Wint b(*this);
		return ++*this, b;
	}
	Wint &operator-=(const Wint &b) //a<b会使a变为0
	{
		if (size() < b.size())
			resize(b.size()); //保证有足够的位数
		for (int i = 0; i < b.size(); ++i)
			(*this)[i] -= b[i];
		return trim(); //单独进位防自运算
	}
	friend Wint operator-(Wint a, const Wint &b)
	{
		return a -= b;
	}
	Wint &operator--() //前置版本
	{
		return *this -= 1; //懒
	}
	Wint operator--(int) //后置版本
	{
		Wint b(*this);
		return --*this, b;
	}
	Wint &operator*=(const Wint &b) //高精度乘法,常规写法
	{
		Wint c;
		c.assign(size() + b.size(), 0);
		for (int j = 0, k, l; j < b.size(); ++j)
			if (b[j]) //稀疏优化,特殊情况很有效
				for (int i = 0; i < size(); ++i)
				{
					unsigned long long n = (*this)[i];
					for (n *= b[j], k = i + j; n; n /= base)
						c[k++] += n % base;
					for (l = i + j; c[l] >= base || l + 1 < k; c[l++] %= base)
						c[l + 1] += c[l] / base;
				}
		return swap(c), trim(0);
	}
	/*
	Wint& operator*=(const Wint &b)//一种效率略高但对位宽有限制的写法
	{
		vector<unsigned long long> n(size()+b.size(),0);//防爆int
		//乘法算完后统一进位效率高,防止乘法溢出(unsigned long long范围0~1.8e19)
		//位宽为9时size()不能超过18(十进制162位),位宽为8时size()不能超过1800(十进制14400位)等等。
		for(int j=0; j!=b.size(); ++j)
			if(b[j])//稀疏优化,特殊情况很有效
				for(int i=0; i!=size(); ++i)
					n[i+j]+=(unsigned long long)(*this)[i]*b[j];
		for(int i=1; i<n.size(); ++i)//这里用<防止位数0,单独进位防自运算
			n[i]+=n[i-1]/base,n[i-1]%=base;
		return assign(n.begin(),n.end()),trim(0);
	}
	Wint& operator*=(const Wint &b)//fft优化乘法,注意double仅15位有效数字,调小Wint::width不超过2,计算自2*log2(base)+2*log2(len)<53
	{
	    vector<ll> ax(begin(),end()),bx(b.begin(),b.end());
	    ax=FFT(size()+b.size()).ask(ax,bx);
	    for(int i=1; i<ax.size(); ++i)
	        ax[i]+=ax[i-1]/base,ax[i-1]%=base;
	    return assign(ax.begin(),ax.end()),trim(0);
	}
	Wint& operator*=(const Wint &b)//ntt优化,Wint::width不超过2
	{
	    vector<ll> ax(begin(),end()),bx(b.begin(),b.end());
	    ax=FNTT(size()+b.size(),(7<<26)+1,3).ask(ax,bx);
	    for(int i=1; i<ax.size(); ++i)
	        ax[i]+=ax[i-1]/base,ax[i-1]%=base;
	    return assign(ax.begin(),ax.end()),trim(0);
	}
	*/
	friend Wint operator*(Wint a, const Wint &b)
	{
		return a *= b;
	}
	Wint &operator/=(Wint b)
	{
		Wint r, c, d = b.base / (b.back() + 1);
		*this *= d, b *= d, c.assign(size(), 0);
		for (int i = size() - 1; ~i; --i)
		{
			r.insert(r.begin(), (*this)[i]);
			unsigned long long s = 0;
			for (int j = b.size(); j + 1 >= b.size(); --j) //b.size()==0肯定第一行就出问题的
				s = s * b.base + (j < r.size() ? r[j] : 0);
			for (d = c[i] = s / b.back(), d *= b; r < d; r += b)
				--c[i];
			r -= d;
		}
		return swap(c), trim(0); //r为加倍后的余数,可通过高精度除低精度得到真正余数,此处略
	}
	friend Wint operator/(Wint a, const Wint &b)
	{
		return a /= b;
	}
	Wint &operator%=(const Wint &b)
	{
		return *this -= *this / b * b;
	}
	friend Wint operator%(Wint a, const Wint &b)
	{
		return a %= b;
	}
	//开平方,改自ZJU模板
	bool cmp(long long c, int d, const Wint &b) const
	{
		if ((int)b.size() - (int)size() < d + 1 && c)
			return 1;
		long long t = 0;
		for (int i = b.size() - 1, lo = -(base << 1); lo <= t && t <= 0 && ~i; --i)
			if (t = t * base - b[i], 0 <= i - d - 1 && i - d - 1 < size())
				t += (*this)[i - d - 1] * c;
		return t > 0;
	}
	Wint &sub(const Wint &b, long long k, int d)
	{
		int l = b.size() + d;
		for (int i = d + 1; i <= l; ++i)
		{
			long long tmp = (*this)[i] - k * b[i - d - 1];
			if (tmp < 0)
			{
				(*this)[i + 1] += (tmp - base + 1) / base;
				(*this)[i] = tmp - (tmp - base + 1) / base * base;
			}
			else
				(*this)[i] = tmp;
		}
		for (int i = l + 1; i < size() && (*this)[i] < 0; ++i)
		{
			(*this)[i + 1] += ((*this)[i] - base + 1) / base;
			(*this)[i] -= ((*this)[i] - base + 1) / base * base;
		}
		return trim(0);
	}
	friend Wint sqrt(Wint a)
	{
		Wint n;
		n.assign(a.size() + 1 >> 1, 0);
		for (int i = n.size() - 1, l, r; ~i; --i)
		{
			for (l = 0, r = a.base, n[i] = l + r >> 1; r - l > 1; n[i] = l + r >> 1)
			{
				if (n.cmp(n[i], i - 1, a))
					r = n[i];
				else
					l = n[i];
			}
			a.sub(n, n[i], i - 1), n[i] += l + r >> 1;
		}
		for (int i = 0; i < n.size(); ++i)
			n[i] >>= 1;
		return n.trim(0);
	}
	/*
	friend Wint sqrt(const Wint &a)//常规牛顿迭代实现的开平方算法,慢但是好敲
	{
	    Wint b=a,c=(b+1)/2;
	    while(b!=c)swap(b,c),c=(b+a/b)/2;
	    return c;
	}
	friend Wint sqrt(const Wint &a)
	{
	    Wint ret,t;
	    ret.assign((a.size()+1)>>1,0);
	    for(int i=ret.size()-1,l,r; ~i; --i)
	    {
	        for(l=0,r=a.base; r-l>1;)
	        {
	            ret[i]=l+(r-l)/2;
	            t=ret*ret;
	            if(a<t)r=ret[i];
	            else l=ret[i];
	        }
	        if(!l&&i==ret.size()-1)ret.pop_back();
	        else ret[i]=l;
	    }
	    return ret;
	}
	*/
};
int check(Wint n)
{
	Wint sn = sqrt(n);
	return sn * sn == n;
}
int main()
{
	int t;
	for (cin >> t; t--;)
	{
		Wint n;
		cin >> n;
		int ans = check(n) * 2 + check(n * (n - 1) / 2);
		cout << (ans == 0 ? "League of Legends\n" : ans == 1 ? "Clash Royale\n" : ans == 2 ? "Hearth Stone\n" : "Arena of Valor\n");
	}
}

Transport Ship

拆成 01 背包。

#include <stdio.h>
#include <string.h>
const int N = 511, S = 32767 >> 1, M = 1e9 + 7;
int t, n, q, m, v[N], f[N][S];
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d%d", &n, &q);
		for (int i = m = 0, V, C; i < n; ++i)
		{
			scanf("%d%d", &V, &C);
			for (int i = 0; i < C; ++i)
				v[++m] = (1 << i) * V;
		}
		for (int i = f[0][0] = 1; i <= m; ++i)
			for (int s = 0; s < S; ++s)
				if (f[i][s] = f[i - 1][s], s >= v[i])
					f[i][s] = (f[i][s] + f[i - 1][s - v[i]]) % M;
		for (int i = 0, s; i < q; ++i)
		{
			scanf("%d", &s);
			printf("%d\n", f[m][s]);
		}
	}
}

Poor God Water

矩阵乘一下。

#include <cstdio>
#include <algorithm>
#define mul(a, b, c) (1LL * (a) * (b) % (c))
using namespace std;
typedef long long ll;
const ll N = 9, M = 1e9 + 7;
struct Matrix
{
	static int n;
	ll a[N][N];
	Matrix(ll k = 0)
	{
		for (int i = 0; i < n; ++i)
			fill(a[i], a[i] + n, 0), a[i][i] = k;
	}
	ll *operator[](int n)
	{
		return a[n];
	}
};
int Matrix::n = N;
Matrix operator*(const Matrix &a, const Matrix &b)
{
	Matrix r(0);
	for (int i = 0; i < r.n; ++i)
		for (int j = 0; j < r.n; ++j)
			for (int k = 0; k < r.n; ++k)
				r.a[i][j] = (r.a[i][j] + mul(a.a[i][k], b.a[k][j], M)) % M;
	return r;
}
Matrix pow(Matrix a, ll b)
{
	Matrix r(1);
	for (; b; b >>= 1, a = a * a)
		if (b & 1)
			r = r * a;
	return r;
}
int main()
{
	ll t, n, ans;
	for (scanf("%lld", &t); t--;)
	{
		scanf("%lld", &n);
		if (n < 3)
		{
			printf("%d\n", n == 1 ? 3 : 9);
			continue;
		}
		Matrix A, P;
		for (int i = 0; i < N; ++i)
			A[i][0] = 1;
		P[0][3] = P[0][6] = 1;
		P[1][0] = P[1][3] = P[1][6] = 1;
		P[2][0] = P[2][3] = 1;
		P[3][1] = P[3][4] = P[3][7] = 1;
		P[4][1] = P[4][7] = 1;
		P[5][1] = P[5][4] = 1;
		P[6][5] = P[6][8] = 1;
		P[7][2] = P[7][8] = 1;
		P[8][2] = P[8][5] = 1;
		A = pow(P, n - 2) * A;
		for (int i = ans = 0; i < N; ++i)
			ans = (ans + A[i][0]) % M;
		printf("%lld\n", ans);
	}
}