前言： 这篇文章大概是笔者最初的一篇博客。创作之时代码仍然较为稚嫩。有些地方嫌其过丑，于是略加修改，但总体上依旧保留当初的代码风格。此次选拔赛算是梦开始的地方，曾厝安幼儿园队迈出了从校内选拔向区域赛的第一步，至今历历在目。
Contents
B.是谁打了奶奶
Description
最近发生了一起骇人听闻的打奶奶事件，凶手就是——惊奇队长。
惊奇队长是在电车上打的奶奶，那么我们就来看一个和电车有关的问题。
某市修建了若干条单向通行的电车轨道，每条轨道连接了两个生活区，形成一个n个点m条边的有向图。
现在要规划若干条电车线路，满足如下条件：
1.每条电车线路必须是一个环，也就是说，电车能沿着这条线路循环运行。
2.每个生活区必须恰好在一条电车线路上。
3.每条轨道至多在一条线路上。
所以我们感兴趣的是，能否安排出满足条件的方案?
Format
– Input
每个测试点包含至多100组输入数据，请处理至文件结束。
对于每组数据，第一行两个整数n和m(n\leq1000,m\leq2000)，表示有向图的点数和边数。
接下来m行，每行两个整数u,v(1\leq{u},v\leq{n})，表示有一条通行方向从u到v的电车轨道。
至多5组数据满足n>100,m>200，图中可能有重边或自环。
– Output
按照输入顺序，对于每组数据输出一行。
如果可以安排出这样的方案，输出“Yes”，否则输出“No”（不含引号）。
Sample 1
- Input
4 5
1 2
2 3
3 1
2 4
4 1
- Output
No
题解
思维题。在一个环覆盖中，每个点仅有其前驱结点与后继结点。所以我们可以把每个点u拆成u_1,u_2，对于每条边，连边变成(u_1,v_2)。在一个环上，每个点的u_1,u_2都会连有且只有一次。我们惊喜的发现：这不就是一个裸的二分图匹配问题了吗！如果二分图的最大匹配为n，就是Yes，否则No。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1005;
int n,m;
int head[maxn],eg_num;
struct edge
{
int nex;
int to;
}eg[2*maxn];
void add(int a,int b)
{
eg[++eg_num].nex=head[a];
head[a]=eg_num;
eg[eg_num].to=b;
}
int comb[maxn],dfn[maxn],tim;
int dfs(int rt)
{
for(int i=head[rt];i;i=eg[i].nex)
{
int to=eg[i].to;
if(dfn[to]==tim) continue;
dfn[to]=tim;
if(!comb[to]||dfs(comb[to]))
{
comb[to]=rt;
return 1;
}
}
return 0;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
int ans=0;
eg_num=0;tim=0;
memset(head,0,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(comb,0,sizeof(comb));
for(int i=1,a,b;i<=m;i++)
{
scanf("%d%d",&a,&b);
add(a,b);
}
for(int i=1;i<=n;i++)
{
++tim;
if(dfs(i)) ans++;
}
if(ans==n) printf("Yes\n");
else printf("No\n");
}
return 0;
}
D.塔子哥数数
Description
某日药水哥直播的时候，教塔子哥背九九乘法表。当塔子哥连背了几遍“九六七十二”之后，药水哥有点绝望，便想从更基础的问题教起——数数，现在请你也和塔子哥一起数。
首先在正整数集上定义函数g(n)：
1.g(1)=1
2.如果n能表示成若干个两两不同质数的乘积，那么g(n)=1,否则g(n)=0
现在有一张纸上面，从左到右写了g(1),g(2),…,g(n)，药水哥问塔子哥这个数是多少，也就是把g(1)g(2)g(3)…g(n)连起来看成一个10进制数，其中g(1)是最高位，那么这个数是多少。
这个数可能很大，请输出这个数对于1000000007取模的结果。
Format
– Input
每个测试点仅包含一组输入数据，一行一个正整数 n（1\leq n\leq 10^{11})
– Output
输出一行一个正整数代表本题答案。
Sample 1
– Input
4
- Output
1110
题解
数论好题，考察莫比乌斯函数的本质。我们先来回忆一下莫比乌斯函数的定义：
- 当n不等于1时，n所有因子的莫比乌斯函数值的和为0。
即：\sum_{d|x}\mu(d)=
\begin{cases}
1&\text{x=1}\cr
0&\text{x>1}
\end{cases} - 从通俗上讲，它有如下几个特征：
1）莫比乌斯函数μ(n)的定义域是正整数
2）μ(1)=1
3）当n存在平方因子时，μ(n)=0
4）当n是素数或奇数个不同素数之积时，μ(n)=-1
5）当n是偶数个不同素数之积时，μ(n)=1
\mu(x)=
\begin{cases}
1&{x=1}\cr
(-1)^k&{x=p_1p_2…p_k}\cr
0&\text{其余情况}
\end{cases}
我们惊喜地发现，g(x)就是\mu(x)的绝对值！妈妈我会线性推！再一看数据范围，10^{11}。。。想了半天，决定跳过此题。
还是对数据不够敏感。这种数据范围显然应当是根号做法。正难则反，我们可以先考虑所有位是1，再刨除g(i)=0的位置。
- 计算所有位是1的n位数对1000000007取模
容易观察到，S(n)=\frac{10^n-1}{9}。
所以简简单单地求个快速幂和9的逆元就好啦！ -
计算g(i)=0的位置贡献的值
由g(x)的定义，我们可以看出所有2^2,3^2,…,k^2(k^2\leq n)的倍数要被刨除。对于k^2，我们要刨除的总和：
由于g(k^2),g(2k^2)…从高位向地位排列，因此这是一个以10^{n-k^2}为首项、10^{-k^2}为公比、⌊\frac{n}{k^2}⌋为项数的等比数列。因此，
$$S(k)=\frac{10^{n-k^2}\left(1-10^{-k^2 * \left\lfloor\frac{n}{k^2}\right\rfloor}\right)}{1-10^{-k^2}}$$
- 用容斥原理排除重复计算
如果减去每一个S(k)，显然会有重复。比如考虑k=6，就已经在k=2,k=3减去过两次了，因此还要再加上S(6)。考虑k=30，在k=2,3,5共减了三次，又在k=6,10,15加了3次，因此要减去S(30)。。。想到了什么？莫比乌斯函数！每个k的容斥系数就是它的莫比乌斯函数值！可以用数学归纳法简单证明：
1）k=2,3时满足容斥系数-1=\mu(2)=\mu(3)
2）每个数计算之前已经扣除了除1以外的所有约数各一次。若前x-1个数的容斥系数均为其对应的莫比乌斯函数：我们知道计算x之前已经计算了除x本身和1之外的所有约数各一次，对应的容斥系数均为其莫比乌斯函数。我们要求每个k只扣除一次。由于1不在考虑范围以及\mu(1)=1，因此x的容斥系数为：
-1-\left(\sum_{d|x}\mu(d)-\mu(1)-\mu(x)\right)=\mu(x)
- 得到答案
ans=\frac{10^n-1}{9}+\sum_{k=2}^{k^2\leq n}\left(\mu(k) * \frac{10^{n-k^2}\left(1-10^{-k^2 * \left\lfloor\frac{n}{k^2}\right\rfloor}\right)}{1-10^{-k^2}}\right)
#include <iostream>
#include <cstdio>
typedef long long ll;
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e6;
ll n;
int mu[maxn],prime[maxn],num[maxn],tot;
//求莫比乌斯函数板子
void get_mu()
{
mu[1] = 1;
for(int i = 2; i < maxn; i++)
{
if(!num[i])
{
prime[++tot] = i;
mu[i] = -1;
}
for(int j = 1; j <= tot && i * prime[j] < maxn; j++)
{
num[i*prime[j]] = 1;
if(i % prime[j]) mu[i*prime[j]] = -mu[i];
else
{
mu[i*prime[j]]=0;
break;
}
}
}
}
//快速幂板子
int ksm(int a, ll b)
{
int ans = 1;
for(; b; b >>= 1, a = 1LL * a * a % mod)
{
if(b&1) ans = 1LL * ans * a % mod;
a = 1LL * a * a % mod;
}
return ans;
}
//求逆元板子
int ni(int a, int p)
{
return ksm(a, p-2);
}
int main()
{
scanf("%lld", &n);
ll ans = 1LL * (ksm(10, n) - 1) * ni(9, mod) % mod;
get_mu();
for(ll i = 2; i * i <= n; i++)
{
int tmp1 = (ksm(10, 1LL * i * i * (n / (i * i))) - ksm(10,i * i * (n / (i * i) - 1)) + mod) % mod;
int tmp2 = (ksm(10, 1LL * i * i * (n / (i * i))) - 1 + mod) % mod;
int tmp3 = ksm(10, n - i * i);
int tmp4 = 1LL * mu[i] * tmp2 * tmp3 % mod * ni(tmp1, mod) % mod;
if(mu[i] > 0) ans = (ans + tmp4) % mod;
else if(mu[i] < 0) ans = (ans + tmp4 + mod) % mod;
}
printf("%lld\n", ans);
return 0;
}
F.故乡的樱花树
Description
又到了故乡樱花盛开的时节，川桑想把樱花树移栽到双流机场，因为他相信那个女人有一天会回来的，那时候要有童话般的场景。
樱花树可以看成n个点n-1条边的无向连通图，为了长途运输，它的直径不能太大，这里的直径就是图中最长的简单路径的长度（路径上边权之和）。
现在，已经知道樱花树上所有的边长度之和为m，请你为每条边分配一个边权E_i，使得所有E_i的和等于m，并且樱花树的直径最小。
你只需要输出最小的树的直径保留6位小数的结果。
Format
– Input
每个测试点仅包含一组输入数据。
第一行两个正整数n和m(2\leq n\leq 100000,\ 1\leq m\leq 10^9)
接下来n-1行，每行两个正整数x,y(1\leqx,y\leqn)，表示x号节点和y号节点之间存在一条边。
保证输入数据为一棵樱花树。
– Output
一行一个实数，保留6位小数，为最小的直径。
Sample 1
– Input
4 3
1 2
1 3
1 4
- Output
2.000000
题解
直径的两端是叶子结点。我们来贪心一下：所有直径的长度都相等。
- 证明：如果不是所有路径的长度都相等，那么必有一条（或多条）最长路径、和一条（或多条）最短路径。我们将最长路径的部分权值分给最短路径，答案必定会减小。
这是一个纳什均衡。
一个显然的构造方案：设k为叶子结点的个数，那么给每个叶子结点赋权值\frac{m}{k}、其余结点赋权值0，显然所有的树上路径权值之和即为\frac{2m}{k}。
– 并不严密的正确性证明：对于一颗固定的树，其所有树上路径是确定的，也就是说统计所有树上路径时，每个点被计算的次数是确定的。每条树上路径的权值之和等于\frac{总权值和}{树上路径数}，因此我们要让总权值和尽量小，即给经过次数多的点尽量少的权值。易知父亲结点经过的次数要多于儿子节点。因此将所有权值赋给儿子节点最优。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005;
int n,m;
int tim[maxn],num;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
tim[x]++;tim[y]++;
}
for(int i=1;i<=n;i++)
{
if(tim[i]==1) num++;
}
printf("%.6lf\n",2.0*m/num);
return 0;
}
G.凶手找到了
Description
感谢移动互联网，每当发生一件坏事的时候，我们总是能够立刻找到凶手。
事实上，大家也都知道，所有的坏事都是同一个人干的，每100件坏事就有6324件是他干的。
现在又有一件坏事发生了，请你告诉大家凶手的名字。
Format
– Input
每个测试点仅包含一组输入数据，一行一个字符串，长度不超过1000000。
这个字符串可能包含大小写英文字母，空格，英文逗号、英文句号、英文问号和英文感叹号，描述一件坏事。
– Output
一行一个字符串，凶手的名字。
Sample 1
– Input
Who has killed Albus Dumbledore?
- Output
Xiaochuan Sun
题解
签到题不多说。
#include <iostream>
#include <cstdio>
using namespace std;
char s[1000005];
int main()
{
gets(s);
printf("Xiaochuan Sun\n");
return 0;
}
H.抽象思维派系
Description
学习抽象学派，最关键的是要掌握抽象思维，将一切都抽象起来。
生活处处有抽象，比如我们耳熟能详的“扫雷”，就有一个更加抽象的版本：
给出一个无向图，请你支持如下两种操作：
1.在a号节点上放b个地雷。
2.查询a号节点所有相邻节点（不包括a号节点自己）的地雷总数。
两个节点相邻当且仅当它们之间有边，所有节点一开始都没有地雷。
Format
– Input
每个测试点仅包含一组测试数据。
第一行三个整数n,m,Q\ (n,m,Q \leq 200000)，表示无向图的点数，边数和操作总数。
接下来m行，每行两个整数u,(1\leq u,v\leq n)，表示u号节点和v号节点之间有一条无向边。
接下来Q行，每行是如下两种形式之一。
1 a b，表示在a号节点上放b个地雷(1\leq a \leq n，1\leq b \leq 10^9)。
2 a，表示查询a号节点所有相邻节点（不包括a号节点自己）的地雷总数(1\leq a \leq n)。
输入的无向图可能有重边，但一定没有自环。
– Output
按照输入顺序，对于每个查询操作，输出一行一个整数，表示本次查询的答案。
Sample 1
- Input
4 6 4
1 2
1 3
1 4
2 3
2 4
3 4
1 1 4
2 4
1 2 4
2 3
- Output
4
8
题解
非常具有启发性的一道题。
直接暴力显然是过不了的。不断修改、查询度数很大的点，复杂度O(qm)，直接爆炸。我们T了一发之后感觉是道数据结构题，又没想到该怎么维护，就搁置下来了。
我们分析一下：一共m条边连接了2m次点，因此度数超过\sqrt{2m}的点的数目不超过\sqrt{2m}。我们便可以将所有的点分为这么两类：度数小于\sqrt{2m}的点为0类，否则为1类。
当放地雷的时候，如果是0类点就暴力将所有相邻点的答案加上放的地雷数；如果是1类点就在这个点上打标记。放单个地雷的复杂度便是O(\sqrt{m})。
我们注意到所有拥有标记的点都是1类点。因此我们可以重新构图：每个点只与原先相连的点中的1类点连接。
当查询点时候，ans等于自身的ans（来自于相邻的0类点暴力赋予）再加上所有相邻1类点的标记总数。由于1类点点数量小于\sqrt{2m}，因此单个查询的复杂度也是O(\sqrt{m})。
于是我们得到了O(q\sqrt{m})的算法。
算法的核心就是：巧妙利用分类讨论，将 O(1) 查询 O(m) 放置或者O(1)放置O(m)查询均摊到 O(\sqrt{m}) 的查询与放置。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
typedef long long ll;
using namespace std;
const int maxn=200005;
int n,m,q;
int head[maxn],eg_num;
int n_head[maxn],n_eg_num;
set < pair<int,int> > s;//记录每条边
set < pair<int,int> >::iterator it;
struct node
{
ll ans;//每个点通过暴力获得的答案
int deg;//点点度数
int flag;//0或1类点
ll tag;//1类点的标记
}nd[maxn];
struct edge
{
int nex;
int to;
}eg[2*maxn],n_eg[2*maxn];
void add(int a,int b)
{
eg[++eg_num].nex=head[a];
head[a]=eg_num;
eg[eg_num].to=b;
}
//重新构造图的时候用
void n_add(int a,int b)
{
n_eg[++n_eg_num].nex=n_head[a];
n_head[a]=n_eg_num;
n_eg[n_eg_num].to=b;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1,a,b;i<=m;i++)
{
scanf("%d%d",&a,&b);
//排除重边，顺便记录下所有的边
it=s.find(make_pair(a,b));
if(it==s.end())
{
add(a,b);add(b,a);
nd[a].deg++;nd[b].deg++;
s.insert(make_pair(a,b));
s.insert(make_pair(b,a));
}
}
//按照点的度数做标记
int lim=sqrt(2*m);
for(int i=1;i<=n;i++)
{
if(nd[i].deg>lim) nd[i].flag=1;
else nd[i].flag=0;
}
//重构图：每个点只连接1类点
for(it=s.begin();it!=s.end();it++)
{
int a=it->first,b=it->second;
if(nd[a].flag) n_add(b,a);
}
//开始询问
for(int i=1,tmp,a,b;i<=q;i++)
{
scanf("%d",&tmp);
//添加地雷
if(tmp==1)
{
scanf("%d%d",&a,&b);
//如果这个点的度数小，就把所有相邻点的答案增加
if(nd[a].flag==0)
{
for(int i=head[a];i;i=eg[i].nex)
{
int to=eg[i].to;
nd[to].ans+=b;
}
}
//否则给这个点自身添加标记
else
{
nd[a].tag+=b;
}
}
//开始询问
else
{
scanf("%d",&a);
//每个点的答案等于自身点答案再加上所有相邻的、1类点的标记和
ll ans=nd[a].ans;
for(int i=n_head[a];i;i=n_eg[i].nex)
{
int to=n_eg[i].to;
ans+=nd[to].tag;
}
printf("%lld\n",ans);
}
}
return 0;
}
I.南海观音
Description
参拜南海观音回来之后，小孙明白了很多。
世界是永世的轮回，每个轮回对应一种缘分的组合，迟早，每个人都会尝遍所有的组合。
好在，不用等到所有的轮回结束，我们就可以用我们有限的智慧预测所有的组合，比如下面这道题。
对于一个无向图，若其中某个点的度数为deg，那么它的价值是base^{deg} ，一个无向图的价值是它所有点的价值和。
请统计所有n个点的不同的简单无向图（即没有重边和自环的无向图）的价值和，两个无向图不同当且仅当存在两个点，在一个无向图中有边直接相连，而在另一个无向图中没有。
Format
– Input
每个测试点仅包含一组输入数据。
第一行两个正整数n,base\ (1 \leq n,base \leq 10^9)，含义如题面所述。
– Output
输出一行一个正整数，为题目所求答案对998244353取模的结果。
Sample 1
– Input
3 1
- Output
24
题解
显而易见，所有点对于无向图来说都是对称的。也就是说所有点对于价值和的贡献是相同的，因此我们只需要考虑单个点。
– n个点的无向图中，任意两个点可以连一条边，因此有\frac{n(n-1)}{2}条边，选择连或不连，由乘法原理可知共2^{\frac{n(n-1)}{2}}种无向图。
所以任取一个点，剩下的n-1个点共2^{\frac{(n-1)(n-2)}{2}}种无向图。
– 设这个点的度数为deg，即这个点连出了deg条边。对于每种无向图，都有C_{n-1}^{deg}种连法
– 这个点会连出去0至n-1条边。因此对于这n-1个点的每种无向图，选取的点贡献价值：
\sum_{deg=0}^{n-1} base^{deg} * C_{n-1}^{deg}
细心的同学肯定能就发现了——然而比赛里面我推到这卡住了，队友救了我一命，这不就是二项式定理吗！
然后就愉快的得出了上式的化简形式：
{(base+1)}^{n-1}
所以推得最终的答案：
ans = n * 2^{\frac{n(n-1)}{2}} * (base+1)^{n-1}
两个快速幂完事！
然而比赛里面不小心爆了一次long long，差点成为千古罪人
#include <iostream>
#include <cstdio>
typedef long long ll;
using namespace std;
const int mod=998244353;
int n,base;
ll ksm(int a,ll b)
{
int ans=1,base=a;
while(b>0)
{
if(b&1) ans=1LL*ans*base%mod;
base=1LL*base*base%mod;
b>>=1;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&base);
ll tmp=1LL*(n-1)*(n-2)/2;
int ans=1LL*n*ksm(2,tmp)%mod*ksm(base+1,n-1)%mod;
printf("%d\n",ans);
return 0;
}
J.玩蛇
Description
这个题和孙哥实在扯不上什么关系。
Alice和Bob来到了一个充满着多头蛇的世界，可是他们对蛇并不在乎，他们只想玩游戏。
现在有n条多头蛇，每条多头蛇都有一些奇怪的性质：
对于一条a_i 头蛇
1.它有着1号，2号，3号…a_i号共a_i个头
2.砍掉编号为x的头，若x<a_ix<a，该蛇将分裂成一条a_i-1头蛇，一条a_i-2头蛇……一条a_i-x头蛇。若x=a_i，则该蛇将会被击杀。
现在有n条多头蛇，第i条多头蛇有a_i个头
Alice和Bob轮流对他们进行砍头，谁不能砍了谁就输了。
因为Alice字典序比较靠前所以Alice先砍，请问在双方都采取最优策略的情况下，最后谁能赢得胜利？
Format
– Input
每个测试点包含多组输入数据。
第一行一个正整数T\ (T\leq 100)，表示数据组数。
对于每组数据，第一行一个正整数n\ (1\leq n\leq 1000)。
接下来一行n个正整数，第i个整数表示a_i\ (1\leq a_i \leq 10^{18})
– Output
按照输入顺序，对于每组数据输出一行，如果Alice获得胜利，请输出”Alice”，否则请输出”Bob”（不加引号）。
Sample 1
– Input
1
2
1 1
- Output
Bob
题解
博弈论。题意是x可以变成从x-1开始到任意大于0的数这连续的若干个数，或者x变成0。
很明显是nim游戏的变种，求出sg函数最后异或起来。一看数据范围，1\leq a_i \leq 10^{18}，wtf?? 线性推都不让？不管了，先打一波表为敬。加个前缀和优化，O(n^2) 做法美滋滋
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int sg[205],mex[205],beg[205];
int main()
{
sg[1]=1;sg[2]=2;
beg[1]=1^2;beg[2]=2;
for(int i=3;i<=200;i++)
{
memset(mex,0,sizeof(mex));
for(int j=1;j<i;j++) mex[beg[j]]++;
for(int j=1;;j++)
{
if(!mex[j])
{
sg[i]=j;
break;
}
}
for(int j=1;j<i;j++) beg[j]^=sg[i];
beg[i]=sg[i];
}
for(int i=1;i<=200;i++) printf("sg[%d]: %d\n",i,sg[i]);
return 0;
}
然后得到了如下的东东，就快乐地打印代码把电脑交给队友。
sg[1]: 1
sg[2]: 2
sg[3]: 1
sg[4]: 4
sg[5]: 1
sg[6]: 2
sg[7]: 1
sg[8]: 8
sg[9]: 1
sg[10]: 2
sg[11]: 1
sg[12]: 4
sg[13]: 1
sg[14]: 2
sg[15]: 1
sg[16]: 16
sg[17]: 1
sg[18]: 2
sg[19]: 1
sg[20]: 4
sg[21]: 1
sg[22]: 2
sg[23]: 1
sg[24]: 8
sg[25]: 1
sg[26]: 2
sg[27]: 1
sg[28]: 4
sg[29]: 1
sg[30]: 2
sg[31]: 1
sg[32]: 32
定睛一看，sg函数值不就是约数里有2的几次方就是几吗？蒟蒻并不精通树状数组，没想到lowbit仍然沉浸在打表找到规律的喜悦中的我，就得到一个快乐的O(T * n * log_a)的做法。其实现在还没太明白为啥会T掉。直到精通树状数组的队友提醒了我，我还保险起见加了个快速度入，才A了这题。
#include <iostream>
#include <cstdio>
typedef long long ll;
using namespace std;
int t,n;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=10*x+(ch-'0');ch=getchar();}
return f*x;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ll ans=0,tmp;
for(int i=1;i<=n;i++)
{
tmp=read();
ans^=tmp^(-tmp);
}
if(ans==0) printf("Bob\n");
else printf("Alice\n");
}
return 0;
}