2019-12-29 普及模拟赛 题解

出给学弟的普及模拟赛，现在题解搬到这里来，估计也没人看了，坟贴一个。

T1 密码(password)

题意

给出 $6$ 个字符串，每个字符串有一个标号没有两个标号相同的字符串，标号的范围为 $1\sim 6$。按照标号顺序拼成一个新的字符串，求这个字符串。

对于 $100\%$ 的数据，$\sum |S|≤1000$，且保证 $S$ 中没有空格字符。

算法一

基础题，边读入边开一个 string 数组记录，最后按顺序输出即可。时空复杂度均为 $O(\sum {|S|})$，期望得分 $100$ 分。

Code

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;

string s[7];

int main()
{
    freopen("password.in","r",stdin),freopen("password.out","w",stdout); 
	
    int i,x; string c;
    for (i=1; i<=6; i++) cin>>x>>c,s[x]=c;
	
    for (i=1; i<7; i++) cout<<s[i];
	
    return 0;
} 

T2 环绕膜拜(round)

题意

给定平面上不同的 $n$ 个点，$n$ 为偶数。求一个点，使得这 $n$ 个点组成的图形关于这个点对称；若不存在这样的点，输出 $-1$。

对于 $5\%$ 的数据，$n=2$。
对于 $50\%$ 的数据，$1≤n≤1000$。
对于 $100\%$ 的数据，$1≤n≤10^6$ , $-10^6≤|x_i|,|y_i|≤10^6$，并且保证 $n$ 是一个偶数。
保证若存在对称点，其为整点。

算法一

直接输出两个点连线，期望得分 $5$ 分。

我们用 $cnt_x$ 来表示数值为 $x$ 的牌出现了多少次。那么我们就从 $1$ 到 $n$ 枚举对子，再枚举刻子和顺子。那么深搜的时间复杂度是 $O(2n^2)$，合起来就是 O$(2n^3)$，空间复杂度为 $O(n)$，期望得分 $70$ 分。

算法二

开两个指针 $i,j$ 暴力判断所有的 $O(n^2)$ 的方式是否满足。时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$，期望得分 $50$ 分。

算法三

我们以 $x$ 为第一关键字，以 $y$ 为第二关键字从小到大排序（水平序）。那么可能的配对方案只有 $1$ 和 $n$ 配对，$2$ 和 $n-1$ 配对，$\ldots$，$\frac{n}{2}$ 和 $\frac{n}{2}+1$ 配对。我们1 $O(n)$ 判断一下这个方案是否满足要求即可。

时间复杂度为 $O(n\log{n})$（瓶颈在排序上），空间复杂度为 $O(n)$，期望得分 $100$ 分。

Code

#include <stdio.h>
#include <algorithm>
#define il inline
using namespace std;
const int N=1000005;

int n,X,Y;
struct node{int x,y;}d[N];

il bool cmp(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;}

int main()
{
    freopen("round.in","r",stdin),freopen("round.out","w",stdout); 
	
    scanf("%d",&n); int i;
    for (i=1; i<=n; i++) scanf("%d%d",&d[i].x,&d[i].y);
    sort(d+1,d+n+1,cmp);

    X=(d[1].x+d[n].x)/2,Y=(d[1].y+d[n].y)/2;
    for (i=2; i<=(n+1)/2; i++) if ((d[i].x+d[n-i+1].x)/2!=X||(d[i].y+d[n-i+1].y)/2!=Y) return 0*puts("There is not a place like that.");
    printf("%d %d",X,Y);

    return 0;
}

T3 花生蛋糕(cake)

题意

有一个 $n\times m$ 的网格图，图上有 $k$ 个关键点，求一个切割方式，满足：

• 切出来的每一部分都是矩形
• 每一部分都恰好包含一个关键点

对于 $5\%$ 的数据，$k=1$。
对于 $15\%$ 的数据，$n,m≤3,k≤7$。
对于另外 $5\%$ 的数据，$k=n×m$。
对于 $100\%$ 的数据，$1≤n,m≤300,1≤k≤n×m$。

算法一

直接全部输出1即可，期望得分 $5$ 分。

算法二

$1$ 到 $n\times m$ 各输出一次即可，期望得分 $5$ 分，期望总得分 $10$ 分。

算法三

暴力搜索怎么切割，时间复杂度为 $O(nm^k)$，空间复杂度为 $O(nm)$，期望得分 $15$ 分期望总得分 $20$ 分。

算法四

这里只提供一种构造方案。

从上到下走，先走到第一个关键点个数非 $0$ 行，设此时到了第 $z+1$ 行。

接着对剩下的 $n-z$ 行，分两种情况讨论：

• 这行的关键点数目非 $0$，设其有 $x$ 个花生。
  那么对于前 $x-1$ 个，染色染到其位置为止；对于最后一个，则把剩下的格子都染上。
• 这行的关键点数目为 $0$。
  那么直接和上一行染成一样的就行了。

最后把第1到 $z$ 行，直接把其染成和第 $z+1$ 的颜色就行了。

时空复杂度均为 $O(nm)$，期望得分 $100$ 分。

Code

#include <stdio.h>
using namespace std;
const int N=305;

int n,m,k,last,z,ans[N][N]; char mp[N][N];

int main()
{
    freopen("cake.in","r",stdin),freopen("cake.out","w",stdout);
	
    scanf("%d%d%d",&n,&m,&k); int i,j,cnt;
    for (i=1; i<=n; i++)
    {
        scanf("%s",mp[i]+1);
        for (j=1,cnt=0; j<=m; j++) cnt+=mp[i][j]=='#';
        if (!cnt) 
        {
            if (z==i-1) z++;
            else{for (j=1; j<=m; j++) ans[i][j]=ans[i-1][j];}
        }
        else
        {
            for (j=1,last++; j<=m; j++)
            {
                ans[i][j]=last;
                if (mp[i][j]=='#') if (--cnt!=0) last++;
            }
        }
    }
    for (i=z; i>=1; i--) for (j=1; j<=m; j++) ans[i][j]=ans[i+1][j];
    for (i=1; i<=n; i++) for (j=1; j<=m; j++) printf("%d%c",ans[i][j]," \n"[j==m]);
	
    return 0;
}

T4 零线火线(powerline)

题意

一个人的初始生命值为 $HP$ （生命值无上限），接下来 $n$ 秒，他每秒会受到一次伤害，第 $i$ 秒的伤害值为 $a_i$ 。任何时刻，若 $HP≤0$ ，则视为死亡。

这个人有回血技能：
每受到一次伤害，就会积累一点能量。每次使用能力，就会使用所积累的所有能量，恢复 $15\times$ 能量点数的生命值，并且相邻两次使用的时间至少要有 $CD$ 秒的间隔。

求不会死亡的 $CD$ 的最小值。

对于 $30\%$ 的数据，$n≤12$。
对于 $100\%$ 的数据，$1≤n≤500,0≤a_i≤2000$。

算法一

直接暴力搜索每个位置填上什么数，时间复杂度为 $O(n^m)$，空间复杂度为 $O(n)$，期望得分 $50$ 分。

算法二

首先答案是满足单调性的，可以二分答案，转化为判定性问题。

接下来我们设 $d_i$ 表示第 $1$ 到 $i$ 秒释放能力的次数，记 $sum_i=\sum\limits_{j=1}^{i}{a_j}$。

那么对于 $d_i$，我们有如下几种限制：

• 因为一秒内最多只能释放一次技能，所以有 $0\le d_i-d_{i-1}\le 1$。
• 假设二分值为 $CD$，那么因为两次释放能力的间隔少有 $CD$ 秒，所以有 $d_i-d_{i-CD}\le 1$。
• 设为了存活，到第 $i$ 秒至少需要释放 $pos$ 的能量，则 $pos$ 必须满足：$15pos+HP-sum_{i+1}\le 1$。
  又因为 $pos$ 要最小，所以 $pos=\lceil \frac{sum_{i+1}-HP+1}{15} \rceil$。
  所以在第 $pos$ 到 $i$ 秒必须释放一次能力，所以有 $d_i-d_{pos-1}\ge 1$。

发现这些都是差分约束类的，于是直接建图看最短（长）路是否存在，即是否有负（正）环即可，这可用 DFS 版 SPFA 实现。

时间复杂度最坏是 $O(nm\log)$ 的，实际远远达不到这个上界，空间复杂度为 $O(n)$，期望得分 $100$ 分。

#include <cstdio>
#include <cmath>
#define il inline
using namespace std;
const int N=505,M=1e5+5;

int n,hp,cd=-1,a[N],sum[N],dis[N],ok[N];
int to[M],nx[M],wt[M],hd[N],sze;

il void add(int u,int v,int w){to[++sze]=v,nx[sze]=hd[u],wt[sze]=w,hd[u]=sze;}

il int SPFA(int u)
{
    ok[u]=1; int i,v;
    for (i=hd[u]; i!=n+1; i=nx[i])
	if (dis[v=to[i]]<dis[u]+wt[i])
	{
	    dis[v]=dis[u]+wt[i];
	    if (ok[v]||SPFA(v)) return 1;
	}
    return ok[u]=0;
}

il bool check(int x)
{
    int i,o=0; sze=0;
    for (i=0; i<=n; i++) dis[i]=ok[i]=0,hd[i]=n+1;
    for (i=1; i<=n; i++) add(i-1,i,0),add(i,i-1,-1);
    for (i=x; i<=n; i++) add(i,i-x,-1);
    for (i=1; i<n; i++)
    {
        if (sum[i+1]-hp+1<=0) continue;
        int pos=ceil(1.0*(sum[i+1]-hp+1)/15.0);
        if (pos>i) return 0;
        add(pos-1,i,1);
    }
    for (i=0; i<=n&&!o; i++) o|=SPFA(i);
    return !o;
}

int main()
{
    freopen("powerline.in","r",stdin),freopen("powerline.out","w",stdout); 
	
    scanf("%d%d",&n,&hp); int i;
    for (i=1; i<=n; i++) scanf("%d",a+i),sum[i]=sum[i-1]+a[i];
	
    int l=1,r=n,mid;
    while (l<=r)
    {
        mid=l+r>>1;
        if (check(mid)) cd=mid,l=mid+1;
        else r=mid-1;
    }
	
    if (cd==n) printf("Peanut can play with the wires at will.");
    else printf("%d",cd);
	
    return 0;
}