只做了 AEI 三题，还是太菜了…

Little Sub and Pascal’s Triangle

打表快乐找规律……发现的规律是，对于答案序列中每连续的1<<n个数，后一半序列是由前一半的序列乘二得到的。于是可以直接根据 k 的二进制得到答案。

#include <bits/stdc++.h>
using namespace std;
long long t, k, a;
int main()
{
	for (scanf("%lld", &t); t--; printf("%lld\n", a))
	{
		scanf("%lld", &k);
		for (k -= a = 1; k; k >>= 1)
			if (k & 1)
				a <<= 1;
	}
}

Little Sub and his Geometry Problem

容易发现，对于某个固定的询问 C，符合要求的点一定是随着 X 增加 Y 减少，于是使用 X、Y 方向的双指针维护答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int t, n, k, q, ans;
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d%d", &n, &k);
		vector<vector<int>> e(n + 1);
		for (int i = 0, x, y; i < k; ++i)
			scanf("%d%d", &x, &y), e[x].push_back(y);
		for (scanf("%d", &q); q--; printf("%d%c", ans, q ? ' ' : '\n'))
		{
			ll c, x = 1, y = n, cnt = ans = 0, sum = 0;
			vector<int> cnty(n + 1), sumy(n + 1);
			for (scanf("%lld", &c); x <= n; ++x)
			{
				for (auto u : e[x])
					if (u <= y)
						++cnt, ++cnty[u], sum += x + u, sumy[u] += x + u;
				for (; (x + y) * cnt - sum > c; --y)
					cnt -= cnty[y], sum -= sumy[y];
				if ((x + y) * cnt - sum == c)
					++ans;
			}
		}
	}
}

Little Sub and Mr.Potato’s Math Problem

十分不熟悉的数位 DP，现场做了很久……以后要多多练习。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct POW : vector<ll>
{
	POW(int x, int n) : vector<ll>(n, 1)
	{
		for (int i = 1; i < size(); ++i)
			at(i) = at(i - 1) * x;
	}
} POW10(10, 19);
struct DP
{
	vector<ll> f;
	ll sum;
	DP(const vector<ll> &d) : f(d.size()), sum(0)
	{
		for (int i = 0; i < d.size(); ++i)
		{
			for (int j = f[i] = 0; j <= i; ++j)
				f[i] += (d[j] - (j == 0)) * POW10[i - j];
			sum += f[i] + 1;
		}
	}
};
ll cal(ll n, ll k, ll s, ll len)
{
	if (n > s * POW10[len])
		return cal(n - s * POW10[len], k, s, len + 1);
	return (n / POW10[len] + POW10[ll(log10(k))]) * POW10[len] + n % POW10[len] - 1;
}
int main()
{
	ll t, k, m;
	for (scanf("%lld", &t); t--;)
	{
		scanf("%lld%lld", &k, &m);
		vector<ll> d;
		for (ll n = k; n; n /= 10)
			d.push_back(n % 10);
		reverse(d.begin(), d.end());
		DP dp(d);
		printf("%lld\n", m == dp.sum ? k : m < dp.sum || k == *lower_bound(POW10.begin(), POW10.end(), k) ? 0 : cal(m - dp.sum, k, dp.f.back(), 1));
	}
}

Little Sub and Isomorphism Sequences

容易看出求最大的 k 就是求两个相同元素下标差的最大值，用一个 set 维护即可。为了求稳使用了离散化处理。

#include <bits/stdc++.h>
#define MP(i) make_pair(vs[i].size() < 2 ? -1 : *vs[i].rbegin() - *vs[i].begin(), i)
using namespace std;
typedef int ll;
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();
	}
};
ll getll(FILE *in = stdin)
{
	ll val = 0, sgn = 1, ch = getc(in);
	for (; !isdigit(ch) && ch != EOF; ch = getc(in))
		if (ch == '-')
			sgn = -sgn;
	for (; isdigit(ch); ch = getc(in))
		val = val * 10 + ch - '0';
	return ungetc(ch, in), sgn * val;
}
int main()
{
	for (ll t = getll(); t--;)
	{
		ll n = getll(), m = getll();
		Ranker input;
		for (int i = 0; i < n; ++i)
			input.push_back(getll());
		for (int i = 0; i < m; ++i)
		{
			input.push_back(getll());
			if (input.back() == 1)
			{
				input.push_back(getll());
				input.push_back(getll());
			}
		}
		Ranker::iterator it = input.begin();
		Ranker rk(input), a;
		rk.init();
		vector<set<int>> vs(rk.size());
		for (int i = 0; i < n; ++i)
		{
			a.push_back(rk.ask(*(it++)));
			vs[a.back()].insert(i);
		}
		set<pair<int, int>> q;
		for (int i = 0; i < vs.size(); ++i)
			q.insert(MP(i));
		for (int i = 0; i < m; ++i)
		{
			if (*(it++) == 1)
			{
				ll x = *(it++) - 1;
				q.erase(MP(a[x]));
				vs[a[x]].erase(x);
				q.insert(MP(a[x]));
				a[x] = rk.ask(*(it++));
				q.erase(MP(a[x]));
				vs[a[x]].insert(x);
				q.insert(MP(a[x]));
			}
			else
				printf("%d\n", q.rbegin()->first);
		}
	}
}