2019年湘潭大学程序设计竞赛（重现赛）题解

概述

因为湘潭大学的ABCD题目过于简单，我希望大家都有能力完成上述的题目，所以这里我不做详述。所有我重点解答一下后4题的解法。

E-Watermelon

本题的解法就是维护两个值，我用L和R进行表示，L和R初始值都为m，那么很明显我们可以用L表示经过前i个人吃西瓜后所能剩下的最多西瓜数量是多少，那么对于lililalala每次减少对应的a[i]值，但是对于其他人只用减少1即可。而R表示每个人都按自己最大肚量吃所能剩下的最少的值，即每次经过一个人都需要减少对应的a[i]值。那么明显可以得出一个结论，就是如果对于除了lililalala以外的所有人如果L值先一步小于等于0，那么输出NO，如果对于lililalala当前R值更早小于等于0，那么输出YES。

#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 1e5+100;
 
int a[maxn];
 
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n, m;
        scanf("%d%d", &n, &m);
        int id = 0;
        for(int i = 0; i < n; i++){
            scanf("%d", &a[i]);
            if(a[i] > a[id]) id = i;
        }
        int L = m, R = m;
        int i = 0;
        while(true){
            if(i == id){
                if(R <= 0){
                    puts("YES");
                    break;
                }
                L -= a[i];
                R -= a[i];
            }
            else{
                if(L <= 0){
                    puts("NO");
                    break;
                }
                L--;
                R -= a[i];
            }
            i = (i+1)%n;
        }
    }
    return 0;
}

有更快的解法吗？

上述程序的时间复杂度是$O(m)$O(m)，那么能继续优化吗？？
如果我们把除了lililalala的人看做一个整体呢？那么对于lililalala每次$L$L和$R$R减少$a[i]$a[i]，对于剩余的$n-1$n−1个人每次L减少$n-1$n−1,每次$R$R减去$n-1$n−1个人$a$a数组的值的总和，但是注意维护的开头部分需要注意，因为lililala可能处于队伍的中间，例如：$n$n个人对应的$a$a数组的值是：1 2 3 4 5 4 3 2 1,那么我们首先处理前面的1 2 3 4部分，然后按照上述的思想进行处理。代码这里大家自己理解自己重新写一下。

F Black & White

因为题目要求连续的0或者连续的1的最大值，那我们可以将连续的1变为0，或者连续的0变为1即可（注：这里的连续0或者1是指0和0之间可能存在1，但是不能存在0，举个简单的例子01101010，这里面可以第一个，第四个，第六个和第八个0是连续的），一种比较好想的方法是直接二分答案，然后再序列中判断该长度能够通过m次操作得到，时间复杂度$O(n lg n)$O(nlgn)代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
string s;
int a[maxn],pre0[maxn],pre1[maxn];
int n,m;
bool check(int mid)
{
    for(int i=1;i<=n-mid+1;i++)
        if(pre1[i+mid-1]-pre1[i-1]<=m||pre0[i+mid-1]-pre0[i-1]<=m)
            return true;
    return false;
}
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        cin>>s;
        for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
        for(int i=1;i<=n;i++)
            if(a[i]==1)
                pre0[i]=pre0[i-1],pre1[i]=pre1[i-1]+1;
            else
                pre1[i]=pre1[i-1],pre0[i]=pre0[i-1]+1;
        int low=0,high=n,mid,ans=0;
        while(low<=high)
        {
            mid=(low+high)>>1;
            //cout<<mid<<endl;
            if(check(mid))
                ans=mid,low=mid+1;
            else
                high=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}

有没有更快的写法呢，当然也是存在的：我们可以将连续的0或者1变为对应1或者0，按照这样的思想顺序进行处理就可以了，时间复杂度为$O(n)$O(n)更多的细节简单见代码，代码给出了对应的注释：

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

int main()
{
    int t,n,num,k;
    cin>>t;
    while(t--){
        cin>>n>>num;
        scanf("%s",s);
        int ans=0;
        int len=strlen(s);
        int k=0,cnt=0;
        //对头部进行处理
        a[k++]=-1,b[cnt++]=-1;
        // a统计0所在的位置, b统计1所在的位置
        for(int i=0;i<len;i++)
            if(s[i]=='0') a[k++]=i;
            else b[cnt++]=i;
        //对尾部进行处理
        a[k]=len,b[cnt]=len;
        for(int i=0;i<k;i++){
            //这一步表示把从i+1(i=0是作者设的-1，所以统一从i+1开始)到i+num中所有位置中的0都变为1所能达到的最大1的长度，注意不能越界
            int s=min(k,i+num+1);
            // 注意头和尾处理的时候将0变成1，但是i+1位置如果前面是1话还需要把前面的1也考虑进去
            // 同理i+num将0变成1的时候也需要把i+num后面的1也考虑进去，所以代码中作者头部取a[i]+1，尾取a[s]-1
            // 实际从i到s一共包括num+2个0的位置了,还有就是作者头尾的处理方式值得学习。
            ans=max((a[s]-1)-(a[i]+1)+1,ans);
        }
        //下面同理将1变为0.
        for(int i=0;i<cnt;i++)
        {
            int s=min(cnt,i+num+1);
            ans=max((b[s]-1)-(b[i]+1)+1,ans);
        }
        cout<<ans<<endl;
    }
}

G Truthman or Fakeman

这道题的解法就是建图，然后对图进行染色。题目中有2中描述信息，一种是u,v,0 – u认为v是一个Fakeman; 如果u是Truthman，那么v就是Fakeman，那么u和v的身份不同，如果u是Fakeman，那么因为u说假话，那么v是Truthman，u和v的身份仍然不相同。另一种描述信息是：u,v,1 – u认为v是一个Truthman; 这里不做过多分析，类比上述分析，u和v身份相同，所以这样我们就可以对每个人设置一个身份来得到其他人的身份。
图示如下：

这里我想大概理解了，上次我教了大家邻接表建图的方法，这里我用的也是这个方法。不会的同学可以问一下会的同学，这里不做过多解释了。给出代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+100;
 
struct Edge{
    int to, val, next;
    Edge(){}
    Edge(int a, int b, int c):to(a), val(b), next(c){}
}e[maxn<<1];
 
char s[maxn];
int head[maxn], tot;
int color[maxn], vis[maxn], num0, num1;
 
bool dfs1(int u){
    bool flag = false;
    for(int i = head[u]; i != -1; i = e[i].next){
        int v = e[i].to;
        if(color[v] == -1){
            if(e[i].val) color[v] = color[u];
            else color[v] = 1-color[u];
 
            if(color[v] == 0) num0++;
            else num1++;
            flag = flag||dfs1(v);
        }
        else if(e[i].val?color[u]!=color[v]:color[u]==color[v]) return true;
    }
    return flag;
}
 
void dfs2(int u, int val){
    vis[u] = 1;
    if(color[u] == val) s[u] = '1';
    else s[u] = '0';
    for(int i = head[u]; i != -1; i = e[i].next){
        int v = e[i].to;
        if(!vis[v]) dfs2(v, val);
    }
}
 
void init(){
    memset(vis, 0, sizeof(vis));
    memset(color, -1, sizeof(color));
    memset(head, -1, sizeof(head));
    tot = 0;
}
 
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        init();
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i = 0; i < m; i++){
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            e[tot] = Edge(v, w, head[u]);
            head[u] = tot++;
            e[tot] = Edge(u, w, head[v]);
            head[v] = tot++;
        }
        int flag = 0;
        for(int i = 1; i <= n; i++)if(color[i] == -1){
            num0 = 1, num1 = 0;
            color[i] = 0;
            flag = flag||dfs1(i);
 
            if(num0 > num1) dfs2(i, 0);
            else dfs2(i, 1);
        }
 
        if(flag) puts("-1");
        else{
            for(int i = 1; i <= n; i++) printf("%c", s[i]);
            puts("");
        }
    }
    return 0;
}

Chat

一个分组背包问题，关于背包问题网上有一个非常好的教程叫做背包九讲，大家自己去搜索，不懂得群里交流。
这道题预处理的过程非常有意思：我们用mx[i][j]表示第i天与女神通话时间为j不需要上线的时间，预处理之后，讲分组背包的板子网上套就可以了

#include<bits/stdc++.h>
using namespace std;
char s[205];
int dp[205],sum[205],mx[205][205];
 
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int n, m, h;
        memset(dp, 0, sizeof(dp));
        scanf("%d%d%d",&n,&m,&h);
        memset(mx, 0, sizeof(mx));
        for(int i = 1; i <= n; i++){
            scanf("%s",s+1);
            for(int i=1;i<=m;i++)
                sum[i]=s[i]-'0'+sum[i-1];
            // ,mx[i][j]表示第i天与女神通话时间为j不需要上线的时间
            mx[i][sum[m]]=m;
            for(int j=1;j<=m;j++)
                for(int k=j;k<=m;k++)
                {
                    int tot=sum[m]-(sum[k]-sum[j-1]);
                    mx[i][tot]=max(mx[i][tot],m-(k-j+1));
                }
        }
        //dp[i]表示女神愤怒点数为i时不需要上线的最大时间
        for(int i=1;i<=n;i++){
            for(int j=h;j>=0;j--){
                for(int g=0;g<=m;g++)
                    if(j-g>=0)
                        dp[j]=max(dp[j],dp[j-g]+mx[i][g]);
            }
        }
        printf("%d\n",n*m-dp[h]);
    }
}