铺地毯
题解：比大小
#include <cstdio>
const int MAXN = +;
int n, x, y, a[MAXN], b[MAXN], g[MAXN], k[MAXN];
inline int Solve(){
for (int i=n; i>; i--)
if (a[i]<=x && x<=a[i]+g[i] && b[i]<=y && y<=b[i]+k[i]) return i;
return -;
}
int main(){
scanf("%d", &n);
for (int i=; i<=n; i++)
scanf("%d %d %d %d", &a[i], &b[i], &g[i], &k[i]);
scanf("%d %d", &x, &y);
printf("%d\n", Solve());
}
carpet.cpp
选择客栈:
题解：模拟。cj表示最近的一个可行的咖啡馆，tot[i]表示之前颜色i出现过的次数legal[i]表示颜色i在cj之前出现过的次数，last[i]表示颜色i最后出现的编号
#include <cstdio>
#include <cstring> const int MAXK = +; int n, k, p, color, cost, cj, Pri, legal[MAXK], tot[MAXK], last[MAXK];
char c; inline int NextInt(){
int ret = ;
do
c = getchar();
while (!(<=c && c<=)); do
ret *= , ret += c-, c = getchar();
while (<=c && c<=); return ret;
} int main(){
memset(tot, , sizeof(tot));
memset(legal, , sizeof(legal)); n = NextInt(), k = NextInt(), p = NextInt(), Pri = ;
for (int i=; i<=n; i++){
color = NextInt(), cost = NextInt();
if (cost<=p) cj = i;
if (cj>=last[color]) legal[color] = tot[color];
Pri += legal[color] , tot[color] ++, last[color] = i;
}
printf("%d\n", Pri);
}
hotel.cpp
计算系数：
题解：组合数+快速幂。之前一直wa，直到把一些变量变成long long，然后多mod几次，就过了...
factor.cpp
聪明的质检员：
题解：二分
#include <cstdio>
#include <algorithm>
#define LL "%lld"
using namespace std; typedef long long ll;
const int MAXN = +;
const ll INF = 1e12; ll n, m, s, L, R, Mid, Pri, w[MAXN], l[MAXN], r[MAXN], v[MAXN], sum[MAXN], sumv[MAXN]; inline bool check(int x){
for (int i=; i<=n; i++)
if (w[i]>=x)
sum[i] = sum[i-]+,
sumv[i] = sumv[i-]+v[i];
else
sum[i] = sum[i-],
sumv[i] = sumv[i-]; ll cj = ;
for (int i=; i<=m; i++)
cj += (sum[r[i]]-sum[l[i]-])*(sumv[r[i]]-sumv[l[i]-]); Pri = min(Pri, abs(cj-s));
return s<=cj;
} int main(){
scanf(LL LL LL, &n, &m, &s), L = Pri = INF, R = -INF;
for (int i=; i<=n; i++)
scanf(LL LL, w+i, v+i),
L = min(L, w[i]), R = max(R, w[i]);
for (int i=; i<=m; i++)
scanf(LL LL, l+i, r+i); while (L<=R){
Mid = (L+R)>>;
if (check(Mid)) L = Mid+;
else R = Mid-;
}
printf(LL, Pri);
}
check.cpp