NOIP2011题解
大家好，又见面了，我是你们的朋友全栈君。
D1T1.铺地毯
题目描述
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯，一共有n张地毯，编号从 1 到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。 地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入
输入共 n+2行。 第一行有一个整数n，表示总共有 n张地毯。 接下来的 n行中，第 i+1行表示编号 i的地毯的信息，包含四个正整数 a，b，g，k，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在 x轴和 y轴方向的长度。 第 n+2 行包含两个正整数 x 和 y，表示所求的地面的点的坐标（x，y）。
输出
输出共 1 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。
样例输入
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2样例输出
3
水题 1 #include<cstdio>
2 int a[10001],b[10001],g[10001],k[10001];
3 int n,x,y;
4 bool in(int i){
5 int leftup=b[i]+k[i],rightdown=a[i]+g[i];
6 return x>=a[i]&&x<=rightdown&&y>=b[i]&&y<=leftup;
7 }
8 int main(){
9 scanf("%d",&n);
10 for(int i=1;i<=n;i++){
11 scanf("%d%d%d%d",&a[i],&b[i],&g[i],&k[i]);
12 }
13 scanf("%d%d",&x,&y);
14 for(int i=n;i>=1;i--){
15 if(in(i)){
16 printf("%d\n",i); return 0;
17 }
18 }
19 puts("-1");
20 return 0;
21 }D1T2.选择客栈
题目描述
丽江河边有 n 家很有特色的客栈，客栈按照其位置顺序从 1 到n 编号。每家客栈都按照某一种色调进行装饰（总共 k 种，用整数 0 ~ k-1 表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。
两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过 p。 他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过 p元的咖啡店小聚。
输入
输入共n+1行。 第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值； 接下来的 n行，第 i+1 行两个整数，之间用一个空格隔开，分别表示 i 号客栈的装饰色调和 i 号客栈的咖啡店的最低消费。
输出
输出只有一行，一个整数，表示可选的住宿方案的总数。
样例输入
5 2 3
0 5
1 3
0 2
1 4
1 5样例输出
3 1 #include<cstdio>
2 int n,k,p,sum,pos;
3 int a[200001],b[200001],c[200001];
4 int main(){
5 scanf("%d%d%d",&n,&k,&p);
6 for(int i=1;i<=n;i++){
7 int col,q;
8 scanf("%d%d",&col,&q);
9 if(q<=p) pos=i;
10 if(pos>=a[col]) c[col]=b[col];
11 a[col]=i;
12 sum+=c[col];
13 b[col]++;
14 }
15 printf("%d\n",sum);
16 return 0;
17 }D2T1.计算系数
题目描述
求 (ax+by)^k 的展开中 x^n*y^m 项的系数。由于系数可能很大，只要求输出除以 10007 的余数。
输入
一行共五个整数，分别为 a,b,k,n,m
输出
一个整数，为该项系数除以10007的余数。
样例输入
1 1 3 1 2样例输出
3提示
数据范围：
30% 0<=k<=10,
50% a=1,b=1
100% 0<=k<=1000, 0<=n,m<=k 且 n+m=k, 0<=a,b<=100,000
杨辉三角：f[i][j]=f[i-1][j]+f[i-1][j-1];
最后乘一下系数就好
1 #include<cstdio>
2 #define ll long long
3 #define clz 10007ll
4 ll a,b;
5 int k,n,m;
6 ll ans=1;
7 ll f[2001][2001];
8 int main(){
9 scanf("%lld%lld%d%d%d",&a,&b,&k,&n,&m);
10 for(int i=1;i<=k;i++) f[i][0]=f[i][i]=1;
11 for(int i=2;i<=k;i++){
12 for(int j=1;j<i;j++){
13 f[i][j]=(f[i-1][j]+f[i-1][j-1])%clz;
14 }
15 }
16 ans=f[k][m]%clz;
17 for(int i=1;i<=n;i++) ans*=a,ans%=clz;
18 for(int i=1;i<=m;i++) ans*=b,ans%=clz;
19 printf("%lld\n",ans%clz);
20 return 0;
21 }D2T2.聪明的质检员
题目描述
有个质量监督员负责检查矿石质量。 其中 N 个矿石分别有其质量 W[i] 和价值 V[i]。检测标准是，将该矿石分成给定的 M 个区间（可能重叠或重复），每个区间的检验值等于该区间内所有质量不小于 W 的矿石的数量，乘以它们的价值之和。也就是 sigma(i,1)*sigma(i,V[i]) (L[i]<=i<=R[i] 且 Wi>=W) 。然后总的质量标准值 Y 为所有区间检验值的总和。其中， W 是某个质量标准参数。 该人员决定调整参数 W 的值，使得 Y 尽量接近规定的标准 S. 求 Y-S 的绝对值的最小值。
输入
输入第一行是三个整数 N,M,S 。接下来 N 行每行为矿石 i 的质量 W[i] 和 V[i]。再接下来 M 行每行是两个整数 L[i] R[i] ，表示一个区间[ L[i] , R[i] ]。
输出
输出一个整数，表示 Y-S 的绝对值的最小值。
样例输入
10 10 1475400
23954 25180
18805 2701
17195 5663
7044 13659
8139 30927
19774 25516
7472 4572
5999 6166
1185 13621
10414 26521
2 10
4 7
5 8
1 6
2 7
1 3
2 7
3 4
1 6
1 10样例输出
27196提示
数据范围：
10% 1<=m,n<=10
30% 1<=m,n<=500
50% 1<=m,n<=5000
70% 1<=m,n<=10000
100% 1<=m,n<=200,000, 0<Wi,Vi<=106, 0<s<=1012,1<=Li<=Ri<=N
二分答案，注意long long
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #define ll long long
6 using namespace std;
7 int n,Q;
8 ll S,ans=10000000000000ll;
9 int w[200001],c[200001],l[200001],r[200001];
10 ll gs[200001],sum[200001];
11 ll L=9999999999999ll,R=-9999999999999ll,mid;
12 ll Max(ll a,ll b){return a>b?a:b;}
13 ll Min(ll a,ll b){return a<b?a:b;}
14 ll check(ll m){
15 memset(gs,0,sizeof(gs));
16 memset(sum,0,sizeof(sum));
17 for(int i=1;i<=n;i++){
18 if(w[i]>=m) gs[i]++,sum[i]+=c[i];
19 }
20 for(int i=1;i<=n;i++){
21 gs[i]+=gs[i-1];
22 sum[i]+=sum[i-1];
23 }
24 ll C=0;
25 for(int i=1;i<=Q;i++){
26 C+=(gs[r[i]]-gs[l[i]-1])*(sum[r[i]]-sum[l[i]-1]);
27 }
28 return C;
29 }
30 void ef(){
31 while(L+1<R){
32 mid=(L+R)>>1;
33 ll C=check(mid);
34 ans=min(ans,abs(C-S));
35 if(C<S) R=mid;
36 else L=mid;
37 }
38 //printf("%lld ",L);
39 }
40 int main(){
41 scanf("%d%d%lld",&n,&Q,&S);
42 for(int i=1;i<=n;i++){
43 scanf("%d%d",&w[i],&c[i]);
44 }
45 for(int i=1;i<=Q;i++){
46 scanf("%d%d",&l[i],&r[i]);
47 }
48 for(int i=1;i<=n;i++){
49 L=min(L,(ll)w[i]);
50 R=max(R,(ll)w[i]+1ll);
51 }
52 ef();
53 printf("%lld\n",ans);
54 return 0;
55 } 发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/155539.html原文链接：https://javaforall.cn
腾讯云开发者
