ICPC North Central NA Contest 2018
待补
- A后缀数组
- H概率
1. 题目分析
- A：后缀数组待补
- B: dp版题
- C: 数论--小学数学奥赛
- D: 大模拟
- E: 签到
- F: 思维签到
- G: 有条件的最短路问题--卡内存，交换数组第二维和第三维
- H: 概率待补
- I: 羊狼菜思维题
- J: 数学题--故意给出很大范围，实际用不到那么大范围
2. 题解
A.Pokegene
后缀数组
B.Maximum Subarrays
C.Rational Ratio
题意：给定一个循环小数的前半部分和循环节长度，该前半部分由不循环的部分和循环部分组成，循环部分只出现一次。求该小数对应的分数
题解：小学数学奥数题，把一个小数转换为分数的方法如下:
- 先把小数的整数部分拆出来，记为x
- 把小数部分的不循环部分拆出来，记为y
- 把小数部分的循环部分拆出来，记为z
那么小数对应的分数为: x + (y - z) / (9..9(z个9)0..0(y个0))
例如:1.6 1 => x = 1, y = 0, z = 6,则1 + (6-0) / 9 = 5 / 3
123.456 2 => x = 123, y = 4, z = 56, 则123 + (456 - 4) / 990 = 61111/495
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
string s;
int len;
cin >> s >> len;
int idx = s.find(".");
string first = "0", second = "0";
first = s.substr(0, idx);
second = s.substr(idx + 1);
// cout << first << " " << second << endl;
int len_second = second.size();
LL mother = 0;
for (int i = 1; i <= len; ++i) mother = mother * 10 + 9;
for (int i = 1; i <= len_second - len; ++i) mother *= 10;
// cout << mother << endl;
LL son = atoll(second.c_str()) - atoll(second.substr(0, len_second - len).c_str());
// cout << son;
LL gcd = __gcd(mother, son);
// cout << first << endl;
mother /= gcd, son /= gcd;
cout << son + mother * atoll(first.c_str()) << "/" << mother;
return 0;
}
D.Travel the Skies
题意:有 k 个机场，总共运行 n 天，有 m 架飞机，每架飞机有四个属性：u 代表起点，v 代表终点，d 代表哪天
起飞，z 表示飞机的容量 (可以乘多少人)，在第 b 天，有 c 名希望旅游的乘客到达 a 机场，你可以安排旅客的起飞日
期 (到达日期当天或者之后的任何一天) 和目的地，问你是否能够保证每架飞机都能够装满，每架飞机飞行花费一天时
间，一架飞机只飞行一次但乘客可以飞行多次
题解:按照题意直接模拟即可，idx[a][d] 存储在 a 机场第 d 天起飞的飞机编号，cnt[a][d] 则表示在 a 机场第 d 天
的人数，从前向后遍历每一天，对于每一天遍历所有机场，尽量将每一架飞机装满，由于乘客可以多次飞行，所以需要
将每架飞机目的地第二天的人数加上这架飞机上的乘客数，如果某一天某个机场还有乘客没有起飞，则直接留到第二
天
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1510;
const int M = 15;
struct node {
int u, v, d, c;
};
int k, n, m;
int cnt[M][M];
vector<int> idx[M][M];
node p[N];
int main()
{
scanf("%d%d%d", &k, &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d%d", &p[i].u, &p[i].v, &p[i].d, &p[i].c);
idx[p[i].u][p[i].d].push_back(i);
}
for (int i = 1; i <= k * n; i++) {
int a, d, t;
scanf("%d%d%d", &a, &d, &t);
cnt[a][d] = t;
}
for (int d = 1; d <= n; d++) {
for (int a = 1; a <= k; a++) {
int len = (int)idx[a][d].size();
for (int b = 0; b < len; b++) {
int id = idx[a][d][b];
int t = min(cnt[a][d], p[id].c);
cnt[a][d] -= t;
p[id].c -= t;
cnt[p[id].v][d + 1] += t;
}
cnt[a][d + 1] += cnt[a][d];
}
}
int flag = 1;
for (int i = 1; i <= m; i++)
if (0 != p[i].c) flag = 0;
if (1 == flag) printf("optimal\n");
else printf("suboptimal\n");
return 0;
}
E. Euler's Number
题意:输入 n，计算 e
思路:签到题
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n;
double euler(int n)
{
double res = 0, fac = 1.0;
for (int i = 0; i <= n; i++) {
if (0 == i) res += fac;
else {
fac /= i;
res += fac;
}
}
return res;
}
int main()
{
scanf("%d", &n);
printf("%.15lf\n", euler(n));
return 0;
}
F. Lipschitz Constant
题意:给定二维平面上 n 个点，求任意两点间斜率绝对值的最大值
题解:斜率绝对值的最大的两个点一定是 x 坐标相邻的两个点，按照 x 坐标排序，选择相邻的点计算斜率
证明：用反证法证明，如图，假设 AB 斜率绝对值最大，并且 AB 不相邻，如果 AB 之间存在一点 C 在 AB 直线 的下方，显然 kBC > kAB，如果 AB 之间存在另一点 D 在 AB 上方，同理会有 kDA > kAB，所以假设不成立，即斜率绝对值的最大的两个点一定是 x 坐标相邻的两个点
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 200010;
struct node {
double x, y;
};
node p[N];
int n;
bool cmp(node a, node b)
{
return a.x < b.x;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lf%lf", &p[i].x, &p[i].y);
sort(p + 1, p + n + 1, cmp);
double res = 0;
for (int i = 2; i <= n; i++) {
double t = abs(p[i].y - p[i - 1].y) / abs(p[i].x - p[i - 1].x);
res = max(res, t);
}
printf("%.9lf\n", res);
return 0;
}
G. Tima goes to Xentopia
题意:有一张无向图N个点M条边，每条边有颜色，可能为白，红，蓝，同时每条边还有一个边权。小A从1号点出发走到n号点，问是否存在一条经过k1条红边，k2条蓝边的最短路，如果有，输出其最短路权值；如果没有，输出-1
N ~ 450, M ~ 1100, K1 * K2 <= 800
题解:
本题求解一个带有条件的最短路，是一个模板题。但是如果开始dis[450][800][800]，那么mle，因此由k1*k2<=800，则dis[450][800][100],首先要判断k1和k2的大小，小的当成k2.有条件的最短路和没条件的最短路区别在于放入st数组和dis数组设置。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
LL const INF = 0x3f3f3f3f3f3f3f3f;
struct point {
int id, r, b;
LL dis;
point(int _id, int _r, int _b, LL _dis) : id(_id), r(_r), b(_b), dis(_dis) {}
bool operator < (const point & t) const {
return dis > t.dis;
}
};
// int const N = 460, M = 1110;
LL dis[500][810][100];
int st[500][810][100];
int k1, k2, n, m, s, t, idx, e[3000], ne[3000], h[500], w[3000], color[3000];
void add(int a, int b, int c, int col) {
e[idx] = b, w[idx] = c, color[idx] = col, ne[idx] = h[a], h[a] = idx++;
}
void Dijkstra() {
memset(dis, 0x3f, sizeof dis);
priority_queue<point> q;
dis[s][0][0] = 0;
q.push({s, 0, 0, 0});
while(!q.empty()) {
point temp = q.top();
q.pop();
if(st[temp.id][temp.r][temp.b]) continue; // 记录的时候要记点，边1，边2
st[temp.id][temp.r][temp.b] = 1;
for(int i = h[temp.id]; ~i; i = ne[i]) {
point t = {e[i], temp.r + (color[i] == 1), temp.b + (color[i] == 2), temp.dis + w[i]};
if(t.r > k1 || t.b > k2) continue;
if(t.dis < dis[t.id][t.r][t.b]) {
dis[t.id][t.r][t.b] = t.dis;
q.push(t);
}
}
}
printf("%lld\n", dis[t][k1][k2] == INF ? -1 : dis[t][k1][k2]);
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
memset(h, -1, sizeof h);
cin >> n >> m >> k1 >> k2;
bool change = false;
if (k1 < k2) {
swap(k1, k2);
change = true;
}
for (int i = 1, a, b, weight, colorr; i <= m; ++i) {
cin >> a >> b >> weight >> colorr;
if (change) colorr = 3 - colorr;
add(a, b, weight, colorr);
add(b, a, weight, colorr);
}
cin >> s >> t;
// cout << s << " " << t << endl;
Dijkstra();
return 0;
}
H. New Salaries
概率待补
I. Other Side
题意: 农夫有W匹狼，S只羊，C颗菜，当农夫不在场的时候狼会吃羊，羊会吃菜，但狼不吃菜。船的最大容量是K，农夫要将货物运到河对岸，问货物是否收到损失
题解:
羊必须和狼和菜分开，将狼和菜看成一个整体，狼和菜一起运，或者是只运羊。
（1）如果S < K || W + C < K，Yes
船上可以装下全部的羊，或者可以装下全部的狼和菜，可以把少的一方一直放在船上，把多的一方分多趟运到对岸。
（2）如果S == K && W + C <= 2 * K
船上放上全部的羊就满了，先把 K 只羊运到对岸，再把 K 个狼和菜运到对岸，再将羊运回起点，将剩下的狼和菜全部运到对岸，最后再运羊。可以发现，当W + C <= 2 * K时可以成功。
（3）如果 W + C == K && S <= 2 * K
#include <bits/stdc++.h>
using namespace std;
int main() {
int w, c, s, k;
cin >> w >> s >> c >> k;
int flg = 0;
if (s < k || w + c < k) flg = 1;
if (s == k && w + c <= 2 * k) flg = 1;
if (s <= 2 * k && w + c == k) flg = 1;
if (flg) cout << "YES";
else cout << "NO";
return 0;
}
J.Kaleidoscopic Palindromes
题意:求区间[a, b]内的所有数字中，2~k进制都是回文串的数字个数
a~2e6, k~1e5
题解:由于能够满足2~k进制都是回文串的数字个数非常少，因此只需要直接暴力枚举即可
#include <bits/stdc++.h>
using namespace std;
int a, b, k;
bool check(int x, int base) {
int pal[100], cnt = 0;
while (x) {
pal[cnt ++] = x % base;
x /= base;
}
for (int i = 0; i < cnt; ++i) {
if (i < cnt - i - 1 && pal[i] != pal[cnt - i - 1]) return false;
}
return true;
}
int main () {
cin >> a >> b >> k;
int sum = 0;
for (int i = a; i <= b; ++i) {
int j;
for (j = 2; j <= k; ++j) {
if (!check(i, j)) break;
}
if (j == k + 1) sum ++;
}
cout << sum;
return 0;
}