前言

本蒟蒻的第一篇题解，有写的不好地方欢迎大家私信评论。

我认为D，F需要一定的代码能力，处理好细节就可以，E硬控我一小时，但好歹最终做出来了，Bingbong说还算是挺板的算贡献题，实在是泰牛。

题解

A.小红的字符串

输出字符种类减一即可

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    std::string s;
    std::cin >> s;
    std::set<char> st;
    for (auto it : s) {
        st.insert(it);
    }
    std::cout << st.size() - 1 << '\n';
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    i64 t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
} 

B.小红的序列乘积

题目问的只是个位数，那其他位数的贡献就直接忽略不计，每次计算对10取模即可。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    int ans = 0;
    int pre = 1;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        a[i] %= 10;
        pre *= a[i];
        pre %= 10;
        if (pre == 6) {
            ans++;
        }
    }

    std::cout << ans << '\n';
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    i64 t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
} 

C.小红的数组重排

目标要求为。

我们拿出任意两项来看，化简之后为，再看，化简之后为。

以此类推我们发现任意相邻两项之间没有直接大小关系，但对于任意一位置来说，记一下每个数字出现的次数，如果出现了三次及以上，那一定无法得到一个好数组，那其他情况一定就都可以了吗，显然是不行，我们发现0出现两次就无法排了，所以除了以上说的两种情况，其余情况均可经过重排得到好数组，排序后输出即可

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    std::map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        mp[a[i]]++;
        if (mp[a[i]] == 3) {
            std::cout << "NO";
            return;
        }
    }
    
    std::sort(a.begin() + 1, a.end());
    if(a[2] == 0) {
        std::cout << "NO";
        return;
    }
    
    std::cout << "YES" << '\n';
    for (int i = 1; i <= n; i++) {
        std::cout << a[i] << ' ';
    }

}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    i64 t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
} 

D.虫洞操纵者

bfs没什么好说的，可以预处理出来所有的虫洞，但我这里仅展示一份比较暴力的代码，复杂度好像也不是很高，毕竟墙少跑的少，墙多break的快。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void solve() {
    int n;
    std::cin >> n;

    std::vector<std::vector<int> > mp(n + 2, std::vector<int> (n + 2, 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            std::cin >> mp[i][j];
        }
    }

    std::vector<std::vector<int> > vis(n + 5, std::vector<int> (n + 5, -1));
    auto bfs = [&] () -> int {
        std::queue<std::pair<int, int> > q;
        q.push({1, 1});
        vis[1][1] = 0;
        while(!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i], yy = y + dy[i];
                if (vis[xx][yy] != -1) continue;
                if (mp[xx][yy] == 1) {
                    if (i == 0) {
                        for (int j = y; j >= 0; j--) {
                            if (mp[x][j] == 1) {
                                xx = x, yy = j + 1;
                                break;
                            }
                        }
                    }
                    else if (i == 1) {
                        for (int j = x; j >= 0; j--) {
                            if (mp[j][y] == 1) {
                                xx = j + 1, yy = y;
                                break;
                            }
                        }
                    }
                    else if (i == 2) {
                        for (int j = y; j <= n + 1; j++) {
                            if (mp[x][j] == 1) {
                                xx = x, yy = j - 1;
                                break;
                            }
                        }
                    }
                    else {
                        for (int j = x; j <= n + 1; j++) {
                            if (mp[j][y] == 1) {
                                xx = j - 1, yy = y;
                                break;
                            }
                        }
                    }
                    if (vis[xx][yy] != -1) continue;
                    vis[xx][yy] = vis[x][y] + 1;
                    q.push({xx, yy});
                }
                else {
                    vis[xx][yy] = vis[x][y] + 1;
                    q.push({xx, yy});
                }
            }
        }
        return vis[n][n];
    };

    std::cout << bfs();
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    i64 t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
} 

E.小红的序列乘积2.0

加强版，那就不能单纯算前缀和了，考虑，表示的是到位置有多少种个位数以数字结尾的方案数，考虑转移方程为 + ，还可以一维数组滚动一下，如果当前位置的值乘上上一个位置结尾的个位数为那就计算一下贡献。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

const int mod = 1e9 + 7;

i64 ksm(i64 a, i64 b) {
    i64 ans = 1;
    while (b) {
        if (b & 1) {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }

    return ans;
}

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        a[i] %= 10;
    }
    
    //一维数组滚动写法
    std::vector<i64> f(10);
    f[1] = 1;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        std::vector<i64> tp(10, 0);
        for (int j = 0; j < 10; j++) {
            if (!f[j]) continue;
            if ((j * a[i]) % 10 == 6) {
                ans = (ans + f[j] * ksm(2, n - i) % mod) % mod;
            }
            tp[j] += f[j];
            tp[j] %= mod;
            tp[(j * a[i]) % 10] += f[j];
            tp[(j * a[i]) % 10] %= mod;
        }
        f = tp;
    }
    //二维数组写法
    //std::vector<std::vector<i64> > f(n, std::vector<i64> (10));
    // f[0][1] = 1;
    // int ans = 0;
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 0; j < 10; j++) {
    //         if (j * a[i] % 10 == 6) {
    //             ans = (ans + f[i - 1][j] * ksm(2, n - i) % mod) % mod;
    //         }
    //         f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
    //         f[i][j * a[i] % 10] = (f[i][(j * a[i]) % 10] + f[i - 1][j]) % mod;
    //     }
    // }
    std::cout << ans << '\n';
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    i64 t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
} 

F.灯下定影

几何板子题，粘点板子上来就写了吧，我当时是因为求直线与圆相交的板子的前提是直线一定与圆有交点，但我没判断，导致ub了

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

double eps = 1e-8;

struct point
{
    double x, y;
};

struct line
{
    point a, b;
};

double distance(point p1, point p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

double distance(double x1,double y1,double x2,double y2) {
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

point intersection(point u1,point u2,point v1,point v2)
{
    point ret=u1;
    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x+=(u2.x-u1.x)*t;
    ret.y+=(u2.y-u1.y)*t;
    return ret;
}

void intersection_line_circle(point c,double r,point l1,point l2,point& p1,point& p2)
{
    point p=c;
    double t;
    p.x+=l1.y-l2.y;
    p.y+=l2.x-l1.x;
    p=intersection(p,c,l1,l2);
    t=sqrt(r*r-distance(p,c)*distance(p,c))/distance(l1,l2);
    p1.x=p.x+(l2.x-l1.x)*t;
    p1.y=p.y+(l2.y-l1.y)*t;
    p2.x=p.x-(l2.x-l1.x)*t;
    p2.y=p.y-(l2.y-l1.y)*t;
}

double xmult(point p1,point p2,point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

double disptoline(point p,point l1,point l2)
{
    return fabs(xmult(p,l1,l2))/distance(l1,l2);
}

int intersect_line_circle(point c,double r,point l1,point l2)
{
    return disptoline(c,l1,l2)<r+eps;
}

std::vector<std::pair<double, double>> segs;
//区间合并
void merge(std::vector<std::pair<double, double> > &segs)
{
    std::vector<std::pair<double, double>> res;//用来存储
    //按区间的左端点来进行排序，然后再按照第二个排序（pair很像）
    std::sort(segs.begin(),segs.end());
    double st = -2e9, ed = -2e9;
    for(auto seg : segs)
    {
        //如果比较区间的左端点不在当前区间中
        if(ed < seg.first)
        {
            //判断一下是否更新 新的当前区间（以防第一次更新）
            if(st!=-2e9) res.push_back({st,ed});
            st = seg.first,ed = seg.second;//更新区间，变成当前区间
        }
        //如果比较区间的左端点在区间中更新一下最大的右端点
        else ed = std::max(ed,seg.second); 
    }
    //看一下，最后一个元素是否被合并
    if(st!=-2e9) res.push_back({st,ed});
    
    segs = res;
}


void solve() {
    double x0, y0, r;
    std::cin >> x0 >> y0 >> r;
    point p0 = {x0, y0};

    int n;
    double x;
    std::cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        double sx, sy, tx, ty, v;
        std::cin >> sx >> sy >> tx >> ty >> v;

        point pl1 = {sx, sy}, pl2 = {tx, ty};
        point p1, p2;
        intersection_line_circle(p0, r, pl1, pl2, p1, p2);
        
        if (intersect_line_circle(p0, r, pl1, pl2) == 0) continue;

        double tp1 = pl2.x - pl1.x;
        double tp2 = p2.x - pl1.x;
		
        //这里在判断射线的方向是否能与圆有交点，因为两个点一定不重合，先判一下射线x的方向与交点方向
        //如果射线是平行与y轴的就用纵坐标去判断是否相交。
        if(tp1 != 0) {
            // std::cout << tp1 << '\n';
            if ((tp1 > 0 && tp2 < 0) || (tp1 < 0 && tp2 > 0)) continue;
        }
        else {
            tp1 = pl2.y - pl1.y;
            tp2 = p2.y - pl1.y;
            if ((tp1 > 0 && tp2 < 0) || (tp1 < 0 && tp2 > 0)) continue;
        }

        double dis1 = distance(pl1, p1);
        double dis2 = distance(pl1, p2);

        if (dis1 - dis2 > 0) std::swap(dis1, dis2);
        segs.push_back({dis1 / v, dis2 / v + x});
    }

    merge(segs);

    double ans = 0;
    for (auto [l, r] : segs) {
        // std::cout << l << ' ' << r << '\n';
        ans += r - l;
    }

    std::cout << std::fixed << std::setprecision(12) << ans << '\n';
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);
    i64 t = 1;
    // std::cin >> t;
    while (t--) {
        solve();
    }
}