简单总结下这次蓝桥杯

感觉搜索多了很多，相比去年考板子（二维单调队列、字典树、欧拉函数）有所变化

附个人代码，maybe与正解有所差异
预估5 + 0 + 10 + (2~10) + (4.5~7.5) + (4.5~15) + (16~20) + 20
62 ~ 87.5 ?

A.进制(签到) 32

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int x = 8100178706957568 ;
    for(int i = 11 ; i <= 36 ; ++ i) 
    {
        int y = x , ok = 1 ; 
        while (y) 
        {
            if ( y % i >= 10 ) {
                ok = 0; 
                break ;
            }
            y /= i ; 
        }
        if ( ok ) return cout << i << '\n' , 0 ; 
    }
    return 0;
}

B.逆序对期望(暴力) 65.33

#include <bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n ;
    std::cin >> n ;
    std::vector<int> a(n) ;
    for(int i = 0 ; i < n ; ++ i) a[i] = i + 1 ;
    ld ret = 0 ; 
    for(int i = 0 ; i < n ; ++ i)
        for(int j = 0 ; j < n ; ++ j)
            if ( i != j ) 
                for(int x = 0 ; x < n ; ++ x)
                    for(int y = 0 ; y < n ; ++ y)
                        if ( x != y )
                        {
                            int num = 0 ;
                            swap(a[i] , a[j]) ;
                            swap(a[x] , a[y]) ; 
                            for(int k1 = 0 ; k1 < n ; ++ k1)
                                for(int k2 = k1 + 1 ; k2 < n ; ++ k2)
                                    if ( a[k1] > a[k2] ) ++ num ; 

                            swap(a[x] , a[y]) ; 
                            swap(a[i] , a[j]) ;
                            ret += num * (ld)1 / (n *( n - 1) * (n - 1) * n) ;
                        }
    std::cout << fixed << setprecision(2) << ret << '\n' ;
    return 0;
}

C.传送阵(枚举)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int tot, cnt[N], n, a[N], b[N];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> a[i] ;
        -- a[i] ;
    }
    for(int i = 0 ; i < n ; ++ i)
    {
        int pre = i ;
        if ( !b[pre] ) 
        {
            ++ tot ; 
            while ( !b[pre] )
            {
                b[pre] = tot; 
                pre = a[pre] ; 
                ++ cnt[tot] ; 
            }
        }
    }
    int ret = 0 ;
    for(int i = 0 ; i < n ; ++ i)
    {
        int pre = ((i - 1) % n + n) % n , nxt = (i + 1) % n ; 
        if ( b[pre] != b[i] ) ret = std::max(ret , cnt[b[pre]] + cnt[b[i]]) ;
        if ( b[nxt] != b[i] ) ret = std::max(ret , cnt[b[nxt]] + cnt[b[i]]) ;
        ret = std::max(ret , cnt[b[i]]) ;
    }
    std::cout << ret << '\n' ;
    return 0;
}

前缀总分(暴力？)

浅浅算了下最坏情况$200 * 200 * 26 * 200 2.08e8 $ 斯~ 不确定最里面y[0,m]能不能跑满

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 210 ;
int cnt[N] ; 
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n ;
    std::cin >> n ;
    std::vector<std::string> a(n) ;
    for(auto &p : a) std::cin >> p ;

    int ret = 0 , sum = 0 ;
    for(int i = 0 ; i < n ; ++ i)
        for(int j = 0 ; j < n ; ++ j)
            if ( i != j ) 
            {
                int m = std::min(a[i].size() , a[j].size()) ;
                for(int k = 0 ; k < m ; ++ k)
                    if ( a[i][k] != a[j][k] ) break ;
                    else ++cnt[i] , ++ sum; 
            }
    for(int i = 0 ; i < n ; ++ i)
        for(int j = 0 ; j < (int)a[i].size() ; ++ j)
            for(int k = 0 ; k < 26 ; ++ k)
            {
                char ch = a[i][j] ;
                a[i][j] = char('a' + k) ;
                int num = 0 ;
                sum -= cnt[i] ;
                for(int x = 0 ; x < n ; ++ x) 
                    if ( x != i ) 
                    {
                        int m = std::min(a[i].size() , a[x].size()) ;
                        for(int y = 0 ; y < m ; ++ y)
                            if ( a[i][y] != a[x][y] ) break ;
                            else ++ num ; 
                    }
                ret = std::max(ret , sum / 2 + num); 
                sum += cnt[i] ; 
                a[i][j] = ch ;
            }

    std::cout << ret << '\n' ;
    return 0;
}

E.遗迹

..赛时bfs弄的斯~弄了点数据没问题就交了,极限数据过不了。
测试了下 n = 1000 , m = 30000 能在3s内跑完 预估跑过20-40%测试点

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e3 + 10 , M = 1e5 + 10 ;
const int inf = 0x3f3f3f3f ; 
int d[M][N] ;
int n , m , L ;
std::string s , t ;
std::vector<int> a[26] ; 
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m >> L >> s >> t ;
    s = "#" + s ;
    t = "#" + t ; 
    memset(d , 0x3f, sizeof d) ;
    for(int i = 1 ; i <= n ; ++ i)
        a[s[i] - 'a'].push_back(i) ;
    queue<pair<int , int>> que ;
    for(auto p : a[t[1] - 'a']) que.push({p , 1}) , d[1][p] = 0 ; 
    while ( !que.empty() ) 
    {
        auto p = que.front() ; que.pop() ;
        for(auto q : a[t[p.second + 1] - 'a'])
        {
            if ( d[p.second + 1][q] > d[p.second][p.first] + abs(p.first - q)) 
            {
                d[p.second + 1][q] = d[p.second][p.first] + abs(p.first - q) ; 
                que.push({q , p.second + 1}) ;
            }
        }
    }
    for(int i = m ; i >= 1 ; -- i)
        for(int j = 1 ; j <= n ; ++ j)
            if ( d[i][j] <= L ) return std::cout << i << '\n' , 0 ; 
    return 0;
}

F.送快递（枚举？）

枚举加哪条边，跑bfs，emm感觉也是混个20%测试点的分的做法

#include <bits/stdc++.h>
using namespace std;
const int N = 310 , inf = 0x3f3f3f3f ; 
std::set<int> edges[N] ; 
int n , m ;
int d[N] ; 
bool st[N] ;
int bfs(int x,int y) {
    memset(st , 0 ,sizeof st) ;
    memset(d , 0x3f , sizeof d) ;
    queue<int> que ;
    que.push(x) ;
    d[x] = 0 ;
    st[x] = true ;
    while ( !que.empty() ) 
    {
        int p = que.front() ; que.pop() ;

        for(auto v : edges[p])
        {
            if ( d[v] > d[p] + 1 ) {
                d[v] = d[p] + 1 ;
                que.push(v) ;
            }
        }
    }
    return d[y] ; 
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m ;
    for(int i = 1 ; i < n ; ++ i )
    {
        int u , v ;
        std::cin >> u >> v;
        edges[u].insert(v) ;
        edges[v].insert(u) ; 
    }
    std::vector<std::pair<int , int>> a(m) ;
    for(auto & p : a) cin >> p.first >> p.second ;
    int ret = inf ; 
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = i + 1 ; j <= n ; ++ j)
            if ( !edges[i].count(j) ) 
            {
                edges[i].insert(j) ;
                edges[j].insert(i) ;
                int num = 0 ;
                for(auto p : a)
                    num += bfs(p.first , p.second) ;
                ret = std::min(ret , num) ; 
                edges[i].erase(j) ;
                edges[j].erase(i) ; 
            }
    std::cout << ret << '\n' ;
    return 0;
}

G.狡兔k窟 (dijstra)

同洞窟的点建边权为0的边，原边建边权为1，跑dijstra $O(Tmlogn)$ 但感觉最坏是$O(n^3logn)$ 斯~可能有组测试点会被T的可能

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5010 ; 
typedef pair<int , int> PII ;
int n , m  ;
std::vector<PII> edges[N] ;
std::vector<int> c[N] ;
int d[N] ;
int dijstra(int x,int y) 
{
    memset(d , 0x3f , sizeof d) ;
    priority_queue<PII , std::vector<PII> , greater<PII>> que ;
    que.push({0 , x}) ;
    d[x] = 0 ; 
    while (!que.empty())
    {
        auto p = que.top() ; que.pop() ;
        if ( d[p.second] < p.first ) continue ;
        for(auto v : edges[p.second])
        {
            if ( d[v.first] > d[p.second] + v.second )
            {
                d[v.first] = d[p.second] + v.second ;
                que.push({d[v.first] , v.first}) ;
            }
        } 
    }
    return d[y] ;
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m ;
    for(int i = 1 ; i <= n ; ++ i)
    {
        int x ;
        std::cin >> x;
        c[x].push_back(i) ; 
    }
    for(int i = 1 ; i < n ; ++ i)
    {
        int u , v ;
        std::cin >> u >> v ;
        edges[u].push_back({v , 1}) ;
        edges[v].push_back({u , 1}) ;
    }
    for(int i = 1 ; i <= n ; ++ i)
        for(auto p : c[i])
            for(auto q : c[i])
                if ( p != q ) 
                    edges[p].push_back({q , 0}) ;
    while (m--)
    {
        int u , v;
        std::cin >> u >> v ;
        std::cout << dijstra(u , v) << '\n' ;
    }
    return 0;
}

H.装修(树形dp)

典，难度堪比上司的舞会。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10 ; 
typedef pair<int , int> PII ;
int f[N][2] ; // 典
std::vector<PII> edges[N] ;
int n ; 
int cnt[N] ;
void dfs(int v,int fa)
{
    int sum = 0 ;
    for(auto p : edges[v])
    {
        int u = p.first ;
        if (u != fa)
        {
            dfs(u , v) ;
            if ( f[u][0] > f[u][1] ) 
                sum += f[u][0] , cnt[u] = 0 , f[v][1] += f[u][0] ;
            else 
                sum += f[u][1] , cnt[u] = 1 , f[v][1] += f[u][1] ;
        }
    }
    for(auto p : edges[v]) 
    {
        int u = p.first , w = p.second ; 
        if ( u != fa ) 
        {
            f[v][0] = std::max(f[v][0] , w + f[u][1] + sum - f[u][cnt[u]] ) ;
        } 
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n ;
    for(int i = 1 ; i < n ; ++ i)
    {
        int u , v , w ;
        std::cin >> u >> v >> w ;
        edges[u].push_back({v , w}) ;
        edges[v].push_back({u , w}) ;
    }
    dfs(1 , 0) ;
    std::cout << std::max(f[1][0] , f[1][1]) << '\n' ;
    return 0;
}