神仙题，留坑..
同\(\text{A}\)
小学数竞里有讲过，无向图一笔画的充要条件是有零个或两个“奇点”（偶点个数不限），“奇点”在这里就是指度为奇数的点...
其实上面两种情况就分别对应着欧拉回路和欧拉通路，并且如果把两个奇点连起来的话欧拉通路就变成欧拉回路了。
于是我们考虑本题应该也可利用这种思路。对于至少有 \(2\) 个点的无向连通块，如果它有 \(2*k\) 个奇点（注意奇点必有偶数个，因为每条边可看做贡献了两个度，所以总度是偶数，而偶点不管有多少个他们的总度都是偶数，所以奇点的总度也应该也是偶的，所以奇点就必须有偶数个），那么我们把这 \(2*k\) 个奇点任意两两连接就可以使这个连通块不含任何奇点，也就成为一个欧拉回路了。找到欧拉回路后，再断掉这 \(k\) 条新增的边，就得到 \(k\) 段欧拉通路，也就得解了。
当然，如果这个连通块只有一个点，那就特判一下，此时不存在欧拉通路。
\(\text{AC}\) 代码：
#include <cstdio> #include <cstring> #include <vector> const int MV = 100007, ME = MV; struct Ed { int v, ne, id; bool used; } ed[3 * ME]; // 注意这里不是平常无向图的两倍，因为还会加边！如果所有的点都是奇点就会加MV/2条双向边也就是MV条边，所以要开3倍 int head[MV], tot; inline void edd(int u, int v, int id) { ed[++tot] = {v, head[u], id, false}; head[u] = tot; } int deg[MV]; bool vis[MV]; std::vector<int> path[MV]; int pnt; void dfs(int u) { vis[u] = true; for (int i=head[u]; i; i=ed[i].ne) { if (!ed[i].used) { ed[i].used = ed[i^1].used = true; dfs(ed[i].v); if (ed[i].id == 0) // 遇到了补的边 ++pnt; else path[pnt].push_back(-ed[i].id); } } } int main() { int V, E; while (~scanf("%d %d", &V, &E)) { tot = 1; pnt = 0; memset(deg, 0, sizeof(*deg) * (V+1)); memset(vis, 0, sizeof(*vis) * (V+1)); memset(head, 0, sizeof(*head) * (V+1)); for (int i=1; i<=E; ++i) { int u, v; scanf("%d %d", &u, &v); ++deg[u], ++deg[v]; edd(u, v, i), edd(v, u, -i); } static int odd_v[MV]; int odd_t = 0; for (int v=1; v<=V; ++v) if (deg[v] & 1) odd_v[odd_t++] = v; for (int i=0; i<odd_t; i+=2) edd(odd_v[i], odd_v[i+1], 0), edd(odd_v[i+1], odd_v[i], 0); // 此时每个连通块都是一个单点or一个欧拉回路 // 先遍历那些有奇点的（曾经补过边的）连通块 for (int v=1; v<=V; ++v) if (!vis[v] && (deg[v]&1)) ++pnt, dfs(v), --pnt; // 再遍历剩下的的连通块（注意跳过单点连通块，否则会出现长度为0的路径，这是本题不需要输出的） for (int v=1; v<=V; ++v) if (!vis[v] && deg[v]) ++pnt, dfs(v); printf("%d\n", pnt); for (int i=1; i<=pnt; ++i) { printf("%d ", path[i].size()); for (auto p : path[i]) printf("%d ", p); puts(""); path[i].clear(); } } return 0; }两个人玩游戏，轮流每次从 \(\{1, 2, 3, ..., n\}\) 的集合中选一个数，然后把集合中存在的这个数的所有因子剔除（包括自身），如果某个人无法再操作（面对∅）则输掉游戏，问是否先手必胜？
答案是肯定的。若 \(n==1\)，那显然先手必胜。若 \(n>1\)，先考虑 \(\{2, 3, ..., n\}\)，如果面对这一批后手有必胜策略，则加上 \(1\) 之后先手者第一步拿 \(1\)，那么就先手必胜了；而如果先手者对 \(\{2, 3, ..., n\}\) 已经有必胜策略，那么算上 \(1\) 后还是按原来必胜策略来即可必胜，因为先手者不管拿什么非 \(1\) 都会拿走 \(1\)。
\(\text{AC}\) 代码（C）：
main(){while(~scanf("%*d"))puts("Yes");}\(\text{AC}\) 代码：
\(\text{AC}\) 代码：
有两个长度均为 \(n\) 的数组 \(a, b\)，\(a\) 初始时全为 \(0\)，\(b\) 为给定的一个 \(1\sim n\) 的排列\(q\) 次操作，有两种，一是把 \(a\) 区间 \([l, r]\) 加 \(1\)，二是求 \(\sum\limits_{i=l}^{r}\lfloor \frac{a_i}{b_i} \rfloor\)
区间加和区间求和，能想办法用线段树维护吗？这里需要转一下脑筋...要充分利用取整操作答案更新的周期性和离散性。
我们维护一个 \(c\) 数组和 \(sum\) 数组，初始时 \(c=b，sum=\{0\}\)，每次进行第一种操作时就对 \(c\) 的对应区间减 \(1\)。减完之后，看看此区间内 \(c\) 的最小值是否为 \(0\)，若为 \(0\) 则查到是哪个(些)点，查到这些减到 \(0\) 的位置（记组成集合 \(S\)），此时这些地方的 \(c[i](i\in S)\) 已经累计减少了 \(b[i]\) 次了（等价于 \(a[i]\) 累计增加了 \(b[i]\) 次），于是就把 \(sum[i]\) 加一，然后再把 \(c[i]\) 重新赋上 \(b[i]\) 的值。这样，每次查询求和式的时候，只需查询 \(sum[i]\) 的区间和即可。
所以这就可以用线段树维护了。
再看看复杂度有没有保证：维护 \(sum\) 肯定是保证 \(O(q\log n)\) 的，不过区间减一的时候可能还涉及叶节点查询，这样复杂度可能会爆炸。但考虑到查询叶节点最多不超过 \(\sum\limits_{i=1}^{n}\frac{q}{i}\) 次，这货又是调和级数是和 \(\log(q)\) 同阶的，所以区间更新的复杂度是保证 \(O(q\log^2 n)\) 的。整体复杂度 \(O(q\log^2 n)\)，可以接受。
\(\text{AC}\) 代码：
#include <cstdio> #define MIN(a, b) ((a)<(b)?(a):(b)) const int MN = 100007; typedef int vint, xint, sint; const xint ROOT = 1; class STree { private: struct Node { xint l, r; sint min, s, lza; } t[MN << 2]; vint *arr; xint ll, rr; #define li i<<1 #define ri i<<1|1 #define t_mid ((t[i].l+t[i].r) >> 1) #define add_v(i, v) \ ({ \ t[i].min += v, \ t[i].lza += v; \ }) #define pd(i) \ ({ \ if (t[i].lza) \ { \ add_v(li, t[i].lza); \ add_v(ri, t[i].lza); \ t[i].lza = 0; \ } \ }) #define pu(i) \ ({ \ t[i].min = MIN(t[li].min, t[ri].min), \ t[i].s = t[li].s + t[ri].s; \ }) void build(const xint i, const xint l, const xint r) { t[i].l = l, t[i].r = r, t[i].lza = 0; if (l == r) { t[i].min = arr[r]; t[i].s = 0; } else { build(li, l, t_mid); build(ri, t_mid+1, r); pu(i); } } void dec(const xint i) { if (ll <= t[i].l && t[i].r <= rr && t[i].min > 1) add_v(i, -1); else { if (t[i].l == t[i].r && t[i].min == 1) { t[i].min = arr[t[i].r]; t[i].s += 1; } else { pd(i); if (ll <= t_mid) dec(li); if (rr > t_mid) dec(ri); pu(i); } } } sint sum(const xint i) { if (ll <= t[i].l && t[i].r <= rr) return t[i].s; else { pd(i); sint s = 0; if (ll <= t_mid) s += sum(li); if (rr > t_mid) s += sum(ri); return s; } } public: void build(vint *a, const xint l, const xint r) { arr = a; build(ROOT, l, r); } void dec(const xint l, const xint r) { ll = l, rr = r; dec(ROOT); } sint sum(const xint l, const xint r) { ll = l, rr = r; return sum(ROOT); } }; STree st; int b[MN]; int main() { char op[9]; int n, q, l, r; while (~scanf("%d %d", &n, &q)) { for (int i=1; i<=n; ++i) scanf("%d", b+i); st.build(b, 1, n); while (q--) { scanf("%s %d %d", op, &l, &r); if (*op == 'a') st.dec(l, r); else printf("%d\n", st.sum(l, r)); } } return 0; }给定一个长度 \(n\) 的数组 \(a\)，数组中每存在一个逆序对（\(i<j,\ a[i]>a[j]\)）则需付出 \(x\) 元的代价。 你可以进行任意多次的相邻交换操作，每次操作代价是 \(y\) 元。 求进行任意次操作后能达到的最小代价。
考虑相邻交换操作，每次操作最多消除一个逆序对，因此如果 \(y>x\)，做操作是肯定会亏的；而如果 \(y==x\)，做操作最多也就保证不会付出更多代价，不可能减少代价。
因此只有当 \(y<x\) 时我们才有可能通过相邻交换操作减少代价。我们能不能做到每次操作必消除一个逆序对呢？其实是可以的。我们每次从后往前找第一个相邻的逆序对（和prev_permutation的第一步是一样的），如果找不到则说明序列已经有序；如果找到，则把这个逆序对靠前的那个数一直往后挪，每挪一次（进行一次相邻交换操作）就消除了一个逆序对，一直挪到不能消除逆序对为止。显然完成这么一轮后，后面这一段仍然保持着单调不减性。于是一直这样操作下去整个序列也就单调不减了，也就排完序了，并且整个过程中每次相邻交换都消除了一个逆序对。
因此我们是可以做到每次操作都消除一个逆序对的。因此 \(y<x\) 时最少付出的代价就是 \(y*\)逆序对个数。
综上可以发现，题目的答案正是 \(\min(x, y)*\)逆序对个数。可以用归并排序 / 权值树状数组 / 平衡树来做。
\(\text{AC}\) 代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<map> #define N 200010 #define LL long long #define INF 0x3f3f3f3f using namespace std; int n,i,a,b,be; int c[N],d[N]; LL Ans,cnt; inline int Abs(int x){return (x<0)?-x:x;} inline int Min(int a,int b){return (a<b)?a:b;} inline int Max(int a,int b){return (a>b)?a:b;} inline int read(){ int p=0; char c=getchar(); while (c<48||c>57) c=getchar(); while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar(); return p; } inline void Merge(int low,int high){ int mid=(low+high)>>1,l=0,r=0,e=0; if (low==high) return; Merge(low,mid); Merge(mid+1,high); l=low; r=mid+1; e=low; while (l<=mid&&r<=high){ if (c[l]<=c[r]) d[e++]=c[l++]; else { Ans+=(mid-l+1); d[e++]=c[r++]; } } while (l<=mid) d[e++]=c[l++]; while (r<=high) d[e++]=c[r++]; for (i=low;i<=high;i++) c[i]=d[i]; } int main(){ // freopen("zht.in","r",stdin); // freopen("zht.out","w",stdout); while (~scanf("%d%d%d",&n,&a,&b)){ if (n==1){ cout<<"0"<<endl; continue; } for (i=1;i<=n;i++) scanf("%d",&c[i]); Ans=0; Merge(1,n); cnt=Min(a,b); cout<<(LL)Ans*cnt<<endl; } return 0; }E、G 较简单，赛后应马上补上。
C、F 属于常见知识点，也应尽快补上。
其余神仙题...待进一步提升实力后再回来填坑吧QAq
转载于:https://www.cnblogs.com/403-forbidden/p/11312619.html
相关资源：JAVA上百实例源码以及开源项目