Problem A – 写文案
与此题相似的还有最近 CodeForces Round #540 (Div, 3) – D2 与 Educational Codeforces Round 60 (Div. 2) – C。
二分解法
本题需要求 v 的最小值，并且要求 f(v) \ge n。
f(v) = \sum_{i=0}^\infty \left\lfloor\frac{v}{k^i}\right\rfloor
考虑这个函数的单调性，非常容易发现，f(v) 随着 v 的增大而增大。直接二分第一个 f(v) \ge n时的 v 即可。可以尝试用这种思路去做上面两题。
#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
int n, k;
int check(int i)
{
lld sa = 0, sb = i;
while (sb)
sa += sb, sb /= k;
return sa >= n ? 1 : -1;
}
int solve()
{
if (check(1)==1) return 1;
int l = 1, r = 1e9+7, m;
while (r-l>1)
{
m = (l+r)>>1;
if (check(m)==1)
r = m;
else
l = m;
}
return r;
}
int main()
{
scanf("%d %d", &n, &k);
printf("%d\n", solve());
return 0;
}
小范围暴力做法
可以发现，答案一定大于等于 n – \lfloor n / k\rfloor – 1，剩余答案大约在 O(\log n) 的范围内，暴力判断即可。但是此做法似乎无法通过提到的两题。
Problem B – 摆石子
动态规划解法
dp[n][m] 表示加入前 n 种颜色后，长度为 m 的排列有多少种方案。那么有
dp[i][j] = \sum_{k=0}^{j} C_j^k dp[i-1][j-k]
其中 1 \le i \le n, 0 \le j \le \sum_{p=1}^ia_p，如果预处理了组合数，那么总的时间复杂度为 O(\prod_{1 \le i \lt j \le n}a_i a_j) \le 10^8，并且是多组测试样例，15秒，是可以做的。
生成函数解法
由于所求的是排列型生成函数，所以考虑排列型生成函数。对于第 i 种颜色，对于长度为 k 的排列，方案数总为 1，其生成函数为 C_i(x)，总生成函数为 B(x)，即有。
B(x) = \prod_{i=1}^n C_i(x) = \prod_{i=1}^n \sum_{k=0}^{a_i} \frac{x^k}{k!} = \sum_{k=0}^m b_k \frac{x^k}{k!}
那么最后答案就是 \sum_{i=1}^k b_k。如果采用直接暴力多项式乘法，复杂度同上，但是常数好像小一点，维护起来也比较简单；另外如果遇到这种1e9+7的取模多项式乘法，可以考虑用拆系数FFT来做。
#include <vector>
#include <cstdio>
#include <algorithm>
typedef long long lld;
using namespace std;
const int MOD = 1e9+7;
int a[110];
const int MAXN = 1e4+5;
int inv[MAXN], invs[MAXN], fac[MAXN];
void init()
{
inv[0] = invs[0] = fac[0] = 1;
inv[1] = invs[1] = fac[1] = 1;
for (int i = 2; i < MAXN; i++)
{
inv[i] = 1LL*(MOD-MOD/i)*inv[MOD%i]%MOD;
invs[i] = 1LL*invs[i-1]*inv[i]%MOD;
fac[i] = 1LL*fac[i-1]*i%MOD;
}
}
vector<int> conv(vector<int> &a, vector<int> &b)
{
vector<int> ans(a.size()+b.size()-1, 0);
for (int i = 0; i < a.size(); i++)
{
for (int j = 0; j < b.size(); j++)
{
ans[i+j] = int((ans[i+j] + 1LL * a[i] * b[j]) % MOD);
}
}
return ans;
}
int main()
{
int n, cas = 0; init();
while (scanf("%d", &n) == 1)
{
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
sort(a, a+n);
vector<int> fx(1,1), gx(1,1);
for (int i = 0; i < n; i++)
{
while (gx.size() <= a[i])
gx.push_back(invs[gx.size()]);
vector<int> fgx = conv(fx, gx);
fx = fgx;
}
int ans = 0;
for (int i = 1; i < fx.size(); i++)
ans = (ans + 1LL * fx[i] * fac[i]) % MOD;
printf("Case %d: %d\n", ++cas, ans);
}
return 0;
}
Problem C – 算数字
简单筛选出2~10000的素数，保存到一个连续数组中。暴力求解；或者维护一个长度为10000的数组，表示对应标号的方案数，然后枚举连续数组的开头 i 和结尾 j 以计数。
#include <cstdio>
typedef long long lld;
using namespace std;
const int MAXN = 1e4+5;
int pri[MAXN], pcn, qzh[MAXN];
int cnt[MAXN];
bool isnp[MAXN];
void init_prime()
{
for (int i = 2; i < MAXN; i++)
{
if (!isnp[i]) pri[pcn++] = i;
for (int j = 0; j < pcn; j++)
{
if (i*pri[j] >= MAXN) break;
isnp[i*pri[j]] = 1;
if (i%pri[j]==0) break;
}
}
for (int i = 1; i <= pcn; i++)
qzh[i] = qzh[i-1] + pri[i-1];
for (int i = 0; i < pcn; i++)
for (int j = i+1; j <= pcn; j++)
if (qzh[j]-qzh[i] < MAXN)
cnt[qzh[j]-qzh[i]]++;
else break;
}
int main()
{
init_prime();
int n;
while (scanf("%d", &n) == 1 && n)
printf("%d\n", cnt[n]);
return 0;
}
Problem D – 复制玩具
可以发现，y-1 就是原始玩具投入机器的次数。那么再简单判断一下克隆玩具的情况即可。
#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
int main()
{
int x, y;
scanf("%d %d", &x, &y);
bool checked = true;
if (y<1) checked = false;
if ((x-y+1)%2) checked = false;
if (x < y-1) checked = false;
if (y == 1 && x != 0) checked = false;
printf(checked ? "Yes\n" : "No\n");
return 0;
}
Problem E – 蛙跳
分 k 的奇偶，计算左跳右跳次数即可。
#include <cstdio>
typedef long long lld;
using namespace std;
int main()
{
int t; lld a, b, k, ans;
scanf("%d", &t);
while (t--)
{
scanf("%lld %lld %lld", &a, &b, &k);
ans = (a-b)*(k/2) + a*(k%2);
printf("%lld\n", ans);
}
return 0;
}
Problem F – 地铁
这是一个图论题啦，感兴趣的同学可以去学一下图论中的最短路和最小生成树。
两点之间线段最短，然后再把同一条地铁线上地铁站之间的距离除以4加入图中，跑一遍最短路，最后将路程的米转换为分钟。
由于这是非负权完全图，直接使用最原始的 dijkstra 算法，复杂度为 O(V^2)。输入的时候要注意技巧，利用scanf的返回值。
#include <map>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
typedef long long lld;
using namespace std;
const int MAXV = 220;
double c[MAXV][MAXV];
double dis[MAXV];
bool vis[MAXV];
int n;
struct point
{
int x, y;
point(int _x = 0, int _y = 0) { x = _x, y = _y; }
bool operator==(const point &b) const { return x==b.x && y==b.y; }
bool operator<(const point &b) const { return (x==b.x && y<b.y) || (x<b.x); }
double operator-(const point &b)
{
int xx = x - b.x;
int yy = y - b.y;
return sqrt(1.0*xx*xx + 1.0*yy*yy);
}
};
map<point,int> V;
map<int,point> V2;
int get_id(const point &wtf)
{
if (V.count(wtf)) return V[wtf];
V[wtf] = ++n; V2[n] = wtf; return n;
}
bool input_station()
{
int x1, y1, x2, y2;
if (scanf("%d %d", &x1, &y1) != 2) return false;
while (scanf("%d %d", &x2, &y2) == 2 && ~x2 && ~y2)
{
point p1(x1,y1), p2(x2,y2);
int i1 = get_id(p1), i2 = get_id(p2);
double dis = min((p1-p2)/4, c[i1][i2]);
c[i1][i2] = c[i2][i1] = dis;
x1 = x2, y1 = y2;
}
return true;
}
void dijkstra()
{
dis[1] = 0;
for (int i = 1; i <= n; i++)
{
double minc = c[0][0];
int p = -1;
for (int j = 1; j <= n; j++)
if (!vis[j] && minc > dis[j])
minc = dis[j], p = j;
vis[p] = true;
for (int j = 1; j <= n; j++)
if (!vis[j] && dis[j] > dis[p] + c[p][j])
dis[j] = dis[p] + c[p][j];
}
}
int main()
{
int xh, yh, xs, ys;
scanf("%d %d %d %d", &xh, &yh, &xs, &ys);
memset(c, 0x55, sizeof(c));
memset(dis, 0x55, sizeof(dis)); // double INF in memory
point h(xh,yh), s(xs,ys);
V[h] = ++n; V2[n] = h;
V[s] = ++n; V2[n] = s;
while (input_station());
for (int i = 1; i <= n; i++)
{
for (int j = i+1; j <= n; j++)
{
double dis = min(c[i][j], V2[i]-V2[j]);
c[i][j] = c[j][i] = dis;
}
}
dijkstra();
printf("%.0f\n", dis[2]*6/1000+1e-8);
return 0;
}
Problem G – 半素数
先筛选出1-3000的所有素数，保存到一个连续数组中，然后对1-3000的每个数字，将每个素数进行试除，如果满足素因子个数仅为2的条件，那么记录下来，最后统计一下，结束。
#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
const int MAXN = 1e4+5;
int pri[MAXN], pcn, qzh[MAXN];
int cnts[MAXN];
bool isnp[MAXN];
void init_prime()
{
for (int i = 2; i < MAXN; i++)
{
if (!isnp[i]) pri[pcn++] = i;
for (int j = 0; j < pcn; j++)
{
if (i*pri[j] >= MAXN) break;
isnp[i*pri[j]] = 1;
if (i%pri[j]==0) break;
}
}
for (int i = 1; i <= 3000; i++)
{
int cnt = 0;
for (int j = 0; j < pcn; j++)
if (i % pri[j] == 0)
cnt++;
if (cnt == 2)
cnts[i]++;
}
for (int i = 1; i <= 3000; i++)
cnts[i] = cnts[i]+cnts[i-1];
}
int main()
{
init_prime();
int t;
scanf("%d", &t);
printf("%d\n", cnts[t]);
return 0;
}
Problem H – 骨牌摆放
一个长度为 n 的排列，可以由长度为 n-1 的排列后面添加一个 |，或者由长度为 n-2 的排列后面添加 = 或 □ 得到。那么 F_n = 2F_{n-2} + F_{n-1}，递推计算就好了。
由于没有取模，而且 long long 也存不下，所以考虑手动写个十进制加法算法或者使用 JAVA 的大数类即可。
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
BigInteger[] f = new BigInteger[251];
f[0] = f[1] = BigInteger.ONE;
for (int i = 2; i < 251; i++)
f[i] = f[i-1].add(f[i-2]).add(f[i-2]);
Scanner cin = new Scanner(System.in);
while (cin.hasNextInt())
System.out.println(f[cin.nextInt()]);
}
}
Problem I – 几点了
根据每个字符自己的特点，进行超级大的分类讨论好了。（大雾）
#include <cstdio>
typedef long long lld;
using namespace std;
char screen[22][22];
int check(int x)
{
if (screen[1][x+3] == '.' && screen[4][x] == '.')
return 5;
if (screen[1][x+3] == '.' && screen[4][x] == 'X')
return 6;
if (screen[0][x+1] == '.' && screen[3][x+1] == '.')
return 1;
if (screen[0][x+1] == '.' && screen[3][x+1] == 'X')
return 4;
if (screen[0][x+1] == 'X' && screen[3][x+1] == '.' && screen[6][x+1] == '.')
return 7;
if (screen[3][x+1] == '.')
return 0;
if (screen[4][x+3] == '.')
return 2;
if (screen[1][x] == '.')
return 3;
if (screen[4][x] == '.')
return 9;
return 8;
}
void solve()
{
for (int i = 0; i < 7; i++)
scanf("%s", screen[i]);
printf("%d", check(0));
printf("%d", check(5));
printf(":");
printf("%d", check(12));
printf("%d", check(17));
printf("\n");
}
int main()
{
int t; scanf("%d", &t);
while (t--) solve();
return 0;
}
Problem J – 匹配字
这题是询问，有多个模板字符串，他们中有多少个在目标字符串中出现。
这个算法叫做 Aho-Corasick automaton，中文名叫做 AC自动机，推荐阅读 这篇文章 来了解它的算法内容。
中考终于结素了。。嗯~考的还扣以~一中没问题。。
