2021牛客多校第一场题解
A题
题目大意：Alice和Bob轮流取石子，两堆分别为n和m，每次从一堆取k(k>0)，另一堆取s*k(s>=0)，输入为t组，每组输入n,m，问谁会赢。（t<1e4,n,m<5e3)
思路：f(i,j)表示输赢状态，1为必胜，0为必败，从当前必败推出f(i+k,j+sk)和f(i+sk,j+k)必胜。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
bitset<N> f[N];
int main(){
int t;
for(int S = 0;S <= 10000;S++){
for(int i = max(0,S-5000),j = S - i;i<=5000&&j>=0;i++,j--){
if(!f[i][j]){
for(int k = 1;i + k <= 5000;k++)
for(int s = 0;j + s*k <= 5000;s++)
f[i+k][j+s*k] = 1;
for(int k = 1;j + k <= 5000;k++)
for(int s = 0;i + s*k <= 5000;s++)
f[i+s*k][j+k] = 1;
}
}
}
scanf("%d",&t);
while(t--){
int n,m;
scanf("%d%d",&n,&m);
if(f[n][m])puts("Alice");
else puts("Bob");
}
return 0;
} 注意：bool数组和int数组过不了牛客上的编译，bitset<_size> f[_size]用法学一下
H题
题目大意：给出a1,a2......an，求一个数mod使得每个数%mod的值都不相同且满足mod最小。n<=5e5
思路：枚举每两个数之间的差值，mod为不在差值和差值倍数的集合中的最小值。注意求差值时n²会tle，用fft求解即可。
ac代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6+6;
const double PI = acos(-1);
int n,m;
struct Complex{
double x,y;
Complex operator+(const Complex &t)const{
return {x+t.x,y+t.y};
}
Complex operator-(const Complex &t)const{
return {x-t.x,y-t.y};
}
Complex operator*(const Complex &t)const{
return {x*t.x-y*t.y,x*t.y+y*t.x};
}
}a[N],b[N];
int rev[N],bit,tot;
void fft(Complex a[],int inv){
for(int i = 0;i < tot;i++)
if(i < rev[i])
swap(a[i],a[rev[i]]);
for(int mid = 1;mid < tot;mid <<= 1){
auto w1 = Complex({cos(PI/mid),inv*sin(PI/mid)});
for(int i = 0;i < tot;i += mid << 1){
auto wk = Complex({1,0});
for(int j = 0;j < mid;j++,wk = wk*w1){
auto x = a[i + j],y = wk*a[i+j+mid];
a[i+j] = x+y,a[i+j+mid] = x-y;
}
}
}
}
bool vis[N] = {0};
bool check(int x){
for(int i = x;i <= N;i+=x)
if(vis[i])return 0;
return 1;
}
int main(){
scanf("%d",&n);
m = n;
for(int i = 0;i < n;i++){
int X;
scanf("%d",&X);
a[X].x = 1.0;
b[500000-X].x = 1.0;
}
// while((1 << bit) < N )bit++;
bit = 20;
tot = 1 << bit;
// cout << "bit "<<bit << endl;
for(int i = 0;i < tot;i++)rev[i] = (rev[i >> 1] >> 1)|((i&1)<<(bit-1));
fft(a,1),fft(b,1);
for(int i = 0;i < tot;i++)a[i] = a[i] * b[i];
fft(a,-1);
for(int i = 0;i <= 500000+500000;i++){
int x = (int)(a[i].x/tot+0.5);
// cout << "i "<<x<<endl;
if(x > 0)vis[abs(i - 500000)] = 1;
}
// for(int i = 0;i <= 20;i++)cout << vis[i]<<" "<<i<<endl;
for(int i = n;i < 500000+5050;i++){
if(check(i)){
cout << i << endl;
break;
}
}
return 0;
}注意：tot即为数组大小，大小不是n+m+1而是5e5*2+1
G题
题目大意：给出a1,a2,......,an和b1,b2,......,bn，对数组a进行k次交换，使得|a1-b1|+|a2-b2|+......+|an-bn|的值最大。
思路：对于任意两组(a1,b1),(a2,b2)，不妨令a1>a2，则|a1-b1|+|a2-b2| = a1+a2-b1-b2,有以下两种情况:1.b1>a2，则交换后|a1-b2|+|a2-b1| = a1-b2+b1-a2,贡献为2*(b1-a2)。2.b1<a2，则交换后|a1-b2|+|a2-b1| = a1+a2-b1-b2,贡献为0 。所以将a,b排好序后从大到小枚举贡献，假设贡献大于0的有s组，则循环时取min(s,k)，即如果可以全取到s组而还有剩余交换次数则做无意义交换，如果不够k组则取贡献前k大。
ac代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
typedef long long LL;
LL ans = 0;
int a[N],b[N],A[N],B[N];
int main(){
int n,k;
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;i++)scanf("%d",&a[i]);
for(int i = 1;i <= n;i++)scanf("%d",&b[i]);
for(int i = 1;i <= n;i++)A[i] = max(a[i],b[i]),B[i] = min(a[i],b[i]),ans+=A[i] - B[i];
sort(A+1,A+1+n),sort(B+1,B+1+n);
for(int i = 1;i <= min(k,n);i++){
LL t = 2*(B[n - i + 1] - A[i]);
if(t > 0)ans+=t;
else break;
}
cout << ans << endl;
return 0;
}K题
题目大意：多组输入，给出序列a1,a2......an，求出a数组另一个排列，使得sqrt(a1-0)+sqrt(a2-1)+sqrt(a3-2)+......+sqrt(an-(n-1))最小。
思路：多次迭代使得每个位置对应的sqrt(i-a[i])最小，bi表示sqrt(i)。迭代具体方法为比较b[i-a[i]]+b[j-a[j]]和b[i-a[j]]+b[j-a[i]]的大小，若前者大则交换。
ac代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 4e4+4;
long double b[N];
int a[N];
int main(){
int t,n;
scanf("%d",&t);
for(int i = 0;i <= N;i++)b[i] = sqrt(i);
while(t--){
scanf("%d",&n);
for(int i = 0;i < n;i++)scanf("%d",&a[i]);
sort(a,a+n);
for(int ii = 0;ii <= 10;ii++)
for(int i = 0;i < n;i++)
for(int j = i + 1;j < n;j++)
if(b[abs(i - a[i])] + b[abs(j - a[j])] > b[abs(i - a[j])] + b[abs(j - a[i])])
swap(a[i],a[j]);
for(int i = 0;i < n;i++)printf("%d ",a[i]);
printf("\n");
}
return 0;
} 注意：double的精度不够，开long double。
I题
题目大意：给出n个数组成的数组，是1~n之间的数的一个排列。两人轮流选，要求选的数比已选的都大，另外，同一个人后选的数在数组中出现的位置要比之前选的靠后。每次取到不能取为止，求两人取数的期望轮数。
思路：dp(i,j)表示上一个人选i，当前人选j的期望轮数。从大到小枚举i和j。满足 a[ j ] > i 则说明后面计算过，否则更新dp[ a[j] ][ i ]。
ac代码：
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353,N = 5010;
typedef long long LL;
LL dp[N][N];//当前人选i，下一个人选j的期望轮数
LL inv[N],a[N];
LL qsm(LL a,int b){
LL res = 1;
while(b){
if(b&1)res = (res*a)%mod;
a = (a*a)%mod;
b>>=1;
}
return res;
}
int main(){
int n;
cin >> n;
for(int i = 1;i <= n;i++)cin >> a[i],inv[i] = qsm(i,mod-2);
for(int i = n;i >= 0;i--){
LL cnt = 0,sum = 0;//sum期望和
for(int j = n;j >= 0;j--){
if(a[j] > i)cnt++,sum+=dp[i][a[j]],sum%=mod;
else {
dp[a[j]][i] = 1;
if(!cnt)continue;
dp[a[j]][i]+=sum*inv[cnt]%mod,dp[a[j]][i]%=mod;
}
}
}
LL res = 0;
for(int i = 1;i <= n;i++)res = (res + dp[0][i])%mod;
res = res * inv[n] % mod;
cout << res << endl;
return 0;
} p.s. 这题还没太想明白，过几天再看看。
查看5道真题和解析
投递字节跳动等公司10个岗位 >