C2020寒假练习赛1

信息学——模拟赛

T1. WORD PROCESSOR

签到题，依照题意模拟即可。

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,k,now;
string s;
int main(){
    n=read(),k=read();
    for (register int i=1;i<=n;++i)
        {
        cin>>s;
        int len=s.size();
        if (now+len>k)
           now=0,printf("\n");
        if (now)
           printf(" ");
        cout<<s;
        now+=len;
        }
    return 0;
}

T2. PHOTOSHOOT

不难发现如果确定了$a_1$，其他的就都确定了。

又由于$n$最大只有$1000$，考虑枚举$a_1$，容易得出：

在递推的过程中开一个桶记录当前$a_i$有没有出现过。

由于要求字典序最小，如果当前序列满足题意，就可以直接输出。

时间复杂度$O(n^2)$

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n; 
int b[1005],a[1005];
bool tong[1005],err;
int main(){
    n=read();
    for (register int i=1;i<n;++i)
        b[i]=read();
    for (register int i=1;i<=n;++i)
        {
        err=0,memset(tong,0,sizeof(tong));
        a[1]=i,tong[i]=1;
        for (register int j=2;j<=n;++j)
            {
            a[j]=b[j-1]-a[j-1];
            if (a[j]<1||a[j]>n||tong[a[j]])
               {
               err=1;
               break;
               }
            tong[a[j]]=1;
            }
        if (!err)
           break;
        }
    for (register int i=1;i<n;++i)
        printf("%d ",a[i]);
    printf("%d",a[n]);
    return 0;
}

T3. RACE

由于必须整数秒，很难处理最少多少秒跑$k$米的问题。

反向思考，考虑跑$t$秒最多多少米。

先不考虑限速。

想要跑得最多肯定要一直加速。

但由于有限速的存在，不能一直加速，需要在中途减速。

最优的情况应该是先一直加速

然后一直减速使其结束时低于限速。

所以我们分两段考虑。

首先累计增速路程。

若当前速度超过限速，则开始累计降速路程。

当两端路程和到达$k$时，则得出答案。

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,t;
inline int work(int x)
{
    int cnt=1,t=0,up=0,down=0;
    while (cnt)
          {
          up+=cnt,t++;
          if (up+down>=n)
             return t;
          if (cnt>=x)
             {
             down+=cnt,t++;
             if (up+down>=n)
                return t;
             }
          cnt++;
          }
}
int main(){
    n=read(),t=read();
    while (t--)
          {
          int x=read();
          printf("%d\n",work(x));
          }
    return 0;
}