2016.10.29 NOIP模拟賽 PM 考試整理

300分的題，隻得了第三題的100分。

題目+資料：連結：http://pan.baidu.com/s/1o7P4YXs 密碼：4how

T1：這道題目存在着諸多的問題：

1.開始的序列是無法消除的（這與題目描述明顯不符啊），即使有很多可以連消的，而我的程式每次隻在插入的位置向兩側尋找可以消除的，自然就錯了。

2.開始時的序列居然可以為空，真是讓人措手不及！

3.一些很特殊的玩法：比如AAABBCCC，在4處打上B，B消除之後，後面的C撞到了A，C有3個，消除，但是A卻不消除！！！（意思是在這種情況下，隻管後面的。

T2：

1 /*
 2 思路：分析題目可以知道：如果目前的棧為空或者棧頂元素小于還沒進棧元素的最大值時，應該使元素進棧，直到最大值進棧；否則，棧頂元素出棧。 
 3 我的錯誤：思路是正确的，但是敲代碼的時候出現了錯誤，我把未進棧的max與棧中的max進行了比較，但是應該是把未進棧的max與棧頂進行比較這樣比較出來，才是最大的。因為棧中的max不能被立刻輸出的。 
 4 為了預防再出現這樣的錯誤：以後有了思路的題目，都要先敲出僞代碼.....
 5 */
 6 #define N 1000010
 7 #include<iostream>
 8 using namespace std;
 9 #include<cstdio>
10 int n,num[N],maxnum=0,maxsta=0;
11 int sta[N],topt=0;
12 int read()
13 {
14     int ret=0;
15     char s=getchar();
16     while(s<'0'||s>'9') s=getchar();
17     while(s>='0'&&s<='9')
18     {
19         ret=ret*10+s-'0';
20         s=getchar();
21     }
22     return ret;
23 }
24 void input()
25 {
26     n=read();
27     for(int i=1;i<=n;++i)
28        num[i]=read();
29 }
30 int main()
31 {
32     freopen("haha.in","r",stdin);
33     freopen("haha.out","w",stdout);
34     input();
35     maxnum=n;
36     int i=1;
37     while(i<=n)
38     {
39         if(maxnum>sta[topt])
40         {
41             for(;i<=n;++i)
42             {
43                 if(maxnum==num[i])
44                 {
45                     printf("%d ",num[i]);
46                     i++;
47                      break;
48                 }
49                 sta[++topt]=num[i];
50             }
51             maxnum=0;
52             for(int j=i;j<=n;++j)
53               maxnum=max(maxnum,num[j]);
54         }
55         else{
56                 printf("%d ",sta[topt]);
57                 topt--;    
58         }
59     }
60     while(topt>=1) printf("%d ",sta[topt--]);
61     fclose(stdin);
62     fclose(stdout);
63     return 0;
64 }      

T3：

1 /*
 2 二分+一定的數學判斷：
 3 為了能夠使這些邊不相交，那麼肯定是小聯小，大連大了。
 4 二分這些線段，用數學方法判斷點在直線的哪一邊？（不會的請自行百度，國中知識）
 5 */
 6 #define N 200010
 7 #include<iostream>
 8 using namespace std;
 9 #include<cstdio>
10 #include<algorithm>
11 int n,x0[N],y0[N],m;
12 void input()
13 {
14     scanf("%d",&n);
15     for(int i=1;i<=n;++i)
16       scanf("%d",&x0[i]);
17     for(int i=1;i<=n;++i)
18       scanf("%d",&y0[i]);
19     scanf("%d",&m);
20     sort(x0+1,x0+1+n);
21     sort(y0+1,y0+1+n);
22 }
23 double panduan(int k,int x,int y)
24 {
25     return (double)((1.0*y0[k]*x/x0[k]+1.0*y-1.0*y0[k]));
26 }
27 int main()
28 {
29     freopen("hahaha.in","r",stdin);
30     freopen("hahaha.out","w",stdout);
31     input();
32     int x,y;
33     for(int i=1;i<=m;++i)
34     {
35         scanf("%d%d",&x,&y);
36         int l=1,r=n;
37         while(l<=r)
38         {
39             int mid=(l+r)>>1;
40             if(panduan(mid,x,y)>=0) l=mid+1;
41             else r=mid-1; 
42         }
43         printf("%d\n",r);
44     }
45     fclose(stdin);
46     fclose(stdout);
47     return 0;
48 }