NOIP2017 时间复杂度 洛谷3952（Day1 T2）

WWX

https://www.luogu.org/problemnew/show/P3952
题目很长，就不贴了
一道没有什么营养的大模拟

吴语林

1. #include <cstdio>
   
2. #include <algorithm>
   
3. #include <iostream>
   
4. #include <cmath>
   
5. #include <cstring>
   
6. #include <map>
   
7. #include <string>
   
8. #include <vector>
   
9. #include <queue>
   
10. #include <stack>
    
11. using namespace std;
    
12. char c[1000],code[100];
    
13. int n,w,le;
    
14. int main()
    
15. {
    
16.         int t;
    
17.         scanf("%d",&t);
    
18.         while(t--)
    
19.         {
    
20.                 scanf("%d ",&n);
    
21.                 gets(c);
    
22.                 w=0,le=strlen(c);
    
23.                 if(c[2]=='n')
    
24.                         for(int i=4;i<le&&isdigit(c[i]);i++)
    
25.                                 (w*=10)+=(c[i]-'0');
    
26.                 stack<int> s;
    
27.                 int e=1,book[26]={0},ef[26]={0},now=0,flag=-1,res=0;
    
28.                 for(int i=1;i<=n;i++)
    
29.                 {
    
30.                         gets(code);
    
31.                         if(code[0]=='F')
    
32.                         {
    
33.                                 int k=code[2]-'a';
    
34.                                 s.push(k);
    
35.                                 if(!book[k])
    
36.                                         book[k]=1;
    
37.                                 else
    
38.                                 {
    
39.                                         printf("ERR\n");
    
40.                                         e=0;
    
41.                                         for(int j=i+1;j<=n;j++)
    
42.                                                 gets(code);
    
43.                                         break;
    
44.                                 }
    
45.                                 int a=0,b=0,j=4;
    
46.                                 for(j=4;isdigit(code[j])||code[j]=='n';j++)
    
47.                                 {
    
48.                                         if(code[j]=='n')
    
49.                                                 a=1000000;
    
50.                                         (a*=10)+=(code[j]-'0');
    
51.                                 }
    
52.                                 j++;
    
53.                                 for(j;isdigit(code[j])||code[j]=='n';j++)
    
54.                                 {
    
55.                                         if(code[j]=='n')
    
56.                                                 b=1000000;
    
57.                                         (b*=10)+=(code[j]-'0');
    
58.                                 }
    
59.                                 if(b-a>1000)
    
60.                     if(flag==-1)
    
61.                                         {
    
62.                                 now++;
    
63.                                                 res=max(res,now);
    
64.                                                 ef[k]=true;
    
65.                                         }
    
66.                                 if(a>b)
    
67.                     if(flag==-1) flag=k;
    
68.                         }
    
69.                         else if(code[0]=='E')
    
70.                         {
    
71.                                 if(s.empty())
    
72.                                 {
    
73.                                         printf("ERR\n");
    
74.                                         e=0;
    
75.                                         for(int j=i+1;j<=n;j++)
    
76.                                                 gets(code);
    
77.                                         break;
    
78.                                 }
    
79.                 int k=s.top();
    
80.                 s.pop();book[k]=false;
    
81.                 if(flag==k)
    
82.                                         flag=-1;
    
83.                 if(ef[k])
    
84.                                 {
    
85.                     ef[k]=false;
    
86.                     now--;
    
87.                 }
    
88.                         }
    
89.                 }
    
90.                 if(e)
    
91.                 {
    
92.                         if(s.size())
    
93.                                 printf("ERR\n");
    
94.                         else if(res==w)
    
95.                                 printf("Yes\n");
    
96.                         else
    
97.                                 printf("No\n");       
    
98.                 }
    
99.         }
    
100.         return 0;
     
101. }

复制代码

WWX

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cstring>
   
4. #include <cstdio>
   
5. using namespace std;
   
6. 
   
7. int T,L,MX,CNT,top;
   
8. bool ERR_;
   
9. struct Node
   
10. {
    
11.     int id,step;
    
12.     bool naive;
    
13. } data[110];
    
14. char s[10],s1[10],s2[10];
    
15. bool use[30];
    
16. inline int read()
    
17. {
    
18.     int x=0;
    
19.     char ch=getchar();
    
20.     while(ch<'0'||ch>'9')
    
21.         ch=getchar();
    
22.     while(ch>='0'&&ch<='9')
    
23.     {
    
24.         x=x*10+ch-'0';
    
25.         ch=getchar();
    
26.     }
    
27.     return x;
    
28. }
    
29. int main()
    
30. {
    
31.     //freopen("complexity.in","r",stdin);
    
32.     //freopen("complexity.out","w",stdout);
    
33.     T=read();
    
34.     while(T--)
    
35.     {
    
36.         MX=0;
    
37.         top=0;
    
38.         CNT=0;
    
39.         ERR_=false;
    
40.         memset(use,0,sizeof(use));
    
41.         L=read();
    
42.         scanf("%s",&s[0]);
    
43.         if(s[2]=='1')
    
44.             CNT=0;
    
45.         else for(int i=4; s[i]>='0'&&s[i]<='9'; i++)
    
46.                 CNT=CNT*10+s[i]-'0';
    
47.         while(L--)
    
48.         {
    
49.             char ch=getchar();
    
50.             while(ch!='F'&&ch!='E')
    
51.                 ch=getchar();
    
52.             if(ch=='E')
    
53.             {
    
54.                 if(ERR_)
    
55.                     continue;
    
56.                 if(!top)
    
57.                     ERR_=true;
    
58.                 if(!ERR_)
    
59.                 {
    
60.                     use[data[top].id]=false;
    
61.                     top--;
    
62.                 }
    
63.             }
    
64.             else
    
65.             {
    
66.                 while(ch<'a'||ch>'z')
    
67.                     ch=getchar();
    
68.                 if(!ERR_)
    
69.                 {
    
70.                     if(use[ch-'a'])
    
71.                         ERR_=true;
    
72.                 }
    
73.                 if(!ERR_)
    
74.                 {
    
75.                     top++;
    
76.                     data[top].id=ch-'a';
    
77.                     use[data[top].id]=true;
    
78.                 }
    
79.                 for(int i=0; i<=3; i++)
    
80.                     s1[i]=s2[i]='?';
    
81.                 scanf("%s%s",&s1[0],&s2[0]);
    
82.                 if(ERR_)
    
83.                     continue;
    
84.                 int L=0,R=0;
    
85.                 if(s1[0]=='n')
    
86.                     L=100;
    
87.                 else for(int i=0; s1[i]>='0'&&s1[i]<='9'; i++)
    
88.                         L=L*10+s1[i]-'0';
    
89.                 if(s2[0]=='n')
    
90.                     R=100;
    
91.                 else for(int i=0; s2[i]>='0'&&s2[i]<='9'; i++)
    
92.                         R=R*10+s2[i]-'0';
    
93.                 if(L>R)
    
94.                     data[top].naive=true;
    
95.                 else data[top].naive=data[top-1].naive;
    
96.                 if(L<100&&R==100&&!data[top].naive)
    
97.                     data[top].step=data[top-1].step+1;
    
98.                 else data[top].step=data[top-1].step;
    
99.                 MX=max(MX,data[top].step);
    
100.             }
     
101.         }
     
102.         if(top)
     
103.             ERR_=true;
     
104.         if(ERR_)
     
105.             cout<<"ERR"<<endl;
     
106.         else if(MX==CNT)
     
107.             cout<<"Yes"<<endl;
     
108.         else cout<<"No"<<endl;
     
109.     }
     
110.     return 0;
     
111. }
     

复制代码