ACM-ICPC 2018 沈阳赛区网络预赛 wu-kan

Made In Heaven

Astar 求 K 短路。

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef int ll;
const ll INF = 1e9;
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 Dijkstra : Graph
{
	vector<ll> d;
	Dijkstra(int n) : Graph(n) {}
	void ask(int s)
	{
		d.assign(v.size(), INF);
		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].a.size(); ++i)
				if (k = v[u].a[i], to = e[k].to,
					d[to] > d[u] + e[k].dist)
				{
					d[to] = d[u] + e[k].dist;
					q.push(make_pair(-d[to], to));
				}
		}
	}
};
struct Astar : Dijkstra
{
	vector<ll> ans;
	Astar(int n) : Dijkstra(n) {}
	void ask(int s, int t, int k, int T)
	{
		Dijkstra::ask(s);
		ans.assign(k, INF);
		if (d[t] == INF)
			return;
		vector<int> cnt(v.size(), 0);
		priority_queue<pair<ll, int>> q;
		for (q.push(make_pair(-d[t], t)); cnt[s] < k && !q.empty();)
		{
			ll dis = -q.top().first;
			int u = q.top().second;
			if (u == s)
				ans[cnt[s]] = dis;
			if (dis > T)
				return;
			if (q.pop(), ++cnt[u] > k)
				continue;
			for (int i = 0, k; i < v[u].b.size(); ++i)
				k = v[u].b[i], q.push(make_pair(d[u] - d[e[k].from] - e[k].dist - dis, e[k].from));
		}
	}
};
int main()
{
	for (int n, m, s, e, k, t; ~scanf("%d%d%d%d%d%d", &n, &m, &s, &e, &k, &t);)
	{
		Astar g(n + 1);
		for (int u, v, w; m--;)
		{
			scanf("%d%d%d", &u, &v, &w);
			g.add({u, v, w});
		}
		g.ask(s, e, k, t);
		printf(g.ans[k - 1] > t ? "Whitesnake!\n" : "yareyaredawa\n");
	}
}

Fantastic Graph

转换一下变成一个有源汇上下界网络流模型。

#include <cstdio>
#include <vector>
using namespace std;
typedef int ll;
const ll INF = 1e9;
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 ISAP : Graph
{
	ll flow;
	vector<ll> f;
	vector<int> h, cur, gap;
	ISAP(int n) : Graph(n) {}
	void add(Edge ed)
	{
		Graph::add(ed);
		swap(ed.from, ed.to), ed.cap = 0;
		Graph::add(ed);
	}
	ll dfs(int s, int u, int t, ll r)
	{
		if (r == 0 || u == t)
			return r;
		ll _f, _r = 0;
		for (int &i = cur[u], k; i < v[u].a.size(); ++i)
			if (k = v[u].a[i], h[u] == h[e[k].to] + 1)
			{
				_f = dfs(s, e[k].to, t, min(r - _r, e[k].cap - f[k]));
				f[k] += _f, f[k ^ 1] -= _f, _r += _f;
				if (_r == r || h[s] >= v.size())
					return _r;
			}
		if (!--gap[h[u]])
			h[s] = v.size();
		return ++gap[++h[u]], cur[u] = 0, _r;
	}
	void ask(int s, int t)
	{
		h.assign(v.size(), 0);
		cur.assign(v.size(), 0);
		gap.assign(v.size() + 2, 0);
		/*for(deque<int> q(h[t]=gap[t]=1,t); !q.empty(); q.pop_front())//可选预处理
            for(int i=0,u=q.front(),k,to; i<v[u].a.size(); ++i)
                if(to=e[v[u].a[i]].to,!h[to])
                    ++gap[h[to]=h[u]+1],q.push_back(to);*/
		for (f.assign(e.size(), flow = 0); h[s] < v.size();)
			flow += dfs(s, s, t, INF);
	}
};
int main()
{
	for (int n, m, k, l, r, kase = 0; ~scanf("%d%d%d", &n, &m, &k);)
	{
		ISAP g((n + m) * 2 + 9);
		scanf("%d%d", &l, &r);
		for (int i = 0, u, v; i < k; ++i)
		{
			scanf("%d%d", &u, &v);
			v += n;
			g.add({2 * u + 1, 2 * v, 1});
		}
		int s = 2 * (n + m + 1), t = s + 1, ss = t + 1, tt = ss + 1;
		g.add({t, s, INF});
		for (int i = 1; i <= n; ++i)
			g.add({s, 2 * i, INF});
		for (int i = n + 1; i <= n + m; ++i)
			g.add({2 * i + 1, t, INF});
		for (int i = 1; i <= n + m; ++i)
		{
			g.add({2 * i, 2 * i + 1, r - l});
			g.add({ss, 2 * i + 1, l});
			g.add({2 * i, tt, l});
		}
		g.ask(ss, tt);
		printf("Case %d: %s\n", ++kase, g.flow == (n + m) * l ? "Yes" : "No");
	}
}

Spare Tire

#include <cstdio>
#include <vector>
#define mul(a, b, m) ((a) * (b) % (m))
using namespace std;
typedef long long ll;
const ll M = 1e9 + 7;
ll n, m, ans1, ans2, INV[9];
vector<ll> fac;
void getfac(ll n)
{
	fac.clear();
	for (ll i = 2; i * i <= n; ++i)
		if (n % i == 0)
			for (fac.push_back(i); n % i == 0;)
				n /= i;
	if (n > 1)
		fac.push_back(n);
}
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;
}
void dfs(ll cur, ll num, ll val)
{
	if (cur == fac.size())
	{
		if (val != 1)
		{
			ll t = n / val, k = mul(mul(t * (t + 1) / 2 % M, num % 2 ? M - 1 : 1, M), val, M);
			if (ans1 += k, ans1 >= M)
				ans1 -= M;
			if (ans2 += mul(mul(mul(k, (t * 2 + 1), M), INV[3], M), val, M), ans2 >= M)
				ans2 -= M;
		}
		return;
	}
	dfs(cur + 1, num, val), dfs(cur + 1, num + 1, val * fac[cur]);
}
int main()
{
	for (ll i = 0; i < 9; ++i)
		INV[i] = pow(i, M - 2, M);
	while (~scanf("%lld%lld", &n, &m))
	{
		ans1 = n * (n + 1) / 2 % M;
		ans2 = ans1 * (2 * n + 1) % M * INV[3] % M;
		getfac(m);
		dfs(0, 0, 1);
		printf("%lld\n", (ans1 + ans2) % M);
	}
}

Lattice’s basics in digital electronics

做了一遍就不想再做一遍的沙雕大模拟…为了模拟而模拟。字典树跑掉。

#include <cstdio>
using namespace std;
const int NPOS = -1, N = 200009 << 2;
struct AhoCorasick
{
	struct Node
	{
		int ch[2], val;
		int &to(char c)
		{
			return ch[c - '0'];
		}
		Node() : val(NPOS)
		{
			ch[0] = ch[1] = 0;
		}
	} v[N];
	int siz;
	AhoCorasick() : siz(1) {}
	void add(char s[], int val)
	{
		int u = 0;
		for (int i = 0; s[i]; u = v[u].to(s[i++]))
			if (!v[u].to(s[i]))
			{
				v[u].to(s[i]) = siz;
				v[siz++] = Node();
			}
		v[u].val = val;
	}
};
char stak[N], data[N];
int t, kase = 0, m, n;
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d%d", &m, &n);
		AhoCorasick ac;
		for (int i = 0, c; i < n; ++i)
		{
			scanf("%d%s", &c, data);
			ac.add(data, c);
		}
		scanf("%s", stak);
		int len = 0, siz = 0;
		for (int i = 0; stak[i]; ++i)
		{
			stak[i] = '0' <= stak[i] && stak[i] <= '9' ? stak[i] - '0' : 'a' <= stak[i] && stak[i] <= 'z' ? stak[i] - 'a' + 10 : stak[i] - 'A' + 10;
			len += 4;
			for (int j = 1; j <= 4; ++j)
				data[len - j] = '0' + stak[i] % 2, stak[i] /= 2;
		}
		for (int i = 0, cnt; i + 8 < len; i += 9)
		{
			for (int j = cnt = 0; j < 8; ++j)
				if (data[i + j] == '1')
					++cnt;
			if (cnt % 2 != (data[i + 8] == '0' ? 1 : 0))
				continue;
			for (int j = 0; j < 8; ++j)
				stak[siz++] = data[i + j];
		}
		for (int i = 0, u = 0, cnt = 0; i < siz; ++i)
			if (ac.v[u = ac.v[u].to(stak[i])].val != NPOS)
			{
				printf("%c", ac.v[u].val);
				u = 0;
				if (++cnt == m)
					break;
			}
		printf("\n");
	}
}

Supreme Number

#include <stdio.h>
#include <string.h>
char s[127];
int t, n, kase, a[] = {1, 2, 3, 5, 7, 11, 13, 17, 23, 31, 37, 53, 71, 73, 113, 131, 137, 173, 311, 317};
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%s", s);
		if (strlen(s) > 3)
			n = 318;
		else
			sscanf(s, "%d", &n);
		for (int i = 19; ~i; --i)
			if (a[i] <= n)
			{
				printf("Case #%d: %d\n", ++kase, a[i]);
				break;
			}
	}
}