@
目录- 前言
- 前置知识补充
- 问题 A: 珂朵莉
- 问题 B: 可莉的烦恼
- 问题 C: 小A的画
- 问题 D: KMP自动机fail树dfs序建可持久化线段树
- 问题 E: 谜题：结局
- 问题 F: 奶龙列阵（easy version）
- 问题 G: 小A的密码
- 问题 H: 谜题：铸币
- 问题 I: 小Z的完全平方数
- 问题 J: 奶龙列阵（hard version）
- 结语
前言
这次比赛通过2-3题的人占大部分。按照过题人数来看，难度是B<A<C<D<E<F<G。整体来看这次题目的代码量都不是特别大，大部分题目的代码在30-40行，E题模拟也只有60多行。
下面是我的题解，如果题解有不懂、错误或者有更好的方法可以评论或者私信交流一下
前置知识补充
题解使用的语言是c++，但是基本和 c 语言一样，与 c 语言相比主要就是输入和输出有一点区别，如有其他的c++内容代码注释会有解释，有 c 语言基础应该是看得懂的。
下面我来说一下c++的输入和输出
//以一个 int 类型的数据来举例
int a;
cin>>a; //c++输入
scanf("%d",&a); //c语言输入
cout<<a<<'\n'; //c++输出
printf("%d\n",a); //c语言输出
// 下面是关闭同步流，可以去查一下更详细的解释
// 简单来说就是提高c++输入和输出的效率
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
好了，接下来来看题目吧
问题 A: 珂朵莉
解题思路
A题求通项公式，我感觉是一个数学题，但是我数学能力有限，求不出通项公式。所以我是找规律找出来的。
根据题目给的 a1=4 ，还有递推公式：
an+1 = ( 4 * an -9 ) / ( an - 2 );
可以列出前6个分别为：4/1，7/2，10/3，13/4，16/5，19/6.
相信这里规律已经很明显了。
我们可以得出通项公式为：an = ( 3 * n + 1 ) / n ;
通项公式出来了，那代码就很简单了
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
void solve()
{
int n;
cin>>n;
// x 为分子 y 为分母
int x=3*n+1,y=n;
cout<<x<<' '<<y<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//多组数据输入
cin >> _;
while (_--) solve();
return 0;
}
问题 B: 可莉的烦恼
解题思路
这题就是把题目的式子化简，几次平方差公式和完全平方公式就可以化简，这里我就不演示了，化简出来的式子是：
y2 + 2xy + 2x4 + x2 - z =0 ;
这是一个一元二次方程，直接用求根公式求解
好了，看代码吧
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
void solve()
{
int x,z;
cin>>x>>z;
// 计算 a b c 的值
int a=1,b=2*x,c=2*x*x*x*x+x*x-z;
// 判断是否无解
if(b*b-4*a*c<0)
{
cout<<"No Solution!"<<'\n';
return;
}
double y1=(-b+sqrt(b*b-4*a*c))/2*a;
double y2=(-b-sqrt(b*b-4*a*c))/2*a;
// 考虑两个解相等（相当于只有一个解）的情况
if(y1==y2) cout<<y1<<'\n';
else cout<<y1+y2<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
问题 C: 小A的画
解题思路
这题重点就是：当 0 和 1 相邻时，我们只能对其中一个进行染色。我们通过逆向思维，先把所有的 0 和 1 都上色。然后遍历整个字符串，每碰到一对相邻的 0 和 1 我们就取消上色其中的一个。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
void solve()
{
// string 是字符串类型
// 如果输入 n 个字符对应的下标从 0到n-1
// 这里直接用char数组也行
string s;
cin>>s;
// 获取字符串s的长度
int n=s.length();
// 默认对所有 0 和 1 上色
int ans=n;
// 遍历整个字符串，注意从1开始，不然i-1会越界
for(int i=1;i<n;i++)
{
// 判断 0 和 1 是否相邻
if(s[i]!=s[i-1])
{
// 对 0 和 1 其中一个取消上色
ans--;
// 这里i++是因为：当前i和i-1位已经构成了一对01
// i不能在后面再使用，所以i++
i++;
}
}
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
问题 D: KMP自动机fail树dfs序建可持久化线段树
解题思路
这题就是kmp的模板题，但是数据不是很大，没学过kmp算法的也可以二分做。这里我的解法是kmp，如果有需要二分解法的我后续再更新。
题目要求：字符串的最小周期
即求：字符串长度 - 最长的相等的真前缀与真后缀的长度。
kmp算法可以 O(n) 的时间复杂度求出整个最长的长度。
二分的时间复杂度是 O(nlogn) 。
下面看代码吧
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
int nex[N];
void solve()
{
int n;
string s;
cin>>n>>s;
// 让s的下标从 0到n-1 改成 1到n
s=" "+s;
// mx用来记录最长的真前后缀相等的长度
int mx=0;
// kmp模板 nex数组记录最长前后缀长度
for(int i=2,j=0;i<=n;i++)
{
while(j&&s[i]!=s[j+1]) j=nex[j];
if(s[i]==s[j+1]) j++;
nex[i]=j;
// 更新mx的值
mx=max(mx,nex[i]);
}
//输出最小周期
cout<<n-mx<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
问题 E: 谜题：结局
解题思路
这题就是根据题目的意思模拟操作就行了，具体的细节看代码的注释吧。
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
int n,m;
// 定义一个结构体储存随从的属性
struct Q
{
// idx 表示编号 a 表示攻击力 b 表示血量
int a,b,idx;
// 自定义排序规则
bool operator < (const Q&x)const
{
if(a!=x.a) return a<x.a;
if(b!=x.b) return b<x.b;
return idx<x.idx;
}
}t[N];
void solve()
{
cin>>n>>m;
// 输入随从数据
for(int i=1;i<=n;i++)
{
cin>>t[i].a>>t[i].b;
// 初始化编号
t[i].idx=i;
}
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y;
// 在末尾增加一个随从，记得初始化编号
++n;
t[n].idx=n;
cin>>t[n].a>>t[n].b>>x>>y;
// 交换下标为 x和y 的随从属性
// 可以使用swap函数
// 注意编号不用交换
swap(t[x],t[y]);
// 交换两次编号，相当于没有交换
swap(t[x].idx,t[y].idx);
}
else
{
int x,y;
cin>>x>>y;
// 下标为 x和y 的随从相互攻击
t[x].b-=t[y].a;
t[y].b-=t[x].a;
}
}
// 排序
sort(t+1,t+1+n);
int k=0;
// 遍历整个数组，计算有多少随从还活着
for(int i=1;i<=n;i++)
{
if(t[i].b>0) k++;
}
cout<<k<<'\n';
// 输出还活着的随从的编号
for(int i=1;i<=n;i++)
{
if(t[i].b>0) cout<<t[i].idx<<' ';
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
问题 F: 奶龙列阵（easy version）
解题思路
根据题目意思我们可以得出：奇数排的所有奶龙举的手相同，偶数排的所有奶龙举的手相同。
奇数排的奶龙数量依次是：1，3，5，7，9，11，13
偶数排的奶龙数量依次是：2，4，8，10，12，14，16
可以得出：
奇数排的通项公式：an = 2n - 1 ，
求和公式：Sn = n2 ;
偶数排的通项公式：an = 2n ，
求和公式：Sn = n(n+1) ;
我们可以对排数进行二分，再确定奇数排和偶数排的数量，从而可以算出各自需要的奶龙数量，最后判断是否能按题目的要求列阵。
细节看代码注释
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
// 感觉数据挺大的还是开ll好一点
ll n,a,b,c;
bool check(ll mid)
{
// x 为奇数排的数量 y 为偶数排的数量
ll x=mid/2+(mid%2),y=mid/2;
// sum1 为奇数排需要的奶龙数量 sum2 为偶数排
ll sum1=x*x,sum2=y*(y+1);
// 如果奶龙数量大于所有奶龙，则不符合题意
if(sum1+sum2>n) return false;
// 假设奇数排举左手 偶数排举右手
// 注意d1 d2 不能小于 0
ll d1=sum1-a,d2=sum2-b;
d1=max(d1,0LL);d2=max(d2,0LL);
// 符合题意
if(d1+d2<=c) return true;
// 假设奇数排举右手 偶数排举左手
d1=sum2-a,d2=sum1-b;
d1=max(d1,0LL);d2=max(d2,0LL);
if(d1+d2<=c) return true;
// 如果上述没有符合题意的情况，则不符合题意
return false;
}
void solve()
{
cin>>n>>a>>b>>c;
// 确定排数的左右边界，最少为 0 排，最多不超过 n 排
ll l=0,r=n+1;
// 二分
while(l+1!=r)
{
ll mid=(l+r)>>1;
// 判断是否符合题意
if(check(mid)) l=mid;
else r=mid;
}
// 输出答案，二分中始终保证 l 排符合题目的要求
cout<<l<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
问题 G: 小A的密码
解题思路
这道题是一个找规律题，但是对于无解的情况我感觉我的解释可能不那么容易看懂。先说结论当 n<=4 或者 n=6 的时候是无解的。
我们从题目给的样例来看吧
长度为 5：21200
我们来考虑长度为 6，我们先不管这个密码正不正确，直接在长度为 5 的基础上最后加一个 0 ，同时下标为 0 的地方数字加一，得到的密码就是：321000，由于第一个是 3，那么下标为3的地方数字应该为 1，就是：321100，但是如果把下标为 3 处的 0 修改成 1 那么下标为 0 处的数字应该减 1 ，可以重复此过程，但是无论如何都得不到正确的密码，所以长度为 6 无解。
还有 n<=4 的情况，大家可以自己去尝试，也是无解的。
接下来我们再考虑其他的
长度为 7：在上面我们得到了一个长度为 6 的错误的密码：321100，在这个基础上我们只需要在最后加一个 0 就是一个长度为 7 的正确的密码：3211000。
我们再往后写几个：
长度为 7：3211000
长度为 8：42101000
长度为 9：521001000
长度为 10：6210001000
长度为 11：72100001000
这里规律已经很明显了，第一位就是 n-4 ，第二三位分别为 2，1 ，然后倒数第四位是 1 ，其他的全是 0 ，还有一个长度为 5 的不符合这个规律，我们可以直接将它特判掉。
ok，看代码吧
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
void solve()
{
int n;
cin>>n;
// 无解的情况
if(n<=4||n==6)
{
cout<<-1<<'\n';
return;
}
// 特判长度为 5 的情况
if(n==5)
{
cout<<"2 1 2 0 0\n";
return;
}
// 根据规律输出密码
cout<<n-4<<" 2 1 ";
for(int i=3;i<n;i++)
{
if(i==n-4) cout<<1<<' ';
else cout<<0<<' ';
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
问题 H: 谜题：铸币
解题思路
这题思路很简单，就是分六种情况：酒馆等级为1-6级购买随从所需的铸币期望。然后在这六种情况中取最小值。
虽然思路很简单但是代码实现还是有一定难度的，我们直接来看代码吧
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
int x;
double p[10][10];
void solve()
{
cin>>x;
for(int i=1;i<=6;i++)
for(int j=1;j<=6;j++)
{
cin>>p[i][j];
// 直接预处理让 p 存储刷到几星随从的概率
p[i][j]/=1000;
}
// 答案初始化为一个最大值，因为后面要取小
double ans=1e9;
// now 记录固定消费
// 初始化为 3 因为购买一个随从要花费 3 铸币
double now=3,p1;
// 循环六次，分别表示酒馆等级 1-6
for(int i=1;i<=6;i++)
{
// 如果酒馆等级为 i 时刷出 x 星的随从概率大于 0
if(p[i][x]>0)
{
// p1 记录刷新的随从中，没有一个是 x 星的概率
// i 等级的酒馆刷出 x 星的随从概率为 p[i][x]
// 所以不是 x 星随从的概率为 1-p[i][x]
// i 等级酒馆每次能刷出 i+1 个随从
p1=pow(1-p[i][x],i+1);
// 刷新的次数期望为 1/(1-p1)，每次刷新需要 1 铸币
// 所需的消费为：刷新所需的铸币期望 + 固定消费(now)
// 更新ans
ans=min(ans,1/(1-p1)+now);
}
// 下面为升级酒馆所需的花费
if(i==1) now+=5;
if(i==2) now+=7;
if(i==3) now+=8;
if(i==4) now+=9;
if(i==5) now+=11;
}
// 设置精度为小数点后 3 位
// 类似于 c 语言输出中的 %.3f
cout<<fixed<<setprecision(3)<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
问题 I: 小Z的完全平方数
解题思路
这题是要判断 n 个数相乘最后的结果是不是一个完全平方数。
本质上是一个质因数分解的题目，即对 n 个数进行质因数分解，最后每个质因数的次幂和要为偶数，则这 n 个数的积为完全平方数。
质因数分解：任何一个正整数都可以唯一地分解成若干质数的乘积。
但是考虑到数据范围：1<=n<=1000，1<=xi<=1e18 。
对 n 个数进行质因数分解时间复杂度太高，因为我们质因数分解前要先筛出所有的质数，x 的数量级达到了1e18，在筛选质数的时候就已经超时了。
转变一下思路：我们每次选择两个数，求两个数的最大公约数，然后这两个数同时约去最大公约数，这里最大公约数被约去了两次，即偶数次。最后我们只需要判断这 n 个数它本身是不是一个完全平方数，如果有一个不是，那么结果就不是一个完全平方数。
说了那么多，来看代码吧
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
// 数据很大 开ll
ll n,a[N];
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
// 排序，这里排不排序都行
sort(a+1,a+1+n);
// 每次选择下标为 i和j 的数
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
// 注意 i和j 不能相等
// 相等相当于我们只选择了一个数
if(j==i) continue;
// __gcd() 函数是求最大公约数，是c++库里面的
// 可以直接使用
ll x=__gcd(a[i],a[j]);
a[i]/=x;a[j]/=x;
}
}
// 判断 n 个数本身是否为完全平方数
for(int i=1;i<=n;i++)
{
ll k=sqrt(a[i]);
// 有一个不是直接输出 No
if(k*k!=a[i])
{
cout<<"No\n";
return;
}
}
// n 个数都是完全平方数 输出Yes
cout<<"Yes\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
cin >> _;
while (_--) solve();
return 0;
}
问题 J: 奶龙列阵（hard version）
解题思路
首先感谢一下陌队提名我为奶龙大王，没想到居然是压轴题。
建议先看一下前面 F 题的题解再来看这个。
这题和 F 题的区别在：
- 列阵方式不一样，F 题的第 k 排有k个奶龙，这题的第 k 排有 2k-1个奶龙。
- 数据大小不一样，F 题只有一组数据，这题有 T 组数据（T <= 1000000）。
和 F 题同样的分析：
奇数排的奶龙数量依次是：1，5，9，13，17，21，25
偶数排的奶龙数量依次是：3，7，11，15，19，23，27
可以得出：
奇数排的通项公式：an = 4n - 3 ，
求和公式：Sn = n(2n - 1) ;
偶数排的通项公式：an = 4n - 1 ，
求和公式：Sn = n(2n + 1) ;
思路和 F 是一样的只不过是最后的通项公式和求和公式不一样
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
// 感觉数据挺大的还是开ll好一点
ll n,a,b,c;
bool check(ll mid)
{
// x 为奇数排的数量 y 为偶数排的数量
ll x=mid/2+(mid%2),y=mid/2;
// sum1 为奇数排需要的奶龙数量 sum2 为偶数排
ll sum1=x*(2*x-1),sum2=y*(2*y+1);
// 如果奶龙数量大于所有奶龙，则不符合题意
if(sum1+sum2>n) return false;
// 假设奇数排举左手 偶数排举右手
// 注意d1 d2 不能小于 0
ll d1=sum1-a,d2=sum2-b;
d1=max(d1,0LL);d2=max(d2,0LL);
// 符合题意
if(d1+d2<=c) return true;
// 假设奇数排举右手 偶数排举左手
d1=sum2-a,d2=sum1-b;
d1=max(d1,0LL);d2=max(d2,0LL);
if(d1+d2<=c) return true;
// 如果上述没有符合题意的情况，则不符合题意
return false;
}
void solve()
{
cin>>a>>b>>c;
n=a+b+c;
// 确定排数的左右边界，最少为 0 排，最多不超过 n 排
ll l=0,r=n+1;
// 二分
while(l+1!=r)
{
ll mid=(l+r)>>1;
// 判断是否符合题意
if(check(mid)) l=mid;
else r=mid;
}
// 输出答案，二分中始终保证 l 排符合题目的要求
cout<<l<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
// 多组数据输入
cin >> _;
while (_--) solve();
return 0;
}
结语
想来想去还是记录一下今年的新生赛吧，毕竟明年还是个未知数，也希望明年我还有能力写题解吧。
最后祝大家天天开心，早日脱单٩(๑^ o ^๑)۶
标签：int,题解,ll,long,2024,程序设计,using,代码,奶龙 From： https://www.cnblogs.com/jin1/p/18627817