E题:

地址:https://codeforces.com/problemset/problem/500/C
<--!more -->
题解:这题刚开始想了半天也没有想出来一个具体思路。后面看了题解才发现很巧妙。不妨考虑样例所给顺序:1 3 2 3 1。 可以发现对于某个数在他第一次出现的时候,要读到它时 必然至少要抬起它之前所有的数字的重量(去重后) 可以自己画画图来看。那么就可以进行贪心:对于某个第一次出现的数字i,尽可能让他只需要抬所需要的前面的去重后的数字的数量。那么只需要维护一个栈即可。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1505;
stack<int> s;
int w[MAXN],order[MAXN],mark[MAXN],temp[MAXN],vis[MAXN];
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= m; i++){
        cin >> order[i];
        if(!vis[order[i]]){
            vis[order[i]] = 1;
            mark[i] = 1;
            //cout<<i<<' '<<order[i]<<endl;
        }
    }
    for(int i = m; i >= 1; i--){
        if(vis[order[i]] && mark[i]){
            s.push(order[i]);
        }
    }
    int ans = 0;
    for(int i = 1; i <= m; i++){
        int now = order[i];
        int sum = 0;
        int cnt = 0;
        while(s.top() != now){
            //cout<<s.top()<<' ';
            temp[++cnt] = s.top();
            sum += w[s.top()];
            s.pop();
        }
        s.pop();
        for(int j = cnt; j >= 1; j--) s.push(temp[j]);
        s.push(now);
        ans += sum;
    }
    cout<<ans;
    return 0;
}

B题:
题目链接:https://codeforces.com/contest/689/problem/B

对于这道题来说,看似需要连很多条边来,但实际上只需要相邻两个点之间连一条权值为1,以及特定的两个点连一条权值为1的边,跑一遍BFS即可

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
int head[MAXN],dis[MAXN],vis[MAXN];
struct edge{
    int u,v,next;
}e[MAXN * 5];
int n,cnt;
void insert(int u, int v){
    e[++cnt].u = u; e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt;
}
void bfs(){
    vis[1] = 1;
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = head[u]; i ; i = e[i].next){
            int v = e[i].v;
            if(!vis[v]){
                dis[v] = dis[u] + 1;
                vis[v] = 1;
                q.push(v);
            }
        }
    }
    for(int i = 1; i <= n; i++) cout<<dis[i]<<' ';
}
int main(){
    cin >> n;
    for(int i = 1; i <= n - 1; i++){
        insert(i, i + 1);
        insert(i + 1, i);
    }
    for(int i = 1; i <= n; i++){
        int x;
        scanf("%d", &x);
        insert(i, x);
    }
    bfs();
    return 0;
}

C题:

题目链接:https://codeforces.com/contest/873/problem/D

题解:题目的意思是做一个类似的求出一个数组mergesort的次数。那么我们不妨构造一个1,2,3,4...1, 2, 3, 4 ...数组,对他进行反mergesort 对于每次mergesort,只需交换a[mid]a[mid]a[mid+1]a[mid+1]即可,当次数满足题目要求时返回即可。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN],p2[MAXN];
int n,k;
void find(int l, int r){
    if(k == 0 || r - l <= 1){
        return;
    }
    k -= 2;
    int mid = (l + r) / 2;
    swap(a[mid], a[mid - 1]);
    find(l, mid);
    find(mid, r);
    
}
int main(){
    cin >> n >> k;
    if(k % 2 == 0) {
        cout<<-1; return 0;
    }
    for(int i = 1; i <= n; i++) a[i] = i;
    k--;
    find(1, n + 1);
    if(k)
    cout<<-1;
    else for(int i = 1; i <= n; i++) cout<<a[i]<<' ';
    return 0;
}

D题:
题目链接:https://codeforces.com/contest/25/problem/D

题解:先做一遍生成树,将冗余边记录下来,以及记录下来有多少个集合。然后,枚举两个集合,对于两个集合,输出一个冗余边,然后两个集合之间连边即可。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n,vis[MAXN];
struct edge{
    int u,v;
}e[MAXN * MAXN],non[MAXN];
int f[MAXN],head[MAXN],num,cnt;
int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}
int main(){
    cin >> n;
    for(int i = 1; i <= n - 1; i++){
        scanf("%d %d", &e[i].u, &e[i].v);
    }
    for(int i = 1; i <= n; i++) f[i] = i;
    for(int i = 1; i <= n - 1; i++){
        int x = find(e[i].u);
        int y = find(e[i].v);
        if(x != y){
            f[y] = x;
        }
        else{
            non[++cnt].u = e[i].u; non[cnt].v = e[i].v;
        }
    }
    cout<<cnt<<endl;
    if(cnt == 0) return 0;
    for(int i = 1; i <= n; i++){
        int u = find(i);
        if(!vis[u]){
            head[++num] = u;
            vis[u] = 1; 
        }
    }
    for(int i = 1; i <= cnt; i++){
        int u = find(head[i]);
        int v = find(head[i + 1]);
        cout<<non[i].u<<' '<<non[i].v<<' '<<u<<' '<<v<<endl;
        f[v] = u;
    }
    return 0;
}