在（不是19年，其他年份有一些）面试笔试课里讲过！b站也有(2019A, B, C轮和2018所有轮题A和一个题B) ！(2020在lee215有A-G(即除了H轮))快去做字幕~ 懂了后自己saber或限时挑战一下

题目描述

KickStart题目特点： 不能直接做出来，需要考虑一个性质 –yxc
y总模板：【基础排序】
【数据结构】
【图论dfs bfs 最短路最小生成树 二分图】

A轮A题：(和2018年H轮B题很像)
前缀和
需要的训练时间是 $k*a_{i} - \sum_{j = i - k - 1}^{i}{a_j}$ 这个-前缀和长度为k的区间和最小值即可. -(s[i] - s[i - k]) for i = k; i<= n;
也就是从第一个数开始选长度为k的区间，算他的时间，一直到区间最后一个。在所有时间中取最小值即可

//我用的w代指a
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100005;
int s[N];
int w[N];
int main()
{
    int T;
    cin >> T;

    for (int C = 1; C <= T; C++)
    {
        int n, k;
        cin >> n >> k;
        s[0] = 0;
        for (int j = 1; j <= n ; j++) cin >> w[j];
        sort(w + 1, w + n + 1); //这里需要排序，不然没法最小值
        for (int j = 1; j <= n ; j++)
            s[j] = s[j - 1] + w[j];
        int res = 1e9 + 7; //比最大值大就行。
        for (int i = k; i <= n; i++)
            res = min(res, w[i] * k - s[i] + s[i - k]);
        if (res < 0) res = 0;
        printf("Case #%d: %d\n", C, res);
    }
    return 0;
}

B题。只过了一百来号人… AC了B就可以去面试了吧. 不过2020年参赛的人多了，可能要AK KS才能排上号
要是2021年按这种出我要一轮游了 现场补习acwing

【最大值最小】 —>可以二分来做

#include<bits/stdc++.h> //解决库的问题

二维BFS模板:

void bfs(int k) // 最终答案k，最大的最小距离是多少
{
    queue<PII> q;
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '1')
            {
                dist[i][j] = 0;
                q.push({i, j});
            }
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while(q.size())
    {
        auto t = q.front();
        q.pop();
        int x = t.first, y = t.second;
        int distance = dist[x][y];
        if (distance == k) continue; //终点 结束
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && n >= 0 && b < m && dist[a][b] == -1)
                {dist[a][b] = distance + 1; q.push({a, b});}
        }
    }
}

B题代码：

#include <iostream>
#include <cstring>
#include <queue>
#include <limits.h>
#include <memory.h>
using namespace std;

const int N = 255;
int n, m; //长，宽
int dist[N][N]; //每个点到补给站的距离
string g[N]; //地图

typedef pair<int, int>PII;

void bfs(int k)
{
    queue<PII> q; //bfs宽搜队列
    memset(dist, -1, sizeof dist); //初始化所有点到补给站的距离
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '1') //如果当前点是补给站
            {
                dist[i][j] = 0;
                q.push({i, j}); //补给站放进去
            }
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    //只要队列不空
    while(q.size())
    {
        auto t = q.front(); //取队头元素  
        q.pop();
        int x = t.first, y = t.second; //点坐标
        int distance = dist[x][y]; //(x,y )到补给站距离
        if (distance == k) continue; //已经到第k层了(k步)，就不更新其他点了k + 1...etc.
        //枚举周围点（四个方向） 。利用偏移量 ↑(x坐标减一) →(列y坐标+1) ↓(x坐标+1行下一位) ←(y坐标-1列左移)  //根据读入来看，读的是g[i], x表示行号, y自然就列号
        for(int i = 0; i < 4; i++) 
        {
            int a = x + dx[i], b = y + dy[i]; //加偏移量，即新的位置，走到的点的坐标
            //宽搜流程: 新的点必须在范围内
            if (a >= 0 && a < n && b >= 0 && b < m && dist[a][b] == -1){ //并且没被遍历过 -1
                dist[a][b] = distance + 1; //到补给站距离+1
                q.push({a, b}); //这个点放入队中
            }
        }
    }
}
bool check(int k)
{
    //cout << k << endl;
    bfs(k); //从k出发，把所有点标记(遍历) .算出(不加点时)所有点到补给站的距离

    int min_sum = INT_MAX, max_sum = INT_MIN; // x+y_min, x-y_max
    int min_sub = INT_MAX, max_sub = INT_MIN;
    //算一下x+y,x-y最小值和最大值
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (dist[i][j] == -1)
            {
                min_sum = min(min_sum, i + j);
                max_sum = max(max_sum, i + j);
                min_sub = min(min_sub, i - j);
                max_sub = max(max_sub, i - j);
            }

    if (min_sum == INT_MAX) return true;// 如果k特别大, 所有点都遍历到，不需要建立补给站->true

    // 遍历所有点
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (g[i][j] == '0') // 如果是0，判断是否可以建补给站合法 // 判断新图
            {
                int sum = max(abs(i + j - min_sum), abs(i + j - max_sum));
                int sub = max(abs(i - j - min_sub), abs(i - j - max_sub));
                if (max(sum, sub) <= k) return true; //如果sum和sub都小于k，说明找到了合法的位置，（建完后所有点到这个补给站距离都小于k）在这建
            }

    return false;
}

int main()
{
    int T;
    cin >> T;
    for (int C = 1; C <= T; C++)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> g[i];
        //二分模板
        int l = 0, r = n + m;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (check(mid)) r = mid; // 成立则ans在(0, mid)
            else l = mid + 1; //否则在(mid,n)
        }

        printf("Case #%d: %d\n", C, r);
    }

    return 0;
}

看来应该是要用dfs[摊手]证明不出来性质，只能提出一个伟大的假设，就当我说的都是对的了
具体等结束了再贴

要学习前辈的刻苦，我太懒了，问题一长就不想读题了。。

摘取自github
栗子的KickStart题解
2020 : ABCDEFGH

2019 : ABCDEFGH

2018 : GH
这家伙还写了d2l
William Lin （神） 油管
lee215 b站（最近周赛有几期量子阅读法特别刺激） 公众号看题解（拿出手机/pad谢谢）

模板template 这个一会儿链到y总那四份
还有DP 那几种背包参考思路。和各式各样的模型。（基础课，提高课）定义＋遍历集合 最后ans操作更新一下

https://www.keybr.com 打字（毕竟比赛是计时哒）

William 《论如何Competitive Programming》

CP is for Problem Solving
reading is not ps。#reading too much 注意
5分钟原则。 每一百分钟CP，只有5分钟被动阅读。多来95%主动想解题思路。Active！Thinking！man一点主动上

不要用太过高级的结构

如果你用简单方法实现不了，高级结构更难应用上，implement is hard this case
每个人进步速率不同，可能有的需要几年积累赶上大部队
Comparing your Progress with others is not PRODUCTIVE
CP is like a marathon, not a sprint. 竞赛是马拉松，而不是冲刺
神的（dc社区俱乐部）网站 https://discord.com/invite/AneA5wg
0) English, Math, Typing 0:22
1) Learning to Program 2:20
2) Starting CP 3:35
3) Common Mistakes 5:46
a. Relying on college courses 6:12
b. Reading too much - 5% rule 6:33
c. Learning too advanced techniques 7:06
d. Comparing yourself to others 7:51
(实际上神遥不可及打个卡练手试下套路，调整好心态吧~~)
(可能要几个月，如果使用的是神的套路/模板与系统方法)

输入

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //然后后面正常用
}

Template

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla