2016 SCPC

1.cpp

#include<iostream>
#include<algorithm>
using namespace std;

unsigned long long n,dp[64][2];
void dfs(unsigned long long n, int step)
{
	if (step == 64 || (n % 3 == 0 && n > dp[step][1])) return;
	dp[step][1] = min(n, dp[step][1]);
	if (n > 4 && n % 2 == 0 && (n - 1) % 3 == 0)
		dfs((n - 1) / 3, step + 1);
	dfs(n * 2, step + 1);
}
int main()
{
	dp[0][0] = dp[0][1]=1;
	for (int i = 1; i < 64; i++)
		dp[i][0] = dp[i - 1][0]*2, dp[i][1] = 1ull<<63;
	dfs(1, 0);
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{	
		cin >> n;
		cout << "Case #" << tc << "\n" << dp[n][1] << " " << dp[n][0] << "\n";
	}
}

2.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

long long dp[55001][101], total[55001];
bool mine[55001];
const int MAX = 1000000009;
int main()
{
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		int n, k, l, m;
		scanf("%d %d %d", &n, &k, &l);
		for (int i = 0; i < l; i++)
		{
			scanf("%d", &m);
			mine[m] = true;
		}
		total[0] = 1;
		for (int i = 1; i <= n; i++)
		{
			if (mine[i]) continue;
			for (int j = 1, pos = i - j; pos >= 0 && j <= k; pos--, j++)
			{
				dp[i][j] = (total[pos] + MAX - dp[pos][j]) % MAX;
			}
			for (int j = 1; j <= k; j++)
				if(!mine[i])
					total[i] += dp[i][j], total[i] %= MAX;
		}
		cout << "Case #" << tc << "\n" << total[n] % MAX << "\n";
		memset(dp, 0, sizeof(dp));
		memset(mine, 0, sizeof(mine));
		memset(total, 0, sizeof(total));
	}
}

3.cpp

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;

bool chk[101][101];
int main()
{
	int t;

	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		int node[101] = { 0 }, k, l, n, m, x, y, trc=0, ans = 0;
		bool tr[101] = { 0 };
		scanf("%d %d", &k, &l);
		scanf("%d %d", &n, &m);
		for (int i = 0; i < m; i++)
		{
			scanf("%d %d", &x, &y);
			chk[x][y] = chk[y][x] = true;

			node[x]++;
			node[y]++;
		}
		while(1)
		{
			bool f = false;
			for (int i = 1; i <= n; i++)
			{
				if (tr[i])continue;
				if (node[i] < k || n - trc - node[i] - 1 < l)
				{
					f = true;
					ans += i;
					tr[i] = true;
					trc++;
					for (int j = 1; j <= n; j++)
					{
						if (i == j) continue;
						if (chk[i][j]) node[j]--;
					}
				}
			}
			if (!f)break;
		}
		cout << "Case #" << tc << "\n" << ans << "\n";
		memset(chk, 0, sizeof(chk));
	}
}

4.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

struct Node
{
	int dist, next;
	Node(int a, int b){ dist = a, next = b; }
	bool operator <(const Node &n) const
	{
		return next > n.next;
	}
};
int dist[100001], parent[100001];
bool visited[100001];
int getParent(int p)
{
	if (parent[p] == -1) return p;
	return getParent(parent[p]);
}
int main()
{
	int t;
	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{	
		int n, m, k, x, y, z;
		vector<vector<Node> >v;
		priority_queue<Node> pq;
		scanf("%d %d %d", &n, &m, &k);
		v.resize(n + 1);
		for (int i = 1; i <= n; i++) dist[i] = 2e9;
		for (int i = 0; i < m; i++)
		{
			scanf("%d %d %d", &x, &y, &z);
			v[x].push_back(Node(y, z));
			v[y].push_back(Node(x, z));
		}
		for (int i = 0; i < k; i++)
		{
			scanf("%d", &x);
			parent[x] = -1;
			v[0].push_back(Node(x, 0));
		}
		dist[0] = 0;
		pq.push(Node(0, 0));
		while (!pq.empty())
		{
			Node tmp = pq.top();
			pq.pop();

			if (visited[tmp.dist]) continue;
			visited[tmp.dist] = true;

			int cur = tmp.dist, len = v[cur].size();

			for (int i = 0; i < len; i++)
			{
				int next = v[cur][i].dist, nextdist = dist[cur] + v[cur][i].next;
			
				if (dist[next] > nextdist)
				{
					dist[next] = nextdist;
					if (parent[next] != -1) parent[next] = getParent(cur);
					pq.push(Node(next, dist[next]));
				}
				else if (dist[next] == nextdist)
					if(parent[next] != -1)
						parent[next] = min(parent[next], getParent(cur));
			}
		}
		long long sum1 = 0, sum2 = 0;

		for (int i = 1; i <= n; i++)
		{
			int root = parent[i] == -1 ? -1 : parent[i];
			sum1 += root == -1 ? 0 : dist[i];
			sum2 += root == -1 ? i : root;
		}
		cout << "Case #" << tc << "\n" << sum1 << "\n" << sum2 << "\n";
		memset(parent, 0, sizeof(parent));
		memset(visited, 0, sizeof(visited));
	}
}

5.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>
using namespace std;
struct Shoes
{
	int start, end, need;
	Shoes(int a, int b, int c) { start = a, end = b, need = c; }
	Shoes() {}
};
struct Times
{
	int time;
	int index;
	Times(int a, int b) { time = a, index = b; }
	bool operator <(const Times &n) const
	{
		return time > n.time;
	}
};
struct People
{
	int start, end;
	People(int a, int b) { start = a, end = b;}
	People() {}
};
int main()
{
	int t;

	cin >> t;
	for (int tc = 1; tc <= t; tc++)
	{
		int s, p, pl[100] = { 0 };
		bool f = true;
		Shoes sh[200];
		People po[100];
		priority_queue<Times> pq;

		scanf("%d %d", &s, &p);
		for (int i = 0; i < s; i++)
			scanf("%d %d %d", &sh[i].start, &sh[i].end, &sh[i].need);
		for (int i = 0; i < p; i++)
		{
			scanf("%d %d", &po[i].start, &po[i].end);
			for (int j = po[i].start; j < po[i].end; j++) pl[j]++;
		}

		for (int i = 0; i < 100; i++)
		{
			for (int j = 0; j < s; j++)
			{
				if (!sh[j].need || sh[j].start > i) continue;
				if (i == sh[j].end)
				{
					f = false;
					break;
				}
				int remain = sh[j].end - i - sh[j].need;
				pq.push(Times(remain, j));
			}
			if (!f)break;
			for (int j = 0; j < pl[i] && !pq.empty(); j++)
			{
				Times tmp = pq.top();

				pq.pop();
				sh[tmp.index].need--;
			}
		}
		bool ff = !f ? false : true;
		for (int i = 0; i < s; i++)
		{
			if (sh[i].need)
			{
				ff = false;
				break;
			}
		}
		cout << "Case #" << tc << "\n";
		if(!ff) cout << "0\n";
		else cout << "1\n";
		memset(sh, 0, sizeof(sh));
		memset(po, 0, sizeof(po));
	}
}