牛客周赛 Round 60（A,B,C,D,E,F）

比赛链接

官方题解

这场基本都是数学题，官方题解讲的还不错，F能听懂的话其实不难。E是一个球盒模型的组合问题，F是化简递推式，成环时的解决方法很不错。

---

A 困难数学题

思路：

一个数异或两次结果为 $0$，异或四次结果也是 $0$

code：

#include <iostream>
#include <cstdio>
using namespace std;int main(){cout<<0<<endl;return 0;
}

---

B 构造序列

思路：

如果正负数个数差不多，正常排就可以。

但是如果有一种数数量很多，比如正数很多，我们只能正负相间来排，不过我们可以让首尾为正数，这样用到的正数就会尽可能多，假设一共有 $2n+1$ 个数，那么正数就会用到 $n+1$ 个。

所以看一下多的那种数是否超过 少的数+1 个，多出来的部分就用不到了。

code：

pypy3 的代码，不过应该挺好理解的

x,y = [int(i) for i in input().split()]if x > y:t = xx = yy = tif y > x+1:print(2*x+1)
else:print(x+y)

---

C 连点成线

思路：

其实可以发现问题可以转化成对每一行找两头的点算距离，以及对每一列找两头的点算距离，因为中间的点一定不可能是最长的，所以不用看。而且对于列的计算，我们可以将行列坐标翻转，然后按行来做。

那么我们现在只需要对每一行找两头的点算距离，之后翻转行列坐标再算一次即可。这一步做法很多，先排序，可以枚举行坐标然后双指针找两端的点，也可以按横坐标升序来枚举点的横坐标，二分来找两端的纵坐标。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define pii pair<int,int>
const int maxn=1e5+5;int n,m;
pii a[maxn];int calc(){//x相同 y的最大差值 sort(a+1,a+m+1);int ans=0;for(int l=1,r;l<=m;l=r+1){r=upper_bound(a+1,a+m+1,pii(a[l].first,n))-a-1;ans=max(ans,a[r].second-a[l].second);}return ans;
}int main(){cin>>n>>m;for(int i=1;i<=m;i++){auto &[x,y]=a[i];cin>>x>>y;}int ans=calc();for(int i=1;i<=m;i++){auto &[x,y]=a[i];swap(x,y);}ans=max(ans,calc());cout<<ans<<endl;return 0;
} 

---

D 我们N个真是太厉害了

思路：

说白了就是给你 $n$ 个数，问你用这些数无法表示的最小的数是多少。

我们可以对 $n$ 个数排个序，假设用前 $i-1$ 个数最大可以表示到 $mx$（也就是说前 $i-1$ 个数可以表示 $0\sim mx$ 任何一个数），如果 $a_i\le mx+1$，那么低于 $mx$ 的数可以用前 $i-1$ 个数来凑，而高于 $mx$ 的数可以通过使用 $a_i$ 来凑，最多可以凑到 $a_i+mx$。

否则如果 $a_i>mx+1$，那么就会出现至少 $mx+1$ 无法被表示的情况，因为我们已经排好序了，后续的 $a_j$ 肯定都 $>mx+1$，所以最小的无法表示的数就是 $mx+1$。

我们维护 $mx$，如果能继续往下凑就加入 $mx$，否则我们就找到了第一个无法表示的数，也就是答案。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+5;int T,n;
int a[maxn];int calc(){int mx=0;for(int i=1;i<=n;i++){if(a[i]>mx+1)return mx+1;else {mx+=a[i];if(mx>=n)return -1;}}return -1;
}int main(){cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);int ans=calc();if(~ans)cout<<ans<<endl;else cout<<"Cool!"<<endl;}return 0;
}

---

E 折返跑

思路：

因为两边的杆子要占两个格子，所以实际上能移动的距离是 $n-2$。因为跑 $m$ 趟，第一趟和最后一趟不移动杆子，所以实际上就只移动了 $m-1$ 次杆子。

我们每次至少移动一格杆子，不能把杆子移动的总长度超过两个杆子的总距离。而且我们还能把移动左右两边的杆子都看作是移动一根杆子，因为不管移动哪个杆子，两个杆子的相对距离变化是一样的。

这就有点像球盒模型了。我们把一格看成一个小球，把每一趟移动杆子的距离看成盒子，把球放入盒子看成让这一趟移动杆子的距离增加一格。那么这就是一个将 $n-2$ 个相同的小球放入 $m-1$ 个不同盒子，不能空盒，可以剩球的球盒模型。

球盒模型不可以剩球，但是我们可以多加入一个新的盒子，将 $n-2$ 个相同的小球放入 $m$ 个不同盒子，放入新盒的球看作剩下的球就行了（也就是垃圾桶）。这样的话就转化成了经典的球盒模型，使用隔板法来做。

将 $n-2$ 个相同的小球放入 $m$ 个不同盒子，不能空盒。既然不能空盒，就向每个盒子里预先加入一个小球，$m-1$ 个不能空盒的盒子各放入一个，球剩下 $n-m-1$ 个，这样就转化成了 将 $n-m-1$ 个相同的小球放入 $m$ 个不同盒子，可以空盒 的问题了，向 $n-m-1+(m-1)=n-2$ 个位置上放入 $m-1$ 个隔板，其余位置放小球，这样分割出来的 $m$ 个区间看作放入盒子的方法，方案数就是 $C_{n-2}^{m-1}$ 了。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e6+5;
const int N=1e6;
typedef long long ll;
const ll mod=1e9+7;ll qpow(ll a,ll b){ll base=a%mod,ans=1;b%=mod;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans;
}
ll inv(ll x){return qpow(x,mod-2);}int T,n,m;
ll fac[maxn],ifac[maxn];ll C(ll x,ll y){//C_x^yreturn fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}int main(){cin>>T;fac[0]=1;for(int i=1;i<=N;i++)fac[i]=fac[i-1]*i%mod;ifac[N]=inv(fac[N]);for(int i=N;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;while(T--){cin>>n>>m;cout<<C(n-2,m-1)<<endl;}return 0;
}

---

F 口吃

思路：

这个题在官方题解里讲的其实挺好的。

假设 $f_i$ 表示讲第 $i$ 个字的期望讲字的个数，根据题意可知 $f_n=1$。根据题意不难列出：$$f_1=1+\frac{a_1}{a_1+b_1}{f}_2+\frac{b_1}{a_1+b_1}{f}_1$$$$f_i=1+\frac{a_i^2}{(a_i+b_i{)}^2}{f}_{i+1}+\frac{2a_i{b}_i}{(a_i+b_i{)}^2}{f}_i+\frac{b_i^2}{(a_i+b_i{)}^2}{f}_{i-1}$$
整理可得：$$f_1=f_2+\frac{a_1+b_1}{a_1}$$$$(a_i^2+b_i^2)f_i=a_i^2{f}_{i+1}+b_i^2{f}_{i-1}+(a_i+b_i{)}^2$$
发现问题比较麻烦，因为这个递推式没法递推，如果我们从小到大递推的话，我们算 $f_i$ 需要预先知道 $f_{i+1}$ 的值，但是我们又没算出来，而算 $f_{i+1}$ 的值又需要知道 $f_i$ 的值，这时候就成环了（或者叫死锁）。

如果我们能把 $f_{i+1}$ 或 $f_{i-1}$ 的其中一个转化为 $f_i$，就可以打破这个死锁局面了。发现第一个 $f_1=f_2+\frac{a_1+b_1}{a_1}$ 的式子可以带入到当 $i=2$ 时的 $(a_2^2+b_2^2)f_2=a_2^2{f}_3+b_2^2{f}_1+(a_2+b_2{)}^2$ 中，这样可以把 $f_1$ 转化为 $f_2$，这时整个式子就变为了 $f_2$ 与 $f_3$ 的关系式，化简后会得到一个形为 $f_2=P\ast f_3+Q$ 的形式。

而这个 $f_2$ 与 $f_3$ 的关系式可以类似地再次带入到 $i=3$ 时的式子 $2$ 里，同理可以得到 $f_3$ 与 $f_4$ 的关系式，是一个形如 $f_3=P\ast f_4+Q$ 的关系式，同理继续带入。

发现我们可以去递推算每一对 $P,Q$，然后从 $n$ 往 $1$ 递推 $f_1$ 即可。

假设 $f_{i-1}=P_{i-1}\ast f_i+Q_{i-1}$，带入式子 $2$ 得：$$(a_i^2+b_i^2)f_i=a_i^2{f}_{i+1}+b_i^2{f}_{i-1}+(a_i+b_i{)}^2$$$$(a_i^2+b_i^2)f_i=a_i^2{f}_{i+1}+b_i^2(P_{i-1}\ast f_i+Q_{i-1})+(a_i+b_i{)}^2$$$$(a_i^2+b_i^2)f_i=a_i^2{f}_{i+1}+b_i^2{P}_{i-1}\ast f_i+b_i^2{Q}_{i-1}+(a_i+b_i{)}^2$$$$(a_i^2+b_i^2-b_i^2{P}_{i-1})f_i=a_i^2{f}_{i+1}+b_i^2{Q}_{i-1}+(a_i+b_i{)}^2$$$$f_i=\frac{a_i^2}{a_i^2+b_i^2-b_i^2{P}_{i-1}}{f}_{i+1}+\frac{b_i^2{Q}_{i-1}+(a_i+b_i{)}^2}{a_i^2+b_i^2-b_i^2{P}_{i-1}}$$因此：$$P_i=\frac{a_i^2}{a_i^2+b_i^2-b_i^2{P}_{i-1}},Q_i=\frac{b_i^2{Q}_{i-1}+(a_i+b_i{)}^2}{a_i^2+b_i^2-b_i^2{P}_{i-1}}$$

code：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const ll mod=1e9+7;ll qpow(ll a,ll b){ll base=(a%mod+mod)%mod,ans=1;b%=mod;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans;
}
ll inv(ll x){return qpow(x,mod-2);}int n;
ll a[maxn],b[maxn];
ll p[maxn],q[maxn];
ll f[maxn];int main(){cin>>n;for(int i=1;i<n;i++)cin>>a[i];for(int i=1;i<n;i++)cin>>b[i];p[1]=1;q[1]=(a[1]+b[1])%mod*inv(a[1])%mod;for(int i=2;i<n;i++){ll A=a[i]*a[i]%mod,B=b[i]*b[i]%mod,C=(a[i]+b[i])*(a[i]+b[i])%mod;ll t=inv(((A+B-B*p[i-1])%mod+mod)%mod);p[i]=A*t%mod;q[i]=(B*q[i-1]+C)%mod*t%mod;}f[n]=1;for(int i=n-1;i>=1;i--){f[i]=p[i]*f[i+1]+q[i];f[i]%=mod;}cout<<f[1];return 0;
}