USTCPC2025题解汇总（部分）

hgckythgcfhk · 2025-04-05 19:01:28 · 算法·理论

A

这题主要的难度在于读题和对题意建模，对于题意一句话总结就是对三个奖牌线的上下界，比如金牌线，定义一个金牌线 a 合法当且仅当小于等于 a 的元素的个数为 g，其他线以此类推，先考虑不按上述偏序排序，直接对于整数的情况，上下界分别是对应排名的数和对应排名的下一个数加 1，于是我们需要对这题的元素定义加 1 操作，当罚时不为 0 时对一个元素加 1 等于罚时减 1，否则是多做一个题但罚时吃满，假设多做一题后做了 x 题，相当于在 300 分钟内每分钟都吃 30 发然后乘 20 分钟等于 180000 分钟，然后加上 299x，注意第 i 分钟表示时间轴上 [i,i+1) 的区间，且有效的分钟是第 0 到 299 所以一共是 300 分钟。

#include <bits/stdc++.h>
using namespace std;
const int MN = 4e5 + 7;
typedef pair<int, int> P;
int n, A, B, C, D;
P a[MN];
int calc(int x) {
    return 279 * x + 180000;
}
void pre(P a, P b) {
    if (b.second == 0) cout << b.first + 1 << " " << calc(b.first + 1) << endl;
    else cout << b.first << " " << b.second - 1 << endl;
}
bool cmp(P a, P b) {
    if (a.first != b.first) return a.first > b.first;
    return a.second < b.second;
}
int main() {
    cin >> A >> B >> C >> D, n = A + B + C + D;
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1, cmp);
    cout << a[A].first << " " << a[A].second << " ";
    pre(a[A], a[A + 1]);
    B = A + B;
    cout << a[B].first << " " << a[B].second << " ";
    pre(a[B], a[B + 1]);
    C = B + C;
    cout << a[C].first << " " << a[C].second << " ";
    pre(a[C], a[C + 1]);
}

B

对于每个 flag{ 找到下一个 } 随便找一组使得中间没有 { 直接模拟即可。

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
char a[N];
bool f=false;
int v=0,t=0;
int main(){
    cin>>a;
    int len=strlen(a);
    //cout<<len<<endl;
    for(int i=4;i<len;i++){
        if(a[i]=='{'){
            v=0;
            if(a[i-4]=='f' && a[i-3]=='l'&&a[i-2]=='a'&&a[i-1]=='g'){
                v=i-3;
            }
        }else if(a[i]=='}'){
            if(v){
                f=true;
                t=i;
                break;
            }
        }
    }
    if(!f){
        printf("NOT FOUND");
    }else{
        for(int i=v-1;i<=t;i++)cout<<a[i];
    }
    return 0;
}

C

显然赚到的钱是一个关于 p 的一次多项式，设第 a 天的钱为 k_a\cdot p+b_a，则有 k_a\cdot p+b_a=x，解得 p=\dfrac{x-b_a}{k_a} ，由于所有数都是整数，所以无解当且仅当这里不整除，这两个系数可以维护一个两个元素的结构体递推出来，事实上这就是斐波那契数列。

#include <bits/stdc++.h>
#define il inline
#define rg register
#define cit const rg unsigned
#define open ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)//,freopen("C.in","r",stdin),freopen("C.out","w",stdout)
#define int rg unsigned
#define void il void
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define vector basic_string
#define pq priority_queue
#define vint vector<unsigned>
#define vll vector<ll>
#define vull vector<ull>
#define ump unordered_map
#define ust unordered_set
#define deq deque
#define mkp make_pair
#define pii pair<unsigned,unsigned>
#define pll pair<ull,ull>
#define fi first
#define se second
#define Bool(a,n) bitset<n>a
#define sca(a) for(int $=0;$<n;cin>>a[++$])
#define cle(a) memset(a,0,sizeof a)
#define tmx(a) memset(a,0x3f,sizeof a)
#define tmn(a) memset(a,0xbf,sizeof a)
#define tif(a) memset(a,0xff,sizeof a)
//#define ge getchar_unlocked()
#define pu putchar_unlocked
#define lik(x) __builtin_expect((x),1)
#define ulk(x) __builtin_expect((x),0)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
//#define abs(a,b) (a>b?a-b:b-a)
#define fls cout<<endl;
#define PP pop_back()
#define PS push
#define BK back()
#define SZ size()
//inline ll max(const rg ll a,const rg ll b){return a>b?a:b;}
//inline ll min(const rg ll a,const rg ll b){return a<b?a:b;}
inline ll abs(const rg ll a,const rg ll b){return a>b?a-b:b-a;}
using namespace std;constexpr unsigned N=1<<17,M=4e3+2;//constexpr ll inf=1e9+7;
//unsigned p;
constexpr unsigned p=998244353;
//constexpr unsigned p=1e9+7;
//自动取模类
/**/
namespace mod{
    void add(int&a,cit b){a+=b,a>=p?a-=p:0;}
    void sub(int&a,cit b){add(a,p-b);}
    il unsigned mul(cit ll a,cit ll b){return a*b%p;}
    il unsigned pw(int ll a,int b){int ll s=1;for(;b;b>>=1,a=a*a%p)b&1?s=s*a%p:0;return s;}
    il unsigned inv(cit a){return pw(a,p-2);}
    void div(int&a,cit b){a=mul(a,inv(b));}
    il unsigned div(cit a,cit b){return mul(a,inv(b));}
}
using mod::add;
using mod::sub;
using mod::mul;
using mod::inv;
using mod::pw;
/**/
/**/
namespace IO{unsigned char b[1<<22],*l=b,*r=b;
    #define ge (ulk(l==r)?r=(l=b)+fread(b,1,1<<22,stdin):0,ulk(l==r)?'\0':*l++)
    il unsigned rd(){int char c=ge;int s=0;while(c<48||c>58)c=ge;while(lik(c<59&&c>47))s=s*10+(c&0b1111),c=ge;return s;}
    void rd(int&s){int char c=ge;s=0;while(c<48||c>58)c=ge;while(lik(c<59&&c>47))s=s*10+(c&0b1111),c=ge;}
}using IO::rd;
struct A{ull a,b;il A operator+(A c){c.a+=a,c.b+=b;return c;};il A(){a=0,b=0;}il A(cit ll x,cit ll y){a=x,b=y;}}_[22];
unsigned a,b;ull x;
void init(){cin>>a>>x>>b;

}void solve(){init();if(_[a].b>x){cout<<"-1\n";return;}
    x-=_[a].b;if(x%_[a].a){cout<<"-1\n";return;}
    x/=_[a].a;cout<<1ll*x*_[b].a+_[b].b<<'\n';
}signed main(){open;int t=1;cin>>t;_[1]=A(1,0),_[2]=A(1,1);
    for(int i=3;i<=20;++i)_[i]=_[i-1]+_[i-2];
    while(t--)solve();}

删除了引用的被注释掉的 hgckythgcfhk.h 的内容，保证这部分全是注释。

D

假设你是一个不会数学分析且不能查资料的线下选手。

首先你要知道最基本的定义，不一定要严谨，你可以认为在连续数学意义上积分是前缀和导数是差分，两者互为逆运算。同时你要知道在 \int 这个符号上加上两个数表示区间和，最后你可以认为 dx 没什么用。

根据前缀和和差分的线性，可以大胆的认为积分和导数满足线性，即 \int a\cdot f(x)=a\cdot \int f(x),\int f(x)+g(x)=\int f(x)+\int g(x)。由于这个符号确实会使整个公式看起来不太整齐，同时前面假设了你不熟悉积分，为了让符号比较好看，不妨换成不会数学分析的情况下比较熟悉的 \sum，需要注意这种表示并不严谨，但这篇题解建立在你并不熟悉这个符号的前提之上。

根据积分的线性，我们可以把多项式拆开单独处理每一项，同时可以把系数提出来，也就是说，我们只需要算 \sum \dfrac{x^n}{x^2+1}，事实上这个并不好处理，但注意到我们实际上只需要算 \sum_{x=0,x\in \R}^{1} \dfrac{x^n}{x^2+1}。考虑提出一个 x^2，设原式 =dp[n]，于是：

注意到积分和导数互为逆运算，所以我们直接构造函数 f(x)=\dfrac{x^{n-1}}{n-1}，这个不难构造，构造这个函数的理由是 f^\prime (x)=x^{n-2}。

现在我们可以递推整个 dp 数组，不过我们需要处理边界情况，现在我们不会算 dp[0] 和 dp[1]。

这里假设你不会数学分析，提供几种方法。

首先剩下的函数足够简单，可以直接贺自适应性普森积分的板子或者暴力打表，对于暴力，我们可以对于足够小的区间不假设成直线而是构造一个低次多项式求积分，这个根据上面构造的函数我们现在是会的，同时由于线下可以带纸质资料，且我知道 42 队的一个魔怔老哥带了一行李箱的纸质材料，所以贺自适应性普森积分板子是合法的。

不太暴力的做法的话我会推 dp[1]，前面提到过我们只需要求区间的积分，注意到 \ln x 求导后可以得到 \dfrac{1}{x} 可以考虑构造函数 f(x)=\ln(x^2+1)，于是 2dp[1]=\ln(2)-\ln(1)=\ln(2)。

目前我还不会不用真正的积分手段推 dp[0]，但不代表不行，以后我想出来会填坑。

其实样例解释里也可以直接推测出来 dp[0] 和 dp[1]，第二个样例可以直接得到 dp[0]，然后减一减就可以算出 dp[1]。

事实上你可以结合上述多种方法得到这两个常数，具体的结合方法太多了我就不举例了，事实证明，这题在不会数学分析且不能上网查资料的情况下是可做的，只需要熟练掌握积分的定义（大体意思上的定义，不需要严谨，严谨会适得其反）和求导的一些技巧。

#include<iostream>
#include<cmath>
using namespace std;
typedef double dt;
const dt pi=3.14159265358979323846;
const int N=1e5+10;
int n,a[N]={};
dt ans=0.0;
int main(){
    scanf("%d",&n);
    for(int i=0;i<=n;i++)scanf("%d",a+i);
    for(int i=n;i>=2;i--){
        a[i-2]-=a[i];
        ans+=1.0*a[i]/(i-1);
    }
    if(n>=1)ans+=log(2.0)*a[1]/2.0;
    ans+=1.0*pi*a[0]/4.0;
    printf("%.15f",ans);
    return 0;
}

事实上，我在写这篇题解后翻阅过普林斯顿的微积分读本，在其最后部分有解释过估算积分的算法，其中辛普森法则其实就是上面那说的把区间的函数图像看成二次函数的暴力，这可以理解为不自适应辛普森积分，哪怕是这种不自适应的，误差都能达到 \dfrac{1}{180}|M|(r-l)h^4，其中假设区间是等的，每段长为 h，|M| 是所求区间函数值的绝对值的最大值，而本题的值域只有 10^9，而且如果真的卡满则答案很大，而最后只需要相对误差够就行，为了造一组答案绝对值小于 1 且最大值很大的函数，其最大值一定会至少带一个很小的常数，而且我认为本题的性质决定了可能构造不出最大值 O(nV) 且答案 O(1) 的函数，往最理想的想一个不一定能造出来的函数图像，由于 f(0)=a[0]，也就是 O(V) 的，考虑到 [0,1] 区间的特殊性，函数不会爆增，最理想的是上升到 \dfrac{\sum_{i=0}^{n}|a[i]|}{4} 处下来到 -\dfrac{\sum_{i=0}^{n}|a[i]|}{4} 处，然后回到 0。这个常数至少是 \dfrac1 4 的，而且明显是连 \dfrac1 4 都远远达不到的，加上其实我看后面几个数据的答案都是 10^3 到 10^4 并且卡这个没意义，所以完全没必要把 h 开的很小，由于 n\le 10^5，所以这样的乱搞是能过的，即使不行，可以考虑对数据分治，越大越不好卡，可以越大 h 越小，或者直接把 h 开成一个根据 n 计算的函数，这一个东西的证明在普林斯顿的微积分读本上没证，说比较复杂，所以可以认为没必要学的。

E

注意到重心的最大的子树的 size 小于 \frac{n}{2}，这个性质使得把重心拆出来形成的多个子树划分成两个集合，每个集合的 size 的和不超过 \frac{2}{3}n。事实上这个东西可以卡满，考虑让重心当根然后分 3 个一样大的子树。

合并两个集合可以枚举一个集合里的所有带着根的答案去在另一个集合里二分。

大体做法就是这样，不需要详细解释，我重点说一些细节，事实上这个做法在理论上是题面说的暴力，而且貌似还有时间复杂度更优的做法，这个东西直接写是过不了的，现在说几个卡常的方法。

首先一定要保证 chk 的复杂度不要假掉，这里一定要只带一个 n，判断连通可以保留集合内所有边然后在当前判的集合里数多少边是在当前判的集合有多少条边，然后用 popcount 算点数，点数减边数就是连通块个数，连通块个数是 1 的时候合法，这样可以避开并查集的大常数。

然后经过我的测试，对 set 进行 lower_bound 的时间复杂度疑似是错的，就算是对的也是大常数，所以应该先放到 vector 里面进二分。

划分集合的过程未必要真正的去完美的划分，事实上我记得有这么一个题好像正解是随机化，大概就是说把 n 个数划分成两个集合使得两个集合和的差绝对值最小，大概就是直接贪心的把当前的数放到小的集合，然后随机打乱多做几次，可以认为这么做是对的。

具体的直接看程序吧，这次没有 42 队的赛时代码，是我自己写的，42 队做出了帮我卡常的贡献。

为防止因火车头导致无法过审，这里省略了缺省源，只放核心程序。

#define debug if(1.0*(clock()-t0)/CLOCKS_PER_SEC>=0.6)cout<<"-1",exit(0)
vint a[40];unsigned b[40],m,seed=time(0);unsigned t0=clock();
#define R() (seed^=(seed^=(seed<<11)>>13)<<17)
struct tree{set<unsigned>s,id;vint c;unsigned rt,n,f[40],res;unsigned mp[40],e[40][40],$[40][2],d;
    void ins(vint _){for(cit&i:_)id.emplace(i),++n;}
    void init(){int i=0;for(cit&j:id)mp[j]=++i;res=0;
        for(cit&u:id)for(cit&v:a[u]){cit x=mp[u],y=mp[v];debug;
        if(!y)continue;e[x][y]=e[y][x]=1;}d=0;
        for(i=1;i<=n;++i)for(int j=1;j<i;++j)if(e[i][j])++d,$[d][0]=i,$[d][1]=j;
        c+=(unsigned)0;for(cit&j:id)c+=b[j];}
    il unsigned fd(cit x){return f[x]==x?x:f[x]=fd(f[x]);}
    il unsigned calc(cit _){int sum=0;for(int i=1;i<=n;++i)if(_&(1<<i))sum+=c[i],sum>=m?sum-=m:0;return sum;}
    void chk(cit _){int cnt=0;
        for(int i=1;i<=d;++i)if((_&(1<<$[i][0]))&&(_&(1<<$[i][1])))++cnt;
        cnt=__builtin_popcount(_)-cnt;if(cnt>1)return;
        cit t=calc(_);res=max(res,t);if(_&(1<<rt))s.emplace(t);
    }void ans(){rt=mp[rt];for(int i=0;i<(1<<n);++i)chk(i<<1);}
}t1,t2;unsigned rt,dp[40],s[40],f[40];unsigned n;
void dfs(cit u){s[u]=1;for(cit&v:a[u])if(v^f[u])dfs(v),s[u]+=s[v],dp[u]=max(s[v],dp[u]);dp[u]=max(n-s[u],dp[u]);}
void gf(cit u){s[u]=1;for(cit&v:a[u])if(v^f[u])f[v]=u,gf(v),s[u]+=s[v];}
il vint val(cit u){vint _;_+=u;for(cit&v:a[u])_+=val(v);return _;}
void init(){rd(n),rd(m);int mn=40,s1=0,s2=0,b1=0,b2=0;
    for(int i=2;i<=n;++i)a[f[i]=rd()]+=i,a[i]+=f[i];dfs(1);
    for(int i=1;i<=n;++i)mn>dp[i]?mn=dp[i],rt=i:0,rd(b[i]);
    cle(f);gf(rt);for(int i=1;i<=n;++i)a[i]=vint();vint _,a1,a2;
    for(int i=1;i<=n;++i)a[f[i]]+=i;for(cit&v:a[rt])if(v)a[n+1]+=v;
    for(cit&v:a[rt])s1<s2?(s1+=s[v],a1+=v):(s2+=s[v],a2+=v);
    vint ans1=a1,ans2=a2;for(int i=1;i<=16;++i){
        a1=vint(),a2=vint(),b1=b2=0;
        for(int j=a[rt].SZ-1;j;--j)swap(a[rt][j],a[rt][R()%j]);
        for(cit&v:a[rt])b1<b2?(b1+=s[v],a1+=v):(b2+=s[v],a2+=v);
        if(max(s1,s2)>max(b1,b2))b1=s1,b2=s2,ans1=a1,ans2=a2;}
    for(cit&v:ans1)t1.ins(val(v));for(cit&v:ans2)t2.ins(val(v));
    _+=rt,t1.ins(_),t1.init(),_=vint(),_+=n+1,t2.ins(_),t2.init();
}void solve(){init();t1.rt=rt,t2.rt=n+1;t1.ans(),t2.ans();int ans=0;
    if(t1.s.SZ>t2.s.SZ)swap(t1.s,t2.s);vint tt;for(cit&x:t2.s)tt+=x;
    for(cit&x:t1.s){auto it=lower_bound(tt.begin(),tt.end(),m-x);if(it==tt.begin())continue;--it;ans=max(x+*it,ans);}
    cout<<max(ans,max(t1.res,t2.res));
}signed main(){open;int t=1;//cin>>t;
    while(t--)solve();}

F

这个问题的结构显然具有集合的单调性，所以先考虑判定一个 x 会使得哪些点的答案至少为 x，也就是要写一个 chk，这里其实已经可以推测大体做法就是整体二分或者不断扩大 x 并维护 x\to x+1 的变化，但先不讨论这个，先按部就班的刻画问题的结构。

A 在一个点 u 上能赢的充要条件是与 u 相连的能赢的节点个数大于 x，因为 B 一定会删能使 A 赢的边，否则一定不优，所以必要性是显然的，同时如果 B 删不完 A 一定会走到一个能赢的点，所以这个条件是充要的。

考虑刻画能赢的节点个数，可以容斥成度数减去不能赢的节点个数，而度数小于等于 x 的节点一定不可能赢，先把这些点标记下来删掉，然后剩下的点相当于已经减去了不能赢的节点个数，然后重复这个过程直到所有点都被删掉或者没有点能删得掉为止。

由于节点之间的影响不好处理，看起来不太整体二分，所以考虑维护 x\to x+1 的变化，前面提到过问题结构具有集合的单调性，所以初始化 x=0，可以考虑当没法继续删点的时候让 x\to x+1 继续做，然后相当于一个数据结构问题，单点减 1，全局 \min，删除全局 \min，数据结构中维护的是度数，由于度数不超过 n，所以可以开 n 的 vector，每个点只会被删一次和被换到度数更小的 vector 不超过度数次，所以时间复杂度是 O(n+m) 的，当然这个可以用线段树维护，而且事实上我现在贺的赛时代码确实是线段树写的。

#include<iostream>
#include<vector>
#define lo (o<<1)
#define ro (lo|1)
#define mr(x,y) make_pair(x,y)
using namespace std;
const int N=1e6+10,inf=1e7;
typedef pair<int,int>pi;
int n,m,a[N],nw=0,ans[N];
struct Tree{
    pi b[N<<2];
    void build(int o=1,int l=1,int r=n){
        if(l==r){
            b[o]=mr(a[l],l);
            return;
        }
        int mid=(l+r)>>1;
        build(lo,l,mid);
        build(ro,mid+1,r);
        b[o]=min(b[lo],b[ro]);
    }
    void update(int qx,int tf,int o=1,int l=1,int r=n){
        if(l==r){
            if(tf==0)b[o].first=b[o].first-1;
            else b[o].first=inf;
            return;
        }
        int mid=(l+r)>>1;
        if(qx<=mid)update(qx,tf,lo,l,mid);
        else update(qx,tf,ro,mid+1,r);
        b[o]=min(b[lo],b[ro]);
    }
}T;
vector<int>bc[N];
int main(){
    scanf("%d%d",&n,&m);
    //for(int i=1;i<=n;i++)ans[i]=-1;
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        bc[u].push_back(v);
        bc[v].push_back(u);
        a[u]++,a[v]++;
    }
    T.build();
    for(int i=1;i<=n;i++){

        nw=max(T.b[1].first,nw);
        int u=T.b[1].second;
        ans[u]=nw;
        T.update(u,1);
        int sz=bc[u].size();
        for(int j=0;j<sz;j++){
            int v=bc[u][j];
            //cout<<v;
            T.update(v,0);
        }
    }
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    return 0;
}

G

H

注意到最小值，所以显然直接走现成的边是比较优的，如果这条边大于 0，则答案一定是 0，否则考虑周围是否有全大于 0 的环，有则答案是 0，否则答案是 1，所以如果输入的时候有大于 1 的边一定无解。

因为边权只有两种，所以可以分开考虑，先把 f(u,v)=0 的边加上，这种边最好的处理方式是全放 1，因为我们要兼顾剩下的边，所以真的全放 1 是不太优的，但考虑到把某条边设为 0 后一定有另一条全 1 的路径，对于别的边，如果真的要走这两个点之间的路径完全可以绕路不直接走这两个点之间的边，所以这条边设为 0 是没用的。

于是可以发现每条边的权值其实是确定的，只需要最后判这样赋权是否合法就行。

同时根据上对 1 的连通块的处理，我们先加入 1 边后的连通块两两的 f 等于 0，所以，同一个连通块内出现 f(u,v)=1 的边是不合法的，而对于跨连通块的情况由于现在只需要加入 0 的边，所以无论怎么连都是不影响的。

其实看到上面 f 是 0 的条件就可以观察出来 1 相当于是有边 0 相当于是没边，因为上面的描述提示了我们要尽量不走 0 的边。

#include<iostream>
using namespace std;
const int N=2e5+10;
typedef long long ll;
int n,m,pa[N],a[N];
bool ans=false;
struct bc{
    int u,v;
    ll w;
}b[N];
int fd(int x){
    if(pa[x]==x)return x;
    else return pa[x]=fd(pa[x]);
}
void adp(int x,int y){
    int xf=fd(x),yf=fd(y);
    if(xf!=yf)pa[yf]=xf;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)pa[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d%lld",&b[i].u,&b[i].v,&b[i].w);
        if(b[i].u==b[i].v && b[i].w!=0)ans=true;
        else if(b[i].w==0)adp(b[i].u,b[i].v);
        else if(b[i].w>1)ans=true;
    }
    if(ans){
        printf("No");
        return 0;
    }
    for(int i=1;i<=m;i++){
        if(b[i].w==0){
            a[i]=1;
        }else if(b[i].w==1){
            a[i]=0;
            if(fd(b[i].u)==fd(b[i].v))ans=true;
        }
    }
    if(ans){
        printf("No");
    }else{
        printf("Yes\n");
        for(int i=1;i<=m;i++)printf("%d ",a[i]);
    }
    return 0;
}

I

由于路径可以不是简单路径，所以为了使得 \operatorname{mex} 最大一定会走完整个连通块的每一条边，这样一定不劣，所以两个点的 f 等价于这两个点所在连通快的 \operatorname{mex}，只需要构造一个连通块有 0 到 f(u,v)-1 就行，然后如果连通块边数不够或者里面的边的 f 不相等则无解。

#include <bits/stdc++.h>
#define il inline
#define rg register
#define cit const rg unsigned
#define open ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)//,freopen("I.in","r",stdin),freopen("I.out","w",stdout)
#define int rg unsigned
#define void il void
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define vector basic_string
#define pq priority_queue
#define vint vector<unsigned>
#define vll vector<ll>
#define vull vector<ull>
#define ump unordered_map
#define ust unordered_set
#define deq deque
#define mkp make_pair
#define pii pair<unsigned,unsigned>
#define pll pair<ull,ull>
#define fi first
#define se second
#define Bool(a,n) bitset<n>a
#define sca(a) for(int $=0;$<n;cin>>a[++$])
#define cle(a) memset(a,0,sizeof a)
#define tmx(a) memset(a,0x3f,sizeof a)
#define tmn(a) memset(a,0xbf,sizeof a)
#define tif(a) memset(a,0xff,sizeof a)
//#define ge getchar_unlocked()
#define pu putchar_unlocked
#define lik(x) __builtin_expect((x),1)
#define ulk(x) __builtin_expect((x),0)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
//#define abs(a,b) (a>b?a-b:b-a)
#define fls cout<<endl;
#define PP pop_back()
#define PS push
#define BK back()
#define SZ size()
//inline ll max(const rg ll a,const rg ll b){return a>b?a:b;}
//inline ll min(const rg ll a,const rg ll b){return a<b?a:b;}
inline ll abs(const rg ll a,const rg ll b){return a>b?a-b:b-a;}
using namespace std;constexpr unsigned N=1e6+1,M=4e3+2;//constexpr ll inf=1e9+7;
//unsigned p;
constexpr unsigned p=998244353;
//constexpr unsigned p=1e9+7;
//自动取模类
/**/
namespace mod{
    void add(int&a,cit b){a+=b,a>=p?a-=p:0;}
    void sub(int&a,cit b){add(a,p-b);}
    il unsigned mul(cit ll a,cit ll b){return a*b%p;}
    il unsigned pw(int ll a,int b){int ll s=1;for(;b;b>>=1,a=a*a%p)b&1?s=s*a%p:0;return s;}
    il unsigned inv(cit a){return pw(a,p-2);}
    void div(int&a,cit b){a=mul(a,inv(b));}
    il unsigned div(cit a,cit b){return mul(a,inv(b));}
}
using mod::add;
using mod::sub;
using mod::mul;
using mod::inv;
using mod::pw;
/**/
namespace IO{unsigned char b[1<<22],*l=b,*r=b;
    #define ge (ulk(l==r)?r=(l=b)+fread(b,1,1<<22,stdin):0,ulk(l==r)?'\0':*l++)
    il unsigned rd(){int char c=ge;int s=0;while(c<48||c>58)c=ge;while(lik(c<59&&c>47))s=s*10+(c&0b1111),c=ge;return s;}
    void rd(int&s){int char c=ge;s=0;while(c<48||c>58)c=ge;while(lik(c<59&&c>47))s=s*10+(c&0b1111),c=ge;}
}using IO::rd;
unsigned n,m;struct A{unsigned u,v,w;}e[N];vint a[N];
unsigned b[N],ans[N];vint c[N];
void dfs(cit u,cit rt){b[u]=rt;for(cit&v:a[u])if(!b[v])dfs(v,rt);}
void init(){rd(n),rd(m);
    for(int i=1;i<=m;++i)rd(e[i].u),rd(e[i].v),rd(e[i].w),a[e[i].u]+=e[i].v,a[e[i].v]+=e[i].u;
    for(int i=1;i<=n;++i)if(!b[i])dfs(i,i);
    for(int i=1;i<=m;++i)c[b[e[i].u]]+=i;

}void solve(){init();
    for(int i=1;i<=n;++i)if(c[i].SZ){int id=0;
        for(cit&j:c[i])if(!id)id=e[j].w;
        else if(id^e[j].w){cout<<"No\n";return;}
        if(id>c[i].SZ){cout<<"No\n";return;}
        for(int j=0;j<id;++j)ans[c[i][j]]=j;
        for(int j=id;j<c[i].SZ;++j)ans[c[i][j]]=p;
    }cout<<"Yes\n";for(int i=1;i<=m;++i)cout<<ans[i]<<' ';
}signed main(){open;int t=1;//cin>>t;
    while(t--)solve();}

删除了引用的被注释掉的 hgckythgcfhk.h 的内容，保证这部分全是注释。

J

设 dis(G,u,v) 表示在图 G 上 u 到 v 的最短路，设 A 表示原图，B=\{(u,v)\in A |(u,v,dis(A,u,v))\}。

也就是说 B 是 A 的边然后把边权改成最短路后形成的新图。\forall(u,v)\in A,dis(A,u,v)\le dis(B,u,v)，感性理解一下，B 里的所有边都是 A 的边组合而来的。

先算出所有 dis(B,x,y)，如果有 dis(B,x,y)<dia(A,x,y)=f(x,y) 则一定无解。

根据上述结论，在 B 中一定直接走两个点的边，这样肯定是合法的，也就是是说，先判一下最短路对不对然后直接用输入的东西建边就行。

#include<iostream>
using namespace std;
typedef long long ll;
const int N=510,M=2e5+10;
const ll inf=1e12;
int n,m;
ll a[M],g[N][N];
bool ans=false;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)g[i][j]=0;
            else g[i][j]=inf;
        }
    }
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d%lld",&u,&v,a+i);
        if(g[u][v]!=inf){
            if(g[u][v]!=a[i])ans=true;
        }
        g[u][v]=g[v][u]=a[i];
    }
    for(int k=1;k<=n;k++){
        if(ans)break;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(g[i][j]==inf)continue;
                if(g[i][k]+g[k][j]<g[i][j]){
                    ans=true;
                    break;
                }
            }
            if(ans)break;
        }
        if(ans)break;
    }
    if(ans){
        printf("No");
    }else{
        printf("Yes\n");
        for(int i=1;i<=m;i++)printf("%lld ",a[i]);
    }
    return 0;
}

K

L

非常好的打表题，先考虑 n=\dfrac{m^2+m}{2} 的做法。

首先要先重新审视打表这件事情，打表并不一定是真的打一个“表”，也不一定是要直接把答案打出来输出，事实上更重要的是观察最优解的组合结构，做打表题是在 LCA 长训营传出来的一个训练方法，所以我认为打表并不可耻。

观察 m=6 的解：

1 5 3 4 2 6 
1 6 2 4 3 5 
2 4 3 5 1 6 
2 6 1 5 3 4 
3 4 2 6 1 5 
3 5 1 6 2 4 
4 2 6 1 5 3 
4 3 5 1 6 2 
5 1 6 2 4 3 
5 3 4 2 6 1 
6 1 5 3 4 2 
6 2 4 3 5 1