2454 字
12 分钟
Codeforces板刷记录（1800~2000， 构造题）
2024-09-27
ACM
Codeforces
ProblemRating
1981C - Turtle and an Incomplete Sequence1800思路很简单，想到了。但是有点模拟了，代码能力还是不够，写了80min.
1994D - Funny Game1900没有想到。
1956D - Nene and the Mex Operator2000看了一点提示想到了。实现起来也花了挺久。
1951D - Buying Jewels2000完全想歪了，不会。构造确实妙。
D - Koxia and Game2000思路很简单，想到了。实现起来有点难受，代码能力还是不够。
C - Another Array 问题2000这个构造我确实想不到。
1991D - Prime XOR Coloring1900想到了但没完全想到。
D - Birthday Gift1900我是纯baka了，一开始没想到，后面写出来了也调了好久。
1895D - XOR Construction1900这题写的很顺，思路也很顺，30min内写完，但是用不是正解的写法。
D - Tenzing and His Animal Friends1900想不到从最短路入手，思维还是不够。

1981C - Turtle and an Incomplete Sequence#

#include <bits/stdc++.h>
using namespace std;


#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif


typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,ll> P;
const int maxn=2e5;


int n;
ll a[maxn+5];
ll b[maxn+5];


vector<ll> tmp;
int need(ll x,ll y){
    ll xx=x,yy=y;
    // debug(x,y);
    if (x<y)
        swap(x,y);
    vector<bool> X,Y;
    while (x)
        X.push_back(x&1),x>>=1;
    while (y)
        Y.push_back(y&1),y>>=1;
    reverse(X.begin(),X.end());
    reverse(Y.begin(),Y.end());
    int i,j;
    for (i=0,j=0;i<X.size()&&j<Y.size();i++,j++){
        if (X[i]!=Y[j])
            break;
    }
    int ret=Y.size()-j+(X.size()-j);
    tmp.clear();
    xx=min(xx,yy);
    tmp.push_back(xx);
    // debug(Y.size()-j+(X.size()-j),i,j);
    int l=Y.size()-j;
    // debug(l,xx);
    while (l){
        xx>>=1;
        debug(xx);
        tmp.push_back(xx),l--;
    }
    for (;j<X.size();j++){
        xx<<=1;
        xx|=X[j];
        tmp.push_back(xx);
    }
    return ret;
}


void solve(void){
  cin>>n;
    vector<P> vec;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        if (a[i]!=-1){
            vec.push_back(P{i,a[i]});
            b[i]=a[i];
        }
    }
    int m=vec.size();
    if (m==0){
        bool vis=false;
        for (int i=1;i<=n;i++,vis^=1)
            cout<<(vis?1:2)<<' ';
        cout<<endl;
        return ;
    }
    for (int i=0;i+1<m;i++){
        debug(i);
        if (vec[i].first+1==vec[i+1].first){
            if (!(vec[i].second==(vec[i+1].second/2)||vec[i+1].second==(vec[i].second/2))){
                cout<<-1<<endl;
                return ;
            }
            continue;
        }
        int delta=need(vec[i].second,vec[i+1].second);
        // debug(delta);
        // debug(delta>(vec[i+1].first-vec[i].first),((vec[i+1].first-vec[i].first-delta)&1));
        if (delta>(vec[i+1].first-vec[i].first)||((vec[i+1].first-vec[i].first-delta)&1)){
            cout<<-1<<endl;
            return ;
        }
        int j=vec[i].first+1;
        if (tmp.front()!=vec[i].second)
            reverse(tmp.begin(),tmp.end());
        tmp.pop_back();
        int k=1;
        while (k<tmp.size()){
            b[j]=tmp[k];
            k++;
            j++;
        }
        bool vis=true;
        while (j<vec[i+1].first){
            if (vis)
                b[j]=b[j-1]<<1;
            else
                b[j]=b[j-1]>>1;
            vis^=1;
            j++;
        }
    }
    bool vis=(vec.front().second>=2)?true:false;
    for (int i=vec.front().first-1;i;i--){
        if (vis)
            b[i]=b[i+1]>>1;
        else
            b[i]=b[i+1]<<1;
        vis^=1;
    }
    vis=(vec.back().second>=2)?true:false;
    for (int i=vec.back().first+1;i<=n;i++){
        if (vis)
            b[i]=b[i-1]>>1;
        else
            b[i]=b[i-1]<<1;
        vis^=1;
    }
    for (int i=1;i<=n;i++)
        cout<<b[i]<<' ';
  cout<<endl;
}


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int t=1;
  cin>>t;
  while (t--){
        debug(t);
        solve();
    }
//    cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}

1994D - Funny Game#

做过类似的，但是这次还是没想到。妙就妙在看见把一个不断增加的 xx 看作模数时，要想起鸽笼原理。所以这个是必定有解的，有点诈骗了。

#include <bits/stdc++.h>
using namespace std;


//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif


typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=2000;


int n;
int a[maxn+5];


struct DSU {
    vector<int> fa;
    DSU(int n): fa(n){  // 创建n个集合，编号从0开始
        iota(fa.begin(),fa.end(),0);
    }
    int find(int x){
        return (x==fa[x])?x:(fa[x]=find(fa[x]));
    }
    void merge(int x,int y) {
        fa[find(x)]=find(y);
    }
};


void solve(void){
  cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    DSU dsu(n+1);
    stack<P> ans;
    for (int m=n-1;m;m--){
        map<int,P> mp;  // mod, P(set,u)
        for (int u=1;u<=n;u++){
            int x=a[u]%m;
            if (mp.find(x)!=mp.end()){
                if (mp.find(x)->second.first!=dsu.find(u)){
                    ans.push(P{u,mp.find(x)->second.second});
                    dsu.merge(dsu.find(u),mp.find(x)->second.second);
                    break;
                }
            }
            else
                mp[x]=P{dsu.find(u),u};
        }
    }
    cout<<"YES"<<endl;
    while (ans.empty()==false){
        cout<<ans.top().first<<' '<<ans.top().second<<endl;
        ans.pop();
    }
}


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int t=1;
  cin>>t;
  while (t--)
    solve();
//    cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}

1956D - Nene and the Mex Operator#

如果一个区间 [l,r][l,r] 内没有0，那操作后肯定会创造出一个0。这时候如果0旁边没有11，继续操作肯定也会创造出 11。

那很显然，长度为 nn 的数组，最后得到的答案一定满足

ans≥n2ans\geq n^2

也就是说我们有机会构造出全部都是 nn 的序列。

如果一个数 ai>na_i> n。它只要处于任何一个操作区间内，是一定会被降低的。那很容易想到，考虑到 nn 的规模很小，每个数只有两种情况（允许处于操作区间内，不允许处于操作区间内）。那就枚举每种情况，1表示不允许处于操作区间内，0表示允许处于操作区间内。

假设情况是1001001000，那就对允许的三个长度分别为2、2、3的区间，计算每个区间内经过操作能达到的最大和是多少。计算可以用区间dp。

设 dp[l][r]dp[l][r] 表示区间 [l,r][l,r] 内能达到的最大和

dp[l][r]=max⁡k∈[l,r]{dp[l][k]+(r−k)2}dp[l][r]=\max_{k\in [l,r]} \{dp[l][k]+(r-k)^2\}

时间复杂度能过。

#include <bits/stdc++.h>
using namespace std;


#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif


typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=18;


int n;
int a[maxn+5];
int pre[maxn+5];
#define sum(l,r) (pre[r]-pre[(l)-1])


int dp[maxn+5][maxn+5];
int from[maxn+5][maxn+5];


stack<P> stk;
void dfs(int l,int r){
    debug(l,r,from[l][r]);
    int k=from[l][r];
    if (k==0)
        return ;
    if (k==r)
        k=l-1;
    stk.push(P{k+1,r});
    if (k!=l-1)
        dfs(l,k);
}


vector<P> vec;


/* 把[l,r]变成[0,r-l] */
void dfs2(int l,int r){
    if (l>r)
        return ;
    if (a[r]!=r-l){
        dfs2(l,r-1);
        vec.push_back(P{l,r});
        for (int i=l;i<=r;i++)
            a[i]=r-l;
    }
    dfs2(l,r-1);
}


void solve(void){
  cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }
    memset(from,0,sizeof(from));
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j++){
            dp[i][j]=sum(i,j);
            if ((j-i+1)*(j-i+1)>dp[i][j]){
                dp[i][j]=(j-i+1)*(j-i+1);
                from[i][j]=j;
            }
        }
    for (int len=2;len<=n;len++)
        for (int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            for (int k=l;k<r;k++)
                if (dp[l][r]<dp[l][k]+(r-k)*(r-k)){
                    dp[l][r]=dp[l][k]+(r-k)*(r-k);
                    from[l][r]=k;
                }
        }
    int lim=(1<<n)-1;
    P ans={-1,0};  // value, mask
    for (int mask=0;mask<=lim;mask++){
        int l=0;
        int now=0;
        for (int i=1;i<=n;i++)
            if (mask&(1<<(i-1))){
                if (i-l-1>0)
                    now+=dp[l+1][i-1];
                l=i;
                now+=a[i];
            }
        if (n-l>0)
            now+=dp[l+1][n];
        if (now>ans.first)
            ans=P{now,mask};
    }
    cout<<ans.first<<' ';
    int mask=ans.second;
    int l=0;
    for (int i=1;i<=n;i++)
        if (mask&(1<<(i-1))){
            if (i-l-1>0)
                dfs(l+1,i-1);
            l=i;
        }
    if (n-l>0)
        dfs(l+1,n);
    vec.clear();
    while (!stk.empty()){
        int l=stk.top().first,r=stk.top().second;
        stk.pop();
        dfs2(l,r);
        for (int i=l;i<=r;i++)
            a[i]=r-l;
        vec.push_back(P{l,r});
    }
    cout<<vec.size()<<endl;
    for (P p: vec)
        cout<<p.first<<' '<<p.second<<endl;
}


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int t=1;
//  cin>>t;
  while (t--)
    solve();
//    cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}

1951D - Buying Jewels#

#include <bits/stdc++.h>
using namespace std;


//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif


typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;


ll n,k;


void solve(void){
  cin>>n>>k;
    if (n<k)
        cout<<"NO"<<endl;
    else if (n==k)
        cout<<"YES\n1\n1\n"<<endl;
    else{
        ll t=1;
        if ((t+1)*((n-k+t)/t)>n){
            cout<<"YES\n2"<<endl;
            cout<<((n-k+t)/t)<<' '<<1<<endl;
        }
        else
            cout<<"NO"<<endl;
    }
}


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int t=1;
  cin>>t;
  while (t--)
    solve();
//    cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}

D - Koxia and Game#

#include <bits/stdc++.h>
using namespace std;


#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif


typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const ll mod=998244353;
const int maxn=1e5;


int n;
int a[maxn+5],b[maxn+5];


int self_cir,cir;


struct Edge{
    int u,v;
    bool vis;
} edge[maxn+5];
#define next(from,eptr) ((eptr->u==eptr->v)?(eptr->u):((eptr->u)^(eptr->v)^(from)))
vector<Edge*> G[maxn+5];


int flag[maxn+5];
bool dfs(int u,const int tag){
    flag[u]=tag;
    debug(u,tag);
    bool ret=false;
    for (Edge* e: G[u]){
        if (e->vis==false){
            int v=next(u,e);
            if (flag[v]==tag)
                cir++;
            e->vis=true;
            if (flag[v])
                ret=true;
            ret|=dfs(v,tag);
        }
    }
    return ret;
}


void expand(int u){
    flag[u]=u;
    for (Edge* e: G[u]){
        if (e->vis==false){
            int v=next(u,e);
            e->vis=true;
            expand(v);
        }
    }
}


void prepare(){
    self_cir=0,cir=0;
    for (int i=1;i<=n;i++)
        G[i].clear();
    memset(flag,0,sizeof(flag));
}


ll qpow(ll a,ll b,ll mod){
    a%=mod;
    ll res=1;
    while (b>0) {
        if (b&1)
            res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}


void solve(void){
  cin>>n;
    prepare();
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=1;i<=n;i++)
        cin>>b[i];
    for (int i=1;i<=n;i++){
        if (a[i]==b[i])
            self_cir++;
        edge[i]=Edge{a[i],b[i],false};
        G[a[i]].push_back(&edge[i]);
        G[b[i]].push_back(&edge[i]);
    }
    for (int i=1;i<=n;i++){
        debug(G[i].size());
        if (G[i].size()==0){
            cout<<0<<endl;
            debug("1");
            return ;
        }
        else if (G[i].size()==1&&flag[i]==0){
            flag[i]=i;
            if (dfs(i,i)==0){
                cout<<0<<endl;
                debug(i);
                return ;
            }
        }
    }
    for (int i=1;i<=n;i++)
        if (flag[i]==false)
            expand(i),cir++;
    debug_array(flag,6);
    debug(self_cir,cir);
    cout<<(qpow(2LL,(ll)(cir-self_cir),mod)*qpow((ll)n,self_cir,mod))%mod<<endl;
}


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int t=1;
  cin>>t;
  while (t--)
    solve();
//    cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}

C - Another Array#

#include <bits/stdc++.h>
using namespace std;


//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif


typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=2e5;


int n;
ll a[maxn+5];


void solve(void){
  cin>>n;
    ll maxx=LONG_LONG_MIN;
    int pos;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        if (maxx<a[i])
            maxx=a[i],pos=i;
    }
    ll ans=0;
    if (n==1)
        ans=a[1];
    else if (n==2)
        ans=max(a[1]+a[2],abs(a[2]-a[1])*2LL);
    else if (n==3){
        if (a[1]==maxx||a[3]==maxx)
            ans=maxx*(ll)n;
        else{
            ans=max(max(a[3]+(a[2]-a[1])*2,3*(a[2]-a[1])),max(a[1]+(a[2]-a[3])*2,3*(a[2]-a[3]))),ans=max(a[1]+a[2]+a[3],ans);
            ans=max(ans,max(a[1]*3,a[3]*3));
        }
    }
    else
        ans=(ll)n*maxx;
    cout<<ans<<endl;
}


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int t=1;
  cin>>t;
  while (t--)
    solve();
//    cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}

1991D - Prime XOR Coloring#

#include <bits/stdc++.h>
using namespace std;


//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif


typedef unsigned long long ull;
typedef long long ll;
const int maxn=2e5;


int n;


int start[]={0,1,2,2,3,3,4};


void solve(void){
  cin>>n;
    if (n<=6){
        cout<<start[n]<<endl;
        for (int i=1;i<=n;i++)
            cout<<start[i]<<' ';
    }
    else{
        cout<<4<<endl;
        for (int i=1;i<=n;i++)
            cout<<((i%4)?(i%4):4)<<' ';
    }
    cout<<endl;
}


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int t=1;
  cin>>t;
  while (t--)
    solve();
//    cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}

D - Birthday Gift#

要求分最大的k，使得结果小于等于 xx。其实就是在分段时，尽可能让结果小，最后判断能否小于 xx。我一开始只想着分段最大还要小于 xx，其实可以换个角度想。

要让结果尽可能小，从高位到低位，肯定是尽可能先为0，做不到再1。要求是0，必须每个分段中该位的1的个数都是偶数。显然如果该位 a1a_1~ana_n 的1个数是奇数，这就是不可能做到的。只有偶数才可能做到。所以：

对于每一位，如果a1∼ana_1\sim a_n的1个数是偶数，那它不同划分方式是可以为0，也可以为1.

对于每一位，如果a1∼ana_1\sim a_n的1个数是奇数，那它无论怎么划分，最终都是奇数，结果是1.

所以我们遍历 xx 的从高到低每一位，

如果是1，且该位a1∼ana_1\sim a_n为奇数个1，我们就不用管。

如果是1，且该位a1∼ana_1\sim a_n为偶数个1，我们进行最大划分，然后结束，直接输出结果。

如果是0，且该位a1∼ana_1\sim a_n为奇数个1，输出-1。

如果是0，且该位a1∼ana_1\sim a_n为偶数个1，就结合前面的位继续尝试划分。

#include <bits/stdc++.h>
using namespace std;


#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif


typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e5;
const int maxb=30;


int n,x;
int a[maxn+5];


bool isji[maxb+5][maxn+5];


#define getbit(x,k) (((x)>>(k))&1)


void solve(void){
  cin>>n>>x;
    x++;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int k=30;k>=0;k--){
        for (int i=1;i<=n;i++)
            if (getbit(a[i],k))
                isji[k][i]=isji[k][i-1]?0:1;
            else
                isji[k][i]=isji[k][i-1];
    }
    vector<int> incon;
    int ret=-1;
    for (int k=30;k>=0;k--){
        debug(k,getbit(x,k),isji[k][n]);
        if (getbit(x,k)==0&&isji[k][n])
            break;
        if (getbit(x,k)==1&&isji[k][n]==1)
            continue;
        incon.push_back(k);
        if (getbit(x,k)==0&&isji[k][n]==0&&k)
            continue;
        if (k==0&&getbit(x,k)==0&&isji[k][n]==0)
            break;
        debug_array(incon,incon.size());
        debug(k);
        vector<int> ans;
        for (int i=1;i<=n;i++){
            bool ok=true;
            for (int t: incon)
                if (isji[t][i]){
                    ok=false;
                    break;
                }
            debug(i,ok);
            if (ok)
                ans.push_back(i);
        }
        if (getbit(x,k)==1&&isji[k][n]==0)
            incon.pop_back();
        ret=max(ret,(int)ans.size());
    }
  cout<<ret<<endl;
}


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int t=1;
  cin>>t;
  while (t--)
    solve();
//    cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}

1895D - XOR Construction#

和前面一道很像。也是按位处理。

#include <bits/stdc++.h>
using namespace std;


//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif


typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=4e5;
const int maxb=18;


int n;
int a[maxn+5],b[maxn+5];


int target[maxb+5];
int cnt[maxb+5];
#define getbit(x,k) (((x)>>(k))&1)


int ans[maxb+5];
int val;
vector<int> pos;


int flag[maxn+5];
int tag;


bool dfs(int u){
    if (u>=pos.size()){
        val=0;
        for (int k=maxb;k>=0;k--)
            if (ans[k])
                val|=(1<<k);
        tag++;
        for (int i=1;i<=n;i++)
            if (flag[val^b[i]]==tag)
                return false;
            else
                flag[val^b[i]]=tag;
        return true;
    }
    ans[pos[u]]=0;
    if (dfs(u+1))
        return true;
    ans[pos[u]]=1;
    if (dfs(u+1))
        return true;
    return false;
}


void solve(void){
  cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=b[i-1]^a[i-1];
    }
    for (int i=0;i<n;i++)
        for (int b=maxb;b>=0;b--)
            if (getbit(i,b))
                target[b]++;
    for (int i=1;i<=n;i++)
        for (int k=maxb;k>=0;k--)
            if (getbit(b[i],k))
                cnt[k]++;
    pos.clear();
    for (int k=maxb;k>=0;k--)
        if (target[k]){
            if (cnt[k]*2!=n){
                if (cnt[k]==target[k])
                    ans[k]=0;
                else
                    ans[k]=1;
            }
            else
                pos.push_back(k);
        }
  dfs(0);
    for (int i=1;i<=n;i++)
        cout<<(val^b[i])<<' ';
    cout<<endl;
}


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int t=1;
//  cin>>t;
  while (t--)
    solve();
//    cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}

D - Tenzing and His Animal Friends#

#include <bits/stdc++.h>
using namespace std;


//#undef LOCAL_DEBUG
#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define debug(...) (void)0
#define debug_array(arr, len) (void)0
#define debug_container(container) (void)0
#endif


typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll,int> P;
const int maxn=100;


int n,m;
vector<P> G[maxn+5];


ll d[maxn+5];
void dijkstra(int s){
    for (int i=1;i<=n;i++)
        d[i]=LONG_LONG_MAX;
    priority_queue<P,vector<P>,greater<P>> que;
    que.push(P{0,s});
    d[s]=0;
    while (!que.empty()){
        P p=que.top();
        int u=p.second;
        ll dis=p.first;
        que.pop();
        if (d[u]<dis)
            continue;
        for (P e: G[u]){
            int v=e.second;
            ll w=e.first;
            if (d[v]>d[u]+w){
                d[v]=d[u]+w;
                que.push(P{d[v],v});
            }
        }
    }
}


void solve(void){
  cin>>n>>m;
  for (int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        G[u].push_back(P{w,v});
        G[v].push_back(P{w,u});
    }
    dijkstra(1);
    if (d[n]==LONG_LONG_MAX){
        cout<<"inf"<<endl;
        return ;
    }
    vector<P> dis(n);
    for (int i=1;i<=n;i++)
        dis[i-1]=P{d[i],i};
    sort(dis.begin(),dis.end());
    vector<P> ans;
    ll tot=0;
    for (int i=0;i<dis.size();i++){
        P p=dis[i];
        int u=p.second;
        if (ans.empty()==false){
            ans.back().first=p.first-dis[i-1].first;
            tot+=ans.back().first;
        }
        if (u==n)
            break;
        ans.push_back(P{0,u});
    }
    cout<<tot<<' '<<ans.size()<<endl;
    string str(n,'0');
    for (P p: ans){
        str[p.second-1]='1';
        cout<<str<<' '<<p.first<<endl;
    }


}


int main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int t=1;
//  cin>>t;
  while (t--)
    solve();
//    cout<<(solve()?"YES":"NO")<<endl;
  return 0;
}
Codeforces板刷记录（1800~2000， 构造题）
https://fuwari.vercel.app/posts/acm/codeforces-exercise-1800-constructive-1/
作者
wegret
发布于
2024-09-27
许可协议
CC BY-NC-SA 4.0
算法笔记：dsu on tree（树上启发式合并）
物联网项目记录（2） 树莓派语音与视觉基础
© 2026 wegret. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari