【暑期集训第一场】欧拉回路 | 思维 | 数论构造 | 容斥原理 | 线段树 | 归并排序
集训1（HDU2018 Multi-University Training Contest 2）
| ID | A | B | C | D | E | F | G | H | I | J |
|---|---|---|---|---|---|---|---|---|---|---|
| AC | O | O | ||||||||
| 补题 | O | O | ? | O |
代码 & 简易题解
[A]：期望？
神仙题，留坑..
[B]：？？
同\(\text{A}\)
[C]：求欧拉通路条数，以及每条的路径
小学数竞里有讲过，无向图一笔画的充要条件是有零个或两个“奇点”（偶点个数不限），“奇点”在这里就是指度为奇数的点...
其实上面两种情况就分别对应着欧拉回路和欧拉通路，并且如果把两个奇点连起来的话欧拉通路就变成欧拉回路了。
于是我们考虑本题应该也可利用这种思路。对于至少有 \(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;
}
[D]：思维
两个人玩游戏，轮流每次从 \(\{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");}[E]：数论构造
\(\text{AC}\) 代码：
[F]：容斥
\(\text{AC}\) 代码：
[G]：线段树
有两个长度均为 \(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;
}
[J]：思维+归并排序
给定一个长度 \(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
总结
- 死磕没有结果时，应该去跟榜...
