本组 Idea 文章长度突然变长了。
G
题目描述
G 国共 个居民， 个无向边把他们连接起来，形成一张图 。
G 国国庆到来，居民们希望拜访所有其他的居民。为了少走路，他们会各自求出以他们为源点的最短路。很快，居民发现，每个人都要求一遍最短路，对于我们这个数据范围不就 TLE 了，还不如多走路！这一点也不符合节日的欢快气氛！
于是，一个居民提出，要不把我们这张图的最小生成树求出来，然后我们就只通过树边拜访居民们，不就行了！这样既能防止 TLE，还能少走路！很多居民表示同意，毕竟我们这个图比较特殊，最小生成树唯一。
但是也有很多反对者。其中一个人提出，有的居民只走树边正好走过的就是最短路，而有的居民不是！
你作为 G 国国王的助理，你提议通过民主投票来决定那个居民的方案是否通过。于是，你需要找出哪些居民同意方案，哪些不同意方案。
G 国国王为了使流程严肃化，他给你了一个叫做“形式化题意”的文件，内容如下：
给出一张无向带权连通图 ，其中 为点集， 为边集。 共 个点， 条边。保证 的最小生成树唯一。设最小生成树 。
定义 为 中结点 与结点 间的最短路大小， 为 中结点 与结点 间的最短路大小。注：由于 为树，所以最短路就是两点间的树上距离。 特殊地，。
设 是这样一个变量，当且仅当满足 时， 为 ；否则 为零。求 。
输入输出格式
输入的第一行为两个正整数 。
接下来 行，每行三个个数字 ，表示一条边权为 的无向边 。
输出 行字符串：
- 若 为 ，则第 行输出
Yes； - 若 为 ，则第 行输出
No；
数据范围与来源
，边权在 int 范围内，所有数均为正整数。
来自 yz。
题解
处理一个 ST 表，表示自根至叶子的前缀和。枚举所有非树边，在形成的环上二分打标记。
H 数字三角形
https://www.luogu.com.cn/problem/U253643
题目描述
给定一个如下的数字三角形，共有无限行。
其规律是：第 列是公差为 的等差数列，首项为 。
4
6 6
8 9 8
10 12 12 10
12 15 16 15 12
14 18 20 20 18 14
16 21 24 25 24 21 16
18 24 28 30 30 28 24 18
20 27 32 35 36 35 32 27 20
22 30 36 40 42 42 40 36 30 22
24 33 40 45 48 49 48 45 40 33 24
...
记数字三角形第 行，第 列的数字为 。例如，第 行，第 列的数字为 。一个数 存在于数字三角形，当且仅当存在一个数对 ，使得 。
需要注意的是，数字三角形中有很多重复的数字，也有一些数字不存在。
现在，Yurchiu 和 给出 个询问，你均需要快速地回答。
询问一共有四种，分别是：
- Yurchiu 想要知道第 行的和。答案对某个正整数 取模。本询问分数占 。
- 给定一个大于 的正整数 。如果不存在于数字三角形中，回答
-1。否则，显然这个数字可以由一个或多个数对 对应。分别求 的最小可能值和 的最大可能值。Yurchiu 想要知道这个问题的答案。显然， 一定存在。本询问分数占 。 - 给定一个坐标 ，其对应 。保证 。以这个坐标为起点，连续走 步。 想要分别知道可走到的最大值和最小值。“走一步”定义为使横坐标或纵坐标加一或减一，且保证走到的坐标合法。本询问分数占 。
- 给定一个大于 的正整数 。如果不存在于数字三角形中，回答
-1。否则，回答 的最小可能值。Yurchiu 想要知道这个问题的答案。特别地，在本询问中，如果 或 不存在，则认为它的值为 。本询问分数占 。
输入格式
第一行包含两个整数 和 ，表示询问的个数和询问类型。
接下来 行。对于询问 2 和 4，每行一个整数。对于询问 1，每行两个整数。对于询问 3，每行三个整数。
输出格式
输出 行。对于询问 1 和 4，每行一个整数。对于询问 2 和 3，每行两个整数。
特别地，如果答案是 -1，那么本行一个整数 -1。
样例 #1
样例输入 #1
2 1
3 998244353
4 998244353
样例输出 #1
25
44
样例 #2
样例输入 #2
2 2
12
6
样例输出 #2
14 18
8 9
样例 #3
样例输入 #3
2 3
7 4 2
8 2 1
样例输出 #3
35 15
28 18
样例 #4
样例输入 #4
6 4
21
16
6
24
2333
40
样例输出 #4
16
15
6
18
-1
33
提示
【样例解释】
样例 #2：第一个询问， 对应的数对有 个， 的值可以是 ，，，。
样例 #3：第二个询问，给定坐标对应的数是 。向右走一步就可以到达最大值 ，向左走一步就可以到达最小值 。
样例 #4：第二个询问， 对应的数对有 个， 可以是 ，，。六个数中，最小的是 。注：表示成括号的形式是为了方便理解，以上六个数是独立的。
【数据范围】
测试点不等分。对于每种询问，均有：
- 对于 的数据，满足 。
- 对于 的数据，满足 。
特别地：
- 对于询问一，。对于 的数据，。注意， 不保证是质数。
- 对于询问二，。
- 对于询问三，。对于 的数据，。
- 对于询问四，。
【本题来源】
- Idea：Yurchiu，。
- 其余：Yurchiu。
题解
这道题数学味很冲，而且只是小学数学的水平。
第一问
注意到把第 行的数字拆成两个因子相乘的形式之后，其和是定值 。这个性质也是解决全部四问的关键，因为这是本题的 idea 核心所在。
令 ，则答案是：
然后我们就做完了？
但是注意到数字很大，一乘就会爆掉，无法应用第四个式子。并且模数 不一定是质数，没法求逆元。用高精度呢，不仅麻烦，而且有 TLE 风险。我们只能对数进行手动除，配合龟速乘解决这一问。
如果直接应用第三个式子，那么有：
- 中必定有一个可以被 整除的数。
- 中必定有一个可以被 整除的数。
那么，我们就可以在不爆掉的情况准确计算了。但是，这样常数大，容易 TLE。
考虑对第四个式子进行等价变形：
针对这个式子计算，常数会小很多。
但是还是 TLE。怎么办？这里提供一个小技巧。龟速乘的 base 可以调大一点。然后你就可以过掉最简单的第一问了。
注意：一定是除完之后，才能模 。原先的错误数据就是这样先模再除产生的。
但是终究还是太水了，所以给了 10 分。5 分是给直接暴力相加的。
第二问
由于数字三角形的对称性，求 的最值相当于求 的最值。
数字三角形的第 列是公差为 的等差数列。那么，首先得出的一个结论是：一个数不存在于数字三角形等价于它是质数。然后，你会发现 与 在同一列上。那就意味着，它们两个数在一个等差数列上。
显然，最小值是 加最小可能公差。最小可能公差又等于 的最小质因子。所以，只需要使用线性筛筛出每个数的最小质因子就行了。最大值，就是加最大因子，也就是加上 除以最小质因子。
现在说明一下如何用线性筛求最小质因子。
考虑线性筛的时间复杂度是线性的特点。为什么时间复杂度是线性的的呢？原因是，合数被且仅被它的最小质因子筛掉。所以一个数被筛掉时，顺便就可以记录下来它的最小质因子。
另外，一个事实是，线性筛中，当满足 i%prime[j]==0 时，就要 break。其原因就是此时 i*prime[j] 的最小质因子就是 prime[j]。如果继续枚举质数，那么接下来的数 i*prime[j+1] 的最小质因子就不是 prime[j+1] 了，那么线性复杂度就无法保证。
简单不简单？
第三问
有点复杂。显然，活动的范围是和 有关的菱形框。下图展示以 为起点， 时的活动范围（其外围的一圈数字也在范围内）。
4
6 6
8 9 8
10 12 12 10
12 15 16 15 12
14 18 20 18 14
16 21 21 16
18 30 24 18
20 27 35 32 27 20
22 30 36 42 42 40 36 30 22
24 33 40 45 48 49 48 45 40 33 24
...
考虑以下不等式：
这两个不等式来自于等差数列的性质和对称性。很自然地推出，在菱形框内的任意一个位置，都可以构造一条路径，到达框的右下边，且路径上的值递增。也就是说，整个框的最大值位于右下边。同理，最小值位于左上边，这里仅以最大值为例，最小值是同理的。
显然，边所在直线的斜率绝对值都等于 。所以，可以考虑以下做法：
为了便于描述以及符合数学的习惯，横线表示为 ，竖线表示为 ，其中 为行号， 为列号。
设直线 ，其中 为直线 与 交点的横坐标。设函数 为 与直线 的交点所在方格的 值。
令 。利用因子和为定值的性质，可以得到：
这是一个开口朝下的二次函数，所以有最大值。当 时， 取到最大值。
但是，方框的边不是直线而是线段，所以要注意定义域。对于询问 ，易得 ，并且 。由于取最大值时 不一定是整数，所以只需要取其上取整和下取整时函数值的最大值即可；注意不要超出定义域。对于最小值，取定义域 的边界 和 的函数值最小值。
另外，注意坑点：
- 不要超出三角形边界。
- 第三次强调，不要超出定义域。
- 注意求最小值时，如果 ，那么最小值就是 。
所以，这道数学题就做完了。但还是很水。
第四问
不妨设 。其中，。
显然题目要求的是 与 两者的最小值。
由于 ，所以 （因为 是定值，根据均值不等式易得此结论）。那么，我们就只考虑求 的最小值就可以了。
现在，让我们比较 和 的大小关系。利用作差法，得：
所以，当 取最小值（不能是 ）时， 最小。现在，问题转化为求一个数的最小非 因子。
首先还是需要使用线性筛筛出每个数的最小质因子。之后，从 枚举到最大值，如果数 的最小质因子 是 ，就令 。这样搞一遍，求得的是最小非 质因子。
再来一个循环，看是否能被 整除且不是 的倍数。如果是，那么这个数的最小非 因子应该是 。这样，这道题就做完了。
注意，如果一个数只能分解为 乘一个质数，那没办法，只能是取 型。
好像压轴问也没有那么难？可能是结论很好猜。
代码
//https://www.luogu.com.cn/paste/wdcjpcpl
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
typedef long long ll;
const ll N=5000000+10,inf=214748364799999999;
ll n,x,ans,flag,p[N],m[N],m2[N],cnt=0,Q;
char t[N];
void Prime()
{
for(ll i=2;i<=N-10;i++)
{
if(t[i]==0) p[++cnt]=i,m[i]=i;
for(ll j=1;i*p[j]<=N-10&&j<=cnt;j++)
{
t[i*p[j]]=1; m[i*p[j]]=p[j];
if(i%p[j]==0) break;
}
}
m[1]=1;
}
void init()
{
for(ll i=1;i<=N-10;i++) m2[i]=m[i];
for(ll i=4;i<=N-10;i++)
if(m2[i]%2==0) m2[i]=m2[i/2];
for(ll i=1;i<=N-10;i++)
if(i%4==0&&m2[i]!=3) m2[i]=4;
}
ll mul(ll a,ll b,ll p)
{
ll ret=0;
if(a<b) swap(a,b);
a%=p; b%=p;
while(b)
{
ret+=a*(b%10)%p;
b/=10; a=a*10%p;
}
return ret;
}
ll mul(ll a,ll b)
{
ll ret=0;
if(a<b) swap(a,b);
while(b)
{
ret+=a*(b%10);
b/=10; a=a*10;
}
return ret;
}
void solve1()
{
ll x,p,f1,f2,f3,ans;
while(Q--)
{
ans=0;
scanf("%lld%lld",&x,&p);
x+=3; f1=x,f2=x+1,f3=x-1;
if(f1%3==0) f1/=3;
else if(f2%3==0) f2/=3;
else f3/=3;
if(f1%2==0) f1/=2;
else f2/=2;
ans=mul(mul(f1,f2,p),f3,p);
ans=(ans-mul(x,2,p)+2)%p;
printf("%lld\n",(ans%p+p)%p);
}
}
void solve2()
{
ll x;
while(Q--)
{
scanf("%lld",&x);
if(m[x]==x) printf("-1\n");
else printf("%lld %lld\n",x+m[x],x+x/m[x]);
}
return;
}
ll F(ll z,ll m)
{
ll ret=-mul(2,mul(z,z));
ret=ret+mul(m+1,z);
ret=ret+m+3;
return ret;
}
ll Max(ll L,ll R,ll m)
{
ll Lpos=floor((m+1)*1.0/4),Rpos=ceil((m+1)*1.0/4);
ll ret=-inf;
if(L<=Lpos&&Lpos<=R) ret=max(ret,F(Lpos,m));
if(L<=Rpos&&Rpos<=R) ret=max(ret,F(Rpos,m));
ret=max(ret,F(L,m)); ret=max(ret,F(R,m));
return ret;
}
ll Min(ll L,ll R,ll m)
{
ll ret=inf;
ret=min(ret,F(L,m)); ret=min(ret,F(R,m));
return ret;
}
void solve3()
{
ll b,d,k,m;
while(Q--)
{
scanf("%lld%lld%lld",&b,&d,&k);
m=b+d-1+k;
printf("%lld ",Max(d,min(d+k,b),m));
m=b+d-1-k;
if(m<=0) printf("4\n");
else printf("%lld\n",Min(max(0ll,d-k),min(d,(ll)ceil(1.0*m/2)),m));
}
return;
}
void solve4()
{
ll x;
while(Q--)
{
scanf("%lld",&x);
if(m2[x]==x) printf("-1\n");
else if(m2[x]==x/2) printf("%lld\n",3ll*(m2[x]-1));
else printf("%lld\n",(m2[x]-1)*(x/m2[x]+1));
}
return;
}
void main()
{
int type;
Prime(); init();
scanf("%lld%d",&Q,&type);
if(type==1) solve1();
if(type==2) solve2();
if(type==3) solve3();
if(type==4) solve4();
return;
}
}
int main()
{
//freopen("triangle.in","r",stdin);
//freopen("triangle.out","w",stdout);
_yz::main();
return 0;
}
I 掷骰子
题目背景
https://www.luogu.com.cn/problem/U239990?contestId=81097
巨佬 zzy 是神，祂所处的世界是常人无法理解的高维空间。一天，巨佬 zzy 穿越到了我们的世界，并找到蒟蒻 Yurchiu，想要和她进行掷骰子游戏。
当然，zzy 的骰子也是常人无法理解的——由于它是高维物体，它可以等可能地掷出从 到 的任意点数！
蒟蒻 Yurchiu 被 zzy 非凡的智慧所震撼，所以她想要问你一个问题。因为 zzy 急着要吊打 Yurchiu，所以 zzy 只给你 的时间回答她的问题。
题目描述
巨佬 zzy 的骰子可以等可能地掷出从 到 的任意点数。
掷骰子游戏是这样的：Yurchiu 连续掷 次骰子，取掷出的最小点数为 Yurchiu 的得分。为了游戏的趣味性和易操作性，限制 要么是 ，要么是 。
蒟蒻 Yurchiu 想知道自己的期望得分是多少。为了避免回答小数（避免有理数取模），你需要将答案乘上 。为了避免答案太大，你只需回答答案对 取模的结果即可。
由于“期望”这个概念蒟蒻 Yurchiu 连听过都没听过，所以她准备了一份说人话的简明题意。
简明题意：
给定 ，，。当 时，求：
当 时，求：
输入格式
本题有多组数据。
第一行一个整数 ，代表数据组数。
对于每组数据，依次读入三个整数 ，，，意义如题面所述。
输出格式
输出共 行。
对于每组数据，共一行，为一个整数，每组数据的答案。
样例 #1
样例输入 #1
3
59 2 59865001
8 2 23460017
179 2 59651546
样例输出 #1
70210
204
1927830
样例 #2
样例输入 #2
3
185 3 89341605
132 3 60140856
111 3 71715879
样例输出 #2
27987210
16912428
38638656
样例 #3
样例输入 #3
2
9999991919810999 2 9999991919810998
9991145149999999 3 9991145149999998
样例输出 #3
4999995959905500
4995572575000000
提示
【数据范围】
对所有测试点保证 ，，，。
特别地：
- 对于一个特定的测试点， 为一固定值。
- 不保证 为质数。
本题输入输出量较大，建议使用较快的输入输出方式。
| 测试点 | ||||
|---|---|---|---|---|
【本题来源】
- Idea：zzy，yz；
- 题面 & 数据 & 标程 & 题解：yz；
- 验题：zzy。
题解
太水了，答案分别为 和 。
J 丕佩
这是一道交互题。
交互库生成两个 的排列 ，，你需要求出对于每一个 的数，在两个排列中的位置 ，。
如， 和 。对于数 ，位置分别为 ，。
可调用的功能：
query(i,j)，表示询问 和 的大小关系。其中，（如 ）。 返回值为 ，代表大于，等于，小于。你最多调用 次。
需实现的功能：
- 输出 行，每行两个数，第 行代表数字 在两个排列中的位置。
子任务 1：限制 。
子任务 2：限制 ，。
对于所有数据， 你的程序能解决的最大值， 你的程序能解决的最大值。
K 跳棋
现有一个 01 字符串，0 可以“吃掉”紧邻的 1，1 可以“吃掉”紧邻的 0。“吃掉”即移除并占领被吃字符的位置并且空出原位置。两字符间有空位则不为紧邻。
求最少剩余几个字符。
- Idea：zzw。
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/bb461b1b6d34/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
