ICPC North Central NA Contest 2018
- 1. 题目分析
- 2. 题解

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;

}

巴特西

ICPC North Central NA Contest 2018

ICPC North Central NA Contest 2018

1. 题目分析

2. 题解

A.Pokegene

B.Maximum Subarrays

C.Rational Ratio

D.Travel the Skies

E. Euler's Number

F. Lipschitz Constant

G. Tima goes to Xentopia

H. New Salaries

I. Other Side

J.Kaleidoscopic Palindromes

最新文章

热门文章