T1: 打扑克

题目链接: A. 打扑克

题目大意

奇数牌在皮蛋手里, 偶数牌在黑妞手里, 然后轮流出牌, 像打扑克的规则, 然后谁出完了谁获胜

solution

又是我们喜闻乐见的找规律题, 我们可以从其中找规律:

我们从偶数牌先考虑,我们可以得知, 在 \(n>2\) 时,我们发现不论谁出牌,最后的赢家都是拥有偶数牌的人, 可以自己证明

然后在考虑奇数牌,我们发现先手出完之后,又变成了偶数牌的情况,然后谁先手谁赢

注意在 \(n=2\) 的时候要特殊处理,不然 \(100 \to 20\)

Code:

/**
*    Author: Alieme
*    Data: 2020.10.1
*    Problem: CSP.ac #265
*    Time: O(t)
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>

#define ll long long
#define rr register

#define inf 1e9
#define MAXN 100010

using namespace std;

inline int read() {
	int s = 0, f = 0;
	char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void print(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}

int t, a;

string s;

signed main() {
	t = read();
	while (t--) {
		cin >> s;
		int p = s[s.length() - 1] + '0';
		a = read();
		if (p & 1) { cout << a << "\n";}
		else if (s == "2")
				cout << a << "\n";
			else cout << 1 << "\n";
	}
}

T2: 粉刷匠

题目链接: B. 粉刷匠

题目大意

染色问题,每次只能染一列或一行,问最后这面墙有多少个格子是蓝色的

solution

我们可以考虑一个逆的思想, 我们倒着做, 最后涂得一定不会被覆盖

所以我们只需要记录一下每一行或者一列的影响,对于位置我们只需要判断这一行有没有被覆盖过即可

Code:

/**
*    Author: Alieme
*    Data: 2020.10.1
*    Problem: CSP.ac #266
*    Time: O(k)
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>

#define int long long
#define rr register

#define inf 1e9
#define MAXN 1000010
#define MAXM 1010

using namespace std;

inline int read() {
	int s = 0, f = 0;
	char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void print(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}

struct Node {
	int x, y, z;
}a[MAXN];

int n, m, k, ans, ans_hang, ans_lie;

bool f_hang[MAXN], f_lie[MAXN];

signed main() {
	n = read();
	m = read();
	k = read();
	for (rr int i = 1; i <= k; i++) a[i].x = read(), a[i].y = read(), a[i].z = read();
	for (rr int i = k; i >= 1; i--) {
		if (a[i].x == 0) {
			if (!f_hang[a[i].y]) f_hang[a[i].y] = 1;
			else continue;
			ans_hang++;
			if (a[i].z == 1) ans += m - ans_lie;
		}
		else {
			if (!f_lie[a[i].y]) f_lie[a[i].y] = 1;
			else continue;
			ans_lie++;
			if (a[i].z == 1) ans += n - ans_hang;
		}
	}
	print(ans);
}

T3: 直线竞速

题目链接; C. 直线竞速

题目大意

给你初始位置和速度, 然后问你t秒后第k位是谁

solution

对于每一次询问,计算出所有人的位置,然后找第k大, 我们可以用 nth_element 来优化

然后就能过掉这个题

然后也可以用冒泡排序来 \(A\) 掉它, 冒泡排序的复杂度是基于交换次数,我们只需要处理一下,然后发现这道题的交换次数最多只进行 \(n^2\) 次

所以我们就理所应到的 \(A\)掉此题

Code:

/**
*    Author: Alieme
*    Data: 2020.10.1
*    Problem: CSP.ac #267
*    Time: O()
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>

#define int long long
#define rr register

#define inf 1e9
#define MAXN 100010

using namespace std;

inline int read() {
	int s = 0, f = 0;
	char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void print(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}

struct Node {
	int t, k, id;
	Node() {}
	Node(int T, int K, int Id) {t = T, k = K, id = Id;}
	bool operator < (const Node &b) const { return t < b.t;}
}q[MAXN];

struct Edge {
	int a, id;
	Edge() {}
	Edge(int A, int Id) {a = A, id = Id;}
	bool operator < (const Edge &b) const { return a > b.a;}
}pai[MAXN];

int n, Q;

int a[MAXN], v[MAXN], ran[MAXN], dis[MAXN], ans[MAXN];

signed main() {
	n = read();
	for (rr int i = 1; i <= n; i++) {
		v[i] = read(), a[i] = read();
		pai[i] = Edge(a[i], i);
	}
	sort(pai + 1, pai + 1 + n);
	for (rr int i = 1; i <= n; i++) ran[i] = pai[i].id;
	Q = read();
	for (rr int i = 1; i <= Q; i++) {
		int t = read(), k = read();
		q[i] = Node(t, k, i);
	}
	sort(q + 1, q + 1 + Q);
	for (rr int i = 1; i <= Q; i++) {
		int t = q[i].t, ra = q[i].k, id = q[i].id;
		for (rr int j = 1; j <= n; j++) dis[j] = t * v[j] + a[j];
		for (rr int j = 1; j <= n; j++)
			for (rr int k = j; k >= 2; k--) 
				if (dis[ran[k]] >= dis[ran[k - 1]]) {
					if (dis[ran[k]] > dis[ran[k - 1]] || (dis[ran[k]] == dis[ran[k - 1]] && ran[k - 1] > ran[k]))
						swap(ran[k], ran[k - 1]);
				}
				else break;
		ans[id] = ran[ra];
	}
	for (rr int i = 1; i <= Q; i++) print(ans[i]), puts("");
}

T4:游戏

题目链接: D. 游戏

题目大意

参考 P1846 游戏

solution

考试还能出原题??

一看就是一道DP

1.我们先预处理一下, 对于每个数都减一, 求和的时候跟原来一样

2.我们从前面删和从后面删效果一样

3.我们可以观察到对于序列取值, 每次至多有一个序列删去超过一个数

然后,我们就可以推出我们的方程了

\(dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + a[i] * b[j]\)

Code:

/**
*    Author: Alieme
*    Data: 
*    Problem: 
*    Time: O()
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>

#define int long long
#define rr register

#define inf 1e9
#define MAXN 2010

using namespace std;

inline int read() {
	int s = 0, f = 0;
	char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void print(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}

int n, m;

int a[MAXN], b[MAXN];

int dp[MAXN][MAXN];

signed main() {
	memset(dp, 127, sizeof dp);
	dp[0][0] = 0;
	n = read(), m = read();
	for (rr int i = 1; i <= n; i++) a[i] = read(), a[i]--;
	for (rr int i = 1; i <= m; i++) b[i] = read(), b[i]--;
	for (rr int i = 1; i <= n; i++)
		for (rr int j = 1; j <= m; j++)
			dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + a[i] * b[j];
	print(dp[n][m]);
}