题面

T1

思路

就是先dfs一遍这棵树，先访问根节点，然后访问右孩子，然后左孩子。最后找出这个序列的最长上升子序列

然后一不小心，把第37行的ans写成了a，瞬间爆零

代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
ll read() {
    ll x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
ll a[N],ans[N],b[N];
int ls[N],rs[N],num;
void dfs(int u) {
    ans[++num] = a[u];
    if(rs[u]) dfs(rs[u]);
    if(ls[u]) dfs(ls[u]);
}
void solve() {
    int js = 0;
    b[0] = -1e9;
    for(int i = 1;i <= num;++i) {
        if(ans[i] > b[js]) b[++js] = ans[i];
        else {
            int k = upper_bound(b + 1,b + js + 1,ans[i]) - b;
            b[k] = ans[i];
        }
    }
    cout<<js;
}
int main() {
    freopen("point.in","r",stdin);
    freopen("point.out","w",stdout);
    int n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    for(int i = 1;i <= n;++i) ls[i] = read(),rs[i] = read();
    dfs(1);
    solve();
    return 0;
}

T2

50分思路

直接按照题意交换，然后归并排序或者树状数组找一下逆序对

100分思路

考虑怎样做到\(10^9\)。可以发现，其实数列中有用的数只有交换的那些数，对于中间的这些数只要找出一个元素来代替，并且给他赋个权值，表示在这个区间内有多少个数就可以了。这样就变成了N*3个数，就可以和五十分一样的方法做了

50分代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
map<int,int>ma;
ll read() {
    ll x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0'&& c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
struct node {
    int l,r;
}Q[N];
int n;
namespace BF1 {
    int a[N],tmp[N];
    ll ans = 0;
    void mul_sort(int l,int r) {
        if(l >= r) return;
        int mid = (l + r) >> 1;
        mul_sort(l,mid);mul_sort(mid+1,r);
        int L = l,R = mid+1;
        int js = l;
        while(L <= mid && R <= r) {
            if(a[L] <= a[R]) tmp[js++]=a[L++];
            else {
                ans += mid - L + 1;
                tmp[js++] = a[R++];
            }
        }
        while(L <= mid) {
            tmp[js++] = a[L++];
        }
        while(R <= r) {
            tmp[js++] = a[R++];
        }
        for(int i = l;i <= r;++i) a[i] = tmp[i];
    }
    void Main(int m) {
        for(int i = 1;i <= m;++i) a[i] = i;
        for(int i = 1;i <= n;++i) swap(a[Q[i].l],a[Q[i].r]);
//      for(int i = 1;i <= m;++i) printf("%d ",a[i]);
        mul_sort(1,m);
        cout<<ans;
    }
}
int main() {
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    n = read();
    int Max = -1;
    for(int i = 1;i <= n;++i) {
        Q[i].l = read(),Q[i].r = read();
        Max = max(Max,max(Q[i].l,Q[i].r));
    }
    BF1::Main(Max);
    return 0;
}

100分代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
map<int,int>ma;
ll read() {
    ll x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0'&& c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
struct node {
    int l,r;
}Q[N];
int n;
namespace BF2 {
    int ls[N * 4],W[N * 4],tot = 0,a[N * 4],tmp[N * 4];
    ll ans = 0;
    void lisan() {
        int num = 0;
        for(int i = 1;i <= n;++i) {
            ls[++num] = Q[i].l,ls[++num] = Q[i].r;
        }
        sort(ls + 1,ls + num + 1);
        int now = 0;
        for(int i = 1;i <= num;++i) {
            if(ls[i] == ls[i - 1]) continue;
            if(ls[i] - ls[i-1] > 1) {
                a[++tot] = tot;
                W[tot] = ls[i] - ls[i - 1] - 1; 
            }
            a[++tot] = tot;
            ma[ls[i]] = tot;
            W[tot] = 1;
        }
        for(int i = 1;i <= n;++i) {
            Q[i].l = ma[Q[i].l];
            Q[i].r = ma[Q[i].r];
        }
    }
    void mul_sort(int l,int r) {
        if(l >= r) return;
        int mid = (l + r) >> 1;
        mul_sort(l,mid);
        mul_sort(mid + 1,r);
        ll WW = 0;
        for(int i = l;i <= mid;++i) WW += W[a[i]];
        int L = l,R = mid + 1,js = l;
        while(L <= mid && R <= r) {
            if(a[L] <= a[R]) {
                WW -= W[a[L]];
                tmp[js++] = a[L++];
            }
            else {
                ans += WW * W[a[R]];
                tmp[js++] = a[R++];
            }
        }
        while(L <= mid) {
            tmp[js++] = a[L++];
        }
        while(R <= r) {
            tmp[js++] = a[R++];
        }
        for(int i = l;i <= r;++i) a[i] = tmp[i];
    }
    void Main() {
        lisan();
        for(int i = 1;i <= n;++i) swap(a[Q[i].l],a[Q[i].r]);
        mul_sort(1,tot);
        cout<<ans;
    }

}
int main() {
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    n = read();
    if(n == 1) {
        int x = read(),y = read();
        if(x > y) swap(x,y);
        cout<< y * 2 - x * 2 - 1;
        return 0;
    }
    int Max = -1;
    for(int i = 1;i <= n;++i) {
        Q[i].l = read(),Q[i].r = read();
        Max = max(Max,max(Q[i].l,Q[i].r));
    }
    BF2::Main();
    return 0;
}

T3

30分思路

每次按照要求将点染色，然后统计联通块个数就可以了。

100分思路

考虑将x染为y时，先将x从树里面拿出来，然后染色，然后重新放回去。在合并的时候，考虑让个数比较小的块加入到个数比较大的块中，舍得复杂度变为\(O(能过)\)

30分代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 200000 + 100;
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0'&& c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int col[N],pnt[N],block[N],nbok,a[N];
struct node {
    int v,nxt;
} e[N * 2];
int ans;
int head[N],ejs,num[N];
void add(int u,int v) {
    e[++ejs].v = v;
    e[ejs].nxt = head[u];
    head[u] = ejs;
}
queue<int>q1,q2,q;
int vis[N];
int bfs(int U) {
    while(!q.empty()) q.pop();
    q.push(U);
    vis[U] = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            if(vis[v]) continue;
            if(a[v] == a[u] ) {
                q.push(v);
                vis[v] = 1;
            }
        }
    }
}
int main() {
    freopen("simulator.in","r",stdin);
    freopen("simulator.out","w",stdout);
    int n = read(),q = read();
    for(int i = 1; i <= n; ++i) a[i] = read();
    for(int i = 1; i < n; ++i) {
        int u = read(),v = read();
        add(u,v);
        add(v,u);
    }
    while(q--) {
        int x = read(),y = read();
        for(int i = 1; i <= n; ++i) {
            if(a[i] == x) a[i] = y;
        }
        ans = 0;
        memset(vis,0,sizeof(vis));
        for(int i = 1; i <= n; ++i) {
            if(!vis[i]) {
                ans++;
                bfs(i);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

100分代码

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
#ifdef WIN32
#define LL "%I64d"
#else 
#define LL "%lld"
#endif
const int N = 300000 + 10; 
vector<int>son[N];
vector<int>to[N];
ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int id[N],cor[N],siz[N];
int ans = 1;
void dfs(int u,int father) {
    for(int i = 0;i < son[u].size();++i) {
        int v = son[u][i];
        if(v == father) continue;
        if(cor[v] != cor[u]) ans++;//孩子与父亲颜色不同，证明有新块 
        dfs(v,u);
    }
}
void del(int x) {
    for(int i = 0;i < son[x].size();++i) {
        int v = son[x][i];
        if(cor[v] != cor[x]) ans--;//以前颜色不同，现在颜色相同了，将ans-- 
    }
}
void ins(int x) {
    for(int i = 0;i < son[x].size();++i) {
        int v = son[x][i];
        if(cor[v] != cor[x]) ans++;//重新加入后颜色变得不同了，将ans++ 
    }
}
//cor表示当前点的颜色，id[x]表示x这个颜色的真实颜色。
//to[x]表示所有颜色为x的点。siz[x]表示颜色为x的点的个数 
int main() {
    freopen("simulator.in","r",stdin);
    freopen("simulator.out","w",stdout); 
    int n = read(),Q = read();
    for(int i = 1;i <= n;++i) {
        cor[i] = read();id[cor[i]] = cor[i];
        to[cor[i]].push_back(i);siz[cor[i]]++;
    }
    for(int i = 1;i < n;++i) {
        int u = read(),v = read();
        son[u].push_back(v);son[v].push_back(u);
    }
    son[1].push_back(0), cor[0] = 0x3e3e3e3e;
    dfs(1,0);//处理出一开始有多少联通块 
    while(Q--) {
        int x = read(),y = read();
        int y_ = y,x_ = x;
        x = id[x],y = id[y];
        id[x_] = 0;//x被合并之后消失 
        if(siz[x] > siz[y]) swap(x,y);//按照包含元素的大小合并 
        id[y_] = y;//y的颜色将变为块比较大的那个颜色 
        for(int i = 0;i < to[x].size();++i) {
            int v = to[x][i];
            del(v);//删除颜色为x的点 
            to[y].push_back(v);//加入到颜色为y的点中去
            siz[y]++; 
            siz[x]--;
        }
        for(int i = 0;i < to[x].size();++i)
            cor[to[x][i]] = y; //将颜色为x的点重新染色 
        for(int i = 0;i < to[x].size();++i)
            ins(to[x][i]);//将原来颜色为x的点重新加入到树中 
        to[x].clear();//颜色为x的点消失 
        printf("%d\n",ans);
    }
    return 0;
}

总结

期望得分100 + 100 + 30 = 230

实际得分0 + 100 + 30 = 130

再手误就剁手！！！

一言

人的一生会遭遇各种各样的事，其中有令人难以置信的事，也有不讲道理的事，但这就是生活。 ——地狱少女