CSP 2020 场外篇

前言

坐标 $\texttt{ZJ}$，初三蒟蒻。

初赛 $\texttt{TG}$ 只有 $\texttt{64pts}$，不幸没过初赛（~~成功退役~~，开始为中考淦 $\texttt{whk}$）。所以只能作为场外选手，进行自测了。

普及篇

$\texttt{T1}$

与二进制相关的一道题，一个数 $x$ 能被表示成 $2$ 的正整数次幂，因此一个数在二进制下的最后一位一定是 $0$，即为偶数时才能够被拆分。

对于一个偶数，从高位开始枚举 $k$，使得最小的 $k$ 满足 $2^k \ge n$，然后 $n = n - 2^k$ 并记录 $2^k$，重复操作直到 $k = 0$。最后输出即可。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a[30],n,k,p; 
int main ()
{
    freopen ("power.in","r",stdin);
    freopen ("power.out","w",stdout);
    int n;
    scanf ("%d",&n);
    p = pow (2,25);
    while (p > 1 && n)
    {    
        while (p > n && p > 1) p >>= 1;
        if (n >= p && p > 1) a[++k] = p,n -= p;
    } 
    if (n) printf ("-1\n");
    else
    {
        for (int i = 1;i <= k;++i) printf ("%d ",a[i]);
        puts ("");
    }
    return 0;
}

$\texttt{T2}$

简单模拟，仔细读题注意一些细节就行 (比如循环范围，数据类型等)。

因为最大的点 $n = 10^5$，如果每次输入后都进行一次快排，最后可能超时。

考虑用一个数组 num[i] 记录不小于分数 $i$ 的人数。输入一个人的分数 $x$ 后，将会对数组 num[0-x] 分别产生 $1$ 的贡献，然后计算出当前获奖人数。

由题知每个选手的成绩均为不超过 $600$ 的非负整数，所以就可以从大到小枚举 num[i]，直到找到第一个 num[i] 满足不小于当前获奖人数后，输出并退出循环。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,w,x,num[605];//num[i] means the number of people that the scores are equal or more than i 
int main ()
{
    freopen ("live.in","r",stdin);
    freopen ("live.out","w",stdout);
    scanf ("%d%d",&n,&w);
    for (int i = 1;i <= n;++i)
    {
        scanf ("%d",&x);
        for (int j = 0;j <= x;++j) ++num[j];
        int now = max ((double) 1,floor ((double) i * w / 100.0));
        for (int j = 600;j >= 0;--j)
        {
            if (num[j] >= now) 
            {
                printf ("%d ",j);
                break; 
            }
        }
    }
    puts ("");
    return 0;
}

$\texttt{T3}$

这是一道模拟题，需要足够的耐心与细心。不过全输出 $0$ 或 $1$ 也可以获得一些分。(~~手动狗头~~)

$\texttt{30pts}$

每一次询问都扫一遍后缀表达式进行计算，时间复杂度为 $O(q\times |s|)$，没啥技术含量，所以其它的测试点全都 $\texttt{TLE}$ 了。

$\texttt{T4}$

一看就是一道 $\texttt{DP}$ 题目，从 $(1,1)$ 走到 $(n,m)$ 的最大价值，可以向右向下向上走。

先来看向右向下，这两个很好处理，状态转移方程如下：

$dp[i][j] = \max (dp[i][j - 1],dp[i - 1][j]) + a[i][j]$

但是对于向上，如果在按之前的顺序转移，那么 $dp[i + 1][j]$ 的值就无法在得到 $dp[i][j]$ 之前得到了。改变一下策略先搜索列再搜索行，这样就能完美解决这个问题。然后把二位改成三位，一个从上开始，另一个从下开始。

需要注意的几点有：

初始化的问题，注意有负数存在。最边上的行与列可能需要特判去进行求解
边界需要着重考虑。
全部加在一起有可能会爆 int，因此要开 long long。
搜索的顺序与求解的顺序是相关的，一定要注意有无后效性。

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int MAX = 1005;
int a[MAX][MAX],n,m;
ll dp[MAX][MAX][2];
int main ()
{
    freopen ("number.in","r",stdin);
    freopen ("number.out","w",stdout);
    //dp[i][j][0] means from (1,1) to (n,m);
    //dp[i][j][1] means from (n,m) to (1,1). 
    memset (dp,0x80,sizeof (dp));
    scanf ("%d%d",&n,&m);
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j) scanf ("%d",&a[i][j]); 
    dp[1][1][1] = dp[1][1][0] = a[1][1];
    dp[n][m][1] = dp[n][m][0] = a[n][m];
    for (int i = 2;i <= n;++i) dp[i][1][0] = dp[i - 1][1][0] + a[i][1];
    for (int i = n - 1;i >= 1;--i) dp[i][m][1] = dp[i + 1][m][1] + a[i][m];
    for (int i = 2;i <= m;++i)
    {
        for (int j = 1;j <= n;++j)//left 
            dp[j][i][0] = dp[j][i][1] = max (dp[j][i - 1][0],dp[j][i - 1][1]) + a[j][i];
        for (int j = 2;j <= n;++j)//down
            dp[j][i][0] = max (dp[j][i][0],dp[j - 1][i][0] + a[j][i]);
        for (int j = n - 1;j >= 1;--j)//up
            dp[j][i][1] = max (dp[j][i][1],dp[j + 1][i][1] + a[j][i]);
    }
    printf ("%lld\n",max (dp[n][m][0],dp[n][m][1]));
    return 0;
}