CSP-J 2020 #2

T1:

比较简单的模拟题。

大概就是看能否将给出的正整数 $x$ 拆分成 $x=2^{\alpha_1}+2^{\alpha_2}+......+2^{\alpha_n}$ 的形式，使得 $\alpha_{min} \gt 0$ 成立。

可以发现只要 $2 \mid n$ 就一定有解，若有解再根据题意模拟求解即可。要从大到小输出！！！

#include <iostream>
#include <string.h>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
int x,cnt;
vector<long long> ans;

int main()
{
    scanf("%d",&x);
    if(x % 2 != 0) 
    {
        printf("-1\n");
        return 0;
    }
    while(x != 0)
    {
        if(x & 1) 
            ans.push_back((long long)1<<cnt);
        x >>= 1;cnt++;continue;
    }
    for(int i = ans.size()-1;i >= 0;i--)
        printf("%d ",ans[i]);
    return 0;
}

T2:

此处提供一种歪解，正解请 出门左转

分析一下这个题需要使用的数据结构的需求，问题就会变得很简单：

1.可以在任意位置插入元素和查询元素。

2.每次插入或查询的时间复杂度 $T \le \rm{\Theta}(\log_2^n)$

那么，可以想到用 vector 在线解决：

设置一个 vector 容器，里面单调维护目前已出现过的所有元素。当读入一个元素时，利用二分 $\rm{\Theta}(\log_2^n)$ 求出当前元素在 vector 中应当处于的位置并插入。对于当前总人数 $i$ ，先 $\rm{\Theta}(1)$ 求出当前应当晋级的人数，然后直接通过取 vector[人数] (此处为降序排列)更新分数线并输出。

此处的vector可以包含多个同分的人：假设分数 $w_i$ 有重，那么如果 $w_i > score\ line$ ，这里面的所有人都要一个一个算进去，那么如果去重就会有bug，如果当前 $w_i=score\ line$ ，那么也会取到最上面的分数为 $w_i$ 的人。又因为最后那一拨可以算作一个人，所以不影响。

#include <algorithm>
#include <iostream>
#include <string.h>
#include <cstring>
#include <vector>
#include <map>

using namespace std;
int n,w,now_ans,pp;
vector<int> ans_arr;
map<int,bool> rec;

int main()
{
    //freopen("live.in","r",stdin);
    //freopen("live.out","w",stdout);
    scanf("%d%d",&n,&w);now_ans=0x3f3f3f3f;
    for(int i = 1;i <= n;i++)
    {
        int t;scanf("%d",&t);
        ans_arr.insert(upper_bound(ans_arr.begin(),ans_arr.end(),t),t);
        int bnd = max(1,i*w/100);
        if(now_ans != ans_arr[i-bnd]) now_ans = ans_arr[i-bnd];
        printf("%d ",now_ans);
    }
    //fclose(stdin);fclose(stdout);
    return 0;
}

T3:

这题属于是绝对的巨模拟。

观察一下，可以发现只要通过之前学的表达式树的方式来表示这个表达式，问题就很简单了。

我们只需要利用深搜确定树上所有节点的值的改变是否会影响到整体式子即可
。
但是，如果直接确定所有节点，发现两个问题：

1.太慢了，那样相当于每个节点向下扩展，复杂度至少 $\rm{\Theta}(uv)$ 级别。

2.当枚举一个非叶子节点时，其值会因为其下的值改变而改变，只有叶子节点没有这个性质。

综上，实际上可以直接搜每一个叶子节点并判定，如果会改变那么同时向上方的节点传递即可。

#include <iostream>
#include <string.h>
#include <cstring>

using namespace std;
const int N = 1000010;
int n,m,q,h[N],e[N],ne[N],w[N];//邻接表存储树
int idx,stk[N],tail;//stk和tail是模拟栈
char cnts[N],s[N];bool st[N];

inline void insert(int a,int b)
{e[idx] = b,ne[idx] = h[a],h[a] = idx++;}

inline int dfs_1(int rt)
{
    if(rt <= n) return w[rt];
    if(cnts[rt] == '!') return w[rt] = !dfs_1(e[h[rt]]);
    else if(cnts[rt] == '&')
    {
        w[rt] = 1;
        for(int i = h[rt];i != -1;i = ne[i])
            w[rt] &= dfs_1(e[i]);
        return w[rt];
    }else
    {
        w[rt] = 0;
        for(int i = h[rt];i != -1;i = ne[i])
            w[rt] |= dfs_1(e[i]);
        return w[rt];
    }
}

inline void dfs_2(int rt)
{
    st[rt] = true;
    if(rt <= n) return ;
    if(cnts[rt] == '!') dfs_2(e[h[rt]]);
    else
    {
        int x = e[h[rt]],y = e[ne[h[rt]]];
        if(cnts[rt] == '&')
        {
            if(w[x]) dfs_2(y);
            if(w[y]) dfs_2(x);
        }
        else
        {
            if(!w[x]) dfs_2(y);
            if(!w[y]) dfs_2(x);
        }
    }
    return ;
}

int main()
{
    cin.tie(0),cout.tie(0);
    cin.getline(s,N);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
        scanf("%d",&w[i]);
    memset(h,-1,sizeof(h));
    m = n;
    for(int i = 0;s[i];i++)
        if(s[i] == 'x')//未知数
        {
            int t = 0;i++;
            while(s[i] <= '9' && s[i] >= '0')
                {t = t * 10 + s[i] - '0',i++;}
            stk[++tail] = t;
        }else if(s[i] == '!')//取反运算符
            cnts[++m] = s[i],insert(m,stk[tail--]),stk[++tail] = m,i++;
        else
            cnts[++m] = s[i],insert(m,stk[tail--]),
            insert(m,stk[tail--]),stk[++tail] = m,i++;

    int rt = stk[tail];
    int res = dfs_1(rt);dfs_2(rt);
    scanf("%d",&q);
    while(q--)
    {
        int op;
        scanf("%d",&op);
        if(st[op] == true) printf("%d\n",!res);
        else printf("%d\n",res);
    }
    return 0;
}

T4:

首先，这应该是个dp，那么分别考虑状态转移和状态表示。

状态表示

正常的方格取数做法是不合法的，因为可能出现下面这种情况导致转移失去无后效性。

图中，红色的路径优先度显然比黑色的优先度更高，会导致 f[i][j+1] 这个位置被错误地更新，那么会出现错误。

所以必须储存多个路径转移方式不同的情况并在这其中取最大值。

$f_{i,j,0}$ 表示从 $w[i][j-1]$ 转移到 $w[i][j]$ 这个点的情况集合中的最大值(向右走)。

$f_{i,j,1}$ 表示从 $w[i-1][j]$ 转移到 $w[i][j]$ 这个点的情况集合中的最大值(向下走)。

$f_{i,j,2}$ 表示从 $w[i+1][j]$ 转移到 $w[i][j]$ 这个点的情况集合中的最大值(向上走)。

那么，目标答案应该是关于位置 $(n,m)$ 的。考虑到 $w[n][m]$ 这个位置下面啥都没有，可以仅从上和左两个方向进行转移： ans = max(f[n][m][0],f[n][m][1]) 。

状态计算：

还是来看一张图：

可以将图中状态转移分成三种情况进行讨论：

case 0:

如果从右面更新 $f_{i,j,0}$ ，那么右边那个的三种状态都可以进行访问，那么可以得到转移方程 $f_{i,j,0}=max(f_{i,j-1,0},f_{i,j-1,1},f_{i,j-1,2})$ 。

case 1:

如果从上面更新 $f_{i,j,1}$ ,那么可以发现有不可用的状态 $f_{i-1,j,2}$ 。看到状态表示的含义，可以得到如果调用该状态，相当于是从 $(i,j)$ 这个点先往上走再走回来，这样会重复经过 $(i,j)$ 这个点，不符合题目中说的每个点只能走一次的规则，所以只有两种状态可以用，得到状态转移方程 $f_{i,j,1} = max(f_{i-1,j,0},f_{i-1,j,1})$。

case 2:

这个情况的思考方式几乎和 $f_{i,j,1}$ 一模一样，只是方向有所改变。因此，可以直接推出转移方程 $f_{i,j,2}=max(f_{i+1,j,0},f_{i+1,j,2})$。

那么，可以得到当前算法时间复杂度为 $\rm{\Theta}(3 \times nm)$ ，一定稳过。

#include <iostream>
#include <string.h>
#include <cstring>

using namespace std;
typedef long long LL;
const int N = 1010;
const long long _INF = -0x3f3f3f3f3f3f3f3f;
LL n,m,g[N][N],f[N][N][3];

inline void init()//先预设为最小值，不用0是因为可能出现负权点。
{
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            for(int k = 0;k < 3;k++)
                f[i][j][k] = _INF;
    return ;
}

inline LL search(LL x,LL y,LL st)
{
    if(x < 1 || y < 1 || x > n || y > m) return _INF;
    if(f[x][y][st] != _INF) return f[x][y][st];
    if(st == 0) f[x][y][st]=max(search(x,y-1,0),max(search(x,y-1,1),search(x,y-1,2)))+g[x][y];
    else if(st == 1) f[x][y][st] = max(search(x-1,y,0),search(x-1,y,1))+g[x][y];
    else if(st == 2) f[x][y][st] = max(search(x+1,y,0),search(x+1,y,2))+g[x][y];
    return f[x][y][st];
}

int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
            scanf("%lld",&g[i][j]);
    init();f[1][1][0] = f[1][1][1] = g[1][1];
    printf("%lld\n",max(search(n,m,0),search(n,m,1)));
    return 0;
}

综上所述，这次的J组题目比较有难度。