A - Acesrc and Cube Hypernet
咕
B - Acesrc and Girlfriend
咕
C - Acesrc and Good Numbers
咕
D - Acesrc and Hunting
咕
E - Acesrc and String Theory
咕
F - Acesrc and Travel
咕
G - Andy and Data Structure
咕
H - Andy and Maze
咕
I - Calabash and Landlord
显然可以分类讨论两个矩形的位置关系,但是很蠢(指比赛时候的我......)。可以将所有坐标离散化在 [0,4]\times [0,4] 的区域内,然后打标记并dfs即可。
J - Quailty and CCPC
签到题,先判断再排序输出即可。
K - Roundgod and Milk Tea
原题可以转化为:有一个二分图,左边是学生节点,右边是奶茶节点,每一个学生可以连向非自己班制作的奶茶,问你最大匹配。由霍尔定理「对于二分图 (U+V,E),最大匹配数 |M|=|U|-\max_{S\subseteq U}(|S|-|N(S)|),其中 N(S) 表示点集 S 中每个点所连点集的并」,我们可以分类讨论。当 S=\varnothing 时,|M|=|U|;当 S 中有两个来自不同班级的同学时,有 N(S)=V,可得 |M|=|V|;当 S 中的同学全部来自同一个班级时,|N(S)|=|V|-b_i,可得 |M|=|U|+|V|-b_i-a_i。
Code
A - Acesrc and Cube Hypernet
B - Acesrc and Girlfriend
C - Acesrc and Good Numbers
D - Acesrc and Hunting
E - Acesrc and String Theory
F - Acesrc and Travel
G - Andy and Data Structure
H - Andy and Maze
I - Calabash and Landlord
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define MAX_N 10
using namespace std;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
int T, x[2][2], y[2][2];
int f[MAX_N][MAX_N];
bool vis[MAX_N][MAX_N];
int getid(vector<int> &v, int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
bool ok(int x, int y) {
return 0 <= x && x < 5 && 0 <= y && y < 5;
}
void dfs(int x, int y) {
vis[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (!vis[nx][ny] && ok(nx, ny) && f[nx][ny] == f[x][y]) {
dfs(nx, ny);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
vector<int> vx, vy;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
cin >> x[i][j] >> y[i][j];
vx.push_back(x[i][j]);
vy.push_back(y[i][j]);
}
}
sort(vx.begin(), vx.end());
sort(vy.begin(), vy.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
vy.erase(unique(vy.begin(), vy.end()), vy.end());
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
x[i][j] = getid(vx, x[i][j]);
y[i][j] = getid(vy, y[i][j]);
}
}
memset(f, 0, sizeof(f));
for (int k = 0; k < 2; k++) {
for (int i = x[k][0]; i < x[k][1]; i++) {
for (int j = y[k][0]; j < y[k][1]; j++) {
f[i][j] |= (1 << k);
}
}
}
memset(vis, false, sizeof(vis));
int ans = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (!vis[i][j]) {
dfs(i, j);
ans++;
}
}
}
cout << ans << endl;
}
}
J - Quailty and CCPC
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_N 100005
#define int long long
using namespace std;
struct Data {
string s;
int p, t;
friend bool operator<(const Data &a, const Data &b) {
if (a.p != b.p) {
return a.p > b.p;
}
return a.t < b.t;
}
};
int T, n, d;
Data a[MAX_N];
signed main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n >> d;
for (int i = 1; i <= n; i++) {
cin >> a[i].s >> a[i].p >> a[i].t;
}
if (n * d % 10 != 5) {
cout << "Quailty is very great" << endl;
continue;
}
sort(a + 1, a + 1 + n);
int pos = n * d / 10 + 1;
cout << a[pos].s << endl;
}
}
K - Roundgod and Milk Tea
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1000005
#define int long long
using namespace std;
int T, n;
int a[MAX_N];
int b[MAX_N];
signed main() {
ios::sync_with_stdio(false);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
int sa = 0, sb = 0;
for (int i = 1; i <= n; i++) {
sa += a[i], sb += b[i];
}
int ans = min(sa, sb);
for (int i = 1; i <= n; i++) {
ans = min(ans, sa + sb - b[i] - a[i]);
}
cout << ans << endl;
}
}