本次比赛题解——>戳这里

写在前面

真的，这一次的第一题把我坑惨了
怎么说呢，要学会反向思考，如果这么想题目复杂了，不如换个方式想，换一个研究对象。
下一次遇到考试时，像我这样的蒟蒻还是先把暴力拿满，在思考其他的。

T1 服务器需求

题目链接：服务器需求

题目描述

小多计划在接下来的n天里租用一些服务器， 所有的服务器都是相同的。接下来 $n$ 天中，第 $i$ 天需要 $a_i$ 台服务器工作，每台服务器只能在这 $n$ 天中工作 $m$ 天，这m天可以不连续。

但是计划不是一成不变的，接下来有 $q$ 次修改计划（修改是永久的），每次修改某一天 $k$ 的需求量 $a_k$ 。

小多希望知道每次修改之后，最少需要多少台服务器。

输入描述:

第一行三个正整数 $n,m,q$ ，分别表示计划的天数，每台服务器能工作的天数和修改次数。随后一行 $n$ 个非负整数，第 $i$ 个数字 $a_i$ 表示原计划第i天需要多少台服务器工作。
随后 $q$ 行，每行两个正整数 $p_i,c_i$ ，表示把第 $p_i$ 天需要的服务器数目改成 $c_i$ 。

输出描述:

第一行输出原计划需要的最少服务器数量。
随后q行，每行输出对应的修改之后，需要的最少的服务器的数量。

示例1

输入

5 3 2
1 1 1 1 1
1 2
2 3

输出

2
2
3

分析

我将题目中重要的部分标注了出来。

所有的服务器都是相同的
这m天可以不连续
修改是永久的

题解

p.s.是我想复杂了，其实这道题可以这样推：（源自出题人的题解：题解）

正确性证明
下面解释一下为什么有上面那个式子。
我们假定已知答案 $x$ ，即需要的最少的服务器个数。显然对于任意 $i$ ，有 $x \ge a_i$ 。接下来考虑如何安排这些服务器。对所有的服务器编号，从 $1$ 到 $n$ 。不妨将前 $a_1$ 台服务器安排给第一天，将接下来 $a_2$ 台服务器安排给第二天，以此类推。如果第某一天安排时，安排完了所有的服务器，则再从第一台服务器开始安排。
通过这种安排方案，可以保证在 $x \ge a_i$ 的情况下不会让同一台服务器在同一天内工作两次。而让每一台服务器运行不超过 $m$ 天，就需要服务器需求的总天次（即 $\sum{a_i}$ ）小于等于所有服务器可以工作的总天次（即 $x \cdot m$ ）。也即 $\sum{ a_i } \le x \cdot m$ 考虑到 $x$ 必须是个整数，即 $\lceil\frac{\sum {a_i}}{m}\rceil \le x$ 反推可以获得 $x$ 的答案，取最小值即为右式 $x\ge \max \left(a_i,\lceil \frac{\sum {a_i}}{m}\rceil \right)$

我的思路

题解是从服务器的角度，一天一天的安排，而我的思路停留在从时间的角度，一台服务器一台服务器地安排。思路复杂了不说，证明也不太严谨。
我们设

$sum = \sum_{i=1}^{n}a[i]$

那么，容易想到一个最优的方案答案为 $\left \lceil \frac{sum}{m} \right \rceil$ 。
即尽量将所有的机器都用满 $m$ 天的方案是最优的，但是，一台机器是不能当做几台机器同时用于一天的，这需要我们尽量减少各个日期所需要的机器的差异。
但其实有些情况下这个答案其实不成立。但是我们所求到的答案一定不会比 $\left \lceil \frac{sum}{m} \right \rceil$ 更小

当 $\left \lceil \frac{sum}{m} \right \rceil < max(a[i],1 <=i<=n)$ 时,这个答案显然不成立。

毕竟最终答案不可能小于最大值。而我们得到的 $\left \lceil \frac{sum}{m} \right \rceil$ 显然是将一台机器当做多台机器用于一天而得到的答案。而此时， $max(a[i],1 <=i<=n)*m>sum$ ，说明我们的每一台新机器都覆盖最大的一天的方案是可行的。我们买进一台机器，都将它用于剩余所需台数最多的 $m$ 天，这样的方案无疑是最优的。在这个过程中，最开始的最大值会一直保持最大，直到结束。因为我们每一次都选的是所需台数最多的 $m$ 天，若在某一次他不是最大值了，就说明最大值-1后小于了第m+1大的值，也就是说此时第m+1大=最大值，这与 $max(a[i],1 <=i<=n)*m>sum$ 矛盾。所以这种情况下，答案为 $max(a[i],1 <=i<=n)$ 。

当 $\left \lceil \frac{sum}{m} \right \rceil >= max(a[i],1 <=i<=n)$ 时,答案就是 $\left \lceil \frac{sum}{m} \right \rceil$ 。

我们还是买进一台机器，都将它用于剩余所需台数最多的 $m$ 天，而此时，最大值一定不会一直保持最大,若此时最大值保持最大，那么就是上一种情况，最优答案是最大值，但是最终的答案不可能小于 $\left \lceil \frac{sum}{m} \right \rceil$ ，故此时最大值等于 $\left \lceil \frac{sum}{m} \right \rceil$ ，答案是 $\left \lceil \frac{sum}{m} \right \rceil$ 。而当最大值改变成另外一天时，根据上面的分析，此时前m+1大都相等，这样下去，个个日期剩余的机器数在进一步减小，直到最后不大于1，此时答案便是 $\left \lceil \frac{sum}{m} \right \rceil$ ，这样，也进一步解释了上一种情况。

然后就直接维护sum与最大值就好
~~STL大法好~~
~~不开longlong见祖宗~~

代码

/*******************
User:Mandy
Language:c++
Problem:nowcoder Requair
Algorithm: 
*******************/
#include<bits/stdc++.h>

using namespace std;

const int maxn = 4e5 + 5;

typedef long long ll;
typedef pair<ll,ll> pir;

int n,m,Q;
long long a[maxn],b[maxn];
long long sum = 0,ma,mi;
struct Edge{
    ll val,id;
};
multiset<ll>s;

template<class T>inline void read(T &x){
    x = 0;char ch = getchar();bool flag = 0;
    while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
    if(flag) x = -x;
}

template<class T>void putch(const T x){if(x > 9) putch(x / 10);putchar(x % 10 | 48);}
template<class T>void put(const T x){if(x < 0) putchar('-'),putch(-x);else putch(x);}

void readdata(){
    read(n);read(m);read(Q);
    for(int i = 1;i <= n; ++ i) read(a[i]),b[i] = a[i],sum += a[i];
}

bool cmp(ll a,ll b) {return a > b;}

void work2(){
    for(int i = 1;i <= n; ++ i){
        s.insert(a[i]);
    }
    put(*--s.end());putchar('\n');
    for(int i = 1;i <= Q; ++ i){
        ll p,c;read(p);read(c);
        multiset<ll>::iterator u = s.find(a[p]);
        s.erase(u);s.insert(c);sum = sum - a[p] + c;a[p] = c;
        put(max((sum + m - 1) / m,*--s.end()));putchar('\n');
    }
}

int main(){
    freopen("big.in","r",stdin);
    freopen("out.out","w",stdout);
    readdata();
    work2();
    return 0;
}

T2 沙漠点兵

题目链接：沙漠点兵

题目描述

我们称一张无向图是仙人掌，当且仅当这张无向图连通且每条边最多属于一个简单环。我们称一张无向图是沙漠，当且仅当这张无向图中所有连通子图都是仙人掌。

给出一个 $\mathit n$ 个点， $\mathit m$ 条边的沙漠，你可以删去其中的 $\mathit k$ 条边。求能分成的连通块数量最大值。

输入描述:

第一行输入三个自然数 $\mathit n, m, k(3 \le n \le 10^6; 0 \le k \le m \le 2 \times 10^6)$ 。
接下来 $\mathit m$ 行，每行输入两个正整数 $\mathit u, v$ $(1 \le u, v \le n)$ 。保证无重边、无自环。

输出描述:

输出一行一个正整数，表示答案。

示例1

输入

5 5 3
1 2
2 3
2 4
2 5
4 5

输出

3

分析

~~其实这道题超级好拿部分分~~

容易发现其实开始的时候选割边是最划算的。
而若割边选完了，我们就得考虑环了。
看题目中的一句话：

这张无向图连通且每条边最多属于一个简单环

这就好办了。我们断一条还没有断过的环的环边，那么我们将会得到环大小-1这么多的割边。
显然一次性断出的割边越多越好，这样就不用频繁地去断对答案没有用的边了。
所以我们贪心地从大环开始断。
找连通块可以用 $Tarjan$ 或并查集
找环和一开始的割边可以直接一次DFS完事

代码

//注意每条边都最多属于一个简单环 
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 5;
const int maxm = 2e6 + 5;

int n,m,k,size,first[maxn],tot,cnt,num,tp,circnt,bridge,ans;
int father[maxn],dfn[maxn],low[maxn],s[maxn],dep[maxn];
bool vis[maxn],used[maxn];

struct Edge{
    int v,nt;
}edge[maxm << 1];

int cir[maxn];

template<class T>inline void read(T &x){
    x = 0;char ch = getchar();bool flag = 0;
    while(!isdigit(ch)) flag |= ch == '-',ch = getchar();
    while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
    if(flag) x = -x;
}

template<class T>void putch(const T x){if(x > 9) putch(x / 10);putchar(x % 10 | 48);}
template<class T>void put(const T x){if(x < 0) putchar('-'),putch(-x);else putch(x);}

void eadd(int u,int v){edge[ ++ size].v = v;edge[size].nt = first[u];first[u] = size;}
int find(int x) {return father[x] == x ? x : father[x] = find(father[x]);}

void readdata(){
    read(n);read(m);read(k);
    for(int i = 1;i <= n; ++ i) father[i] = i;
    for(int i = 1;i <= m; ++ i){
        int u,v;read(u);read(v);
        int fx = find(u),fy = find(v);
        if(fx != fy) father[fx] = fy; 
        eadd(u,v);eadd(v,u);
    }
}
/*
void Tarjan(int u,int f){
    dfn[u] = low[u] = ++tot; s[tp ++ ] = u, vis[u] = 1;
    for(int i = first[u]; i; i = edge[i].nt){
        int v = edge[i].v; if(v == f) continue;
        if(!dfn[v]){ Tarjan(v,u); low[u] = min(low[u],low[v]);}
        else if(vis[v]) low[u] = min(low[u],dfn[v]);
    }
    if(dfn[u] == low[u]){
        cnt++; int x,y = 0;
        do{
            x = s[tp - 1]; -- tp;
            father[x] = cnt; vis[u] = 0;
        }while(x != u);
    }
}
*/
void dfs(int u,int f){
    used[u] = 1;
    for(int i = first[u]; i; i = edge[i].nt){
        int v = edge[i].v; if(v == f) continue;
        if(used[v] == 1){
            if(dep[v] > dep[u]) continue;
            cir[++circnt] = dep[u] - dep[v] + 1;
            bridge += cir[circnt]; //先找出所有的环边，剩下的就都是割边 
        } else {
            dep[v] = dep[u] + 1;
            dfs(v,u);
        }
    }
}

bool cmp(int a,int b){ return a > b;}

void work(){
    /*for(int i = 1;i <= n; ++ i)
        if(!dfn[i]) Tarjan(i,0),++ num;*/
    //找连通块，也可以用tarjan 
    for(int i = 1;i <= n; ++ i){
        if(father[i] == i) ++num;
    } 
    //找环    & 一开始的割边 
    for(int i = 1;i <= n; ++ i) if(!used[i]) dfs(i,0) ;
    bridge = m - bridge; 
    if(k == 0) {put(num); return;}
    if(bridge >= k) {put(num + k); return;}

    k -= bridge; ans = bridge + num;
    if(circnt)sort(cir + 1,cir + 1 + circnt,cmp);

    for(int i = 1;i <= circnt; ++ i){
        if(k <= cir[i]) {ans += k - 1; break;}
        else ans += cir[i] - 1,k -= cir[i];//k也要更新 
    }

    put(ans);
}

int main(){
//    freopen("2.in","r",stdin);
    readdata();
    work();
    return 0;
}

T3 维护序列

题目链接：维护序列

题目描述

图片说明

分析

~~这道题的部分分也很足~~
其实只要把握住题目里的部分分，基本上就可以得一个较好的分数
而且正解确实有些毒瘤
所以我打算先坑在这里

$\color{Cornflowerblue}{为你，所向披靡！}$

$\color{Black}{By}\ \ \ \color{Royalblue}{\ Mandy.H.Y\ }$

$\color{black}{Date:\ \ 2019.11.1}$

牛客CSP-S提高组赛前集训营2解题报告

写在前面

T1 服务器需求

题目描述

分析

题解

我的思路

当时,这个答案显然不成立。

当时,答案就是。

代码

T2 沙漠点兵

题目描述

分析

代码

T3 维护序列

题目描述

分析

当 $\left \lceil \frac{sum}{m} \right \rceil < max(a[i],1 <=i<=n)$ 时,这个答案显然不成立。

当 $\left \lceil \frac{sum}{m} \right \rceil >= max(a[i],1 <=i<=n)$ 时,答案就是 $\left \lceil \frac{sum}{m} \right \rceil$ 。