2015ACM/ICPC亚洲区沈阳站-重现赛(感谢东北大学) wu-kan

Bazinga

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

const int maxn=500+10,maxL=2000+10;
int T,n,ans;
char ch[maxn][maxL];

struct KMP
{
	const string s;
	vector<int> next;
	KMP(const string &s) : s(s), next(s.size() + 1, 0)
	{
		for (int i = 1, j; i < s.size(); ++i)
		{
			for (j = next[i]; j && s[i] != s[j];)
				j = next[j];
			next[i + 1] = s[i] == s[j] ? j + 1 : 0;
		}
	}
	bool find_in(const string &t)const
	{
		for (int i = 0, j = 0; i < t.size(); ++i)
		{
			while (j && s[j] != t[i])
				j = next[j];
			if (s[j] == t[i])
				++j;
			if (j == s.size())
				return 1; //²»return¿ÉµÃµ½tÖÐsµÄËùÓÐÆ¥ÅäµØÖ·i+1-s.size()
		}
		return 0;
	}
};

int main()
{
	scanf("%d",&T);
	for (int t=1;t<=T;t++)
	{
		scanf("%d",&n);
		for (int i=1;i<=n;i++) scanf("%s",ch[i]);

		int L=0,R=0;
		for (int i=n;i>=2;i--) if (!KMP(ch[i-1]).find_in(ch[i])) {R=i;break;}
		if (R==0) {printf("Case #%d: -1\n",t);continue;}
		ans=R;

		L=R;R++;
		while (R<=n)
		{
			while (L>0 && KMP(ch[L]).find_in(ch[R])) L--;
			if (L<=0) break;
			R++;
		}
		ans=max(ans,R-1);

		printf("Case #%d: %d\n",t,ans);
	}

	return 0;
}

Pagodas

#include <bits/stdc++.h>
using namespace std;
int t, n, a, b;
int main()
{
	scanf("%d", &t);
	for (int i = 1; i <= t; i++)
	{
		scanf("%d%d%d", &n, &a, &b);
		cout << "Case #" << i << ": " << (n / (__gcd(a, b)) % 2 ? "Yuwgna" : "Iaka") << endl;
	}
}

Triple

三维偏序,使用二维树状数组维护。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fenwick
{
	struct BaseFenwick
	{
		vector<ll> v;
		BaseFenwick(int n) : v(n, 0) {}
		void add(int x, ll w)
		{
			for (; x < v.size(); x += x & -x)
				v[x] += w;
		}
		ll ask(int x)
		{
			ll ans = 0;
			for (; x; x -= x & -x)
				ans += v[x];
			return ans;
		}
	};
	pair<BaseFenwick, BaseFenwick> p;
	Fenwick(int n) : p(n, n) {}
	void add(int x, ll w) { p.first.add(x, w), p.second.add(x, x * w); }
	void add(int l, int r, ll w) { add(l, w), add(r + 1, -w); }
	ll ask(int x) { return (x + 1) * p.first.ask(x) - p.second.ask(x); }
	ll ask(int l, int r) { return ask(r) - ask(l - 1); }
};
struct Fenwick2
{
	struct BaseFenwick2
	{
		vector<Fenwick> v;
		BaseFenwick2(int r, int c) : v(r, c) {}
		void add(int x, int b, int t, ll w)
		{
			for (; x < v.size(); x += x & -x)
				v[x].add(b, t, w);
		}
		ll ask(int x, int b, int t)
		{
			ll ans = 0;
			for (; x; x -= x & -x)
				ans += v[x].ask(b, t);
			return ans;
		}
	};
	pair<BaseFenwick2, BaseFenwick2> p;
	Fenwick2(int r, int c) : p(BaseFenwick2(r, c), BaseFenwick2(r, c)) {}
	void add(int x, int b, int t, ll w) { p.first.add(x, b, t, w), p.second.add(x, b, t, x * w); }
	void add(int l, int b, int r, int t, ll w) { add(l, b, t, w), add(r + 1, b, t, -w); } //(l,b)~(r,t)
	ll ask(int x, int b, int t) { return (x + 1) * p.first.ask(x, b, t) - p.second.ask(x, b, t); }
	ll ask(int l, int b, int r, int t) { return ask(r, b, t) - ask(l - 1, b, t); }
};
const int M = 1e5 + 9;
int t, n, m, kase;
int main()
{
	for (scanf("%d", &t); t--;)
	{
		vector<tuple<int, int>> a(M);
		vector<tuple<int, int, int, int>> p;
		scanf("%d%d", &n, &m);
		for (int i = 0, x, y; i < n; ++i)
		{
			scanf("%d%d", &x, &y);
			if (get<0>(a[y]) < x)
				a[y] = make_tuple(x, 0);
			if (get<0>(a[y]) == x)
				++get<1>(a[y]);
		}
		for (int i = 0, c, d, e; i < m; ++i)
		{
			scanf("%d%d%d", &c, &d, &e);
			p.emplace_back(get<0>(a[e]), c, d, get<1>(a[e]));
		}
		sort(p.rbegin(), p.rend());
		for (int i = 1; i < p.size(); ++i)
			if (get<0>(p[i - 1]) == get<0>(p[i]) && get<1>(p[i - 1]) == get<1>(p[i]) && get<2>(p[i - 1]) == get<2>(p[i]))
			{
				get<3>(p[i]) += get<3>(p[i - 1]);
				get<3>(p[i - 1]) = 0;
			}
		Fenwick2 f(1023, 1023);
		ll ans = 0;
		for (auto it : p)
			if (get<3>(it))
			{
				if (!f.ask(get<1>(it) + 5, get<2>(it) + 5, 1009, 1009))
					ans += get<3>(it);
				f.add(get<1>(it) + 5, get<2>(it) + 5, get<1>(it) + 5, get<2>(it) + 5, get<3>(it));
			}
		printf("Case #%d: %lld\n", ++kase, ans);
	}
}

Kykneion asma

还是要学习一个,任意模数的 FFT,不是费马素数的模数要用特殊的姿势去膜,不能无脑 NTT。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
#define X real()
#define Y imag()
#ifndef M_PI
const double M_PI = acos(-1);
#endif
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); }
};
struct Factorial : Mod
{
	vector<ll> fac, ifac;
	Factorial(int N, ll M) : fac(N, 1), ifac(N, 1), Mod(M)
	{
		for (int i = 2; i < N; ++i)
			fac[i] = mul(fac[i - 1], i), ifac[i] = mul(M - M / i, ifac[M % i]);
		for (int i = 2; i < N; ++i)
			ifac[i] = mul(ifac[i], ifac[i - 1]);
	}
} M(32767, 1e9 + 7);
struct Rader : vector<int>
{
	Rader(int n) : vector<int>(1 << int(ceil(log2(n))))
	{
		for (int i = at(0) = 0; i < size(); ++i)
			if (at(i) = at(i >> 1) >> 1, i & 1)
				at(i) += size() >> 1;
	}
};
struct FFT : Rader
{
	vector<complex<lf>> w;
	FFT(int n) : Rader(n), w(size())
	{
		for (int i = 0; i < size(); ++i)
			w[i] = polar(1.0, 2 * M_PI * i / size());
	}
	void fft(vector<complex<lf>> &x) const
	{
		for (int i = 0; i < x.size(); ++i)
			if (i < at(i))
				std::swap(x[i], x[at(i)]);
		for (int i = 1; i < size(); i <<= 1)
			for (int j = 0; j < i; ++j)
				for (int k = j; k < size(); k += i << 1)
				{
					complex<lf> t = w[size() / (i << 1) * j] * x[k + i];
					x[k + i] = x[k] - t, x[k] += t;
				}
	}
	vector<ll> ask(const vector<ll> &a, const vector<ll> &b) const
	{
		vector<complex<lf>> xa(a.begin(), a.end()), xb(b.begin(), b.end());
		xa.resize(size()), xb.resize(size()), fft(xa), fft(xb);
		for (int i = 0; i < size(); ++i)
			xa[i] *= xb[i];
		fft(xa);
		vector<ll> ans(size());
		for (int i = 0; i < size(); ++i)
			ans[i] = xa[(size() - i) & (size() - 1)].real() / size() + 0.5;
		return ans;
	}
	vector<ll> askMod(const vector<ll> &a, const vector<ll> &b, ll M) const //任意模数
	{
		vector<complex<lf>> e(size()), c(size());
		for (int i = 0; i < a.size(); ++i)
			e[i].real(a[i] & 0x7fff), e[i].imag(a[i] >> 15);
		for (int i = 0; i < b.size(); ++i)
			c[i].real(b[i] & 0x7fff), c[i].imag(b[i] >> 15);
		fft(e), fft(c);
		vector<complex<lf>> d(c);
		for (int i = 0; i < size(); ++i)
		{
			int fr = (size() - i) & (size() - 1);
			c[i] *= 0.5 * complex<lf>(e[i].X + e[fr].X, e[i].Y - e[fr].Y);
			d[i] *= 0.5 * complex<lf>(e[i].Y + e[fr].Y, e[fr].X - e[i].X);
		}
		fft(c), fft(d);
		vector<ll> ans(size());
		for (int i = 0; i < size(); ++i)
		{
			ll fr = (size() - i) & (size() - 1),
			   p = c[fr].X / size() + 0.5,
			   o = c[fr].Y / size() + 0.5,
			   x = d[fr].X / size() + 0.5,
			   u = d[fr].Y / size() + 0.5;
			ans[i] = (p % M + ((o + x) % M << 15) + (u % M << 30)) % M;
		}
		return ans;
	}
};
int t, n, m, kase;
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d", &n);
		vector<ll> f(n + 1);
		f[0] = 1;
		for (int a = 0; a < 5; ++a)
		{
			scanf("%d", &m);
			for (int i = 0; i <= n; ++i)
				if (n - i - (a == 0) >= 0)
					f[i] = M.mul(f[i], M.fac[n - i - (a == 0)]);
			auto g = FFT(n + m + 2).askMod(f, vector<ll>(M.ifac.begin(), M.ifac.begin() + m + 1), M.M);
			for (int i = 0; i <= n; ++i)
				if (n - i - (a == 0) >= 0)
					f[i] = M.mul(g[i], M.ifac[n - i - (a == 0)]);
		}
		printf("Case #%d: %lld\n", ++kase, f[n]);
	}
}

Meeting

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
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));
				}
		}
	}
};
int t, n, m, kase;
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d%d", &n, &m);
		Dijkstra g(n + m + 1);
		for (int i = 1, t, s; i <= m; ++i)
		{
			scanf("%d%d", &t, &s);
			for (int j = 0, x; j < s; ++j)
			{
				scanf("%d", &x);
				g.add({x, n + i, t});
				g.add({n + i, x, t});
			}
		}
		g.ask(1);
		vector<ll> d;
		swap(d, g.d);
		g.ask(n);
		pair<ll, vector<int>> ans(INF, {});
		for (int i = 1; i <= n; ++i)
		{
			ll tmp = max(d[i], g.d[i]);
			if (ans.first > tmp)
				ans.first = tmp, ans.second.clear();
			if (ans.first == tmp)
				ans.second.push_back(i);
		}
		if (ans.first < INF)
		{
			printf("Case #%d: %lld\n", ++kase, ans.first >> 1);
			for (int i = 0; i < ans.second.size(); ++i)
				printf("%d%c", ans.second[i], "\n "[i + 1 < ans.second.size()]);
		}
		else
			printf("Case #%d: Evil John\n", ++kase);
	}
}