今天做的比较得愉快快呢，除了第三题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 }