题目涉及算法：
- 买铅笔：入门题；
- 回文日期：枚举；
- 海港：双指针；
- 魔法阵；数学推理。
买铅笔
题目链接：https://www.luogu.org/problem/P1909
设至少要买 (num) 只笔，且对于每只钱币，设它的价格为 (a) ，笔数为 (b) ，则花费为最大的那个 (lceil frac{num}{a}
ceil imes b) 。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
int num, a, b, ans = INT_MAX;
int main() {
cin >> num;
for (int i = 0; i < 3; i ++) {
cin >> a >> b;
ans = min(ans, (num+a-1)/a*b);
}
cout << ans << endl;
return 0;
}
回文日期
题目链接：https://www.luogu.org/problem/P2010
使用枚举解决，实现代码如下：
#include <bits/stdc++.h>
using namespace std;
string start_date, end_date;
int cnt;
void solve(int year) {
int a[8];
a[0] = year / 1000;
a[1] = year / 100 % 10;
a[2] = year / 10 % 10;
a[3] = year % 10;
for (int i = 0; i < 4; i ++) a[7-i] = a[i];
int month = a[4]*10 + a[5];
int day = a[6]*10 + a[7];
if (month < 1 || month > 12) return;
int dd = 31;
if (month<8 && month%2==0 || month>7 && month%2!=0) dd = 30;
else if (month == 2) {
if (year%400==0 || year%4==0&&year%100!=0) dd = 29;
else dd = 28;
}
if (day < 1 || day > dd) return;
string s = "";
for (int i = 0; i < 8; i ++) {
s += (char) ('0' + a[i]);
}
if (s >= start_date && s <= end_date) cnt ++;
}
int main() {
cin >>start_date >> end_date;
for (int i = 0; i < 10000; i ++) solve(i);
cout << cnt << endl;
return 0;
}
海港
题目链接：https://www.luogu.org/problem/P2058
本题涉及算法：双指针法。
我们令 (c[i]) 表示当前时刻在海港内国别为 (i) 的人数，令 (cnt) 表示当前时刻海港内有多少个不同国别的人。
我们一开始另 (j = 0) ，然后从 (0) 到 (n-1) 遍历 (i) ：
对于变量 (i) ，首先遍历它里面所有国别 (x) ，(c[x] ++) ，如果此时 (c[x] = 1) ，说明这个国别是第一次有，令 (cnt ++) ；
只要满足 (t[j] le t[i] - 86400) ，我们就执行如下操作：
遍历 (t[j]) 时刻所有旅客的国别 (x) ，(c[x] --) ，如果此时 (c[x] = 0) ，说明这个国别的旅客都没有了，令 (cnt --)；然后就是 (j++) ，直到 (t[j] gt t[i] - 86400) 。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int DELTA = 86400;
int n, a, t[maxn], k[maxn], c[maxn], cnt;
vector<int> x[maxn];
void my_add(int id) { // 增加编号为id的信息
for (int i = 0; i < k[id]; i ++) {
int a = x[id][i];
c[a] ++;
if (c[a] == 1) cnt ++;
}
}
void my_del(int id) { // 删除编号为id的信息
for (int i = 0; i < k[id]; i ++) {
int a = x[id][i];
c[a] --;
if (c[a] == 0) cnt --;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> t[i] >> k[i];
for (int j = 0; j < k[i]; j ++) {
cin >> a;
x[i].push_back(a);
}
}
for (int i = 0, j = 0; i < n; i ++) {
my_add(i);
while (t[j] <= t[i] - DELTA) {
my_del(j ++);
}
cout << cnt << endl;
}
return 0;
}
魔法阵
题目链接：https://www.luogu.org/problem/P2119
题解：本着不重复造轮子的思想，请转 yhf2000 大神的博文：https://www.luogu.org/blog/yhf/solution-p2119
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 15010, maxm = 40040;
int n, m, a[maxn], b[maxn], c[maxn], d[maxn], val[maxm], cnt[maxn];
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i ++) {
scanf("%d", &val[i]);
cnt[ val[i] ] ++;
}
for (int i = 1; 2+9*i <= n; i ++) {
int tmp = 0;
for (int j = 2+9*i; j <= n; j ++) {
tmp += cnt[j-1-9*i] * cnt[j-1-7*i];
c[j-i] += cnt[j] * tmp;
d[j] += cnt[j-i] * tmp;
}
tmp = 0;
for (int j = n-1-9*i; j >= 1; j --) {
tmp += cnt[j+1+8*i] * cnt[j+1+9*i];
a[j] += cnt[j+2*i] * tmp;
b[j+2*i] += cnt[j] * tmp;
}
}
for (int i = 0; i < m; i ++)
printf("%d %d %d %d
", a[ val[i] ], b[ val[i] ], c[ val[i] ], d[ val[i] ]);
return 0;
}
作者：zifeiy