NOIP2011 题解

铺地毯

　　题解：比大小

 1 #include <cstdio>
 2 
 3 const int MAXN = 10000+10;
 4 
 5 int n, x, y, a[MAXN], b[MAXN], g[MAXN], k[MAXN];
 6 
 7 inline int Solve(){
 8     for (int i=n; i>0; i--)
 9         if (a[i]<=x && x<=a[i]+g[i] && b[i]<=y && y<=b[i]+k[i]) return i;
10     return -1;
11 }
12 
13 int main(){
14     scanf("%d", &n);
15     for (int i=1; i<=n; i++)
16         scanf("%d %d %d %d", &a[i], &b[i], &g[i], &k[i]);
17     scanf("%d %d", &x, &y);
18     printf("%d
", Solve());
19 }

carpet.cpp

选择客栈:

　　题解：模拟。cj表示最近的一个可行的咖啡馆，tot[i]表示之前颜色i出现过的次数legal[i]表示颜色i在cj之前出现过的次数，last[i]表示颜色i最后出现的编号

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int MAXK = 50+10;
 5 
 6 int n, k, p, color, cost, cj, Pri, legal[MAXK], tot[MAXK], last[MAXK];
 7 char c;
 8 
 9 inline int NextInt(){
10     int ret = 0;
11     do
12         c = getchar();
13     while (!(48<=c && c<=57));
14     
15     do
16         ret *= 10, ret += c-48, c = getchar();
17     while (48<=c && c<=57);
18 
19     return ret;
20 }
21 
22 int main(){
23     memset(tot, 0, sizeof(tot));
24     memset(legal, 0, sizeof(legal));
25 
26      n = NextInt(), k = NextInt(), p = NextInt(), Pri = 0;
27      for (int i=1; i<=n; i++){
28         color = NextInt(), cost = NextInt();
29         if (cost<=p) cj = i;
30         if (cj>=last[color]) legal[color] = tot[color];
31         Pri += legal[color] , tot[color] ++, last[color] = i;
32      }
33      printf("%d
", Pri);
34 }

hotel.cpp

计算系数：

　　题解：组合数+快速幂。之前一直wa，直到把一些变量变成long long，然后多mod几次，就过了...

factor.cpp

聪明的质检员：

　　题解：二分

 1 #include <cstdio>
 2 #include <algorithm>
 3 #define LL "%lld" 
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int MAXN = 200000+10;
 8 const ll INF = 1e12;
 9 
10 ll n, m, s, L, R, Mid, Pri, w[MAXN], l[MAXN], r[MAXN], v[MAXN], sum[MAXN], sumv[MAXN];
11 
12 inline bool check(int x){
13     for (int i=1; i<=n; i++)
14         if (w[i]>=x)
15             sum[i] = sum[i-1]+1,
16             sumv[i] = sumv[i-1]+v[i];
17         else
18             sum[i] = sum[i-1],
19             sumv[i] = sumv[i-1];
20     
21     ll cj = 0;
22     for (int i=1; i<=m; i++)
23         cj += (sum[r[i]]-sum[l[i]-1])*(sumv[r[i]]-sumv[l[i]-1]);
24     
25     Pri = min(Pri, abs(cj-s));
26     return s<=cj;
27 }
28 
29 int main(){
30     scanf(LL LL LL, &n, &m, &s), L = Pri = INF, R = -INF;
31     for (int i=1; i<=n; i++)
32         scanf(LL LL, w+i, v+i), 
33         L = min(L, w[i]), R = max(R, w[i]);
34     for (int i=1; i<=m; i++)
35         scanf(LL LL, l+i, r+i);
36 
37     while (L<=R){
38         Mid = (L+R)>>1;
39         if (check(Mid)) L = Mid+1;
40         else R = Mid-1;
41     }
42     printf(LL, Pri);
43 }

check.cpp