首页 > 代码库 > NOIP2011 题解

NOIP2011 题解

2024-07-13 09:03:40   222人阅读

铺地毯

　　题解：排序

 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\n", 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     do12         c = getchar();13     while (!(48<=c && c<=57));14     15     do16         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\n", Pri);34 }
hotel.cpp

 

计算系数：

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

 1 #include <cstdio> 2 #include <cstring> 3  4 const int MAXN = 1000;  5 const int MOD = 10007; 6  7 int a, b, k, m, n; 8 long long c[MAXN+10][MAXN+10]; 9 10 inline long long QuickPow(int a, int k){11     long long base = a, ret = 1;12     while (k){13         if (k&1) ret = (ret*base)%MOD;14         base = (base*base)%MOD, k >>= 1;15     }16     return ret%MOD;17 }18 19 int main(){20     memset(c, 0, sizeof(c));21     for (register int i=0; i<=MAXN+1; i++)22         c[i][i] = c[i][0] = 1;23     for (register int i=2; i<=MAXN+1; i++)24         for (register int j=1; j<i; j++)25             c[i][j] = (c[i-1][j]+c[i-1][j-1])%MOD;26 27     scanf("%d %d %d %d %d", &a, &b, &k, &n, &m);28     long long Pri = c[k][n];29     Pri = (Pri*QuickPow(a,n))%MOD, Pri = (Pri*QuickPow(b,m))%MOD;30     printf("%lld\n", Pri);31 }
factor.cpp


联系
我们