网站后台管理界面模板,易联网站制作,阿里云 wordpress 区别,外贸网络推广的公司比赛链接
官方题解
这场基本都是数学题#xff0c;官方题解讲的还不错#xff0c;F能听懂的话其实不难。E是一个球盒模型的组合问题#xff0c;F是化简递推式#xff0c;成环时的解决方法很不错。 A 困难数学题
思路#xff1a;
一个数异或两次结果为 0 0 0#xff…比赛链接
官方题解
这场基本都是数学题官方题解讲的还不错F能听懂的话其实不难。E是一个球盒模型的组合问题F是化简递推式成环时的解决方法很不错。 A 困难数学题
思路
一个数异或两次结果为 0 0 0异或四次结果也是 0 0 0
code
#include iostream
#include cstdio
using namespace std;int main(){cout0endl;return 0;
}B 构造序列
思路
如果正负数个数差不多正常排就可以。
但是如果有一种数数量很多比如正数很多我们只能正负相间来排不过我们可以让首尾为正数这样用到的正数就会尽可能多假设一共有 2 n 1 2n1 2n1 个数那么正数就会用到 n 1 n1 n1 个。
所以看一下多的那种数是否超过 少的数1 个多出来的部分就用不到了。
code
pypy3 的代码不过应该挺好理解的
x,y [int(i) for i in input().split()]if x y:t xx yy tif y x1:print(2*x1)
else:print(xy)C 连点成线
思路
其实可以发现问题可以转化成对每一行找两头的点算距离以及对每一列找两头的点算距离因为中间的点一定不可能是最长的所以不用看。而且对于列的计算我们可以将行列坐标翻转然后按行来做。
那么我们现在只需要对每一行找两头的点算距离之后翻转行列坐标再算一次即可。这一步做法很多先排序可以枚举行坐标然后双指针找两端的点也可以按横坐标升序来枚举点的横坐标二分来找两端的纵坐标。
code
#include iostream
#include cstdio
#include algorithm
using namespace std;
#define pii pairint,int
const int maxn1e55;int n,m;
pii a[maxn];int calc(){//x相同 y的最大差值 sort(a1,am1);int ans0;for(int l1,r;lm;lr1){rupper_bound(a1,am1,pii(a[l].first,n))-a-1;ansmax(ans,a[r].second-a[l].second);}return ans;
}int main(){cinnm;for(int i1;im;i){auto [x,y]a[i];cinxy;}int anscalc();for(int i1;im;i){auto [x,y]a[i];swap(x,y);}ansmax(ans,calc());coutansendl;return 0;
} D 我们N个真是太厉害了
思路
说白了就是给你 n n n 个数问你用这些数无法表示的最小的数是多少。
我们可以对 n n n 个数排个序假设用前 i − 1 i-1 i−1 个数最大可以表示到 m x mx mx也就是说前 i − 1 i-1 i−1 个数可以表示 0 ∼ m x 0\sim mx 0∼mx 任何一个数如果 a i ≤ m x 1 a_i\le mx1 ai≤mx1那么低于 m x mx mx 的数可以用前 i − 1 i-1 i−1 个数来凑而高于 m x mx mx 的数可以通过使用 a i a_i ai 来凑最多可以凑到 a i m x a_imx aimx。
否则如果 a i m x 1 a_i mx1 aimx1那么就会出现至少 m x 1 mx1 mx1 无法被表示的情况因为我们已经排好序了后续的 a j a_j aj 肯定都 m x 1 mx1 mx1所以最小的无法表示的数就是 m x 1 mx1 mx1。
我们维护 m x mx mx如果能继续往下凑就加入 m x mx mx否则我们就找到了第一个无法表示的数也就是答案。
code
#include iostream
#include cstdio
#include algorithm
using namespace std;
const int maxn1e55;int T,n;
int a[maxn];int calc(){int mx0;for(int i1;in;i){if(a[i]mx1)return mx1;else {mxa[i];if(mxn)return -1;}}return -1;
}int main(){cinT;while(T--){cinn;for(int i1;in;i)cina[i];sort(a1,an1);int anscalc();if(~ans)coutansendl;else coutCool!endl;}return 0;
}E 折返跑
思路
因为两边的杆子要占两个格子所以实际上能移动的距离是 n − 2 n-2 n−2。因为跑 m m m 趟第一趟和最后一趟不移动杆子所以实际上就只移动了 m − 1 m-1 m−1 次杆子。
我们每次至少移动一格杆子不能把杆子移动的总长度超过两个杆子的总距离。而且我们还能把移动左右两边的杆子都看作是移动一根杆子因为不管移动哪个杆子两个杆子的相对距离变化是一样的。
这就有点像球盒模型了。我们把一格看成一个小球把每一趟移动杆子的距离看成盒子把球放入盒子看成让这一趟移动杆子的距离增加一格。那么这就是一个将 n − 2 n-2 n−2 个相同的小球放入 m − 1 m-1 m−1 个不同盒子不能空盒可以剩球的球盒模型。
球盒模型不可以剩球但是我们可以多加入一个新的盒子将 n − 2 n-2 n−2 个相同的小球放入 m m m 个不同盒子放入新盒的球看作剩下的球就行了也就是垃圾桶。这样的话就转化成了经典的球盒模型使用隔板法来做。
将 n − 2 n-2 n−2 个相同的小球放入 m m m 个不同盒子不能空盒。既然不能空盒就向每个盒子里预先加入一个小球 m − 1 m-1 m−1 个不能空盒的盒子各放入一个球剩下 n − m − 1 n-m-1 n−m−1 个这样就转化成了 将 n − m − 1 n-m-1 n−m−1 个相同的小球放入 m m m 个不同盒子可以空盒 的问题了向 n − m − 1 ( m − 1 ) n − 2 n-m-1(m-1)n-2 n−m−1(m−1)n−2 个位置上放入 m − 1 m-1 m−1 个隔板其余位置放小球这样分割出来的 m m m 个区间看作放入盒子的方法方案数就是 C n − 2 m − 1 C_{n-2}^{m-1} Cn−2m−1 了。
code
#include iostream
#include cstdio
using namespace std;
const int maxn1e65;
const int N1e6;
typedef long long ll;
const ll mod1e97;ll qpow(ll a,ll b){ll basea%mod,ans1;b%mod;while(b){if(b1)ansans*base%mod;basebase*base%mod;b1;}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(){cinT;fac[0]1;for(int i1;iN;i)fac[i]fac[i-1]*i%mod;ifac[N]inv(fac[N]);for(int iN;i1;i--)ifac[i-1]ifac[i]*i%mod;while(T--){cinnm;coutC(n-2,m-1)endl;}return 0;
}F 口吃
思路
这个题在官方题解里讲的其实挺好的。
假设 f i f_i fi 表示讲第 i i i 个字的期望讲字的个数根据题意可知 f n 1 f_n1 fn1。根据题意不难列出 f 1 1 a 1 a 1 b 1 f 2 b 1 a 1 b 1 f 1 f_11\dfrac{a_1}{a_1b_1}f_2\dfrac{b_1}{a_1b_1}f_1 f11a1b1a1f2a1b1b1f1 f i 1 a i 2 ( a i b i ) 2 f i 1 2 a i b i ( a i b i ) 2 f i b i 2 ( a i b i ) 2 f i − 1 f_i1\dfrac{a_i^2}{(a_ib_i)^2}f_{i1}\dfrac{2a_ib_i}{(a_ib_i)^2}f_{i}\dfrac{b_i^2}{(a_ib_i)^2}f_{i-1} fi1(aibi)2ai2fi1(aibi)22aibifi(aibi)2bi2fi−1 整理可得 f 1 f 2 a 1 b 1 a 1 f_1f_2\dfrac{a_1b_1}{a_1} f1f2a1a1b1 ( 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^2b_i^2)f_ia_i^2f_{i1}b_i^2f_{i-1}(a_ib_i)^2 (ai2bi2)fiai2fi1bi2fi−1(aibi)2 发现问题比较麻烦因为这个递推式没法递推如果我们从小到大递推的话我们算 f i f_i fi 需要预先知道 f i 1 f_{i1} fi1 的值但是我们又没算出来而算 f i 1 f_{i1} fi1 的值又需要知道 f i f_i fi 的值这时候就成环了或者叫死锁。
如果我们能把 f i 1 f_{i1} fi1 或 f i − 1 f_{i-1} fi−1 的其中一个转化为 f i f_i fi就可以打破这个死锁局面了。发现第一个 f 1 f 2 a 1 b 1 a 1 f_1f_2\dfrac{a_1b_1}{a_1} f1f2a1a1b1 的式子可以带入到当 i 2 i2 i2 时的 ( a 2 2 b 2 2 ) f 2 a 2 2 f 3 b 2 2 f 1 ( a 2 b 2 ) 2 (a_2^2b_2^2)f_2a_2^2f_{3}b_2^2f_{1}(a_2b_2)^2 (a22b22)f2a22f3b22f1(a2b2)2 中这样可以把 f 1 f_1 f1 转化为 f 2 f_2 f2这时整个式子就变为了 f 2 f_2 f2 与 f 3 f_3 f3 的关系式化简后会得到一个形为 f 2 P ∗ f 3 Q f_2P*f_3Q f2P∗f3Q 的形式。
而这个 f 2 f_2 f2 与 f 3 f_3 f3 的关系式可以类似地再次带入到 i 3 i3 i3 时的式子 2 2 2 里同理可以得到 f 3 f_3 f3 与 f 4 f_4 f4 的关系式是一个形如 f 3 P ∗ f 4 Q f_3P*f_4Q f3P∗f4Q 的关系式同理继续带入。
发现我们可以去递推算每一对 P , Q P,Q P,Q然后从 n n n 往 1 1 1 递推 f 1 f_1 f1 即可。
假设 f i − 1 P i − 1 ∗ f i Q i − 1 f_{i-1}P_{i-1}*f_{i}Q_{i-1} fi−1Pi−1∗fiQi−1带入式子 2 2 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^2b_i^2)f_ia_i^2f_{i1}b_i^2f_{i-1}(a_ib_i)^2 (ai2bi2)fiai2fi1bi2fi−1(aibi)2 ( a i 2 b i 2 ) f i a i 2 f i 1 b i 2 ( P i − 1 ∗ f i Q i − 1 ) ( a i b i ) 2 (a_i^2b_i^2)f_ia_i^2f_{i1}b_i^2(P_{i-1}*f_{i}Q_{i-1})(a_ib_i)^2 (ai2bi2)fiai2fi1bi2(Pi−1∗fiQi−1)(aibi)2 ( a i 2 b i 2 ) f i a i 2 f i 1 b i 2 P i − 1 ∗ f i b i 2 Q i − 1 ( a i b i ) 2 (a_i^2b_i^2)f_ia_i^2f_{i1}b_i^2P_{i-1}*f_{i}b_i^2Q_{i-1}(a_ib_i)^2 (ai2bi2)fiai2fi1bi2Pi−1∗fibi2Qi−1(aibi)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 (a_i^2b_i^2-b_i^2P_{i-1})f_ia_i^2f_{i1}b_i^2Q_{i-1}(a_ib_i)^2 (ai2bi2−bi2Pi−1)fiai2fi1bi2Qi−1(aibi)2 f i a i 2 a i 2 b i 2 − b i 2 P i − 1 f i 1 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\dfrac{a_i^2}{a_i^2b_i^2-b_i^2P_{i-1}}f_{i1}\dfrac{b_i^2Q_{i-1}(a_ib_i)^2}{a_i^2b_i^2-b_i^2P_{i-1}} fiai2bi2−bi2Pi−1ai2fi1ai2bi2−bi2Pi−1bi2Qi−1(aibi)2因此 P i a i 2 a i 2 b i 2 − b i 2 P i − 1 , Q i 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\dfrac{a_i^2}{a_i^2b_i^2-b_i^2P_{i-1}},Q_i\dfrac{b_i^2Q_{i-1}(a_ib_i)^2}{a_i^2b_i^2-b_i^2P_{i-1}} Piai2bi2−bi2Pi−1ai2,Qiai2bi2−bi2Pi−1bi2Qi−1(aibi)2
code
#include iostream
#include cstdio
using namespace std;
typedef long long ll;
const int maxn1e55;
const ll mod1e97;ll qpow(ll a,ll b){ll base(a%modmod)%mod,ans1;b%mod;while(b){if(b1)ansans*base%mod;basebase*base%mod;b1;}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(){cinn;for(int i1;in;i)cina[i];for(int i1;in;i)cinb[i];p[1]1;q[1](a[1]b[1])%mod*inv(a[1])%mod;for(int i2;in;i){ll Aa[i]*a[i]%mod,Bb[i]*b[i]%mod,C(a[i]b[i])*(a[i]b[i])%mod;ll tinv(((AB-B*p[i-1])%modmod)%mod);p[i]A*t%mod;q[i](B*q[i-1]C)%mod*t%mod;}f[n]1;for(int in-1;i1;i--){f[i]p[i]*f[i1]q[i];f[i]%mod;}coutf[1];return 0;
}
