icpc2019南京区域赛
发布时间
阅读量：
阅读量
文章目录
- 2019年ICPC亚洲南京站区域赛
- A题：具有挑战性的问题
- B题：棋盘分析
- C题：数字路径问题
- F题：试卷评分系统设计
- H题：王子与公主问题
- J题：间谍行动方案
- K题：几何三角形定理应用
2019 ICPC Asia Nanjing Regional
A. A Hard Problem
题意： 签到
题解： 签到
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int const N = 2e5 + 10;
int n, m, T;
int main() {
cin >> T;
while(T--) {
cin >> n;
cout << n / 2 + 1 + (n & 1) << endl;
}
return 0;
}B.Chessboard
题意： 题目看不懂，不补了
题解：
代码：
C.Digital Path
题意：给定一个n×m的矩阵，在其每个格子中均标有一个数值。我们可从任意起点出发，在每次移动时仅限于上下左右四个相邻方向上进行行进，并要求所求解的是满足以下条件的所有完整路径的数量：每条完整路径必须至少包含4个不同的点；且该路径上依次经过的所有点对应的数值序列必须构成公差为1的等差数列。（其中整数约束条件如下：1 \leq n, m \leq 1000；而每个格子中的数值范围则被限定在-10^7 \leq a_{i,j} \leq 10^7之间）
题解： 因为规定了各数字大小依次增加1的原因导致所形成的通路构成一个DAG结构。那么我们可以通过记录每个节点i出发时的状态变量f[i][k]来描述其后续可能的发展情况。具体来说，在本问题中我们定义f[i][1]表示从节点i出发仅延伸一步的道路数量,f[i][2]则表示延伸两步的道路数量,以此类推直到f[i][4]表示从节点i出发至少延伸四步的道路数量。每次我们都采用队列首端元素来动态更新相邻节点的状态信息即可实现整个过程的有效计算。
代码：
/*
3 5
1 2 3 8 7
-1 -1 4 5 6
1 2 3 8 7
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int const MAXN = 1e3 + 10, MAXM = 4e6 + 10, mod = 1e9 + 7;
int n, m, T;
int g[MAXN][MAXN];
int e[MAXM], ne[MAXM], h[MAXN * MAXN], idx, f[MAXN * MAXN][4];
int d[MAXN * MAXN];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int mapping(int x, int y) {
return x * m + y;
}
void add(int a, int b ) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int top_sort() {
queue<int> q;
for (int i = 0; i < n * m; ++i) {
if (d[i] == 0 ) q.push(i), f[i][1] = 1;
}
int res = 0;
while(q.size()) {
auto t = q.front();
q.pop();
int flg = 0;
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
f[j][2] = (f[j][2] + f[t][1]) % mod;
f[j][3] = (f[j][3] + f[t][2]) % mod;
f[j][4] = (f[j][4] + 0ll + f[t][3] + f[t][4]) % mod;
d[j]--;
if (!d[j]) q.push(j);
flg = 1;
}
if (!flg) res = (res + f[t][4]) % mod;
}
return res;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
scanf("%d", &g[i][j]);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
for (int k = 0; k < 4; ++k) {
int nx = i + dx[k], ny = j + dy[k];
if (nx < 0 || nx > n - 1 || ny < 0 || ny > m - 1) continue;
if (g[nx][ny] != g[i][j] + 1) continue;
add(mapping(i, j), mapping(nx, ny));
d[mapping(nx, ny)]++;
}
}
cout << top_sort();
return 0;
}F.Paper Grading
题意： 字典树+cdq分治，留坑，待补
题解：
代码：
H.Prince and Princess
题意： 王子解救公主，xxxx
题解： xxxxx判断一下就好了
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int const N = 2e5 + 10;
int n, m, T;
int main() {
int a, b, c;
cin >> a >> b >> c;
if (a == 1 && b == 0 && c == 0) {
cout << "YES\n";
cout << 0 << endl;
return 0;
}
if (a > b + c) {
cout << "YES\n";
cout << 2 * (b + c) + 1;
}
else cout << "NO\n";
return 0;
}J.Spy
问题要求
题解
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL const INF = 0x3f3f3f3f3f3f3f3f;
int const MAXN = 500;
inline LL read() {
LL x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int n;
LL g[MAXN][MAXN], hl[MAXN], hr[MAXN], slk[MAXN];
int fl[MAXN], fr[MAXN], pre[MAXN], vl[MAXN], vr[MAXN], q[MAXN], ql, qr;
LL a[MAXN], b[MAXN], p[MAXN], c[MAXN];
inline int check(int i) {
vl[i] = 1;
if (fl[i] != -1) {
q[qr++] = fl[i];
vr[fl[i]] = 1;
return 1;
}
while (i != -1) {
fl[i] = pre[i];
swap(i, fr[fl[i]]);
}
return 0;
}
void bfs(int s) {
for (int i = 1; i <= n; i++) vl[i] = vr[i] = 0, slk[i] = INF;
for (vr[q[ql = 0] = s] = qr = 1;;) {
for (LL d; ql < qr;) {
for (int i = 1, j = q[ql++]; i <= n; i++) {
if (!vl[i] && slk[i] >= (d = hl[i] + hr[j] - g[i][j])) {
pre[i] = j;
if (d)
slk[i] = d;
else if (!check(i))
return;
}
}
}
LL d = INF;
for (int i = 1; i <= n; i++) {
if (!vl[i] && d > slk[i]) d = slk[i];
}
for (int i = 1; i <= n; i++) {
if (vl[i])
hl[i] += d;
else
slk[i] -= d;
if (vr[i]) hr[i] -= d;
}
for (int i = 1; i <= n; i++)
if (!vl[i] && !slk[i] && !check(i)) return;
}
}
LL solve() {
for (int i = 1; i <= n; i++) fl[i] = fr[i] = -1, hr[i] = 0;
for (int i = 1; i <= n; i++) hl[i] = *max_element(g[i] + 1, g[i] + n + 1);
for (int j = 1; j <= n; j++) bfs(j);
LL re = 0;
for (int i = 1; i <= n; i++)
if (g[i][fl[i]])
re += g[i][fl[i]];
else
fl[i] = 0;
return re;
}
int main() {
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= n; i++) p[i] = read();
for (int i = 1; i <= n; i++) b[i] = read();
for (int i = 1; i <= n; i++) c[i] = read();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
LL v = b[i] + c[j];
for (int k = 1; k <= n; k++)
if (a[k] < v) g[i][j] += p[k];
}
}
LL ans = solve();
printf("%lld\n", ans);
return 0;
}K.Triangle
问题描述如下：设定一个由三点构成的平面几何图形，并已知其三点坐标分别为P1(x1,y1)、P2(x2,y2)、P3(x3,y3)。现在给定点P0坐标为( xe , ye ) ，并确定该平面图形上是否存在另一顶点Q (xs , ys ) ，使得连接P0与Q 的直线段将此图形分割成两个面积相等的部分？若无法找到这样的Q，则返回值设为 -1
题解： 若点A不位于该三角形的三条边上，则结果为-1；否则可知必存在解。接着考虑当点A位于边AC上时的情形：若a_A > A_C，则可确定点B必定位于某条边上，并且面积的变化呈现单调性趋势进而可用二分法求解其具体数值范围。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, m, T;
// 计算几何模板
const double eps = 1e-8;
// 和0做比较
int sgn(double x) {
if (fabs(x) < eps) return 0; // =0
if (x < 0)
return -1; // < 0
else
return 1; // > 0
}
struct Point {
double x, y;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
}
void input() { scanf("%lf%lf", &x, &y); }
void output() { printf("%.10f %.10f\n", x, y); }
bool operator<(Point b) const {
return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
}
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 operator*(const Point &b) const { return x * b.x + y * b.y; }
//返回向量长度
double len() {
// hypot(x, y), 即sqrt(x * x + y * y)
return hypot(x, y); //库函数
}
//返回两点的距离
double distance(Point p) { return hypot(x - p.x, y - p.y); }
Point operator+(const Point &b) const { return Point(x + b.x, y + b.y); }
Point operator*(const double &k) const { return Point(x * k, y * k); }
Point operator/(const double &k) const { return Point(x / k, y / k); }
//计算pa和pb的夹角， 就是求这个点看a,b 所成的夹角的弧度
};
struct Line {
Point s, e;
Line() {}
// 两点确定一条线段
Line(Point _s, Point _e) {
s = _s;
e = _e;
}
// 点在线段上的判断
bool pointonseg(Point p) {
return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0;
}
};
double getarea(Point a, Point b, Point c) {
double sum = 0;
sum += a.operator^(b) + b.operator^(c) + c.operator^(a);
return fabs(sum) / 2;
}
Point get_mid(Point l, Point r) {
return (l + r) * 0.5;
}
int main() {
Point a, b, c, e, s;
Line ab, bc, ac;
cin >> T;
while (T--) {
a.input(), b.input(), c.input(), e.input();
double tran_area = getarea(a, b, c) / 2;
ab = Line(a, b), bc = Line(b, c), ac = Line(a, c);
if (!ab.pointonseg(e) && !ac.pointonseg(e) && !bc.pointonseg(e)) {
puts("-1");
continue;
}
if (ab.pointonseg(e)) {
double ae = a.distance(e), eb = b.distance(e);
if (ae > eb) {
Point l = a, r = c;
Point mid = get_mid(l, r);
int time = 1000;
while (time--) {
mid = get_mid(l, r);
int flg = sgn(getarea(a, e, mid) - tran_area);
if (flg == 0) break;
else if (flg > 0) r = mid;
else l = mid;
}
mid.output();
} else {
Point l = b, r = c;
Point mid = get_mid(l, r);
int time = 1000;
while (time--) {
mid = get_mid(l, r);
int flg = sgn(getarea(b, e, mid) - tran_area);
if (flg == 0) break;
else if (flg > 0) r = mid;
else l = mid;
}
mid.output();
}
} else if (bc.pointonseg(e)) {
double be = b.distance(e), ce = c.distance(e);
if (be > ce) {
Point l = b, r = a;
int time = 1000;
Point mid = get_mid(l, r);
while (time--) {
mid = get_mid(l, r);
int flg = sgn(getarea(b, e, mid) - tran_area);
if (flg == 0) break;
else if (flg > 0) r = mid;
else l = mid;
}
mid.output();
} else {
Point l = c, r = a;
int time = 1000;
Point mid = get_mid(l, r);
while (time--) {
mid = get_mid(l, r);
int flg = sgn(getarea(e, c, mid) - tran_area);
if (flg == 0) break;
else if (flg > 0) r = mid;
else l = mid;
}
mid.output();
}
} else if (ac.pointonseg(e)) {
double ae = e.distance(e), ec = c.distance(e);
if (ae < ec) {
Point l = c, r = b;
Point mid = get_mid(l, r);
int time = 1000;
while (time--) {
mid = get_mid(l, r);
int flg = sgn(getarea(e, c, mid) - tran_area);
if (flg == 0) break;
else if (flg > 0) r = mid;
else l = mid;
}
mid.output();
} else {
Point l = a, r = b;
Point mid = get_mid(l, r);
int time = 1000;
while (time--) {
mid = get_mid(l, r);
int flg = sgn(getarea(e, a, mid) - tran_area);
if (flg == 0) break;
else if (flg > 0) r = mid;
else l = mid;
}
mid.output();
}
}
}
return 0;
};全部评论 (0)
还没有任何评论哟~