# CSP-J2020第二轮 解题分析

1.优秀的拆分

2 i 2^i 2i可以表示为 1 < < i 1<1<<i

``````#include
#include
#include
using namespace std;
int main()
{
int n; scanf("%d", &n);
if (n % 2) printf("-1\n");
else
{
for (int i = 24; i >= 1; --i)
{
if (n / (1 << i) == 1)
{
n -= (1 << i);
printf("%d ", 1 << i);
}
}
}
return 0;
}
``````

``````#include
#include
#include
using namespace std;
int b[30] ={0,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216};
int v[18000000];
int main()
{
int n; scanf("%d", &n);
if (n % 2)
{
printf("-1"); return 0;
}
for (int i = 1; i <= 24; ++i) v[b[i]] = 1;
int x = n;
while (x)
{
if (v[x])
{
printf("%d ", x);
x = n - x;
n = x;
}else --x;
}
return 0;
}
``````

2.直播获奖

``````#include
#include
#include
#include
#include
using namespace std;
int f[610];
int main()
{
int n, w, cnt, d;
scanf("%d%d", &n, &w);
for (register int t = 1; t <= n; ++t)
{
scanf("%d", &d);
++f[d];  // 记录该成绩的人数有多少个
cnt = t * w / 100;
if (cnt < 1) cnt = 1;
// 找排名第cnt的分数
int s = 0, k;
for (k = 600; k >= 0; --k)
{
s += f[k];
if (s >= cnt) break;
}
printf("%d ", k);
}
return 0;
}
``````

1.插入排序。

2.对顶堆。

3.表达式

``````struct node
{
int par, lchild, rchild,  data;
char c;
}stree[1000010];
``````

``````#include
#include
#include
using namespace std;
char s[1000010];
int a[100010], n, cnt, sstack[1000010], stop;
struct node
{
int par, lchild, rchild,  data;
char c;
}stree[1000010];
int main()
{
int len = 0;
while ((s[++len] = getchar()) != '\n'); s[len] = 32;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
cnt = n;
for (int i = 1; i <= len; ++i)
{
if (s[i] == 'x')
{
int snum = 0, t = i + 1;
while (s[t] != 32)
{
snum = snum * 10 + s[t] - '0';
++t;
}
i = t;
sstack[++stop] = snum;
stree[snum].data = a[snum]; stree[snum].c = a[snum] + '0';
}else if (s[i] == '!')
{
stree[++cnt].lchild = sstack[stop]; --stop;
stree[stree[cnt].lchild].par = cnt;
stree[cnt].data = !stree[stree[cnt].lchild].data;
stree[cnt].c = '!';
sstack[++stop] = cnt;
}else if (s[i] == '&')
{
stree[++cnt].rchild = sstack[stop]; --stop;
stree[cnt].lchild = sstack[stop]; --stop;
stree[stree[cnt].lchild].par = cnt;
stree[stree[cnt].rchild].par = cnt;
stree[cnt].data = stree[stree[cnt].lchild].data & stree[stree[cnt].rchild].data;
stree[cnt].c = '&';
sstack[++stop] = cnt;
}else if (s[i] == '|')
{
stree[++cnt].rchild = sstack[stop]; --stop;
stree[cnt].lchild = sstack[stop]; --stop;
stree[stree[cnt].lchild].par = cnt;
stree[stree[cnt].rchild].par = cnt;
stree[cnt].data = stree[stree[cnt].lchild].data | stree[stree[cnt].rchild].data;
stree[cnt].c = '|';
sstack[++stop] = cnt;
}
}
int q; scanf("%d", &q);
while (q--)
{
int t; scanf("%d", &t);
int p, sres = !a[t];
while (1)
{
p = stree[t].par;
if (stree[p].c == '!') sres = !sres;
else if (stree[p].c == '&')
{
if (stree[p].lchild == t) sres = sres & stree[stree[p].rchild].data;
else sres = sres & stree[stree[p].lchild].data;
}else if (stree[p].c == '|')
{
if (stree[p].lchild == t) sres = sres | stree[stree[p].rchild].data;
else sres = sres | stree[stree[p].lchild].data;
}
if (sres == stree[p].data)
{
sres = stree[cnt].data; break;
}
t = p;
if (stree[t].par == 0) break;
}
printf("%d\n", sres);
}
return 0;
}
``````

1.全都是 ! ! !或大部分是。

2.全都是 & \& &或大部分是。

3.全都是 ∣ | 或大部分是。

``````#include
#include
#include
#include
using namespace std;
char s[1000010];
int a[100010], n, cnt, sstack[1000010], stop;
struct node
{
int lchild, rchild,  data, tag;
char c;
}stree[1000010];
void print_tag(int t)
{
if (stree[t].lchild == 0 && stree[t].rchild == 0) return;  // 叶结点
if (stree[t].tag == 1)
{
stree[stree[t].lchild].tag = stree[stree[t].rchild].tag = 1;
}else if (stree[t].c == '&')
{
if (stree[stree[t].lchild].data == 0) stree[stree[t].rchild].tag = 1;
if (stree[stree[t].rchild].data == 0) stree[stree[t].lchild].tag = 1;
}else if (stree[t].c == '|')
{
if (stree[stree[t].lchild].data == 1) stree[stree[t].rchild].tag = 1;
if (stree[stree[t].rchild].data == 1) stree[stree[t].lchild].tag = 1;
}
print_tag(stree[t].lchild);
print_tag(stree[t].rchild);
}
int main()
{
int len = 0;
while ((s[++len] = getchar()) != '\n'); s[len] = 32;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
cnt = n;
for (int i = 1; i <= len; ++i)
{
if (s[i] == 'x')
{
int snum = 0, t = i + 1;
while (s[t] != 32)
{
snum = snum * 10 + s[t] - '0';
++t;
}
i = t;
sstack[++stop] = snum;
stree[snum].data = a[snum]; stree[snum].c = a[snum] + '0';
}else if (s[i] == '!')
{
stree[++cnt].lchild = sstack[stop]; --stop;
stree[cnt].data = !stree[stree[cnt].lchild].data;
stree[cnt].c = '!';
sstack[++stop] = cnt;
}else if (s[i] == '&')
{
stree[++cnt].rchild = sstack[stop]; --stop;
stree[cnt].lchild = sstack[stop]; --stop;
stree[cnt].data = stree[stree[cnt].lchild].data & stree[stree[cnt].rchild].data;
stree[cnt].c = '&';
sstack[++stop] = cnt;
}else if (s[i] == '|')
{
stree[++cnt].rchild = sstack[stop]; --stop;
stree[cnt].lchild = sstack[stop]; --stop;
stree[cnt].data = stree[stree[cnt].lchild].data | stree[stree[cnt].rchild].data;
stree[cnt].c = '|';
sstack[++stop] = cnt;
}
}

print_tag(cnt);  // 打标记，打上标记的结点，值是否改变，对结果不影响

int ans = stree[cnt].data;
int q; scanf("%d", &q);
while (q--)
{
int t;  scanf("%d", &t);
if (stree[t].tag == 0) printf("%d\n", !ans); else printf("%d\n", ans);
}
return 0;
}
``````

4.方格取数

f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0]：第 j j j列从上到下、从左到右到达 ( i , j ) (i, j) (i,j)的最大值。

f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1]：第 j j j列从下到上、从左到右到达 ( i , j ) (i, j) (i,j)的最大值。

f [ i ] [ j ] [ 2 ] f[i][j][2] f[i][j][2]：合并以上两种方式，到达 ( i , j ) (i, j) (i,j)的最大值。

``````#include
#include
#include
#define ll long long
using namespace std;
int n, m, a[1010][1010];
ll f[1010][1010][3];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);

for (int i = 1; i <= n; ++i) f[i][1][1] = f[i][1][0] = f[i][1][2] = f[i-1][1][0] + a[i][1];

for (int j = 2; j <= m; ++j)
{
// f[i][j][0]
f[1][j][0] = f[1][j-1][2] + a[1][j];
for (int i = 2; i <= n; ++i)
f[i][j][0] = max(f[i][j-1][2], f[i-1][j][0]) + a[i][j];
// f[i][j][1]
f[n][j][1] = f[n][j-1][2] + a[n][j];
for (int i = n - 1; i >= 1; --i)
f[i][j][1] = max(f[i][j-1][2], f[i+1][j][1]) + a[i][j];
// f[i][j][2]
for (int i = 1; i <= n; ++i)
f[i][j][2] = max(f[i][j][0], f[i][j][1]);
}
printf("%lld\n", f[n][m][2]);
return 0;
}
``````

f [ i ] [ j ] [ 0 ] f[i][j][0] f[i][j][0]表示从上到下、从左到右到达 ( i , j ) (i, j) (i,j)的最大值， f [ i ] [ j ] [ 1 ] f[i][j][1] f[i][j][1]表示从下到上、从左到右到达 ( i , j ) (i, j) (i,j)的最大值。

``````ll dfs(int x, int y, int t)
{
if (x < 1 || x > n || y < 1 || y > m) return mininf;
if (f[x][y][t] != mininf) return f[x][y][t];
if (t == 0) f[x][y][t] = max(dfs(x-1, y, 0), max(dfs(x, y-1, 0), dfs(x, y-1, 1))) + a[x][y];
else f[x][y][t] = max(dfs(x+1, y, 1), max(dfs(x, y-1, 0), dfs(x, y-1, 1))) + a[x][y];
return f[x][y][t];
}
printf("%lld\n", dfs(n, m, 0));
``````

(0)