本文共 6309 字，大约阅读时间需要 21 分钟。

A

一、题意

n个点m条带权边的无向连通图。边权就是距离。

初始时你在点1，让你依次经过2*k个点，使总距离最小。

定义一个瞬移方式：

（1）你可以从一个传送门花费0距离到达另一个传送门。

（2）初始时每个点都有一个关闭的传送门。

（3）你可以在任何一个点关闭任何一个传送门。

（4）你只能打开当前点的传送门。

（5）同时最多存在两个开启的传送门。

数据范围：

二、题解

只关注一个传送门的位置即可，因为我们可以在需要的时候在当前位置开启一个传送门，到达另一个传送门。

表示到达第i个点时其中一个传送门在j。

转移方式在注释中，就是把ppt的题解模拟了一下。

三、代码

#include<bits/stdc++.h>#define pb push_back#define fi first#define se second#define sz(x)  (int)x.size()#define cl(x)  x.clear()#define all(x)  x.begin() , x.end()#define rep(i , x , n)  for(int i = x ; i <= n ; i ++)#define per(i , n , x)  for(int i = n ; i >= x ; i --)#define mem0(x)  memset(x , 0 , sizeof(x))#define mem_1(x)  memset(x , -1 , sizeof(x))#define mem_inf(x)  memset(x , 0x3f , sizeof(x))#define debug(x)  cerr << '*' << x << '\n'#define ddebug(x , y)  cerr << '*' << x << ' ' << y << '\n'#define ios std::ios::sync_with_stdio(false) , cin.tie(0)using namespace std ;typedef long long ll ;typedef long double ld ;typedef pair<int , int> pii ;typedef pair<ll , ll> pll ;const int mod = 998244353 ;const int maxn = 300 + 10 ;const int inf = 0x3f3f3f3f ;const double eps = 1e-6 ; mt19937  rnd(chrono::high_resolution_clock::now().time_since_epoch().count()) ; int n , m , p ;int c[maxn << 1] ;ll dis[maxn][maxn] ;ll dp[maxn << 1][maxn] ;int main(){    ios ;    cin >> n >> m >> p ;    mem_inf(dis) ;    mem_inf(dp) ;    rep(i , 1 , m)    {        int u , v ;        ll w ;        cin >> u >> v >> w ;        dis[u][v] = min(dis[u][v] , w) ;        dis[v][u] = min(dis[v][u] , w) ;     }    rep(i , 1 , n)  dis[i][i] = 0ll ;    rep(k , 1 , n)  rep(i , 1 , n)  rep(j , 1 , n)  dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]) ;    p = p * 2 ;    rep(i , 1 , p)  cin >> c[i] ;    dp[0][1] = 0 ;    c[0] = 1 ;    rep(i , 0 , p - 1)  rep(j , 1 , n)    {        //1.直接从c[i]走到c[i+1]        dp[i + 1][j] = min(dp[i + 1][j] , dp[i][j] + dis[c[i]][c[i + 1]]) ;        //2.枚举走到c[i+1]之后，传送门的位置变为了哪个节点，设这个节点是k。第二种转移是从c[i]走到k，在k设置传送门，从k传送到j，再从j走到c[i+1]        rep(k , 1 , n)  dp[i + 1][k] = min(dp[i + 1][k] , dp[i][j] + dis[c[i]][k] + dis[j][c[i + 1]]) ;        //3.第三种转移是从c[i]传送到j，从j走到k，在k设置传送门，最后从k走到c[i+1]        rep(k , 1 , n)  dp[i + 1][k] = min(dp[i + 1][k] , dp[i][j] + dis[j][k] + dis[k][c[i + 1]]) ;    }    ll ans = 1e18 ;    rep(i , 1 , n)  ans = min(ans , dp[p][i]) ;    cout << ans << '\n' ;    return 0 ;}

B

一、题意

二、题解

三、代码

C

一、题意

二、题解

三、代码

D

一、题意

二、题解

三、代码

E

一、题意

二、题解

三、代码

F

一、题意

二、题解

三、代码

G

一、题意

二、题解

三、代码

H

对着这个学的：

主席树空间多开点，我开了200倍。

代码

#include<bits/stdc++.h>#define pb push_back#define fi first#define se second#define sz(x)  (int)x.size()#define cl(x)  x.clear()#define all(x)  x.begin() , x.end()#define rep(i , x , n)  for(int i = x ; i <= n ; i ++)#define per(i , n , x)  for(int i = n ; i >= x ; i --)#define mem0(x)  memset(x , 0 , sizeof(x))#define mem_1(x)  memset(x , -1 , sizeof(x))#define mem_inf(x)  memset(x , 0x3f , sizeof(x))#define debug(x)  cerr << #x << " = " << x << '\n'#define ddebug(x , y)  cerr << #x << " = " << x << "   " << #y << " = " << y << '\n'#define ios std::ios::sync_with_stdio(false) , cin.tie(0)using namespace std ;typedef long long ll ;typedef long double ld ;typedef pair<int , int> pii ;typedef pair<ll , ll> pll ;const int mod = 998244353 ;const int maxn = 2e5 + 10 ;const int inf = 0x3f3f3f3f ;const double eps = 1e-6 ; mt19937  rnd(chrono::high_resolution_clock::now().time_since_epoch().count()) ; int n , a[maxn] ;map<int , int> last ;int sum[maxn << 2] ;int ls(int x){   return x << 1 ;}int rs(int x){   return x << 1 | 1 ;}void update(int id , int l , int r , int x , int y){   int mid = (l + r) / 2 ;   if(l == r && l == x){sum[id] = y ; return ;}   if(x <= mid)  update(ls(id) , l , mid , x , y) ;   else  update(rs(id) , mid + 1 , r , x , y) ;   sum[id] = sum[ls(id)] & sum[rs(id)] ;}int query(int id , int l , int r , int x , int y){   int ans = (1 << 30) - 1 ;   int mid = (l + r) / 2 ;   if(y < x)  return 0 ; //不合法的询问   if(x <= l && r <= y)  return sum[id] ;   if(x <= mid)  ans &= query(ls(id) , l , mid , x , y) ;   if(y > mid)  ans &= query(rs(id) , mid + 1 , r , x , y) ;   return ans ;}struct Tree{    int lson[maxn * 200] , rson[maxn * 200] , sum[maxn * 200] ;    int cnt , root[maxn] ;    void init()    {        cnt = 0 ;        mem0(lson) , mem0(rson) ;        mem0(root) , mem0(sum) ;    }    void update(int l , int r , int pre , int &now , int x , int y)    {        cnt ++ ;        lson[cnt] = lson[pre] , rson[cnt] = rson[pre] , sum[cnt] = sum[pre] ;        now = cnt , sum[now] += y ;        if(l == r) return ;        int mid = (l + r) >> 1 ;        if(x <= mid)  update(l , mid , lson[pre] , lson[now] , x , y) ;        else  update(mid + 1 , r , rson[pre] , rson[now] , x , y) ;    }    int query(int id , int l , int r , int x , int y)    {       int ans = 0 ;       int mid = (l + r) / 2 ;       if(y < x)  return 0 ; //不合法的询问       if(x <= l && r <= y)  return sum[id] ;       if(x <= mid)  ans += query(lson[id] , l , mid , x , y) ;       if(y > mid)  ans += query(rson[id] , mid + 1 , r , x , y) ;       return ans ;    }} tree ;vector<pii> v ;void init(int i){    cl(v) ;    int now = i ;    int x = a[i] ;    while(now >= 1)    {        int l = 1 , r = now ;        int p = l ;        while(l <= r)        {            int mid = (l + r) / 2 ;            if(query(1 , 1 , n , mid , i) == x)  p = mid , r = mid - 1 ;            else  l = mid + 1 ;        }        v.pb({x , now}) ;        now = p - 1 ;        if(now >= 1)  x = query(1 , 1 , n , now , i) ;    }}void prework(){    tree.init() ;    rep(i , 1 , n)    {        init(i) ;        tree.root[i] = tree.root[i - 1] ;        for(auto u : v)        {            int x = u.fi ;            int p = u.se ;            if(last.count(x))  tree.update(1 , n , tree.root[i] , tree.root[i] , last[x] , -1) ;            last[x] = p ;            tree.update(1 , n , tree.root[i] , tree.root[i] , p , 1) ;        }    }}int main(){    ios ;    cin >> n ;    rep(i , 1 , n)  cin >> a[i] , update(1 , 1 , n , i , a[i]) ;    prework() ;    int q , ans = 0 ;    cin >> q ;    while(q --)    {        int l , r ;        cin >> l >> r ;         l = (l ^ ans) % n + 1 ;        r = (r ^ ans) % n + 1 ;        if(l > r)  swap(l , r) ;        ans = tree.query(tree.root[r] , 1 , n , l , r) ;        cout << ans << '\n' ;    }    return 0 ;}

I

一、题意

二、题解

三、代码

J

一、题意

二、题解

三、代码

K

一、题意

二、题解

三、代码