青青视频在线播放,久9视频8

A題 Tree

問題描述

給定一顆 $n$ 個(gè)點(diǎn)的樹，樹邊帶權(quán)，試求一個(gè)排列 $P$ ，使下式的值最大
$\sum_{i=1}^{n-1} maxflow(P_i, P_{i+1})$
其中 $maxflow(s, t)$ 表示從點(diǎn) $s$ 到點(diǎn) $t$ 之間的最大流，即從 $s$ 到 $t$ 的路徑上最小的邊權(quán)

輸入格式

第一行一個(gè)整數(shù) $n$ ，表示點(diǎn)數(shù)

下接 $n - 1$ 行，每行三個(gè)數(shù) $u, v,w$ 表示一條連接點(diǎn) $u$ 和點(diǎn) $v$ 權(quán)值為 $w$ 的邊

輸出格式

輸出一行一個(gè)整數(shù)，表示答案

數(shù)據(jù)范圍

對(duì)于前 $5\%$ 的數(shù)據(jù)滿足 $n \leq 8$

對(duì)于前 $40\%$ 的數(shù)據(jù)滿足 $n \leq 200$

對(duì)于前 $60\%$ 的數(shù)據(jù)滿足 $n \leq 2000$

對(duì)于 $100\%$ 的數(shù)據(jù)滿足 $n \leq 100000$

樣例

樣例輸入
2 1 2 2333

樣例輸出
2333

題解

事實(shí)上是一道十行代碼就可以解決的題目
如果要讓 $\sum_{i=1}^{n-1}maxflow(P_i, P_{i+1})$ 的邊權(quán)值最小，就要讓每一條邊只被經(jīng)過一次，那么將所有邊的權(quán)值相加就好了QAQ~~（網(wǎng)上的題解都是些什么玩意。。。）~~

#include<bits/stdc++.h>
using namespace std;
long long n,ans,u,v,w;
int main(){
    cin>>n;
    for(register long long i=1;i<n;i++)cin>>u>>v>>w,ans+=w;
    cout<<ans<<endl;
    return 0;
}

B題 Permutation

問題描述

給定一張 $n$ 個(gè)點(diǎn) $m$ 條邊的無向圖，每條邊連接兩個(gè)頂點(diǎn)，保證無重邊自環(huán)，不保證連通

你想在這張圖上進(jìn)行若干次旅游，每次旅游可以任選一個(gè)點(diǎn) $x$ 作為起點(diǎn)，再走到一個(gè)與 $x$ 直
接有邊相連的點(diǎn) $y$ ，再走到一個(gè)與 $y$ 直接有邊相連的點(diǎn) $z$ 并結(jié)束本次旅游

作為一個(gè)旅游愛好者，你不希望經(jīng)過任意一條邊超過一次，注意一條邊不能即正向走一次又反
向走一次，注意點(diǎn)可以經(jīng)過多次，在滿足此條件下，你希望進(jìn)行盡可能多次的旅游，請(qǐng)計(jì)算出最多
能進(jìn)行的旅游次數(shù)并輸出任意一種方案

輸入格式

第 $1$ 行兩個(gè)正整數(shù) $n$ 與 $m$ ，表示全圖的點(diǎn)數(shù)與邊數(shù)
下接 $m$ 行，每行兩個(gè)數(shù)字 $u$ 與 $v$ 表示一條邊

輸出格式

第 $1$ 行一個(gè)整數(shù) $cnt$ 表示答案

下接 $cnt$ 行，每行三個(gè)數(shù)字 $x$ , $y$ 與 $z$ ，表示一次旅游的路線

如有多種旅行方案，任意輸出一種即可

數(shù)據(jù)范圍

對(duì)于前 $20\%$ 的數(shù)據(jù)， $n < 10,m \leq 20$ .

對(duì)于令 $20\%$ 的數(shù)據(jù)， $m = n - 1$ ，并且圖連通

對(duì)于令 $10\%$ 的數(shù)據(jù)，每個(gè)點(diǎn)的度數(shù)不超過 $2$

對(duì)于 $100\%$ 的數(shù)據(jù)， $n \leq 100000,m \leq 200000$

樣例

樣例輸入
4 5 1 2 3 2 2 4 3 4 4 1

樣例輸出
2 4 1 2 4 3 2

題解

部分分方法很容易想到，DFS或者BFS直接遍歷查找即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010,maxm = 200010;
/*
struct edge{
    int v,next;
    bool used;
}E[maxm*2];
*/
struct anss{
    int a,b,c;
};
vector<int> G[maxn];
//priority_queue< pair<int,int> , vector<pair<int,int>>, less<pair<int,int>> > pq;
int p[maxn],eid;
int degree[maxn];
/*
void init(){
    memset(p,-1,sizeof p);
    eid = 0;
}
*/
inline void insert(int u,int v){
    G[u].push_back(v);
}
inline void insert2(int u,int v){
    insert(u,v);
    insert(v,u);
}
int n,m;
inline bool cmp(const int &a,const int &b){
    if(degree[a] == degree[b]){
        return a < b;
    }else{
        return degree[a] < degree[b];
    }
}
int main(){
    scanf("%d%d",&n,&m);
    memset(degree,0,sizeof degree);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        insert2(u,v);
        degree[u]++;
        degree[v]++;
    }
    for(int i=1;i<=n;i++){
        sort(G[i].begin(),G[i].end(),cmp);
    }
    int cnt = 0;
    //int tcnt[maxn] = {0};
    vector<anss> ansss;
    for(int i=1;i<=n;i++){
        while(degree[i] >= 2){
            //cout << "i:" << i << " degree: " << degree[i] << endl;
            //ansss.push_back({G[i][tcnt[i]*2-2],i,G[i][tcnt[i]*2-1]});
            int son1 = -1,son2 = -1;
            int savep;
            int pp = 0;
            sort(G[i].begin(),G[i].end(),cmp);
            //cout << "savep:" << savep << endl;
            son1 = G[i][0],son2 = G[i][1];
            //cout << "son1:" << son1 << "son2:" << son2 << endl;
            for(int ppp=0;ppp<G[son1].size();ppp++){
                if(G[son1][ppp] == i){
                    //cout << "ppp1:" << ppp << endl;
                    G[son1].erase(G[son1].begin() + ppp);
                    break;
                }
            }
            
            for(int ppp=0;ppp<G[son2].size();ppp++){
                if(G[son2][ppp] == i){
                    //cout << "ppp1:" << ppp << endl;
                    G[son2].erase(G[son2].begin()+ppp);
                    break;
                }
            }
            G[i].erase(G[i].begin()+1);
            G[i].erase(G[i].begin());
            ansss.push_back({son1,i,son2});
            degree[i] -= 2;
            degree[son1]--;
            degree[son2]--;
            cnt++;
        }
    }
    printf("%d\n",cnt);
    for(int i=0;i<ansss.size();i++){
        printf("%d %d %d\n",ansss[i].a,ansss[i].b,ansss[i].c);
    }
    return 0;
}

這種方法的錯(cuò)誤性也很容易發(fā)現(xiàn)。任意一個(gè)強(qiáng)連通圖都有可能導(dǎo)致錯(cuò)誤，即使是部分強(qiáng)聯(lián)通也會(huì)出導(dǎo)致錯(cuò)誤。所以我們需要找其他的思路。
首先我們可以發(fā)現(xiàn)，答案輸出的第一行總是所有聯(lián)通塊中的邊集 $\Sigma{m/2}$ ，此時(shí)我們?cè)诿總€(gè)聯(lián)通塊中任選一點(diǎn)做生成樹，并從根節(jié)點(diǎn)向下遍歷，每找到兩條相連邊就記錄一次即可。當(dāng)然遍歷的順序也很講究，要先查葉子節(jié)點(diǎn)的所連的邊再查父親節(jié)點(diǎn)的所連的邊，這樣才能玄學(xué)保證最優(yōu)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=4e5+10;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
ll n,m,num[maxn],fa[maxn];
bool vis[maxn];
struct edge{
    ll v;
    ll next;
}e[maxn];
ll p[maxn],t=0;
ll edge[maxn];
struct Path{
    ll a,b,c;
};
vector<Path> ans;
void insert(ll u,ll v){
    e[t].v=v;
    e[t].next=p[u];
    p[u]=t++;
}
void insert2(ll u,ll v){
    insert(u,v);
    insert(v,u);
}
void BFS(ll rt){
    ll x,H=0,T=1;
    num[T]=rt;
    fa[rt]=-1;
    while(H-T){
        ll u=num[++H];
        for(ll i=p[u];i!=-1;i=e[i].next){
            ll v=e[i].v;
            if(!fa[v]){
                fa[v]=u;
                num[++T]=v;
            }
        }
    }
    for(x=T;x>=1;x--){
        ll u=num[x];
        edge[0]=0;
        for(ll i=p[u];i!=-1;i=e[i].next){
            ll v=e[i].v;
            if(!vis[i] && v!=fa[u])
                edge[++edge[0]]=i;
        }
        for(ll i=p[u];i!=-1;i=e[i].next){
            ll v=e[i].v;
            if(!vis[i] && v==fa[u])
                edge[++edge[0]]=i;
        }
        for(ll i=1;i+1<=edge[0];i+=2){
            vis[edge[i]]=vis[edge[i]^1]=true;
            vis[edge[i+1]]=vis[edge[i+1]^1]=true;
            ans.push_back((Path){e[edge[i]].v,u,e[edge[i+1]].v});
        }
    }
}
int main(){
    freopen("T1.txt","r",stdin);
    memset(p,-1,sizeof(p));
    n=read(),m=read();
    for(ll i=1;i<=m;i++){
        insert2(read(),read());
    }
    for(ll i=1;i<=n;i++)
        if(!fa[i])BFS(i);
    printf("%lld\n",(ll)ans.size());
    for(ll i=0;i<ans.size();i++)printf("%lld %lld %lld\n",ans[i].a,ans[i].b,ans[i].c);
    return 0;
}

C題 Permutation

問題描述

你有一個(gè)長度為 $n$ 的排列 $P$ 與一個(gè)正整數(shù) $K$

你可以進(jìn)行如下操作若干次使得排列的字典序盡量小

對(duì)于兩個(gè)滿足 $\left|i-j\right| \geq K$ 且 $\left|P_i-P_j\right| =1$ 的下標(biāo) $i$ 與 $j$ ，交換 $P_i$ 與 $P_j$

輸入格式

第一行包括兩個(gè)正整數(shù) $n$ 與 $K$

第二行包括 $n$ 個(gè)正整數(shù)，第 $i$ 個(gè)正整數(shù)表示 $P_i$

輸出格式

輸出一個(gè)新排列表示答案

輸出共 $n$ 行，第 $i$ 行表示 $P_i$

數(shù)據(jù)范圍

對(duì)于前 $20\%$ 的數(shù)據(jù)滿足 $n \leq 6$

對(duì)于前 $50\%$ 的數(shù)據(jù)滿足 $n \leq 2000$

對(duì)于 $100\%$ 的數(shù)據(jù)滿足 $n \leq 500000$

樣例

樣例輸入
8 3 4 5 7 8 3 1 2 6

樣例輸出
1 2 6 7 5 3 4 8

題解

~~非常好的暴力訓(xùn)練題。考試的時(shí)候明顯是在比誰騙的分多Orz~~
首先是大家都懂的20分普通暴力

#include <bits/stdc++.h>
#define maxn 500010
using namespace std;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
struct edge{
    int u,v,w,next;
}E[maxn<<1],A[maxn<<1];
int p[maxn],eid=0;
void init(){
    for(register int i=0;i<maxn;i++)p[i]=-1;
    eid=0;
}
void insert(int u,int v,int w){
    E[eid].u=u;
    E[eid].v=v;
    E[eid].w=w;
    E[eid].next=p[u];
    p[u]=eid++;
}
void insert2(int u,int v,int w){
    insert(u,v,w);
    insert(v,u,w);
}
int n,k;
int t[maxn],a[maxn];
int main(){
    //freopen("T2.txt","r",stdin);
    n=read();k=read();
    for(register int i=1;i<=n;i++)a[i]=read();
    int flag=n;
    while(flag--) {
        for(register int i=1;i<=n;i++){
            for(register int j=i+k;j<=n;j++) {
                if(fabs(a[i]-a[j])==1 && a[i]>a[j]) {
                    int p=a[i];
                    int q=a[j];
                    a[i]=q;
                    a[j]=p;
                }
            }
        }
    }
    for (int i=1;i<=n;i++)cout<<a[i]<<endl;
    return 0;
}

道理都懂，直接暴力查找就好了(:з」∠)
然后是知識(shí)分子的剪枝暴力，用的~~時(shí)間~~要稍微少一點(diǎn)，去掉了對(duì)于無法轉(zhuǎn)換的字符的判斷，雖然復(fù)雜度的上限依然很大，但是下限減小了不少↓

//40分
#include <bits/stdc++.h>
using namespace std;
long long n,k,p[500010],t[500010];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        t[i] = p[i];
    }
    sort(t+1,t+1+n);
    bool flag = 1; 
    int ts =1;
    while(flag){
        flag = 0;
        for(int i=ts;i<n;i++){
            int  tk = 0;
            for(int j=i+1;j<=n;j++){
                if(abs(p[i] - p[j]) == 1){
                    tk++;
                }
                if(abs(i - j) >= k && abs(p[i]-p[j])==1 && p[i]>p[j]){
                    long long temp = p[i];
                    p[i] = p[j];
                    p[j] = temp;
                    flag = 1;
                    /*for(int k=1;k<=n;k++){    
                        cout<<p[k]<<" ";
                    }
                    cout<<endl;*/
                }
                if(tk == 2){
                    break;
                }
            }
        }
        if(p[ts] == t[ts]){
            ts++;
            //cout<<p[ts]<<endl;
        }
    //  t++;
        //cout<<t<<endl;
    }
    for(int i=1;i<=n;i++){
        cout<<p[i]<<endl;
    }
    return 0;
}

PS：我也不知道為什么會(huì)變成40分QAQ
最后是大佬的玄學(xué)暴力。每一次遍歷的時(shí)候提前處理判斷當(dāng)前是否是最佳答案，對(duì)于每一對(duì) $i$ 和 $j$ 而言，若 $i$ 在 $j$ 的前面，那么每一次判斷性質(zhì)時(shí)只判斷 $i-j$ 是否等于1而不是 $abs(i-j)$ ，因?yàn)槿绻?img class="math-inline" src="https://math.jianshu.com/math?formula=i-j%3D1" alt="i-j=1" mathimg="1">成立就說明處在前方的數(shù)的值一定比處在后方的數(shù)的值要大，那么一定要執(zhí)行交換操作。同理，如果 $j-i=1$ 就說明交換之后整個(gè)串的字典序要大于交換之前，因此不做交換。

#include <bits/stdc++.h>
#define maxn 500005
using namespace std;
//tql
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
int n,m;
int a[maxn];
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    bool swaped;
    for(register int k=1;k<=n && swaped;k++){
        swaped=false;
        for(register int i=1;i<=n-m;i++){
            for(register int j=i+m;j<=n;j++){
                if(a[i]-a[j]==1){
                    swap(a[i],a[j]);
                    swaped=true;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)printf("%d\n",a[i]);
    return 0;
}

講完暴力我們?cè)賮砜聪抡?。（轉(zhuǎn)，正解讓本弱雞根本無法理解，會(huì)在正解后給出自己的解法）
作者：a6219221
來源：CSDN
原文：https://blog.csdn.net/a6219221/article/details/52456053

從input的內(nèi)容來分：有2種，分別是有duplicate和no duplicate的

解法：這兩種情況的結(jié)果其實(shí)有有同一個(gè)特性：在同一個(gè)position，同一種字母只能出現(xiàn)一次。只不過沒有duplicate的情況下不需要額外處理就可以達(dá)到這個(gè)效果。針對(duì)有duplicate的情況，我們?cè)诿看蔚膔ecursion中都需要設(shè)置一個(gè)set來儲(chǔ)存這個(gè)位置已經(jīng)使用過的數(shù)字或者字母。見如下的tree：

example: input is: 1, 1, 2
on each recursion level, we skip the duplicate number
                /       |      \
               1       [1]重復(fù)  2               n
             /  \     / \      |  \
            1    2   1   2     1  [1]重復(fù)       n * (n - 1)
           /    /   /   /      |   |
          2    1   2   1       1   1            n * (n - 1) * (n - 2)
 
time: O(n!)
space: O(n)
1 1 2
1 2 1
2 1 1

從input的type來分：
可以是array
可以是list
也可以是個(gè)string

區(qū)別：這里的區(qū)別在于是否能夠in place操作其中的element。比如array就可以快速的swap里面的element，這時(shí)候我們的permutation就可以使用swap的方式。但是string是沒有辦法這樣操作的。所以如果后面2種情況出現(xiàn)又想要做in place的話，最好是重新建立一個(gè)array來儲(chǔ)存其中的內(nèi)容。這樣也可以避免List的get()的時(shí)間復(fù)雜度不恒定的問題。string可以使用toCharArray()來得到char的array

從output的要求來分：

1是不用output，就print出來。

2是要返回一個(gè)List<string>。

3是要返回一個(gè)List<List<Integer>>

區(qū)別： 1.如果不用output，我們可以寫一個(gè)函數(shù)把那個(gè)array或者temp arraylist中的內(nèi)容打印出來。這個(gè)問題一般不大

如果需要返回一個(gè)string，那么input一般來說是一個(gè)string或者是char array.這類的做法也比較方便，用swap的方法最后rst.add(new String(input))就可以實(shí)現(xiàn)
需要注意的是如果要求返回的值是List<List<Integer>>，那么最后加入rst的那步一定是需要一個(gè)一個(gè)把a(bǔ)rray中的數(shù)字添加到最后的list中去的。最好是這樣做，可以保證不會(huì)出問題。因?yàn)椴⒉皇呛苈闊┒也粫?huì)出現(xiàn)想用現(xiàn)成函數(shù)用錯(cuò)的情況。畢竟list中的是object而array中的可能是permitIve type

貼上代碼

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

const int maxn=5e5+10;

void read(int &x)
{
    char c=getchar(); x=0;
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
}

int n,k,p[maxn],q[maxn],deg[maxn];
int tote,FIR[maxn],TO[maxn<<1],NEXT[maxn<<1];
priority_queue<int> pq;

namespace SegTree{
    int mn[maxn<<2];
#define lc (nd<<1)
#define rc (nd<<1|1)
#define mid ((s+t)>>1)

    void init()
    {
        memset(mn,0x3f3f3f3f,sizeof(mn));
    }

    void update(int nd,int s,int t,int id,int val)
    {
        if (s==t) {mn[nd]=val; return;}
        if (id<=mid) update(lc,s,mid,id,val);
        else update(rc,mid+1,t,id,val);
        mn[nd]=min(mn[lc],mn[rc]);
    }

    int query(int nd,int s,int t,int l,int r)
    {
        if (l<=s&&t<=r) return mn[nd];
        int Ans=0x7fffffff;
        if (l<=mid) Ans=min(Ans,query(lc,s,mid,l,r));
        if (r> mid) Ans=min(Ans,query(rc,mid+1,t,l,r));
        return Ans;
    }
}

void addedge(int u,int v)
{
    TO[++tote]=v;
    NEXT[tote]=FIR[u];
    FIR[u]=tote;
    deg[v]++;
}

int main()
{
    int i,x;
    read(n); read(k);
    for (i=1;i<=n;i++)
        read(p[i]),q[p[i]]=i;
    SegTree::init();
    for (i=n;i>=1;i--)
    {
        x=SegTree::query(1,1,n,q[i]-k+1,q[i]);
        if (x<=n) addedge(q[x],q[i]);
        x=SegTree::query(1,1,n,q[i],q[i]+k-1);
        if (x<=n) addedge(q[x],q[i]);
        SegTree::update(1,1,n,q[i],i);
    }
    for (i=1;i<=n;i++)
        if (!deg[i]) pq.push(i);
    for (i=n;i>=1;i--)
    {
        int u=p[i]=pq.top(); pq.pop();
        for (int p=FIR[u];p;p=NEXT[p])
            if (!(--deg[TO[p]])) pq.push(TO[p]);
    }
    for (i=1;i<=n;i++) q[p[i]]=i;
    for (i=1;i<=n;i++) printf("%d\n",q[i]);
}
//轉(zhuǎn)自一個(gè)ACM銀牌選手

然后是本弱雞的粉墨登場

首先我們要明確這是一個(gè)換位問題。這時(shí)我們假設(shè)有三個(gè)數(shù) $a,b,c$ ，如果 $a$ 和 $b$ 可以交換位置且 $b$ 和 $c$ 可以換位置，那么我們就可以知道 $a$ 一定可以和 $c$ 換位置。因此我們需要一個(gè)值來存儲(chǔ)可以換位置的點(diǎn)。用什么方法可以很容易的判斷兩個(gè)元素處于同一個(gè)集合里呢？很顯然是并查集。我們初始化每次判斷i和j位置的值，如果 $i$ 和 $j$ 可以換位置，就在并查集中合并 $i$ 和 $j$ ，最后按字典序排列即可
這時(shí)我們就得到了一個(gè)看似正確的思路。事實(shí)上，這只正確了一半。因?yàn)楫?dāng)我們交換兩個(gè)元素的位置后，他可以通往的位置會(huì)發(fā)生改變。因此這時(shí)我們需要再重復(fù)幾次之前的步驟，直到最后所有元素都沒法再交換位置得到最優(yōu)解時(shí)再停止

#include<bits/stdc++.h>
#define maxn 500000
using namespace std;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
int fa[maxn];
int n,k;
void init(){
    for(register int i=0;i<=n;i++)fa[i]=i;
}
int get(int x){
    if(fa[x]==x)return x;
    return fa[x]=get(fa[x]);
}
int merge(int x,int y){
    x=get(x);
    y=get(y);
    if(x!=y)fa[y]=x;
}
struct edge{
    int a,p;
    //a記錄當(dāng)前的值，p記錄位置 
}E[maxn];
bool cmp(edge a,edge b){
    return a.a<b.a;
}
bool outcmp(edge a,edge b){
    return a.p<b.p;
}
set<int> savenow;//存儲(chǔ)每一次已經(jīng)被用過的位置 
int cas[maxn];//記錄上一次的排列順序 
int main(){
    //freopen("T2.txt","r",stdin);
    init();
    n=read();k=read();
    for(register int i=1;i<=n;i++)E[i].a=read(),E[i].p=i;
    while(1){
        bool here=1;
        for(register int i=1;i<=n-k;i++){
            for(register int j=i+k;j<=n;j++){
                if(abs(E[i].a-E[j].a)==1)merge(i,j);
            }
        }
        for(register int i=1;i<=n;i++){
            int last_time=i;
            for(register int j=1;j<=n;j++){
                if(savenow.count(j))continue;
                if(get(E[i].p)==get(j)){
                    if(E[i].p>E[j].p){
                        swap(E[i].p,E[last_time].p);
                        swap(E[i].p,E[j].p);
                        last_time=j;
                    }
                }
            }
            savenow.insert(E[i].p);
            if(cas[E[i].p]!=E[i].a){
                cas[E[i].p]=E[i].a;
                here=0;
            }
        }
        if(here)break;
    }
    for(register int i=0;i<=n;i++)printf("%d ",cas[i]);
    return 0;
}

是的，這看似是一個(gè)簡便又快捷的寫法，這時(shí)再讓我們抱著激動(dòng)的心情來計(jì)算一下復(fù)雜度
算了。溜（事實(shí)上這個(gè)算法的復(fù)雜度是 $O(n!)$ ）

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

2018 NOIP集訓(xùn)(三)

2018 NOIP集訓(xùn)(三)

A題 Tree

問題描述

輸入格式

輸出格式

數(shù)據(jù)范圍

樣例

題解

B題 Permutation

問題描述

輸入格式

輸出格式

數(shù)據(jù)范圍

樣例

題解

C題 Permutation

問題描述

輸入格式

輸出格式

數(shù)據(jù)范圍

樣例

題解

貼上代碼

然后是本弱雞的粉墨登場

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

2018 NOIP集訓(xùn)(三)

A題 Tree

問題描述

輸入格式

輸出格式

數(shù)據(jù)范圍

樣例

題解

B題 Permutation

問題描述

輸入格式

輸出格式

數(shù)據(jù)范圍

樣例

題解

C題 Permutation

問題描述

輸入格式

輸出格式

數(shù)據(jù)范圍

樣例

題解

貼上代碼

然后是本弱雞的粉墨登場

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av