NOIP2020 CSP/J2 注释代码分享
通过不懈的听y总的课，我终于搞定CSP/J2的题目了……
不过通过我的查看，有些题目是没有注释的，想要清楚的明白程序的意思，就唯有听课，很耗时间（似乎不小心惹怒y总了）……
所以我，一个蒟蒻，一个萌新，就将我写了注释的代码放上来。
当然，如果发现有错的，请评论告诉我，我会及时更改。
第一题：power
#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
if(n%2){ // 由于如果是奇数的话，是不可能用2的正整数次幂相加得出的，所以这里加个特判
cout<<"-1";
return 0;
}
//这道题其实就是将这个数变成二进制表示的数，然后判断哪一位是1，那么就加上这一位\
表示的2的正整数次幂。\
例如：\
10的二进制表示是1010\
最高位和倒数第二位是1\
最高位是2^3=8\
倒数第二位是2^1=2\
8+2=10
for(int i=23;i>=0;i--)
if(n>>i&1) // 如果这一位是1
cout<<(1<<i)<<' '; // 输出这一位表示的2的正整数次幂
return 0;
}
第二题：live
第一种：yxc的代码（使用小根堆和大根堆）
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, w;
scanf("%d%d", &n, &w);
priority_queue<int> left; // 存储没过分数线的分数
priority_queue<int, vector<int>, greater<int>> right; // 存储过了分数线的分数
// 这个程序使用对顶堆存储分数
// 这个程序将right的堆顶分数表示为分数线
for (int i = 1; i <= n; i ++ )
{
int x; // 定义一个临时输入变量
scanf("%d", &x); // 输入第i个学生的分数
if (right.empty() || x >= right.top()) right.push(x); // 如果没有学生或者\
这个分数大于right的堆顶，那么就将x存储到right中
else left.push(x); // 如果这个学生没有超过了分数线，且这个学生不是第一个学生，\
那么就将他存进left里面
// 处理学生分数
int k = max(1, (int)(i / 100.0 * w)); // 计算现在的计划获奖人数
// 这里并没有特判过了分数线的人是多的还是少的，但是其实不需要\
特判，因为如果是多的话，那么只会执行对应的那个while循环，另一种\
情况也一样 ，\
而且由于这个程序用不着判断改变位置的分数，所以并不需要排序
while (right.size() > k) left.push(right.top()), right.pop(); // 如果\
现在的获奖人数大于k，那么就将部分人调取left（没有过分数线）
while (right.size() < k) right.push(left.top()), left.pop(); // 如果\
现在的获奖人数小于k，那么就从left（没有过分数线）中抽取一部分人
printf("%d ", right.top()); // 输出现在的分数线
}
return 0;
}
第二种：题解代码（使用桶排和暴力）：
#include <bits/stdc++.h>
using namespace std;
int n,m,x,a[1000000];
int box(int k){
if(!k) k=1; // 特判k<1
for(int i=600;~i;i--){ // 由于分数最大是600，所以就从600倒循环。
k-=a[i]; // 每次减去得到了这个分数的人
if(k<=0) // 如果名额没有了的话
return i; // 返回现在这个分数
}
return 0x3f; // 如果搜索不到一个合法的分数线的话，随便输出一个数。（当然，\
这个返回不可能会执行，否则就是其他问题了……）
}
int main(){
cin>>n>>m; // 输入
for(int i=1;i<=n;i++){
cin>>x; // 输入第i个学生的成绩
a[x]++; // 桶排
cout<<box(i*m/100)<<' '; // 输出实时的分数线
}
return 0;
}
第三题（码量最大的题）：expr
#include <bits/stdc++.h>
using namespace std;
const int N=1000010; // 数组范围
int n,m; // 定义
char str[N]; // 内部节点编号
int w[N]; // 每个点的存值
int h[N],e[N],ne[N],idx; // 邻接表储存
char c[N]; // 每个点的类型
int stk[N],tt; // 使用栈建立树
bool st[N]; // 标记哪个点会影响到答案
void add(int a,int b){ // 邻接表加边
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int dfs1(int u){ // 计算答案
if(u<=n) // 说明是变量，所以直接退出
return w[u]; // 返回w[u]
if(c[u]=='!') // 如果当前节点是非（！）
return w[u]=!dfs(e[h[u]]); // 返回！所计算的数，然后开始计算
else if(c[u]=='&'){ // 如果当前符号是与（&）
w[u]=1; // 初始化计算初值
for(int i=h[u];~i;i=ne[i]) // 邻接表遍历它的儿子
w[u]&=dfs1(e[i]); // 计算值
return w[u]; // 返回结果
}
else{ // 如果当前节点是或（|）
w[u]=0; // 初始化计算初值
for(int i=h[u];~i;i=ne[i]) // 邻接表遍历它的儿子
w[u]|=dfs1(e[i]); // 计算值
return w[u]; // 返回结果
}
}
void dfs2(int u){ // 检查哪些节点影响答案的值
st[u]=true; // 初始化当前节点会影响答案的值
if(u<=n) // 如果没有儿子
return; // 直接退出
if(c[u]=='!') // 如果这个符号是非（！）
dfs2(e[h[u]]); // 判断一下它的儿子
else{ // 如果这个符号是与或者是或
int a=e[h[u]]; // 取出它的左儿子
int b=e[ne[h[u]]]; // 取出它的右儿子
if(c[u]=='&'){ // 如果这个符号是与（&）
if(w[a]) dfs2(b); // 如果左儿子是1，那么判断一下右儿子
if(w[b]) dfs2(a); // 如果右儿子是1，那么判断一下左儿子
}
else{ // 如果这个符号是或（|）
if(!w[a]) dfs2(b); // 如果左儿子是0，那么判断一下右儿子
if(!w[b]) dfs2(a); // 如果右儿子是0，那么判断一下左儿子
}
}
}
int main(){
cin.getline(str,N); // 由于有空格，所以需要整行读入
scanf("%d",&n); // 变量数量
m=n; // 将存储标号的数组从n开始使用（方便计算答案）
for(int i=1;i<=n;i++) // 读入变量
scanf("%d",&a[i]);
memset(h,-1,sizeof h); // 邻接表初始化
for(int i=0;str[i];i++){ // 将这个后缀表达式转化为一个表达式树
if(str[i]=="x"){ // 如果这个数是个变量
int k=0; // 找出下标
i++;
while(str[i]>="0"&&str[i]<="9") // 分解这个变量的下标
k=k*10+str[i++]-'0'; // 合起下标
stk[++tt]=k; // 存储这个下标
}
else if(str[i]=="!"){ // 如果这个符号是取反
c[++m]=str[i]; // 存储这个符号
add(m,stk[tt--]); // 将这个符号存进表达式树中
stk[++tt]=m; // 存储新节点
i++; // 跳过这个符号
}
else{ // 如果这个符号是与或者是或
c[++m]=str[i]; // 存储这个符号
//由于与或者是或这两个符号都需要两个数进行运算，所以要存两次
add(m,stk[tt--]); // 存储这个符号的左儿子
add(m,stk[tt--]); // 存储这个符号的右儿子
stk[++tt]=m; // 存储新节点
i++; // 跳过这个符号
}
}
int root=stk[tt]; // 取出根节点
int res=dfs1(root); // 计算现在的原答案
dfs2(root); // 处理表达式树中有哪些节点会影响到答案
int q; // 定义临时输入变量
scanf("%d",&q); // 输入查询次数
while(q--){ // 循环
int x; // 定义临时输入变量
scanf("%d",&x); // 输入现在的查询值
if(st[x]) printf("%d\n",!res); // 如果这个下标对应的值所在的节点会影响答案，\
那么输出取反后的答案
else printf("%d\n",res); // 如果这个下标对应的值所在的节点不会影响答案，\
那么输出原答案
}
return 0;
}
第四题：number
/*
第(i,j)个格子的权值：w(i,j)
状态表示：f(i,j)
集合：所有从左上角走到(i,j),且下一步向右走的路线的集合
属性：Max
状态计算：
情况：
1：从上面过来
2：从下面过来
求f(i,j)的两种情况：
1.从(i-1,j)下来。 -> S(从上面(i,j-1)点走到(i-1,j)的集合) + w(i,j)
2.从(i,j-1)向右走过来。 -> f(i,j-1) + w(i,j)
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL; // 由于这道题会爆int，所以要用long long
const int N = 1010; // 定义数组范围
int n, m; // 定义变量
int w[N][N]; // 每个点的数
LL f[N][N]; // 动规数组
int main(){
scanf("%d%d", &n, &m); // 输入
for (int i = 1; i <= n; i ++ ) // 行模拟
for (int j = 1; j <= m; j ++ ) // 列模拟
scanf("%d", &w[i][j]); // 输入每个点的数字
memset(f, -0x3f, sizeof f); // 初始化动规数组
f[1][0] = 0; // 初始化边界
for (int j = 1; j <= m; j ++ ) // 列模拟
{
LL s = -1e18; // 求S
for (int i = 1; i <= n; i ++ ) // 从小到大行模拟
{
s = max(s, f[i][j - 1]) + w[i][j]; // 求第一种情况（从(i-1,j)下来。） 的值
f[i][j] = max(f[i][j], s); // 由于属性是Max，所以要求最大值
}
s = -1e18; // 再次初始化求f(i,j)的临时变量
for (int i = n; i; i -- ) // 从大到小行模拟
{
s = max(s, f[i][j - 1]) + w[i][j]; // 求第二种情况（从(i,j-1)向右走过来。） 的值
f[i][j] = max(f[i][j], s); // 同第41行
}
}
printf("%lld\n", f[n][m]); // 输出从(1,1)走到(n,m)可取数字的最大值
return 0;
}
