当前位置：首页 > news >正文

洛谷P3952 时间复杂度

news 来源：原创 2024/4/30 10:34:05

大毒瘤......

时隔快半年我终于花了两个小时堪堪A掉这一题...果然我还没有准备好。

想法：用DFS模拟递归。

时间复杂度的处理：每层循环取max，然后相加。

最大难点：各种繁杂而令人发指的特判。

为了简明代码，我写了6个辅助函数。

然后就A了...

  1 // shi jian fu za du
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <string>
  5 #include <iostream>
  6 
  7 const int ERR = -99;
  8 
  9 int L, vis[26];
 10 
 11 inline int getOP() { /// F 0 E 1
 12     L--;
 13     char c = getchar();
 14     while(c != 'E' && c != 'F') {
 15         c = getchar();
 16     }
 17     return c == 'E';
 18 }
 19 inline int getName() {
 20     char c = getchar();
 21     while(c < 'a' || c > 'z') {
 22         c = getchar();
 23     }
 24     return c - 'a';
 25 }
 26 inline int getSum() {
 27     int Sum = 0;
 28     char c = getchar();
 29     while(c != 'n' && (c < '0' || c > '9')) {
 30         c = getchar();
 31     }
 32     if(c == 'n') {
 33         return -1;
 34     }
 35     while(c >= '0' && c <= '9') {
 36         Sum = (Sum << 3) + (Sum << 1) + c - 48;
 37         c = getchar();
 38     }
 39     return Sum;
 40 }
 41 inline void getrest() {
 42     while(L) {
 43         int t = getOP();
 44         if(!t) {
 45             t = getName();
 46             t = getSum();
 47             t = getSum();
 48         }
 49     }
 50     return;
 51 }
 52 inline int get(std::string s) {
 53     if(s[2] == '1') {
 54         return 0;
 55     }
 56     int ans = 0;
 57     for(int i = 4; i < s.size() - 1; i++) {
 58         ans = (ans << 3) + (ans << 1) + s[i] - 48;
 59     }
 60     return ans;
 61 }
 62 inline int gettime(int a, int b) {
 63     if(a == -1 && b == -1) {
 64         return 0;
 65     }
 66     else if(a == -1) {
 67         return -1;
 68     }
 69     else if(b == -1) {
 70         return 1;
 71     }
 72     else if(a <= b) {
 73         return 0;
 74     }
 75     return -1;
 76 }
 77 //
 78 inline int DFS(int k, int time) {
 79     int ans = 0, nex_time;
 80     while(L) {
 81         int t = getOP();
 82         if(t == 1) {
 83             if(!k) {
 84                 getrest();
 85                 return ERR;
 86             }
 87             break;
 88         }
 89         /// F
 90         int name = getName();
 91         int a = getSum();
 92         int b = getSum();
 93         if(vis[name]) {
 94             getrest();
 95             return ERR;
 96         }
 97         if(!L) {
 98             return ERR;
 99         }
100         vis[name] = 1;
101         nex_time = gettime(a, b);
102 
103         t = DFS(k + 1, nex_time);
104         vis[name] = 0;
105         if(t == ERR) {
106             return ERR;
107         }
108         if(!L && k) {
109             return ERR;
110         }
111         ans = std::max(ans, t);
112     }
113     if(time == -1) {
114         return 0;
115     }
116     return time + ans;
117 }
118 
119 int main() {
120     int T;
121     scanf("%d", &T);
122     std::string s;
123     while(T--) {
124         scanf("%d", &L);
125         std::cin >> s;
126         int t = get(s);
127         int g = DFS(0, 0);
128         if(g == ERR) {
129             printf("ERR\n");
130         }
131         else if(g == t) {
132             printf("Yes\n");
133         }
134         else {
135             printf("No\n");
136         }
137     }
138     return 0;
139 }

AC代码

[update 2018.10.11]

额，最近练模拟，想起来这道题。因为以前做过一次所以很轻易就A了。

大概十几分钟打完(记得之前是怎么处理的)，第一次交80分，还是个老问题：没有把之前剩余的语句读完。

还需要注意对第一次操作的处理：结束时你没有一个多余的E让你出来，你要自己特判L = 0，然后如果不在最外层的话就是error。

  1 #include <cstdio>
  2 #include <map>
  3 #include <cstring>
  4 
  5 std::map<char, bool> mp;
  6 char s[10];
  7 int L, err;
  8 
  9 inline int read_time() {
 10     scanf("%s", s);
 11     if(s[2] == '1') {
 12         return 0;
 13     }
 14     int x = 0;
 15     for(int i = 4; i < strlen(s) - 1; i++) {
 16         x = (x << 3) + (x << 1) + s[i] - 48;
 17     }
 18     return x;
 19 }
 20 
 21 inline int read_op() {
 22     L--;
 23     scanf("%s", s);
 24     return s[0] == 'E';
 25 }
 26 
 27 inline int read(char &c) {
 28     scanf("%s", s);
 29     c = s[0];
 30     scanf("%s", s);
 31     int a = 0, b = 0;
 32     if(s[0] == 'n') {
 33         a = 101;
 34     }
 35     else {
 36         for(int i = 0; i < strlen(s); i++) {
 37             a = (a << 3) + (a << 1) + s[i] - 48;
 38         }
 39     }
 40     scanf("%s", s);
 41     if(s[0] == 'n') {
 42         b = 101;
 43     }
 44     else {
 45         for(int i = 0; i < strlen(s); i++) {
 46             b = (b << 3) + (b << 1) + s[i] - 48;
 47         }
 48     }
 49     if(a == 101) {
 50         if(b == 101) {
 51             return 0;
 52         }
 53         else {
 54             return -1;
 55         }
 56     }
 57     if(b == 101) {
 58         return 1;
 59     }
 60     if(a > b) {
 61         return -1;
 62     }
 63     return 0;
 64 }
 65 
 66 int solve(int k, char c) {
 67     int large = 0;
 68     char j;
 69     while(1) {
 70         if(!L) {
 71             if(c != '4') {
 72                 err = 1;
 73             }
 74             break;
 75         }
 76         int f = read_op();
 77         if(f) {
 78             break;
 79         }
 80         int temp = read(j);
 81         if(mp[j]) {
 82             err = 1;
 83         }
 84         mp[j] = 1;
 85         large = std::max(large, solve(temp, j));
 86     }
 87     mp[c] = 0;
 88     if(k == -1) {
 89         return 0;
 90     }
 91     return large + k;
 92 }
 93 
 94 inline void work() {
 95     scanf("%d", &L);
 96     err = 0;
 97     mp.clear();
 98     int time = read_time();
 99     int ans = solve(0, '4');
100     if(L) {
101         err = 1;
102         while(L) {
103             if(!read_op()) {
104                 read(s[9]);
105             }
106         }
107     }
108     if(err) {
109         printf("ERR\n");
110         return;
111     }
112     if(ans == time) {
113         printf("Yes\n");
114     }
115     else {
116         printf("No\n");
117     }
118     return;
119 }
120 
121 int main() {
122     int T;
123     scanf("%d", &T);
124     while(T--) {
125         work();
126     }
127     return 0;
128 }