$NOIP2011$ 题解报告

THWZF 2021-08-04 原文

刷水题找自信系列第十五弹

目录

$Luogu\ P1003$ 铺地毯$(\ √\ )$

$Luogu\ P1311$ 选择客栈$(\ √\ )$

$Luogu\ P1312$ $Mayan$游戏（　）

$Luogu\ P1313$ 计算系数$(\ √\ )$

$Luogu\ P1314$ 聪明的质监员$(\ √\ )$

$Luogu\ P1315$ 观光公交$(\ √\ )$

$Luogu\ P1003$ 铺地毯

题目传送门

对于要求的点，我们直接判断是否在地毯范围内即可，注意要求的是最上面的地毯，所以要倒序枚举

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=10002;
 4 int n,a,b,A[N],B[N],G[N],K[N];
 5 int main(){
 6     scanf("%d",&n);
 7     int i;
 8     for(i=1;i<=n;i++)
 9       scanf("%d%d%d%d",&A[i],&B[i],&G[i],&K[i]);
10     scanf("%d%d",&a,&b);
11     for(i=n;i>=1;i--)
12       if(A[i]<=a&&A[i]+G[i]>=a&&B[i]<=b&&B[i]+K[i]>=b) break;
13     if(i==0) printf("-1\n");
14     else printf("%d\n",i);
15     return 0;
16 }

代码戳这里

$Luogu\ P1311$ 选择客栈

题目传送门

$Itst$考过的原题，直接贴个$link\to$戳这里

$Luogu\ P1312$ $Mayan$游戏

题目传送门

$Luogu\ P1313$ 计算系数

题目传送门

就是一道数论题……？首先$a^n*b^m$很显然就可以算出来，然后我们把$(ax+by)^k$看成$k$个$(ax+by)$相乘，那么$x^ny^m$相当于在这$k$个中选出$n$个$x$，然后和剩下的$m$个$y$相乘，于是可以用组合数解决。

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define go(i,a,b) for(register int i=a;i<=b;i++)
 4 using namespace std;
 5 int  a,b,k,n,m;
 6 const int mod=10007;
 7 int f[1002];
 8 int ksm(ll x,int y){
 9     int ans=1;
10     while(y){
11         if(y&1) ans=(ans*x)%mod;
12         x=(x*x)%mod;
13         y>>=1;
14     }
15     return ans;
16 }
17 int main(){
18     scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
19     a%=mod;b%=mod;
20     f[0]=f[1]=1;
21     go(i,2,k) f[i]=(i*f[i-1])%mod;
22     int ans=(ksm((ll)a,n)*ksm((ll)b,m))%mod;
23     int son=f[k];
24     ll mum=f[n]*f[m];
25     mum=(ll)ksm(mum,mod-2);
26     ans=ans*son%mod*mum%mod;
27     printf("%d\n",ans);
28     return 0;
29 }

代码戳这里

$Luogu\ P1314$ 聪明的质监员

题目传送门

二分答案，注意边界和条件

 1 #include<bits/stdc++.h>
 2 #define ri register int
 3 #define ll long long
 4 #define rl register ll
 5 #define go(i,a,b) for(ri i=a;i<=b;i++)
 6 #define back(i,a,b) for(ri i=a;i>=b;i--)
 7 #define g() getchar()
 8 #define il inline
 9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il int fr(){
13     ri w=0,q=1;char ch=g();
14     while(ch<\'0\'||ch>\'9\'){if(ch==\'-\')q=-1;ch=g();}
15     while(ch>=\'0\'&&ch<=\'9\')w=(w<<1)+(w<<3)+ch-\'0\',ch=g();
16     return w*q;
17 }
18 const int N=200002;
19 int n,m,w[N],v[N],L[N],R[N],l=0,r=1e6;
20 ll S,s1[N],s2[N],as,ans=1e12+7;
21 il bool check(ri mid){
22     //cout<<"mid="<<mid<<endl;
23     go(i,1,n){
24         s1[i]=w[i]>=mid?s1[i-1]+v[i]:s1[i-1];
25         s2[i]=w[i]>=mid?s2[i-1]+1:s2[i-1];
26     }
27     as=0;go(i,1,m)as+=(s1[R[i]]-s1[L[i]-1])*(s2[R[i]]-s2[L[i]-1]);
28     ans=min(ans,abs(S-as));
29     return as>=S;
30 }
31 int main(){
32     freopen("1.in","r",stdin);
33     freopen("1.out","w",stdout);
34     n=fr();m=fr();scanf("%lld",&S);
35     go(i,1,n)w[i]=fr(),v[i]=fr();
36     go(i,1,m)L[i]=fr(),R[i]=fr();
37     ri mid=(l+r)>>1;
38     while(l<=r){
39         //cout<<"l="<<l<<" r="<<r<<endl;
40         if(check(mid)){
41             if(as==S){puts("0");return 0;}
42             l=mid+1;
43         }
44         else r=mid-1;
45         mid=(l+r)>>1;
46     }
47     pf("%lld\n",ans);
48     return 0;
49 }
50 /*
51   二分答案
52 */