迟来的题解

本文更新到个人主页中，后续如果有任何修正变动也只会在网页端更新~

特别鸣谢小羽毛在羽猫球一题的题解：) 感谢兴航学弟在T3的题解。

比赛链接：https://www.luogu.com.cn/contest/196515

T1

签到题，所有参与选手均满分。略。

T2

https://www.luogu.com.cn/article/37n1idam

T3

在题目中的提示已经很显然了，如果我们让所有的数都有某个公因子，那么最简单的办法就是让所有数都是偶数。

而刚好在题目中的操作，其实就是两个数相乘。所以最理想的情况就是 奇数都去乘以偶数变成偶数。

关于这里的思路，xh学弟是这样讲的：

最终要使整个序列的最大公约数大于 \(1\)，实际上就是要使最后序列中每一个数字都有共同的因子。

假设我们确定了因子是谁，就只需要把不含该因子的数字乘到含该因子的数字上就可以了，操作次数就是序列中不含该因子数字的个数。

例如序列 \([3，6，9，7]\):
显然 \(3\) 是被包含最多的因子，只需要对 \(7\) 操作一次，所以操作次数为一。

问题转化为如何找到这个因子，由于题中给到的区间是连续的，每两个连续的数字中间一定有一个偶数，所以这个因子就是 \(2\)，区间奇数的数量就是操作次数。

无论如何，最终我们的操作次数就变成了区间中奇数的数量。

需要注意的是对于长度为1的情况需要特殊判断。

如果你能过样例，你基本也能拿到满分。

yxhのstd：（也可以看压缩包里的，zzt太懒惰了，懒得把几个合并到一起。)

#include <iostream>
using namespace std;
int codd(int x){ return x/2+x%2; }
int main(){
    int t;cin>>t;
    while(t--){
        bool flag=0;
        int l,r,k;cin>>l>>r>>k;
        if(codd(r)-codd(l-1)<=k) flag=1;
        if(l==r){
            flag=(l==1)?0:1;
        } 
        cout<<(flag?"YES":"NO")<<endl;
    }
}

T4

崽崽兔的想法太天才了

我们不妨把新数列的前几项列出来：

原本的f函数：

我们将常数项提取出来，再将a前面的系数项提取出来，分别列出常数表和系数表（b表和k表）

b表：

k表：

相信对斐波那契数列熟悉的你一定发现了，我们的b表和k表都是符合斐波那契推理规律的！

那么我们设定使用第i项，可以列出如下方程： b_i + k_i * i = x，经过移项，可以直接算出 i = (x-b_i)/k_i

那么我们经过预处理，将b表和k表维护出来。接下来从小到大的枚举i，经过以上公式可以快速判断出枚举的i是否能作为方程式的解。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e9;
const int maxk = 1e5;
int k[maxk+10],b[maxk+10];
int main() {
	//freopen("fibonacci10.in","r",stdin);
	//freopen("fibonacci10.out","w",stdout);
	k[1]=0; k[2]=1;
	b[1]=1; b[2]=0;
	for(int i=3;i<=maxk;i++) {
		k[i]=k[i-1]+k[i-2];
		b[i]=b[i-1]+b[i-2];
	}
	int t,x;
	cin>>t;
	for(int zzt=1;zzt<=t;zzt++) {
		cin>>x;
		cout<<2<<" "<<x<<endl;
		for(int i=3;i<=1e5;i++) {
			if(b[i]>=x) break;
			if((x-b[i]) % k[i] == 0) {
				cout<<i<<" "<<(x-b[i])/k[i]<<endl;
			}
		}
	}
}

出题人的小心得

由于这种宣发比赛的形式无论是对于twt工作室，还是对于出题人本人，都是一种全新的尝试，故留下一点反思。

关于T1这种纯签到题太省事太简单，后面可能考虑加大一点难度。

T2这种纯板子题也没有思考的价值，对于新生同学来说，完全没接触过动态规划，只靠暴力也很难得到部分分。纯dp不带优化有60，难写的搜索拿30.这其实是不理想的。

T3这种题就是很好的范式，我很满意！有思维高度，有乐趣，只靠高中的数学基础就可以推出来思考出来，这能让大伙感受到算法本身的乐趣。虽然对于高手一看奇偶性就能一眼秒。但是也算优秀题目了。可惜本次排的比较蠢，很多同学被T2劝退就不看了。

T4只能勉强及格，看似是方程之类的其实还是找规律的题目。如果找规律猜规律，我认为更理想的情况是猜测表象更复杂但结论更直观甚至简单的问题。这样才好玩嘛，但是类似的题目很难控制得分。没法送部分分出去。

总结

感谢大家的捧场配合，作为小萌新举办萌新欢乐赛，居然有这么多人捧场，受宠若惊。

希望各位都能找到自己热爱的领域并且为之努力，道阻且长，行则将至。