🌑

小羊儿的心情天空

我的博客 我的实验 友情链接

2.20 JLU 寒假模拟赛

Feb 20, 2019 由 小羊

Problem A - 写文案

与此题相似的还有最近 CodeForces Round #540 (Div, 3) - D2 与 Educational Codeforces Round 60 (Div. 2) - C。

二分解法

本题需要求 vv 的最小值，并且要求 f(v)≥nf(v) \ge n。

f(v)=∑i=0∞⌊vki⌋f(v) = \sum_{i=0}^\infty \left\lfloor\frac{v}{k^i}\right\rfloor

考虑这个函数的单调性，非常容易发现，f(v)f(v) 随着 vv 的增大而增大。直接二分第一个 f(v)≥nf(v) \ge n时的 vv 即可。可以尝试用这种思路去做上面两题。

#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−⌊n/k⌋−1n - \lfloor n / k\rfloor - 1，剩余答案大约在 O(log⁡n)O(\log n) 的范围内，暴力判断即可。但是此做法似乎无法通过提到的两题。

Problem B - 摆石子

动态规划解法

dp[n][m] 表示加入前 nn 种颜色后，长度为 mm 的排列有多少种方案。那么有

dp[i][j]=∑k=0jCjkdp[i−1][j−k]dp[i][j] = \sum_{k=0}^{j} C_j^k dp[i-1][j-k]

其中 1≤i≤n,0≤j≤∑p=1iap1 \le i \le n, 0 \le j \le \sum_{p=1}^ia_p，如果预处理了组合数，那么总的时间复杂度为 O(∏1≤i<j≤naiaj)≤108O(\prod_{1 \le i \lt j \le n}a_i a_j) \le 10^8，并且是多组测试样例，15秒，是可以做的。

生成函数解法

由于所求的是排列型生成函数，所以考虑排列型生成函数。对于第 ii 种颜色，对于长度为 kk 的排列，方案数总为 11，其生成函数为 Ci(x)C_i(x)，总生成函数为 B(x)B(x)，即有。

B(x)=∏i=1nCi(x)=∏i=1n∑k=0aixkk!=∑k=0mbkxkk!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!}

那么最后答案就是 ∑i=1kbk\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的数组，表示对应标号的方案数，然后枚举连续数组的开头 ii 和结尾 jj 以计数。

#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−1y-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 - 蛙跳

分 kk 的奇偶，计算左跳右跳次数即可。

#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(V2)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 - 骨牌摆放

一个长度为 nn 的排列，可以由长度为 n−1n-1 的排列后面添加一个 |，或者由长度为 n−2n-2 的排列后面添加 = 或 □ 得到。那么 Fn=2Fn−2+Fn−1F_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自动机，推荐阅读 这篇文章 来了解它的算法内容。

自豪地采用Hexo | 皖ICP备17014812号-1

GitHub LinkedIn Mail