排位賽 12 題解

排位賽 12 題解

A - Cards

題意

給出n個數(shù)字，求如何兩兩分組可以讓每組數(shù)字之和相等。

思路

水。暴力。

代碼

#include <bits/stdc++.h>
using namespace std;
#define LOCAL

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int n; scanf("%d", &n);
    int num[107]; int sum = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d", num+i);
        sum += num[i];
    }
    int par = sum/(n/2);
    int vis[107] = {};
    for (int i = 0; i < n; ++i) {
        if (vis[i]) continue;
        for (int j = i+1; j < n; ++j) {
            if (vis[j]) continue;
            if (num[i] + num[j] == par) {
                vis[j] = 1;
                printf("%d %d\n", i+1, j+1);
                break;
            }
        }
    }
    return 0;
}

B - Cells Not Under Attack

題意

在 $n\times n$ 的棋盤上放車，求棋盤上有多少個點不能被這些車攻擊到。

思路

去掉被車覆蓋的行和列即可。

代碼

#include <bits/stdc++.h>
using namespace std;
#define LOCAL
#define LL __int64

const int maxn = 1e5+7;
int row[maxn], col[maxn];

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int n, m;
    scanf("%d%d", &n, &m);
    LL x = n, y = n;
    memset(row, 0, sizeof row);
    memset(col, 0, sizeof col);
    while (m--) {
        int a, b; scanf("%d%d", &a, &b);
        if (!row[a]) ++row[a], --x;
        if (!col[b]) ++col[b], --y;
        printf("%I64d ", x*y);
    }
    return 0;
}

C - They Are Everywhere

題意

給出一個字符串，找出最短的包含所有出現(xiàn)過的字母的子串的長度。

思路

尺取法。用兩個變量作為指針，先移動后面的，再移動前面的，更新每個字符出現(xiàn)的次數(shù)。維護最小值。

代碼

#include <bits/stdc++.h>
using namespace std;
#define LOCAL

const int maxn = 1e5+7;

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int n; scanf("%d", &n);
    char s[maxn]; scanf("%s", s);
    map<char,int> vis;
    for (int i = 0; i < n; ++i) vis[s[i]] = 1;
    int let_num = vis.size(); vis.clear();
    int cnt = 1, l = 0, r = 0;
    vis[s[0]] = 1;
    int ans = 0x3f3f3f3f;
    while (r < n) {
        while (cnt < let_num) {
            if (++r >= n) break;
            if (!vis[s[r]]) ++cnt;
            ++vis[s[r]];
        }
        while (cnt >= let_num) {
            ans = min(ans, r-l+1);
            --vis[s[l]];
            if (!vis[s[l++]]) --cnt;
        }
    }
    printf("%d\n", ans);
    return 0;
}

D - As Fast As Possible

題意

一群小學(xué)生出門，小學(xué)生走路速度為v1，大巴速度為v2，大巴一次能載人k個，路癡·求n個小學(xué)生走完l長度的路的最短時間。所有人都只能最多坐一次大巴。

思路

最短時間就是最后一個人到達的時間，那么我們要讓所有人坐大巴的時間相同。設(shè)每個人坐大巴的時間為t1，大巴送過一批人之后回頭接到另一批人的間隔時間為t2，將n個人分為p組，我們只要解如下的方程組即可。

$$
\left{
\begin{aligned}
p\cdot t_1+(p-1)t_2 = &t, \
t_1\cdot v_2+(t-t_1)v_1 = &L, \
t_2\cdot v_2+(t_1+t_2)v_1 = &t_1\cdot v_2
\end{aligned}
\right.
$$

代碼

#include <bits/stdc++.h>
using namespace std;
#define LOCAL

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    double n, l, v1, v2, k;
    scanf("%lf%lf%lf%lf%lf", &n, &l, &v1, &v2, &k);
    int p = (int)n%(int)k?n/k+1:n/k;
    double t1 = l*p/(v2-v1) + l*(p-1)/(v2+v1);
    double t2 = v1*p/(v2-v1) + v1*(p-1)/(v2+v1) + 1;
    printf("%.8lf\n", t1/t2);
    return 0;
}

E - The Unique MST

題意

給出一張圖，求最小生成樹是否是唯一的。

思路

次小生成樹模板題。

代碼

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
#define LOCAL

const int inf = 0x3f3f3f3f;
const int maxn = 105;

bool vis[maxn], used[maxn][maxn];
int lowc[maxn], pre[maxn], Max[maxn][maxn];

int prim(int cost[][maxn], int n){
    int ans = 0;
    memset(Max, 0, sizeof Max);
    memset(used, false, sizeof used);
    memset(vis, false, sizeof vis);
    vis[0] = true;
    pre[0] = -1;
    for (int i = 1; i < n; ++i){
        lowc[i] = cost[0][i];
        pre[i] = 0;
    }
    lowc[0] = 0;
    for (int i = 1; i < n; ++i){
        int minc = inf;
        int p = -1;
        for (int j = 0; j < n; ++j) if (!vis[j] && minc > lowc[j]){
            minc = lowc[j];
            p = j;
        }
        if (minc == inf) return -1;
        ans += minc;
        vis[p] = true;
        used[p][pre[p]] = used[pre[p]][p] = true;
        for (int j = 0; j < n; ++j){
            if (vis[j]) Max[j][p] = Max[p][j] = max(Max[j][pre[p]], lowc[p]);
            if (!vis[j] && lowc[j] > cost[p][j]){
                lowc[j] = cost[p][j];
                pre[j] = p;
            }
        }
    }
    return ans;
}

int ans;
int check(int cost[][maxn], int n){
    int Min = inf;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (cost[i][j] != inf && !used[i][j])
                Min = min(Min, ans + cost[i][j] - Max[i][j]);
    if (Min == inf) return -1;
    return Min;
}

void solve(){
    int cost[maxn][maxn], n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j){
            if (i == j) cost[i][j] = 0;
            else cost[i][j] = inf;
        }
    while (m--){
        int x, y, w;
        scanf("%d%d%d", &x, &y, &w);
        --x, --y;
        cost[x][y] = cost[y][x] = w;
    }
    ans = prim(cost, n);
    if (ans == -1 || ans == check(cost, n)) printf("Not Unique!\n");
    else printf("%d\n", ans);
}

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int t; scanf("%d", &t);
    while (t--) solve();
    return 0;
}

F - Homer Simpson

題意

有t的時間，有兩種漢堡可以吃，
第一種花費m的時間，第二種花費n，
要求盡量使得所有時間都被利用起來。

思路

完全背包問題。

代碼

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define LOCAL

const int maxn = 1e5+7;
const int inf = 0x3f3f3f3f;

int dp[maxn];

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int m, n, t;
    while (~scanf("%d%d%d", &m, &n, &t)) {
        for (int i = 1; i <= t; ++i) dp[i] = -inf;
        dp[0] = 0;
        for (int i = m; i <= t; ++i)
            dp[i] = max(dp[i], dp[i-m]+1);
        for (int i = n; i <= t; ++i)
            dp[i] = max(dp[i], dp[i-n]+1);
        int ans = t;
        while (dp[ans] < 0) --ans;
        printf("%d", dp[ans]);
        ans == t? puts("") : printf(" %d\n", t-ans);
    }
    return 0;
}

G - Pasha and Stick

題意

有一根長為t的木條，求有多少種方法能將其切成非正方形的矩形。

思路

水。注意點是要判斷0。

代碼

#include <bits/stdc++.h>
using namespace std;
#define LOCAL

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int n; scanf("%d", &n);
    int half = n/2;
    if (n&1)
        puts("0");
    else if (half&1)
        printf("%d", half/2);
    else
        printf("%d %d", (half-1)/2, half/2-1);
    return 0;
}

H - Vika and Squares

題意

有n種涂料，給出每種涂料的數(shù)量。用涂料涂色時，若x用第i種涂料，則x+1用第i+1種涂料。問最多能連續(xù)涂多少塊。

思路

模擬。先找出最多能循環(huán)涂多少次，然后找出最長的一個字段，和首尾比較，得到結(jié)果。注意答案需要用__int64。

代碼

#include <bits/stdc++.h>
using namespace std;
#define LOCAL
#define LL __int64

const int maxn = 2e5+7;

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    int n; scanf("%d", &n);
    int num[maxn], mi;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", num+i);
        mi = min(mi, num[i]);
    }
    LL ans = 0;
    ans += 1LL*mi*n;
    int flag = 0, t = 0;
    // flag -> 子串長度
    // t -> 最大子串長度
    for (int i = 1; i <= n; ++i) {
        num[i] -= mi;
        if (!num[i]) {
            if (flag) t = max(t, flag);
            flag = 0;
        }
        else ++flag;
    }
    if (flag) t = max(t, flag);
    int ht = 0, i = 1; // head & tail
    while(num[i] && i <= n) ++i, ++ht;
    i = n;
    while(num[i] && i > 0) --i, ++ht;
    t = max(t, ht);
    printf("%d\n", ans + t);
    return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪：刷leetcod...
    土汪閱讀 12,932評論 0贊 33
  • leetcode刷題記錄本文記錄一下leetcode刷題記錄，記錄一下自己的解法和心得。 LeetCode Two...
    EarthChen閱讀 3,610評論 0贊 6
  • 你是否經(jīng)歷過這樣的情景，某一天上學(xué)，突然你旁邊的座位空了?；蚴峭蝗唤淌业哪骋晃恢?，不再有你熟悉的那個人。 記得在小...
    一人獨占一江水閱讀 348評論 1贊 1
  • 圓珠筆的一個小習(xí)作，總喜歡畫一些花卉，倒不是有多喜歡花，畢竟它只是植物的‘生殖器’這么說是不是會挨揍呢，哈哈，但是...
    閆薪丞閱讀 329評論 0贊 6
  • Chapter1／／ 十年前的心臟很厚，用力才能碎。 里面是紅袖章，發(fā)條青蛙，雞毛毽子，明星禮包，動漫卡片和被積雪...
    Ruueryee閱讀 313評論 0贊 0

友情鏈接更多精彩內(nèi)容