23.5.2 NOIP2011 Day1提高游记

今天做的比较得愉快快呢，除了第三题hh

1.铺地毯

这题我不做太多评价，纯纯的一道大水题。

注意遍历数据的时候倒着遍历，还有就是不能用二维数组，会MLE。

code:

 1 #include<bits/stdc++.h>
 2 #define N 10005
 3 using namespace std;
 4 int a[N],b[N],g[N],k[N];
 5 inline long long read(){
 6     long long ans=0,f=1;
 7     char ch=getchar();
 8     if(ch=='-'){
 9         f=-1;
10     }
11     while(!isdigit(ch)){
12         ch=getchar();
13     }
14     while(isdigit(ch)){
15         ans=((ans<<1)+(ans<<3)+(ch^48));
16         ch=getchar();
17     }
18     return ans*f;
19 }
20 int main(){
21     int n=read();
22     for(int i=1;i<=n;i++){
23         a[i]=read(),b[i]=read(),g[i]=read(),k[i]=read();
24     }
25     int x=read(),y=read(),ans=0;
26     for(int i=n;i>=1;i--){
27         if(a[i]<=x&&a[i]+g[i]>=x&&b[i]<=y&&b[i]+k[i]>=y){
28             ans=i;
29             break;
30         }
31     }
32     if(ans){
33         cout<<ans;
34     }
35     else{
36         cout<<-1;
37     } 
38     return 0;
39 }

2.选择客栈这一题拿到手先想到的是暴力的算法，首先去枚举每一个方块，在[a,b]的区间内是否有<=p，同时判断a==b？，所以用暴力的时间复杂度则为O(n^2);

但是我们可以记录下颜色后再进行遍历，只要在任意同种颜色的区间内扫到了，那么其他的格子自动叠加答案，这样就可以做到O(k*n)

code:

 1 #include<bits/stdc++.h>
 2 #define N 200009
 3 #define M 101
 4 using namespace std;
 5 inline long long read(){
 6     long long ans=0,f=1;
 7     char ch=getchar();
 8     if(ch=='-'){
 9         f=-1;
10     }
11     while(!isdigit(ch)){
12         ch=getchar();
13     }
14     while(isdigit(ch)){
15         ans=((ans<<1)+(ans<<3)+(ch^48));
16         ch=getchar();
17     }
18     return ans*f;
19 }
20 int main(){
21     int n=read(),k=read(),p=read(),color[N],num[M],t,ans=0,price;
22     for(int i=1;i<=n;i++){
23         color[i]=read(),price=read();
24         if(price<=p){
25             for(int j=i;j>t;j--){
26                 num[color[j]]++;
27             }
28             t=i,ans+=num[color[i]]-1;
29         }
30         else{
31             ans+=num[color[i]];
32         }
33     }
34     cout<<ans;
35     return 0;
36 }