NFLS-DAY 7-2

Posted on By 张, 高畅 NFLS-DAY 7-2无评论

T0

无论有没有心情还是得把今天的blog写一下的。

T1

集训队选手们,经过4次考试,计算总分,最后将确定总分最高的4人入选国家队.
每次考试都是满分300分.现在即将进行第四次考试,只剩下16人参加.
告诉你这16人在前三场考试的总分,请计算有多少位同学有进入国家队的可能?
对于同分的情况,按照输入的顺序优先选前面的同学.

签到一下.

#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n = 16, res;
pair<int, int> w[N], p[N];
int main() {
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i].first);
        w[i].second = -i;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            p[j] = w[j];
            if (i == j)
                p[j].first += 300;
        }
        sort(p + 1, p + n + 1);
        reverse(p + 1, p + n + 1);
        for (int j = 1; j <= 4; j++) {
            if (-p[j].second == i) {
                res++;
                break;
            }
        }
    }
    printf("%d", res);
    return 0;
}

T2

N个小朋友排成一列,现在下雨啦,他们需要撑伞.
伞必须由人拿着,其半径为D.
假如小朋友们按顺序标为1,2,…,n,那么若i号拿着伞,则[i-D,i+D]这个闭区间内的小朋友都能不被雨淋到.
请问给他们买多少把伞,就能确保不会有人被淋到呢?

T1、T2应该放反了。

#include <bits/stdc++.h>
using namespace std;
int n, r;
int main() {
    scanf("%d%d", &n, &r);
    printf("%d\n", n / (2 * r + 1) + (n % (2 * r + 1) ? 1 : 0));
    return 0;
}

T3

题目描述
一条笔直公路上分布有N座城市，第i座城市的坐标为P[i]。
开始时一人位于X位置，每次只可以可以向左或向右D个单位，问若要此人遍历全部城市，D值最大可为多少？

只要记录X与P[i]的距离，并将它们进行求最大公约数的操作。

#include <bits/stdc++.h>
using namespace std;
int n, t, res;
int main() {
    scanf("%d%d", &n, &t);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        if (i == 1)
            res = abs(x - t);
        else
            res = __gcd(res, abs(x - t));
    }
    printf("%d", res);
    return 0;
}

T4

你有n根筷子，为了得到长度分别为a,b,c的三根筷子，现在你要施展若干次魔法，问消耗的最小魔法值是多少？
你可以用下面三种魔法改变筷子的长度：
1.消耗1魔法点，选一根竹子，让它的长度增加一
2.消耗1魔法点，选一根长度至少为2的竹子，让它的长度减一
3.消耗10魔法点，选两根竹子，将它们合并，合并之后的竹子是合并前两根竹子长度的总和
求最小消耗的魔法点。

可以只考虑操作三，然后每次求答案再用操作一二。

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n, a, b, c, w[N], res = 1e9;
void dfs(int u, int x, int y, int z, int v) {
    if (x && y && z)
        res = min(res, abs(a - x) + abs(b - y) + abs(c - z) + v - 30);
    if (u > n)
        return;
    dfs(u + 1, x + w[u], y, z, v + 10);
    dfs(u + 1, x, y + w[u], z, v + 10);
    dfs(u + 1, x, y, z + w[u], v + 10);
    dfs(u + 1, x, y, z, v);
}
int main() {
    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    dfs(1, 0, 0, 0, 0);
    printf("%d", res);
    return 0;
}

T5

在观看完战马检阅之后，来自大草原的两兄弟决心成为超级“马农”，专门饲养战马。兄弟两回到草原，将可以养马的区域，分为 N*N 的单位面积的正方形， 并实地进行考察，归纳出了每个单位面积可以养马所获得的收益。接下来就要开始规划他们各自的马场了。
首先，两人的马场都必须是矩形区域。同时，为了方便两人互相照应，也为了防止马匹互相走散，规定两个马场的矩形区域相邻，且只有一个交点。最后，互不认输的两人希望两个马场的收益相当，这样才不会影响他们兄弟的感情。
现在，兄弟两找到你这位设计师，希望你给他们设计马场，问共有多少种设计方案。

前缀和，hash，枚举。

#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = 1e7 + 5, K = 2e7 + 10;
int n, res, a[N][N], s[N][N];
int cnt[K];
int get(int ax, int ay, int bx, int by) {
    return s[bx][by] - s[ax - 1][by] - s[bx][ay - 1] + s[ax - 1][ay - 1];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &s[i][j]);
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= i; k++) {
                for (int l = 1; l <= j; l++) cnt[get(k, l, i, j) + M]++;
            }
            for (int k = i + 1; k <= n; k++) {
                for (int l = j + 1; l <= n; l++) res += cnt[get(i + 1, j + 1, k, l) + M];
            }
            for (int k = 1; k <= i; k++) {
                for (int l = 1; l <= j; l++) cnt[get(k, l, i, j) + M]--;
            }
            for (int k = i; k <= n; k++) {
                for (int l = 1; l <= j; l++) cnt[get(i, l, k, j) + M]++;
            }
            for (int k = 1; k < i; k++) {
                for (int l = j + 1; l <= n; l++) res += cnt[get(k, j + 1, i - 1, l) + M];
            }
            for (int k = i; k <= n; k++) {
                for (int l = 1; l <= j; l++) cnt[get(i, l, k, j) + M]--;
            }
        }
    }
    printf("%d", res);
    return 0;
}

T6

新学期要开始了，乐乐正在为这次的竞选班长准备着。选班长的时候，每个人都把会把自己的那一票，都给自己最好的朋友。如果想要是他们改变想法，就需要给糖果（-_-||）。现在已知每个人，会把自己的那一票投给谁，以及需要多少糖果才能使他们改选。已知乐乐在班里的编号为1。请你帮乐乐算算，他应该选谁，使得他花最少的糖果，就能使得他成为唯一的最高得票人。

终态枚举，枚举以i的票数成功当选班长。

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int n, res = 1e9;
vector<int> V[N];
void input() {
    int a[N];
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 2; i <= n; i++) {
        int x;
        scanf("%d", &x);
        V[a[i]].push_back(x);
    }
    for (int i = 1; i <= n; i++) sort(V[i].begin(), V[i].end());
}
int main() {
    input();
    for (int i = V[1].size(); i <= n; i++) {
        int ans = 0, cnt = V[1].size();
        priority_queue<int, vector<int>, greater<int> > q;
        for (int j = 2; j <= n; j++) {
            if (V[j].size() >= i) {
                for (int k = 0; k < V[j].size(); k++) {
                    if (k <= V[j].size() - i) {
                        ans += V[j][k];
                        cnt++;
                    } else
                        q.push(V[j][k]);
                }
            } else {
                for (int k = 0; k < V[j].size(); k++) q.push(V[j][k]);
            }
        }
        for (int j = cnt; j < i; j++) {
            ans += q.top();
            q.pop();
        }
        res = min(res, ans);
    }
    printf("%d", res);
    return 0;
}
训练日志

发表回复