有问题请评论区聊喵！！！

A：迷星叫

思路

直接使用判断语句模拟输出就行了。

代码展示


#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 5e5 + 5, mod =1e9+7, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il void solve(){
    int n;
    cin>>n;
    if(n==3||n==6){
        cout<<"koishiYun\n";
    }else{
        cout<<"Kato_Shoko\n";
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;

    cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}

B：焚音打

观察

设我们选择的发布顺序为排列 $p_1,p_2,\dots,p_n$ ，其中第 $t$ 个发布的是消息 $p_t$ 。题目中每条消息的实际贡献为

\text{val}_{p_t}=a_{p_t}-b_{p_t}\cdot (t-1).

因此总影响力为

\mathrm{ans}=\sum_{t=1}^n \bigl(a_{p_t}-b_{p_t}(t-1)\bigr) = \sum_{i=1}^n a_i -\sum_{t=1}^n b_{p_t}(t-1).

注意到第一项 $\sum a_i$ 与排列无关。所以要最大化总影响力，等价于最小化

S=\sum_{t=1}^n b_{p_t}(t-1).

直观上，为了使带大权（即大 $b$ ）的项乘以尽可能小的系数 $(t-1)$ ，应该把 $b$ 较大的消息放在前面。

实现

将所有消息按 $b_i$ 非增（从大到小）排序；按此顺序发布即为最优。

代码展示

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 2e5 + 5, mod =1e9+7, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il void solve(){
    int n;
    cin>>n;
    vector<pair<ll,ll>>pa(n);
    for(auto &[x,y]:pa)cin>>x>>y;
    sort(pa.begin(),pa.end(),[&](auto &x,auto &y){
        return x.second>y.second;
    });
    ll ans=0;
    for(ll i=0;i<n;i++){
        auto [a,b]=pa[i];
        ans+=a-b*i;
    }
    cout<<ans<<'\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;

    cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}

C：诗超绊

思路简述

我们要用至多 $m$ 次区间加操作（每次加同一个固定正整数 $d$ ）使序列严格递增。显然，若能用某个 $d$ 实现目标，则对更大的 $d'\ge d$ 也可以实现，因此答案关于 $d$ 是单调的，可用二分查找最小可行的 $d$ 。

给定 $d$ ，如何判断可行？

我们只需判断是否能用不超过 $m$ 次操作，使得每个位置满足

a_i' > a_{i-1}' \quad (\forall, i>1).

由于每次操作将一段连续区间整体加 $d$ ，可以等价地把操作理解为“将某些前缀区间的加次数累积起来”。我们可以贪心地从左到右判断：

设当前已经进行了若干次区间加，使得到位置 $i-1$ 为止，序列已严格递增；
若此时 $a_i \le a_{i-1}$ ，则至少需要让 $a_i$ 增加到 $a_{i-1}+1$ ，因此需要的额外加次数为 $t = \Big\lceil \frac{a_{i-1}+1 - a_i}{d} \Big\rceil;$ 这些加法可视为从位置 $i$ 到结尾都加上 $t$ 次 $d$ ，操作次数总和累加上 $t$ 。

若累计操作次数总和 $\le m$ ，则说明当前 $d$ 可行，否则不可行。

代码展示

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 2e5 + 5, mod =1e9+7, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il void solve(){
    ll n,m;
    cin>>n>>m;
    vector<ll>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];

    bool ok=true;
    for(int i=2;i<=n;i++){
        if(a[i]<=a[i-1]){
            ok=false;
            break;
        }
    }
    if(ok){
        cout<<0<<'\n';
        return ;
    }

    auto check=[&](ll mid)->bool{
        ll cnt=0;
        for(int i=2;i<=n;i++){
            if(a[i]>a[i-1])continue;
            ll diff=a[i-1]-a[i]+1;
            ll t=(diff+mid-1)/mid;
            cnt+=t;
            if(cnt>m)return false;
        }
        return true;
    };

    ll l=1,r=inf,ans=-1;
    while(l<=r){
        ll mid=l+r>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    cout<<ans<<'\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;

    cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}

D：春日影

等价图变换

题中规则如下：在无向图上，若丰川祥子沿同一条边 $u-v$ 连续走两次（ $u\to v$ 再 $v\to u$ ），则当她回到 $u$ 后的下一条移动（从 $u$ 出发的任意一条边）为免费（费用 $0$ ）。此免费机会可重复使用。

考虑节点 $u$ 的所有邻边权重，记

m_u = \min_{(u,x)\in E} w(u,x).

若某条最优路径在节点 $u$ 处触发一次“来回”并随后从 $u$ 走向某邻居 $v$ （且用到免费机会），那么触发往返的最优选择必然是使用权重最小的邻边（使得来回代价 $2\cdot m_u$ 最小）。因此，把这段操作等价为先支付 $2m_u$ （往返代价），然后再走一条原有的 $u\to v$ 边但该次移动视为“免费”——在等价图上直接把它表示为一条代价为 $2m_u$ 的边从 $u$ 到 $v$ 即可（与原来的 $u\to v$ 边并存， $Dijkstra$ 会选择较优的那条）。

因此可以做如下变换并求最短路：

计算每个节点 $u$ 的最短邻边权 $m_u$ 。
在原有无向边保持不变的基础上，对于每个节点 $u$ ，对它的每个原始邻居 $v$ 增加一条有向边 $u\to v$ ，边权为 $2\cdot m_u$ （表示“先在 $u$ 做最短邻边往返，再从 $u$ 出发到 $v$ 的等价代价”）。
在此新图上直接运行一次 $Dijkstra$ ，从 $1$ 到 $n$ 的距离即为答案。

代码展示

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 2e5 + 5, mod =1e9+7, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

vector<pair<ll,ll>>e[N],g[N],G[N];

il auto dijk(int n){
    struct Node{
        ll id,d;
        bool operator<(const Node&a)const{
            return d>a.d;
        }
    };
    priority_queue<Node>pq;
    vector<ll>dis(n+5,inf);
    vector<bool>vis(n+5);

    pq.push({1,dis[1]=0});

    while(!pq.empty()){
        auto [u,d]=pq.top();
        pq.pop();

        if(vis[u])continue;
        vis[u]=true;

        for(auto [v,w]:g[u]){
            if(dis[u]+w<dis[v]){
                pq.push({v,dis[v]=dis[u]+w});
            }
        }
    }
    return dis;
}

il void solve(){
    ll n,m;
    cin>>n>>m;
    while(m--){
        ll u,v,w;
        cin>>u>>v>>w;
        assert(w>=0&&w<=1e9);
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    for(int i=1;i<=n;i++){
        sort(e[i].begin(),e[i].end(),[&](auto &x,auto &y){
            return x.second<y.second;
        });
    }

    for(int u=1;u<=n;u++){
        if(e[u].empty())continue;
        ll w=e[u][0].second*2;
        for(auto [v,ww]:e[u]){
            G[u].push_back({v,w});
        }
    }
    for(int u=1;u<=n;u++){
        g[u]=e[u];
        for(auto [v,w]:G[u]){
            g[u].push_back({v,w});
        }
    }
    auto dis=dijk(n);
    cout<<(dis[n]==inf?-1:dis[n]);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;

    //cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}

E：轮符雨

观察

任意二进制字符串对应其段长的有序正整数序列，反之，定一组段长并指定首字符（0 或 1）即可唯一恢复字符串。因此问题等价于：计数所有有序正整数序列

L_1+\cdots+L_k=n,\quad L_i\ge1

使得

\sum_{i=1}^k\binom{L_i}{2}=T,

最后把结果乘以 $2$ （首字符为 $0$ 或 $1$ 的两种选择）。

动态规划设计

令 $\mathrm{dp}[i][j]$ 为“用若干段恰好凑出总长度 $i$ 且累计得分为 $j$ 的段长序列的数量”。初始状态 $\mathrm{dp}[0][0]=1.$

转移：从状态 $(i,j)$ 可以追加一个段长 $L$ ，其中 $1\le L\le n-i$ ，其对得分的贡献为

\Delta=\binom{L}{2}=\frac{L(L-1)}{2}.

因此转移为

\mathrm{dp}[i+L][j+\Delta]+=\mathrm{dp}[i][j].

最终答案为

\text{ans} = 2 \times \mathrm{dp}[n][T]\pmod{10^9+7}.

复杂度分析

设题中上界为 $T$ ，该方案的最差时间复杂度为

O\bigl(n\cdot T\cdot n\bigr)=O(n^2T),

代码展示

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 1e5 + 5, mod =1e9+7, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il void solve(){
    ll n,t;
    cin>>n>>t;

    vector<vector<ll>>dp(n+5,vector<ll>(t+5));
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=t&&j<=i*(i-1)/2;j++){
            if(!dp[i][j])continue;
            for(int l=1;i+l<=n;l++){
                ll val=j+l*(l-1)/2;
                if(val>t)break;
                dp[i+l][val]=(dp[i+l][val]+dp[i][j])%mod;
            }
        }
    }
    cout<<dp[n][t]*2%mod<<'\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;

    cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}

F：明弦音

$\mathrm{fa}[x]$ ：并查集父指针；

$\mathrm{w}[x]$ ： $a[x]-a[\mathrm{fa}[x]]$ (对父亲的“势能差”)，路径压缩后变为 $a[x]-a[\mathrm{root}]$ (即节点 $x$ 相对根节点 root 的势能差)。

1. 合并 $a[u]-a[v]=k$

查找 $u$ 的根 $\mathrm{fa}[u]$ ，计算 $d_u=\mathrm{w}[u]$ （此时 $d_u=a[u]-a[\mathrm{fa}[u]]$ ）；
查找 $v$ 的根 $\mathrm{fa}[v]$ ，计算 $d_v=\mathrm{w}[v]$ （此时 $d_v=a[v]-a[\mathrm{fa}[v]]$ ）；
若 $\mathrm{fa}[u]=\mathrm{fa}[v]$ ：检查 $d_u-d_v$ 是否等于 $k$ ，若不等则存在矛盾；
若 $\mathrm{ru}\ne\mathrm{rv}$ ：需满足 $a[\mathrm{fa}[u]]-a[\mathrm{fa}[v]] = k + d_v - d_u,$ 按大小合并：

方式 1：把 $\mathrm{fa}[u]$ 挂到 $\mathrm{fa}[v]$ 上，令 $\mathrm{w}[\mathrm{fa}[u]] = k + d_v - d_u$ ；
方式 2：把 $\mathrm{fa}[v]$ 挂到 $\mathrm{fa}[u]$ 上，令 $\mathrm{w}[\mathrm{fa}[v]] = -(k + d_v - d_u)$ 。

2. 绝对赋值 $a[u]=k$ 视作约束 $a[u]-a[0]=k$ ，定义固定节点 $0$ （满足 $a[0]=0$ ）；调用 $\mathrm{mer}(u,0,k)$ 即可实现该绝对赋值。

3. 差值查询 $a[u]-a[v]$

若 $u$ 和 $v$ 的根不同：结果未知（返回 UNKNOWN）；
若 $u$ 和 $v$ 同根：答案唯一，为 $\mathrm{w}[u]-\mathrm{w}[v]$ 。

三、正确性

任意点到根的 $\mathrm{w}$ 值即该点相对根节点的值差；
所有等式约束均转化为“根节点间相对常量”的要求；
同一连通块内任意两点的差值唯一确定；
不同连通块之间无约束关联，差值无法确定。

四、复杂度 并查集路径压缩 + 按大小合并：摊还时间复杂度 $O\bigl((n+q)\alpha(n)\bigr)$ 。

代码展示

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 5e5 + 5, mod =998244353, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

ll fa[N],w[N];

il int find(int x){
    if(fa[x]==x)return x;
    ll da=fa[x];
    ll next_x=find(da);
    w[x]+=w[da];
    return fa[x]=next_x;
}
il void me(ll x,ll y,ll k){
    int u=find(x),v=find(y);
    fa[u]=v;
    w[u]=w[y]+k-w[x];
}

il void solve(){
    int n,q;
    cin>>n>>q;
    for(int i=0;i<=n;i++){
        fa[i]=i;
        w[i]=0;
    }
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            ll u,v,k;
            cin>>u>>v>>k;

            if(find(u)!=find(v)){
                cout<<"OK\n";
                me(u,v,k);
            }else{
                if(w[u]-w[v]!=k){
                    cout<<"CONTRADICTION\n";
                }else{
                    cout<<"OK\n";
                }
            }

        }else if(op==2){
            ll u,k;
            cin>>u>>k;
            if(find(u)!=find(0)){
                me(u,0,k);
                cout<<"OK\n";
            }else{
                if(w[u]-w[0]!=k){
                    cout<<"CONTRADICTION\n";
                }else{
                    cout<<"OK\n";
                }
            }

        }else{
            ll u,v;
            cin>>u>>v;
            if(find(u)!=find(v)){
                cout<<"UNKNOWN\n";
            }else{
                cout<<w[u]-w[v]<<'\n';
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;

    cin >> t;
    
    while (t--) {

        solve();

    }

    return 0;
}

题解 | #Kato_Shoko#

有问题请评论区聊喵！！！

A：迷星叫

思路

代码展示

B：焚音打

观察

实现

代码展示

C：诗超绊

思路简述

代码展示

D：春日影

等价图变换

代码展示

E：轮符雨

观察

动态规划设计

复杂度分析

代码展示

F：明弦音

代码展示

最后有什么疑问可以在评论区指出来喵！！！