2018 Multi-University Training Contest 8
Contents
A. Character Encoding
题意：
用
思路：
当没有
减去有大于的关于
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int maxn = 1e6 + 10;
ll fac[maxn];
ll inv[maxn];
ll invfac[maxn];
void Init() {
fac[0] = inv[0] = invfac[0] = 1;
fac[1] = inv[1] = invfac[1] = 1;
for (int i = 2; i < maxn; ++i) {
fac[i] = fac[i - 1] * i % MOD;
inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
invfac[i] = invfac[i - 1] * inv[i] % MOD;
}
}
ll calc(ll n, ll m) {
if (m > n || m < 0 || n < 0)
return 0;
return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
}
int n, m, k;
int main() {
Init();
int t;
scanf("%d", &t);
while (t--) {
scanf("%d %d %d", &n, &m, &k);
ll ans = 0;
for (int i = 0; i <= m; ++i) {
ll tmp = k - 1ll * i * n + m - 1;
if (tmp < 0)
break;
if (i & 1)
ans = (ans - calc(m, i) * calc(tmp, m - 1) % MOD + MOD) % MOD;
else
ans = (ans + calc(m, i) * calc(tmp, m - 1) % MOD) % MOD;
// cout << i << " " << m << " " << calc(m, i);
// cout << tmp << " " << m - 1 << " " << calc(tmp, m - 1) << endl;
}
printf("%lld\n", ans);
}
return 0;
}
B. Pizza Hub
题意：
给出一个三角形，以及一个矩形的宽度，求一个最小的高度使得矩形能够覆盖三角形。
思路：
显然一定有一个点在矩形的顶点，枚举计算即可
Code
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e2;
int sgn(double x) {
if (fabs(x) < eps)
return 0;
else
return x > 0 ? 1 : -1;
}
struct Point {
double x, y;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
}
void input() {
scanf("%lf %lf", &x, &y);
}
Point operator-(const Point &b) const {
return Point(x - b.x, y - b.y);
}
double operator^(const Point &b) const {
return x * b.y - y * b.x;
}
double distance(Point p) {
return hypot(x - p.x, y - p.y);
}
double len() {
return hypot(x, y);
}
double operator*(const Point &b) const {
return x * b.x + y * b.y;
}
} P[maxn];
int w;
double ans;
double area;
void calc(Point a, Point b) // low high
{
if (sgn(a * b) < 0)
return;
if (sgn(a * a - w * w) <= 0) {
if (sgn(a ^ b) < 0)
return;
if (sgn((a * b) * (a * b) - w * w * (a * a)) > 0)
return;
ans = min(ans, (a ^ b) / sqrt(a * a));
} else {
double h = sqrt(a * a - w * w);
double src1 = atan(h / w);
if (sgn(a ^ b) >= 0) {
double src2 = acos((a * b) / (sqrt(a * a) * sqrt(b * b)));
if (sgn(src1 + src2 - PI / 2) > 0)
return;
double len1 = sqrt(b * b) * cos(src1 + src2);
if (sgn(len1 - w) > 0)
return;
ans = min(ans, max(h, sqrt(b * b) * sin(src1 + src2)));
} else {
double src2 = acos((a * b) / (sqrt(a * a) * sqrt(b * b)));
if (sgn(src1 - src2) < 0)
return;
double len1 = sqrt(b * b) * cos(src1 - src2);
if (sgn(len1 - w) > 0)
return;
ans = min(ans, h);
}
}
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
for (int i = 1; i <= 3; ++i) P[i].input();
// double a = p[1].distance(p[2]);
// double b = p[2].distance(p[3]);
// double c = p[3].distance(p[1]);
// double p = (a + b + c) / 2.0;
// area = sqrt(p * (p - a) * (p - b) * (p - c));
ans = INF * 1.0;
scanf("%d", &w);
calc(P[2] - P[1], P[3] - P[1]);
calc(P[3] - P[1], P[2] - P[1]);
calc(P[1] - P[2], P[3] - P[2]);
calc(P[3] - P[2], P[1] - P[2]);
calc(P[1] - P[3], P[2] - P[3]);
calc(P[2] - P[3], P[1] - P[3]);
for (int i = 1; i <= 3; ++i) P[i].y *= -1.0;
calc(P[2] - P[1], P[3] - P[1]);
calc(P[3] - P[1], P[2] - P[1]);
calc(P[1] - P[2], P[3] - P[2]);
calc(P[3] - P[2], P[1] - P[2]);
calc(P[1] - P[3], P[2] - P[3]);
calc(P[2] - P[3], P[1] - P[3]);
if (ans >= INF * 1.0)
puts("impossible");
else
printf("%.10f\n", ans);
}
return 0;
}
C. City Development
留坑。
D. Parentheses Matrix
题意：
构造一个矩阵，每一行和每一列都会构成一个括号序列，求合法括号序列尽量多。
思路：
分类讨论：
比如
两个都是偶数，如果有一个为
比如
如果两个都大于
比如
像这样构造 答案是
如果
比如
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 10;
int n, m;
char str[maxn][maxn];
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
// printf("%d %d\n", n, m);
if (n % 2 == 1 && m % 2 == 1) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
printf("(");
}
printf("\n");
}
} else if (n % 2 == 1) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (j & 1)
printf("(");
else
printf(")");
}
printf("\n");
}
} else if (m % 2 == 1) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i & 1)
printf("(");
else
printf(")");
}
printf("\n");
}
} else if (n == 2) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i & 1)
printf("(");
else
printf(")");
}
printf("\n");
}
} else if (m == 2) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (j & 1)
printf("(");
else
printf(")");
}
printf("\n");
}
} else if (n == 4) {
for (int i = 1; i <= m; ++i) printf("(");
printf("\n");
for (int i = 1; i <= m; ++i) {
if (i & 1)
printf("(");
else
printf(")");
}
printf("\n");
for (int i = 1; i <= m; ++i) {
if (i & 1)
printf(")");
else
printf("(");
}
printf("\n");
for (int i = 1; i <= m; ++i) printf(")");
printf("\n");
} else if (m == 4) {
for (int i = 1; i <= n; ++i) str[i][1] = '(';
for (int i = 1; i <= n; ++i) {
if (i & 1)
str[i][2] = '(';
else
str[i][2] = ')';
}
for (int i = 1; i <= n; ++i) {
if (i & 1)
str[i][3] = ')';
else
str[i][3] = '(';
}
for (int i = 1; i <= n; ++i) str[i][4] = ')';
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
printf("%c", str[i][j]);
}
printf("\n");
}
} else {
for (int i = 1; i <= m; ++i) str[1][i] = '(';
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i & 1) {
if (j == 1)
str[i][j] = '(';
else if (j == m)
str[i][j] = ')';
else if (j & 1)
str[i][j] = ')';
else
str[i][j] = '(';
} else {
if (j & 1)
str[i][j] = '(';
else
str[i][j] = ')';
}
}
}
for (int i = 1; i <= m; ++i) str[n][i] = ')';
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
printf("%c", str[i][j]);
}
printf("\n");
}
}
}
return 0;
}
E. Magic Square
按题意模拟即可。
Code
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
int t, n;
char G[5][5];
void C(pii a) {
int x = a.first, y = a.second;
char tmp[5][5];
tmp[1][1] = G[x + 1][y];
tmp[1][2] = G[x][y];
tmp[2][1] = G[x + 1][y + 1];
tmp[2][2] = G[x][y + 1];
for (int i = 1; i <= 2; ++i)
for (int j = 1; j <= 2; ++j) G[x + i - 1][y + j - 1] = tmp[i][j];
}
void R(pii a) {
int x = a.first, y = a.second;
char tmp[5][5];
tmp[1][1] = G[x][y + 1];
tmp[1][2] = G[x + 1][y + 1];
tmp[2][1] = G[x][y];
tmp[2][2] = G[x + 1][y];
for (int i = 1; i <= 2; ++i)
for (int j = 1; j <= 2; ++j) G[x + i - 1][y + j - 1] = tmp[i][j];
}
pii pos[4] = {
pii(1, 1),
pii(1, 2),
pii(2, 1),
pii(2, 2),
};
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= 3; ++i) scanf("%s", G[i] + 1);
char op;
int x;
for (int i = 1; i <= n; ++i) {
scanf("%d %c", &x, &op);
if (op == 'C')
C(pos[x - 1]);
else
R(pos[x - 1]);
}
for (int i = 1; i <= 3; ++i) printf("%s\n", G[i] + 1);
}
return 0;
}
F. Boolean 3-Array
留坑。
G. Card Game
留坑。
H. K-Similar Strings
留坑。
I. Make ZYB Happy
留坑。
J. Taotao Picks Apples
题意：
每次可以改变一个值，求改变之后以第一个数开头的最长上升子序列的长度，改变仅当次有效。
思路：
考虑线段树，维护一个
两个区间合并的时候；
- 如果
。 - 那么右区间没有贡献。
- 否则递归查找贡献。
Code
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int t;
int n, m;
int arr[N];
struct SEG {
int cnt[N << 2], Max[N << 2];
void build(int id, int l, int r) {
cnt[id] = Max[id] = 0;
if (l == r)
return;
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
int query(int id, int l, int r, int val) {
if (l == r)
return Max[id] > val;
int mid = (l + r) >> 1;
if (Max[id] <= val)
return 0;
if (Max[id << 1] <= val)
return query(id << 1 | 1, mid + 1, r, val);
else
return cnt[id] - cnt[id << 1] + query(id << 1, l, mid, val);
}
void update(int id, int l, int r, int pos, int val) {
if (l == r) {
cnt[id] = 1;
Max[id] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
update(id << 1, l, mid, pos, val);
else
update(id << 1 | 1, mid + 1, r, pos, val);
cnt[id] = cnt[id << 1] + query(id << 1 | 1, mid + 1, r, Max[id << 1]);
Max[id] = max(Max[id << 1], Max[id << 1 | 1]);
}
} seg;
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", arr + i);
seg.build(1, 1, n);
for (int i = 1; i <= n; ++i) seg.update(1, 1, n, i, arr[i]);
for (int i = 1, x, v; i <= m; ++i) {
scanf("%d%d", &x, &v);
seg.update(1, 1, n, x, v);
printf("%d\n", seg.cnt[1]);
seg.update(1, 1, n, x, arr[x]);
}
}
return 0;
}
K. Pop the Balloons
留坑。
L. From ICPC to ACM
留坑。
Last update: March 29, 2022
Created: March 29, 2022
Created: March 29, 2022