建网站需要用到什么软件,赚钱游戏无广告无门槛,国外怎么做直播网站,网站栏目建设图比赛链接
官方讲解
很幸运参加了内测#xff0c;不过牛客这消息推送天天发广告搞得我差点错过内测消息#xff0c;差点进小黑屋#xff0c;好在开赛前一天看到了。
这场不难#xff0c;ABC都很签到#xff0c;D是个大讨论#xff0c;纯屎#xff0c;E是需要对循环移位…比赛链接
官方讲解
很幸运参加了内测不过牛客这消息推送天天发广告搞得我差点错过内测消息差点进小黑屋好在开赛前一天看到了。
这场不难ABC都很签到D是个大讨论纯屎E是需要对循环移位进行处理和转化转化后很简单如果看不懂我写的可以看官方的讲解画图可能会比较好理解F是数学需要分开计算贡献最后再来一步范德蒙德卷积优化知识点不难就是比较冷门。 A TD
思路
签到
code
#include iostream
#include cstdio
using namespace std;int a,b;int main(){cinab;cout1.0*a/b;return 0;
}B 你好这里是牛客竞赛
思路
如果是以 https://www.nowcoder.com 或者 www.nowcoder.com 作为前缀开头的话那就是牛客主站输出 Nowcoder。如果是以 https://ac.nowcoder.com 或者 ac.nowcoder.com 作为前缀开头的话那就是牛客竞赛输出 Ac。剩下的就是其他网站。
找子串可以用 s t r i n g string string 自带的 f i n d find find 方法它会返回第一个匹配的子串的下标作为前缀开头的话就看 f i n d find find 的值是否为 0 0 0 即可是 0 0 0 就说明一开始就匹配上了也就是前缀。
code
#include iostream
#include cstdio
#include cstring
using namespace std;int T;
string s;int main(){cinT;while(T--){cins;if(s.find(https://ac.nowcoder.com)0 || s.find(ac.nowcoder.com)0)coutAcendl;else if(s.find(https://www.nowcoder.com)0 || s.find(www.nowcoder.com)0)coutNowcoderendl;else coutNoendl;}return 0;
}C 逆序数
思路
一个序列里对任意的一对数只有正序和逆序两种关系不是逆序就是正序。在一个序列里任取两个数的取法有 C n 2 n ∗ ( n − 1 ) 2 C_n^2\dfrac{n*(n-1)}2 Cn22n∗(n−1) 种可能也就是一共有这么多个关系除了 k k k 个逆序剩下的就有 n ∗ ( n − 1 ) 2 − k \dfrac{n*(n-1)}2-k 2n∗(n−1)−k 个正序。
而翻转之后正序就会变成逆序逆序变成正序不管你这个集合是怎么凑的翻转之前是 k k k 个逆序 n ∗ ( n − 1 ) 2 − k \dfrac{n*(n-1)}2-k 2n∗(n−1)−k 个正序翻转之后就是 n ∗ ( n − 1 ) 2 − k \dfrac{n*(n-1)}2-k 2n∗(n−1)−k 个逆序 k k k 个正序。
code
#include iostream
#include cstdio
using namespace std;long long n,k;int main(){cinnk;coutn*(n-1)/2-kendl;return 0;
}D 构造mex
思路
我嘞个大讨论啊屎题。我已经能预想到那好看的通过率了。
我讨论的方法如下
当 k 0 k0 k0 时就尽量让每个数都是 1 1 1最后一个数放剩余的还没用掉的值。 当 s n sn sn 时这时甚至做不到让每个位置都是 1 1 1一定会有位置为 0 0 0因此无解当 s ≥ n s\ge n s≥n 时就可以用上面的思路来凑。 当 k ̸ 0 k\not0 k0 时先凑出 0 , 1 , 2 , … , k − 1 0,1,2,\dots,k-1 0,1,2,…,k−1这样 m e x mex mex 就等于 k k k 了然后再把剩余的值放在后面剩余位置就都放 0 0 0。前面 0 , 1 , 2 , … , k − 1 0,1,2,\dots,k-1 0,1,2,…,k−1 一共 k k k 个数总和为 t o t k ∗ ( k − 1 ) 2 tot\dfrac{k*(k-1)}2 tot2k∗(k−1) 有可能 s t o t stot stot这时连前面的 k k k 个数都凑不出来因此无解。有可能 s t o t stot stot这时正好没有剩余的数因此凑出前 k k k 个数后后面都可以补 0 0 0 当位置个数 n k nk nk 时位置不够因此无解。 n ≥ k n\ge k n≥k 时位置够用上面的方法来凑。 有可能 s − t o t k s-totk s−totk这时不能直接把剩余的值 s − t o t s-tot s−tot 放在后面必须先拆出一个单独的 1 1 1 然后再把 s − t o t − 1 s-tot-1 s−tot−1 放下后面补 0 0 0。 有可能 s − t o t k 1 s-totk1 s−totk1这时做不到先拆出一个单独的 1 1 1 然后再把 s − t o t − 1 s-tot-1 s−tot−1 放下因为也会冲突这时无解。有可能位置个数不够即 n k 2 nk2 nk2这时无解剩余情况按上面的方法来凑。 按上面的方法来凑需要至少 k 1 k1 k1 个位置如果位置不够则无解否则按上面的方法来凑。
code
#include iostream
#include cstdio
using namespace std;
typedef long long ll;ll T,s,n,k;int main(){cinT;while(T--){cinsnk;if(k0){if(sn)coutNOendl;else {coutYESendl;couts-n1 ;for(int i1;in-1;i)cout1 ;coutendl;}}else {ll totk*(k-1)/2;if(stot)coutNOendl;else {if(k1 s-tot1)coutNOendl;else {if(s-tot0){if(nk)coutNOendl;else {coutYESendl;for(int i0;ik;i)couti ;for(int ik1;in;i)cout0 ;coutendl;}}else if(s-totk){if(nk2)coutNOendl;else {coutYESendl;for(int i0;ik;i)couti ;cout1 s-tot-1 ;for(int ik3;in;i)cout0 ;coutendl;}}else {if(nk1)coutNOendl;else {coutYESendl;for(int i0;ik;i)couti ;couts-tot ;for(int ik2;in;i)cout0 ;coutendl;}}}}}}return 0;
}E 小红的X型矩阵
思路
对一个正方形我们可以统计出它两个对角线上有多少个 1 1 1对角线上的位置总个数减去对角线上 1 1 1 的个数就是对角线上 0 0 0 的个数也就是需要用操作 1 1 1 把 0 0 0 翻转成 1 1 1 的次数。然后再统计出一共有多少个 1 1 1减去对角线上 1 1 1 的个数就是对角线以外其他位置上 1 1 1 的个数也就是需要需要用操作 1 1 1 把 1 1 1 翻转成 0 0 0 的次数。这个快速统计对角线上 1 1 1 的个数可以用斜着的前缀和来做。
这个循环移动我们可以看作是移动这两个对角线但是我们对角线一旦循环移动了就会断成两段就很难计数了而且对于 n n n 为奇数的情况两个对角线还会有交点我们交点只能算一次但是用前缀和来快速计数就会算两次很麻烦。
这时我们可以参考数组的循环移位把数组复制一遍到后面。我们可以把这个正方形往 x y xy xy 轴各复制一遍这样从 ( i , j ) (i,j) (i,j) 到 ( i n − 1 , j n − 1 ) (in-1,jn-1) (in−1,jn−1) 的这个矩形就相当于原矩形向左循环移位 i − 1 i-1 i−1 次向上循环移位 j − 1 j-1 j−1 次。
我们枚举矩形的左上角坐标 ( i , j ) (i,j) (i,j)这样对每一个正方形都对应一个循环移位后的正方形统计所有正方形的答案然后取最小值即可。
注意 n n n 为奇数的时候中间会有一个交点前缀和对两个对角线计数会重复算一次需要减掉。
code
#include iostream
#include cstdio
using namespace std;
const int maxn1005;int n,a[maxn1][maxn1],s1[maxn1][maxn1],s2[maxn1][maxn1],tot;int main(){cinn;for(int i1;in;i)for(int j1;jn;j){cina[i][j];tota[i][j];a[in][j]a[i][jn]a[in][jn]a[i][j];}for(int i1;i2*n;i)for(int j1;j2*n;j)s1[i][j]s1[i-1][j-1]a[i][j];for(int i1;i2*n;i)for(int j1;j2*n;j)s2[i][j]s2[i-1][j1]a[i][j];int ans1e9;for(int i1;in;i)for(int j1;jn;j){//枚举左上角坐标 int t0,t1s1[in-1][jn-1]-s1[i-1][j-1],t2s2[in-1][j]-s2[i-1][jn];tt1t2;if(n1){t-a[in/2][jn/2];ansmin(ans,(2*n-1)-ttot-t);}else {ansmin(ans,2*n-ttot-t);}}coutansendl;return 0;
}F 小红的数组回文值
思路
内测时写了一个很神秘的暴力结果过了然后被加强数据卡死了。。。这个暴力其实本质上和正解差不多就差一个范德蒙德卷积优化kuso。
这个题是求所有子序列的回文值但是我们显然不可能枚举出所有的子序列所以我们不妨转化一下视角看每一对数的贡献。
当一对数不同并且在某一个回文串中正好对应那么它就会产生一次贡献假设第 i i i 个位置和第 j j j 个位置的数在某一个回文串中对应并且 a i ̸ a j a_i\nota_j aiaj。怎么算出所有满足这两个数对应的回文串呢
我们可以在前 i − 1 i-1 i−1 个位置和后 n − j n-j n−j 个位置同时选出 k k k 个数在中间的 j − i − 1 j-i-1 j−i−1 个数中选若干个数这样就凑出一个 a i a_i ai 与 a j a_j aj 对应的回文串了。
假设前后各有 x , y x,y x,y 个数也就是 x i − 1 , y n − j xi-1,yn-j xi−1,yn−j那么选取的方案数就是 ∑ k 0 m i n { x , y } C x k ∗ C y k ∗ 2 n − x − y − 2 \sum_{k0}^{min\{x,y\}} C_x^k*C_y^k*2^{n-x-y-2} ∑k0min{x,y}Cxk∗Cyk∗2n−x−y−2。
因为 n 2000 n2000 n2000所以我们可以枚举 i , j i,j i,j算出对应的 x , y x,y x,y然后再枚举 k k k。这样就是一个 O ( n 3 ) O(n^3) O(n3) 的算法会 T T T但是如果我们如果能把枚举 k k k 的过程优化掉就可以压成 O ( n 2 ) O(n^2) O(n2) 的了。
还真能 2 n − x − y − 2 2^{n-x-y-2} 2n−x−y−2 和 k k k 无关可以提出来前面的这个 ∑ k 0 m i n { x , y } C x k ∗ C y k \sum_{k0}^{min\{x,y\}} C_x^k*C_y^k ∑k0min{x,y}Cxk∗Cyk我们不妨设 x y xy xy不然就交换 x , y x,y x,y则 ∑ k 0 x C x k ∗ C y k ∑ k 0 x C x x − k ∗ C y k \sum_{k0}^{x} C_x^k*C_y^k\sum_{k0}^{x} C_x^{x-k}*C_y^k ∑k0xCxk∗Cyk∑k0xCxx−k∗Cyk 这一步可以通过范德蒙德卷积优化得到 C x y x C_{xy}^{x} Cxyx。范德蒙德卷积讲解可以看 OI wiki。
code
#include iostream
#include cstdio
#include algorithm
#include vector
#include cstring
using namespace std;
const int maxn2e35;
typedef long long ll;
const ll mod1e97;int n,a[maxn];
ll qpow(ll a,ll b){ll ans1,basea%mod;b%mod;while(b){if(b1)ansans*base%mod;basebase*base%mod;b1;}return ans;
}
ll inv(ll x){return qpow(x,mod-2);}ll fac[maxn],ifac[maxn];
ll C(ll x,ll y){//C_x^yif(xy)return 0;return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}ll calc(ll x,ll y){if(xy)swap(x,y);return qpow(2,n-x-y-2)*C(xy,x)%mod;
}int main(){cinn;for(int i1;in;i)cina[i];fac[0]1;for(int i1;i2000;i)fac[i]fac[i-1]*i%mod;ifac[2000]inv(fac[2000]);for(int i2000;i1;i--)ifac[i-1]ifac[i]*i%mod;ll ans0;for(int i1;in;i)for(int ji1;jn;j)if(a[i]!a[j])ans(anscalc(i-1,n-j));cout(ans%modmod)%modendl;return 0;
}内测时成功卡AC的 O ( n 3 ) O(n^3) O(n3) 暴力代码虽然最后还是被卡掉了
#include iostream
#include cstdio
#include algorithm
#include vector
#include cstring
using namespace std;
const int maxn2e35;
typedef long long ll;
const ll mod1e97;int n,a[maxn],b[maxn];
ll qpow(ll a,ll b){ll ans1,basea%mod;b%mod;while(b){if(b1)ansans*base%mod;basebase*base%mod;b1;}return ans;
}
ll inv(ll x){return qpow(x,mod-2);}ll fac[maxn],ifac[maxn];
ll C(ll x,ll y){//C_x^yif(xy)return 0;return fac[x]*ifac[y]%mod*ifac[x-y]%mod;
}vectorint c[maxn];ll calc(ll x,ll y){ll ans0;for(int i0;imin(x,y);i)ans(ansC(x,i)*C(y,i))%mod;return qpow(2,n-x-y-2)*ans%mod;
}int main(){cinn;for(int i1;in;i)cina[i];memcpy(b,a,sizeof(b));sort(b1,bn1);int totunique(b1,bn1)-b-1;auto find[](int x)-int{return lower_bound(b1,bn1,x)-b;};for(int i1;in;i)a[i]find(a[i]);for(int i1;in;i)c[a[i]].push_back(i);fac[0]1;for(int i1;i2000;i)fac[i]fac[i-1]*i%mod;ifac[2000]inv(fac[2000]);for(int i2000;i1;i--)ifac[i-1]ifac[i]*i%mod;ll ans0;for(int i1;in;i){ans(ansC(n,i)*(i/2)%mod)%mod;}for(int i1;in;i){for(int l0;lc[i].size();l)for(int rl1;rc[i].size();r){ans(ans-calc(c[i][l]-1,n-c[i][r]))%mod;}}cout(ans%modmod)%modendl;return 0;
}
