简述我的苦逼做题经历

考的是NOIP2017day1原题，

开始看到小凯的疑惑时感觉特水，因为这题初中老师讲过，

很nice的秒切

T2发现是个大模拟，虽然字符串不太会用，但起码题意很好理解

边打代码边敲注释，差点变量名不够用

就这样一个半小时过去了，手捏的样例也过了

以为100pts，就放了过去看T3

T3考的是最短路计数，想了想以前好像没有写过这类题，

硬着头皮写了个dfs暴力统计道路数，为防止跑不出来还加了个计数器特判

期望能在无0环样例中骗点分，

后来在luogu上全WA了

T1 小凯的疑惑

运用了小学奥数的芝士

（赛后听说有根据昨天T2做法骗了60分的，但那个必会MLE，不过在考场上可以用来打表找规律）

 1 #include<iostream>

 2 #include<cstdio>

 3 using namespace std;

 4 long long a, b;//十年OI一场空，不开long long见祖宗

 5 int main()

 6 {

 7     //freopen("math.in","r",stdin);

 8     //freopen("math.out","w",stdout);

 9     cin>>a>>b;

10     cout<<(a*b-a-b)<<endl;

11     return 0;

12 }

T2 时间复杂度

这虽然是个大模拟，但坑点太多了啊

发现给出的程序格式单一，那么直接用cin单独接收就好

用flag标记小明给出的复杂度中有无n，用cst和fcst分别接收常数级的复杂度和指数级的复杂度（后来发现cst只可能是1

为了区分fsct是1的情况，把cst赋成-1

接着读入每个串，把F，和E两种情况分开处理

单独开个char数组存变量的名字，读一个F就加一个，读一个E就减一个（注意加之前先判断有没有重复的

接收起始量和终止量

开两个标记标记是否是n，开两个int记录两个量的大小

开个xh记录循环到的第几层

如果前后都是n，不作处理

考虑到有的循环能直接退出，开个spl标记

开一个栈存储有n的循环层的层数

如果前面只有前面是n，或者前面大于后面并且spl == 0 时间复杂度与top取最大值，并用spl记录此时层数

如果只有后面是n，向栈里加一个元素，大小为此时的层数，时间复杂度与top取最大值

如果层数小于栈顶的层数，就将其弹出

如果有层数小于0或者变量名重复的情况打个标记最后输出REE即可

在E操作中，如果层数小于spl，要记得归0

详细过程看代码

  1 //T2不会是个大模拟吧

  2 #include<iostream>

  3 #include<cstdio>

  4 #include<cstring>

  5 #include<string>

  6 #include<cmath>

  7 using namespace std;

  8 int T, n, cnt, Otime, xh, xh2;//cnt变量名计数

  9 int cst, fcst;//cst：常数级，fcst：指数级

 10 bool err = 0, flag;//标记复杂度是指数级还是常数级

 11 char blm[110];//存变量名

 12 string s1, s2; //读入的程序

 13 int spl;//一个特殊标记，标记外层循环o1，内层循环on^m的情况

 14 int stk[110], top = 0;

 15

 16 void worke(){

 17     cnt--; xh--;

 18     if(xh <= spl) spl = 0;

 19     if(xh < 0) err = 1;

 20     if(xh < stk[top]) top--;

 21     return ;

 22 }

 23

 24 void workf(){

 25     bool str_n = 0, ed_n = 0;//标记起始点是否为n,标记终止点是否为n ;

 26     int str = 0, ed = 0;

 27     string bl, qsl, zzl;//变量， 起始量， 终止量

 28     cin>>bl>>qsl>>zzl;

 29     xh++;//循环层数加一

 30     for(int i = 1; i <= cnt; ++i)

 31         if(blm[i] == bl[0]) {

 32             err = 1; return ;

 33         }

 34     //存变量

 35     //处理起始点

 36     if(qsl[0] == 'n') str_n = true;

 37     else {

 38         for(int i = 0; i < qsl.size(); ++i){

 39             str = str * 10 + qsl[i] - '0';

 40         }

 41     }

 42     //处理终止点

 43     if(zzl[0] == 'n') ed_n = true;

 44     else {

 45         for(int i = 0; i < zzl.size(); ++i){

 46             ed = ed * 10 + zzl[i] - '0';

 47         }

 48     }

 49     if(str_n && ed_n) return ;

 50     blm[++cnt] = bl[0];

 51

 52     if(((str_n && !ed_n) || (!str_n && !ed_n && str > ed)) && !spl) Otime = max(Otime, top), spl = xh;

 53     if(!str_n && ed_n && !spl) {

 54         stk[++top] = xh;

 55         Otime = max(Otime, top);

 56     }

 57     if(xh < stk[top]) top--;

 58     return ;

 59 }

 60

 61 int main()

 62 {

 63     //freopen("complexity.in","r",stdin);

 64     //freopen("complexity.out","w",stdout);

 65     scanf("%d", &T);

 66     while(T--){

 67         scanf("%d", &n);

 68         cnt = cst = fcst = xh = xh2 = top = 0;

 69         flag = 0, err = 0;

 70         Otime = -1;

 71         cin>>s1;

 72 //        cout<<n<<"zsf"<<endl;

 73         int len = s1.size();

 74         for(int i = 0; i < len; ++i){

 75             if(s1[i] == 'n'){

 76                 flag = true;

 77             }

 78             if(s1[i] >= '0' && s1[i] <= '9'){//记录复杂度

 79                 if(flag) fcst = fcst * 10 + s1[i] - '0';

 80                 else cst = -1;

 81             }

 82         }

 83         for(int i = 1; i <= n; ++i){

 84             cin>>s2;

 85             if(s2[0] == 'F') workf();

 86             else worke();

 87 //            cout<<spl<<"zsf"<<xh<<" "<<top<<endl;

 88         }

 89         if(err || xh) printf("ERR\n");

 90         else{

 91             if(!flag){

 92                 if(Otime == cst) printf("Yes\n");

 93                 else printf("No\n");

 94             }

 95             else{

 96                 if(Otime == fcst) printf("Yes\n");

 97                 else printf("No\n");

 98             }

 99         }

100 //        cout<<"lkp"<<Otime<<" "<<cst<<" "<<fcst<<endl;

101     }

102     return 0;

103 }

T3 逛公园

关键是0环的问题不太好处理，但正解好像设计到一点dp，0环直接被过滤掉了

https://www.cnblogs.com/wxyww/p/noip2017Day1T3.html#643448942

这个博客讲的挺好的

题解是SPFA，我用的dij做的（题目中只有0环,嘿嘿，能卡过去）

  1 #include<iostream>

  2 #include<cstdio>

  3 #include<queue>

  4 #include<cstring>

  5 using namespace std;

  6 const int MAXN = 1e5+5;

  7 const int MAXM = 2e5+5;

  8 struct edge{

  9     int to, w, nxt;

 10 }e[MAXM], e2[MAXM];

 11 struct node{

 12     int point, dis;

 13     bool operator < (const node &b) const {return dis > b.dis; }

 14 };

 15 int head[MAXN], num_edge, head2[MAXN], num_edge2;

 16 int T, n, m, k ,p, lim, cnt, ans;

 17 int dis[MAXN], num[MAXN];

 18 bool vis[MAXN];

 19 priority_queue<node> q;

 20

 21 int read(){

 22     int s = 0, w = 1;

 23     char ch = getchar();

 24     while(ch < '0' || ch > '9') {if(ch == '-') w = -1; ch = getchar(); }

 25     while(ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + ch - '0', ch = getchar();

 26     return s * w;

 27 }

 28

 29 void add(int from, int to, int w){

 30     e[++num_edge].to = to;

 31     e[num_edge].w = w;

 32     e[num_edge].nxt = head[from];

 33     head[from] = num_edge;

 34 }

 35

 36 void add2(int from, int to, int w){

 37     e2[++num_edge2].to = to;

 38     e2[num_edge2].w = w;

 39     e2[num_edge2].nxt = head2[from];

 40     head2[from] = num_edge2;

 41 }

 42

 43

 44 void dij(){

 45     memset(dis, 0x3f, sizeof(dis));

 46     memset(vis, 0, sizeof(vis));

 47     dis[n] = 0;

 48     q.push((node){n, 0});

 49     while(!q.empty()){

 50         node t = q.top(); q.pop();

 51         int u = t.point;

 52         vis[u] = 1;

 53         for(int i = head2[u]; i; i = e2[i].nxt){

 54             int v = e2[i].to;

 55             if(dis[v] > dis[u] + e2[i].w){

 56                 dis[v] = dis[u] + e2[i].w;

 57                 if(!vis[v]) q.push((node){v, dis[v]});

 58             }

 59         }

 60     }

 61 }

 62

 63 int bz[MAXN][60], f[MAXN][60];

 64 int dfs(int x, int lim){

 65     if(bz[x][lim] == 2) return f[x][lim];

 66     if(bz[x][lim] == 1) return -1;

 67     bz[x][lim] = 1;

 68     for(int i = head[x]; i; i = e[i].nxt){

 69         int v = e[i].to;

 70         int w = lim - (dis[v] + e[i].w - dis[x]);

 71         if(w < 0 || w > k) continue;

 72         int ans = dfs(v, w);

 73         if(ans == -1) return -1;

 74         f[x][lim] += ans;

 75         f[x][lim] %= p;

 76     }

 77     bz[x][lim] = 2;

 78     return f[x][lim];

 79 }

 80

 81 int main()

 82 {

 83     //freopen("park.in","r",stdin);

 84     //freopen("park.out","w",stdout);

 85     T = read();

 86     while(T--){

 87         memset(head, 0, sizeof(head));

 88         memset(head2, 0, sizeof(head2));

 89         memset(f, 0, sizeof(f));

 90         memset(bz, 0, sizeof(bz));

 91         num_edge = num_edge2 = cnt = 0;

 92         n = read(), m = read(), k = read(), p = read();

 93         for(int i = 1, u, v, w; i <= m; ++i){

 94             u = read(), v = read(), w = read();

 95             add(u, v, w);

 96             add2(v, u, w);

 97         }

 98         dij();

 99         f[n][0] = 1;

100         for(int i = 0; i <= k; ++i){

101             int kkk = dfs(1, i);

102             if(kkk == -1){

103                 cnt = -1; break;

104             }

105             cnt += kkk;

106             cnt %= p;

107         }

108         printf("%d\n", cnt);

109     }

110     return 0;

111  }

巴特西

20201102gryz模拟赛解题报告

简述我的苦逼做题经历

T1 小凯的疑惑

T2 时间复杂度

T3 逛公园

最新文章

热门文章