A、签到

$签到题打印就行，python代码$

print('祝贺祖国成立70周年！')

B、欧涛的烦恼

$给你一个n，代表后面有n个数，你可以对每个数加减，现在想要你把全部的数调整到相同大小，并且和不小于未调整之前$
$q组输入，q \leq 100, n\leq 100 ,a_i \leq 10^7$
$比较显然的结论我们对全部数求合，除掉n，再向上取整就是ans了）我当初还用二分去求过答案，有点笨$

#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;

int main() {
    int T = 1;
    T = read();
    while (T--) {
        int n = read(), sum = 0;
        for (int i = 1; i <= n; ++i)    sum += read();
        sum = ceil(1.0 * sum / n);
        print(sum);
    }
    return 0;
}

C、欧涛最短路

$给你一个n，代表后面有n个加油站，再给你一个m，代表你可以走的最长距离，当你走的超过m还没加油你就死了，n\leq600$
$后面紧跟一行先给出起点的x,y,z；再给出终点的x,y,z$
$想要你求到起点活着到终点最短距离，并且记录通过了那些加油站，如果无法到达输出-1$
$后面还有n行是加油站的x,y,z$
$首先观察数据范围，n的最大值仅仅600，支持O(n^2)的复杂度$
$那么我们建图操作就会变得很简单粗暴，首先不是加油站也不是起点也不是终点的三维坐标点我们根本不关心$
$因为他只是路过，走了没走都一个样，那么我们就直接把起点看作第0个点，加油站们看作第（1...n）个点，终点看作第n+1个点$
$依次枚举起点，往后遍历终点，当两点间距离小于m的时候连边即可$
$最后跑dijkstra跑出最短距离，并且再更新dis[v]的时候使用vector记录路径即可，这样走过的那些路也都记录下来了$

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<double, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const double INF = 1e18;
const double eps = 1e-4;
const int N = 600 + 7;

struct Node {
    double x, y, z;
    double calc(const Node& A) const {
        return sqrt((x - A.x) * (x - A.x) + (y - A.y) * (y - A.y) + (z - A.z) * (z - A.z));
    }
}a[N];

vector<pai> edge[N];
vector<int> ans[N];
int vis[N];
double dis[N];

void dijkstra(int s) {
    fill(dis, dis + N, 1e18);
    dis[s] = 0.0;
    ans[s].clear();
    ms(vis, 0);
    priority_queue<pai, vector<pai>, greater<pai>> pq;
    pq.push({ 0.0,s });
    while (pq.size()) {
        int u = pq.top().second;
        double w = pq.top().first;
        pq.pop();
        if (vis[u])    continue;
        vis[u] = 1;
        for (auto& it : edge[u]) {
            double w = it.first;
            int v = it.second;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push({ dis[v],v });
                ans[v] = ans[u];
                ans[v].push_back(v);
            }
        }
    }
}

int main() {
    int T = 1;
    //T = read();
    while (T--) {
        int n;
        double m;
        scanf("%d %lf", &n, &m);
        scanf("%lf %lf %lf %lf %lf %lf", &a[0].x, &a[0].y, &a[0].z, &a[n + 1].x, &a[n + 1].y, &a[n + 1].z);
        for (int i = 1; i <= n; ++i)
            scanf("%lf %lf %lf", &a[i].x, &a[i].y, &a[i].z);
        ++n;
        for (int i = 0; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j) {
                double tmp = a[i].calc(a[j]);
                if (tmp <= m) {
                    edge[i].push_back({ tmp,j });
                    edge[j].push_back({ tmp,i });
                }
            }
        dijkstra(0);
        if (fabs(dis[n] - INF) < eps)    puts("-1");
        else {
            printf("%.3f\n", dis[n]);
            printf("Start ");
            int len = ans[n].size();
            for (int i = 0; i < len - 1; ++i)
                printf("%d ", ans[n][i]);
            printf("End\n");
        }
    }
    return 0;
}

D、欧涛C 甜甜圈

$看题面意思，看样例猜出题人的出题意思，有点不喜欢这样的题目，就是给你一个字符串，叫你判断字符串中有几个闭合图形$
$0，4，6，9，都有一个闭合环，8有2个闭合环，累加答案就行$

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;

char s[1007];

int main() {
    int T = 1;
    T = read();
    while (T--) {
        scanf("%s", s);
        int ans = 0;
        for (int i = 0; s[i]; ++i)
            if (s[i] == '0' or s[i] == '4' or s[i] == '6' or s[i] == '9')
                ++ans;
            else if (s[i] == '8')
                ans += 2;
        print(ans);
    }
    return 0;
}

E、欧涛爬树

$给你一串字符串，对应下标从1开始的各个字符字母，下面再给出n-1条边构树形结构$
$问你从根节点到子节点走过的不同字符串可以有几个，只要不是完全相同的就是不同字符串，数据范围 n \leq 5e6$
$set + 字符串hash，不同字符串只要想到了使用hash去求值，那这个题目就会变得很简单$
$这个n有点大，用vector炸内存了，只能用前向星去弄了$
$在dfs的时候判断一下走过的点是不是叶子节点的就行了，走到叶子节点当前的hash值插入集合中，最终输出集合的元素个数即可$

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 5e6 + 7;
const int base = 131; // hash倍数

int head[N], tot = 0;//前向星变量
struct Node {
    //int u; //起点
    //int w; //权值
    int v, next;
} edge[N << 1];

void add(int u, int v) {
    tot++;
    //edge[tot].u = u;
    edge[tot].v = v;
    //edge[tot].w = w;
    edge[tot].next = head[u];
    head[u] = tot;
}
char s[N];
unordered_set<ull> st;

void dfs(int u, int fa, ull val) {
    ull now = val * base + s[u]; // 字符串hash值
    bool flag = 1;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa)    continue;
        dfs(v, u, now);
        flag = 0;
    }
    if (flag)    st.insert(now);    //叶子节点就插入当前字符串的 hash 值
}

int main() {
    int n;
    //T = read();
    while (~scanf("%d", &n)) {
        st.clear();
        ms(head, 0);
        scanf("%s", s + 1);
        for (int i = 1; i < n; ++i) {
            int u = read(), v = read();
            add(u, v);
            add(v, u);
        }
        dfs(1, 0, 0);
        print(st.size());
    }
    return 0;
}

F、欧涛B

$T组输入，每组输入第一行位移误差t，x轴最大误差maxx，y轴最大误差maxy，以及存在的n个消除误差点$
$现在想要你判断一下，如果x或者y方向上超过了最大误差，它就死了，误差消除点0的话可以消除x误差，1可以消除y误差$
$现在要你判断它会不会死，直接模拟就行了，看了样例就可以发现，需要算个绝对值$

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;

int main() {
    int T = 1;
    T = read();
    while (T--) {
        bool flag = true;
        int t = read(), maxx = read(), maxy = read(), n = read();
        int prex = read(), prey = read(), op = read();
        int x, y, tmp1 = 0, tmp2 = 0;
        while (--n) {
            x = read(), y = read(), op = read();
            tmp1 += abs((x - prex) * t);
            tmp2 += abs((y - prey) * t);
            if (tmp1 > maxx or tmp2 > maxy)    flag = false;
            if (op == 0)    tmp1 = 0;
            else tmp2 = 0;
            prex = x, prey = y;
        }
        if (flag)    puts("YES");
        else puts("NO");
    }
    return 0;
}

G、数据结构

$待补$

H、谁在说谎

$第一行代表n个人，并且他们会给出n组关系，n\leq 1e5$
$每个人都会说比自己高的人有a_i个，比自己低的人有b_i个，并且保证输入都合法，也就是不会出现输入大于n的情况$
$那么把这句话转换一个意思，也就是我当前成绩是落在区间[a_i+1,n-b_i]上的，并且这个区间分数都是相同的$
$现在需要你找出最少的撒谎人数$
$现在这个问题直接正面有点难求，那么就要转换一个思路了，输出最少撒谎人数，也就是总人数减掉最大合理区间数$
$我们开一个map去统计各个对应区间的出现次数，再通过区间右端点把出现过的区间左端点全部保存起来$
$比较明显的是，两个不同的区间不能够有重复交叉的办法，也就是如果一个区间是[1,3]，一个区间是[3,5]说明一定有一个人说谎了$
$那么也就是最大合理区间也就是只有1个了$
$接下来就要开始dp转移了，假设dp[i]是前i个人的最大合理区间$
$那么dp[i]的初始值就是dp[i-1]也就是第i个人碰到的区间我都不拿，接下来再尝试更新这个ans$
$如果要第i个人说真话，那么只要枚举之前出现过的区间起点j，这个区间数量+dp[j-1]也是一种合法的取法$
$但是这样还要注意一个问题，也就是区间出现的次数可能还会大于i-j+1次，也就是[1,3]区间出现了5次，那么也一定存在2个人说谎了，说真话最多也就是3个人$
$这样遍历n个人之后dp[n]就是n个人最大的合理区间数了$
$状态转移方程dp[i] = max(dp[i-1],min(dp[j-1] + mp[\{j,i\}],i-j+1)) j \in 出现过的区间左端点$

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;

map<pai, int> mp;
vector<int> p[N];
int dp[N];

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        int l = read() + 1, r = n - read();
        if (l > r)    continue;
        ++mp[{l, r}];
        if (mp[{l, r}] == 1)    p[r].push_back(l);
    }
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1];
        for (auto& j : p[i])
            dp[i] = max(dp[i], dp[j - 1] + min(mp[{j, i}], i - j + 1));
    }
    print(n - dp[n]);
    return 0;
}

I、不要666

$数位dp，但是又和大部分数位dp不一样的是，一般数位dp求得是个数$
$它要求的是合理的答案对应元素的和，那我们在开数位dp数组的时候直接用个结构体存了$
$一个代表个数，一个代表合理数的和，接下来只需要传递当前每一位的和，以及10进制下的这位数就行了，有点套板子$

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
int num[25];
ll bs[25];
struct Node {
    int cnt = -1;
    ll sum = 0;
}dp[25][10][10];

Node dfs(int len, int num1, int num2, bool limit) {
    if (!len) {
        if (num1 == 0 or num2 == 0)    return { 0,0 };
        else return { 1,0 };
    }
    if (!limit && ~dp[len][num1][num2].cnt)
        return dp[len][num1][num2];
    int up = limit ? num[len] : 9;
    Node ans;
    ans.cnt = 0;
    for (int i = 0; i <= up; ++i) {
        if (i == 6)    continue;
        Node tmp = dfs(len - 1, (num1 + i) % 6, (num2 * 10 + i) % 6, limit && i == up);
        ans.cnt = (ans.cnt + tmp.cnt) % MOD;
        ans.sum = (ans.sum + tmp.sum + i * bs[len] * tmp.cnt % MOD) % MOD;
    }
    if (!limit)    dp[len][num1][num2] = ans;
    return ans;
}

ll slove(ll n) {
    int cnt = 0;
    while (n) {
        num[++cnt] = n % 10;
        n /= 10;
    }
    return dfs(cnt, 0, 0, true).sum;
}

int main() {
    ll n, m;
    bs[1] = 1;
    for (int i = 2; i < 25; ++i) bs[i] = bs[i - 1] * 10 % MOD;
    while (~scanf("%lld %lld", &n, &m)) {
        printf("%lld\n", (slove(m) - slove(n - 1) + MOD) % MOD);
    }
    return 0;
}

J、组合技