前言
咕了大半年，我回来了
说实话当鸽子的感觉挺不错？？？
题意
给定一个伪代码，判断他总共需要进行几次操作，用多项式形式输出。
题解
首先，这是一道模拟题，发现性质的话比较水
输入及处理
对于 loop 和 op
我们能够很容易的发现，对于任意的 loop 操作，与他有关的是在它上几层的 loop 以及在它下几层的 loop 和 op，简单来说，整个伪代码可以看做一个一 begin 为根树形结构（暂时忽略 break 和 continue），以样例二为例，就像下图（忽略 break 和 continue）
如此一来，我们只需要在读入时进行树形存储，最后扫描统计贡献就行
对于 break 和 continue
我们回忆一下 break 和 continue 的功能
- break ：结束本层循环
- continue : 结束本次循环
很容易发现他们之间有几个共性
都只与本层循环有关，都改变了循环操作的对象，本层循环的剩余部分都
变成了废话不会执行
那么对于 break 和 continue 操作，只需要忽略本层循环的剩余部分，对于 break , 再将循环次数改为1，就完成了对这两个操作的处理。用图表示就像下图（红色部分为发生变化的部分）
最终结构如下
因为题目没说总共有多少个 loop 和 op 操作，所以存数据时最好用 vector 加 指针 的方式存储，如下
点击查看代码
struct Node{
int val; //执行几次
bool leaf; //是否为叶节点，便于最后的统计
Node* father; //父节点是哪个
vector<Node> child; //子节点有哪些
};
Node root;
while (1) {
scanf ("%s", s + 1);
if (s[1] == 'l') {
scanf ("%s", s + 1);
f -> child.push_back ((Node) {Change() % Mod, false, f}); //新建子节点
f = &f -> child.back(); //准备开始下一层循环
}
else if (s[1] == 'o') {
scanf ("%s", s + 1);
f -> child.push_back ((Node) {Change() % Mod, true, f});
}
else if (s[1] == 'b') {
if (f == &root) continue;
f -> val = 1, f = f -> father; //更改本层循环次数，并退回上一层循环
TillEnd(); //忽略本层循环后续部分
}
else if (s[1] == 'c') {
if (f == &root) continue;
f = f -> father;
TillEnd();
}
else if (s[1] == 'e') {
if (f == &root) break; //输入完毕
f = f -> father;
}
}
细心的大佬看官可以发现，loop 和 op 以及 break 和 continue 的处理极其相似，这也是我将他们放到一起分析的原因
统计
因为之前已经存好了树形结构，统计的时候只需要递归进行，传递系数和指数即可
点击查看代码
int ans[N]; //ans_i表示n的i次方的系数
void dfs(Node u, int pow, int coe) {
if (u.leaf) {
ans[pow] = (ans[pow] + coe) % Mod, maxn = max(maxn, pow);
return;
}
for (int i = 0; i < u.child.size(); ++i)
(u.child[i].val == -1) ? dfs(u.child[i], pow + 1, coe % Mod) : dfs(u.child[i], pow, coe * u.child[i].val % Mod);
}
点击查看代码
输出
从高到低输出即可，注意判系数为1及指数为1或0的情况
就下来是喜闻乐见的
全部代码
点击查看代码
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
const int N = 20 + 10;
const int Mod = 998244353;
struct Node{
int val;
bool leaf;
Node* father;
vector<Node> child;
};
Node root;
int ans[N];
char s[N];
int maxn;
inline int read() {
int s = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
return s * f;
}
inline void write(int x) {
if (x < 0) putchar('-'), x = ~(x - 1);
int s[50], top = 0;
while (x) s[++top] = x % 10, x /= 10;
if (top == 0) s[++top] = 0;
while (top) putchar(s[top--] + '0');
}
inline int max(int x, int y) { return x > y ? x : y; }
inline int Change() {
if (s[1] == 'n') return -1;
int n = strlen(s + 1), number = 0;
for (int i = 1; i <= n; ++i) number = (number << 3) + (number << 1) + (s[i] ^ 48);
if (number == 0) return -1;
return number % Mod;
}
inline void TillEnd() {
int cnt = 1;
while (cnt) {
scanf ("%s", s + 1);
if (s[1] == 'l') ++cnt;
else if (s[1] == 'e') --cnt;
}
}
void dfs(Node u, int pow, int coe) {
if (u.leaf) {
ans[pow] = (ans[pow] + coe) % Mod, maxn = max(maxn, pow);
return;
}
for (int i = 0; i < u.child.size(); ++i)
(u.child[i].val == -1) ? dfs(u.child[i], pow + 1, coe % Mod) : dfs(u.child[i], pow, coe * u.child[i].val % Mod);
}
inline void print(int pos) {
if (ans[pos] == 1) {
if (pos == 0) printf ("1");
if (pos == 1) printf ("n");
if (pos >= 2) printf ("n^%d", pos);
}
else {
if (pos == 0) printf ("%d", ans[pos]);
if (pos == 1) printf ("%dn", ans[pos]);
if (pos >= 2) printf ("%dn^%d", ans[pos], pos);
}
}
int main() {
root.val = 0, root.leaf = false, root.father = NULL;
Node* f = &root;
while (1) {
scanf ("%s", s + 1);
if (s[1] == 'l') {
scanf ("%s", s + 1);
f -> child.push_back ((Node) {Change() % Mod, false, f});
f = &f -> child.back();
}
else if (s[1] == 'o') {
scanf ("%s", s + 1);
f -> child.push_back ((Node) {Change() % Mod, true, f});
}
else if (s[1] == 'b') {
if (f == &root) continue;
f -> val = 1, f = f -> father;
TillEnd();
}
else if (s[1] == 'c') {
if (f == &root) continue;
f = f -> father;
TillEnd();
}
else if (s[1] == 'e') {
if (f == &root) break;
f = f -> father;
}
}
dfs(root, 0, 1);
print(maxn);
for (int i = maxn - 1; i >= 0; --i)
if (ans[i]) printf ("+"), print(i);
printf ("\n");
return 0;
}
P.S.
数据里有一个小锅，没注意会WA一个点，那就请各位看官自行去找喽~~
标签：Node,洛谷,int,题解,CTSC1998,break,continue,child,root From： https://www.cnblogs.com/Nebula-Astraea/p/16767326.html