第一题：蓝书原题，单词建边，跑欧拉路；
无向联通图：欧拉路：有2个度数为奇数的点；
欧拉回路：没有度数为奇数的点；
有向联通图：欧拉路：每个点入度=出度 或者 起点出度=入度+1 终点出度=入度-1，剩余点出度=入度；
#include<bits/stdc++.h> using namespace std; const int ME = 200000 + 5; int tot = 1, d[ME], h[ME], cur[ME], now, in[ME], out[ME]; //int ru[ME], rv[ME]; bool vis[ME << 1]; struct edge{int v, nxt, id;}G[ME << 1]; int T, N, M; void add(int u, int v, int id){ G[++tot].v = v, G[tot].nxt = h[u], G[tot].id = id, h[u] = tot; } void print(){ for(int i = now - 1; i; i--) printf("%d ", cur[i]); //for(int i = now - 1; i; i--)fprintf(stderr, "%d %d ", //ru[cur[i]], rv[cur[i]]); puts(""); } int read(){ int x = 0; int f = 1; char c = getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();} return x*=f; } void dfs(int u, int k){ for(int i = h[u]; i; i = G[i].nxt){ if(vis[i])continue; int v = G[i].v; vis[i] = vis[i^1] = 1; dfs(v, i); } cur[++now] = G[k].id; } void dfs2(int u, int k){ for(int i = h[u]; i; i = G[i].nxt){ if(vis[i])continue; int v = G[i].v; //ch++; vis[i] = 1; dfs2(v, i); } cur[++now] = G[k].id; } int main(){ freopen("merge.in","r",stdin); freopen("merge.out","w",stdout); scanf("%d%d%d", &T, &M, &N); if(T == 1){ for(int i = 1; i <= N; i++){ int u = read(), v = read(); add(u, v, i), add(v, u, -i); d[u]++, d[v]++; } int start = 1, cnt = 0; for(int i = 1; i <= M; i++) if(d[i]&1){start = i;cnt++;} if(cnt > 2 || cnt == 1)return !puts("NO"); dfs(start, 0); if(now != N+1)return !puts("NO"); puts("YES"); print(); } else { for(int i = 1; i <= N; i++){ int u = read(), v = read(); add(u, v, i);out[u]++, in[v]++; //ru[i]=u,rv[i]=v; } int st = -1, ed = -1, cnt = 0; for(int i = 1; i <= M; i++) if(in[i] != out[i]){ if(in[i]+1 == out[i])st = i; if(in[i]-1 == out[i])ed = i; cnt++; } if((cnt != 0 && cnt != 2) || ((st == -1 || ed == -1) && cnt != 0))return !puts("NO"); if(st == -1)for(int i = 1; i <= N; i++) if(in[i]) {st = i;break;} dfs2(st, 0); if(now != N+1)return !puts("NO"); puts("YES"); print(); return 0; } }
第二题：有一个性质，发现就好做了，但我根本没有去思考，思维僵化啊；
#include<bits/stdc++.h> using namespace std; const int M = 200005, inf = 1e9; int a[M], n,t[M], c[M]; long long Ans; bool vis[M]; void add(int x){ for(; x <= n; x += x&(-x)) c[x] ++; } int query(int x){ int ret = 0; if(!x)return 0; for(; x; x -= x&(-x)) ret += c[x]; return ret; } #define Ls nd->ls, lf, mid #define Rs nd->rs, mid+1, rg struct Node{ int v; Node *ls, *rs; void up(){ v = min(ls->v, rs->v); } }pool[M << 2], *root, *tail = pool; Node *build(int lf = 1, int rg = n){ Node *nd = ++tail; if(lf == rg)nd->v = a[lf]; else { int mid = (lf + rg) >> 1; nd->ls = build(lf, mid); nd->rs = build(mid+1, rg); nd->up(); } return nd; } void modify(int pos, Node *nd = root, int lf = 1, int rg = n){ if(lf == rg){ if(nd->v <= a[pos]){ Ans -= t[lf]; nd->v = inf; } } else { int mid = (lf + rg) >> 1; if(pos <= mid && nd->ls->v <= a[pos])modify(pos, Ls); if(nd->rs->v <= a[pos])modify(pos, Rs); nd->up(); } } int read(){ int x = 0; int f = 1; char c = getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();} return x*=f; } int main(){ freopen("count.in","r",stdin); freopen("count.out","w",stdout); int m, k; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++)a[i] = read(); for(int i = n; i; i--){ t[i] = query(a[i]-1); add(a[i]); } for(int i = 1; i <= n; i++)Ans += 1LL*t[i]; printf("%lld ", Ans); root = build(); for(int i = 1; i <= m; i++){ k = read(); modify(k); if(i != m)printf("%lld ", Ans); else printf("%lld ", Ans); } }