【题解】牛客小白月赛58 (By Christophe)

A-双子爆破者

• 题目链接 A-双子爆破者
• 题目分析

签到题，根据题目给出的公式输出答案即可.

• 代码

// Problem: 双子爆破者
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/41173/A
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
int T;
double m,M,v;
int main(){
	cin>>T;
	while(T--){
		cin>>M>>m>>v;
		cout<<(m*v)/(M-m)<<endl;
	}
	return 0;
}

B-牛原子

• 题目链接 B-牛原子
• 题目分析

模拟题，根据题意运用前缀和 + 排序即可.

• 代码

// Problem: 牛原子
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/41173/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
#define lg2(x) ((int)(__lg(x)/__lg(2)))
typedef long long LL;
typedef unsigned long long ull;
const int N=1e6+10,INF=2e9+10;
inline int read(){
    int ret=0,f=1; 
	char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-f; ch=getchar(); }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void write(int x){        
    if(x<0){ putchar('-'); x=-x; }      
    if(x>9) write(x/10);     
    putchar(x%10+'0');     
}
int hs1[20]={0,1,2,2,3,3,4,3,4,5,4,5,6,4,5,6,7,5,6,7};//题目中的第一项系数
int hs2[20]={0,2,2,6,2,6,2,10,6,2,10,6,2,14,10,6,2,14,10,6};//对应的 s/p/d/f ，以填满所需的电子数为代表
int T,n,s[20],tp;
struct Node{
	int cg;//电子亚层数
	int spdf;//s or p or d or f
	int ct;//电子数
	bool operator<(const Node &B)const{
		return cg<B.cg||(cg==B.cg&&spdf<B.spdf);
	}
}st[N];
char to(int x){//s->2 p->6 d->10 f->14
	if(x==2) return 's';
	if(x==6) return 'p';
	if(x==10) return 'd';
	return 'f';
}
void update(int i,int k){
	st[++tp]={hs1[i],hs2[i],k};
}
int main(){
	T=read();
	for(int i=1;i<=19;++i) s[i]=s[i-1]+hs2[i];
	while(T--){
		tp=0,n=read();
		int p=upper_bound(s+1,s+19+1,n)-s;
		for(int i=1;i<=p-1;++i) update(i,hs2[i]);
		if(n>s[p-1]) update(p,n-s[p-1]);
		sort(st+1,st+tp+1);
		for(int i=1;i<=tp;++i){
			write(st[i].cg);
			putchar(to(st[i].spdf));
			write(st[i].ct);
			putchar(' ');	
		}
		puts("");
	}
	return 0;
}

C-牛牛

• 题目链接 C-牛牛
• 题目分析

考虑将选 $n-2n-2$ 个转化为选 $22$ 个，

记 $nn$ 张卡牌总和为 $SS$，

选的两个数为 $a_i,a_{j}a\_\{i\},a\_\{j\}$，

$s_0=a_i+a_{j}s\_\{0\}=a\_\{i\}+a\_\{j\}$，

则有 $S-(a_i+a_j)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}m)S-(a\_\{i\}+a\_\{j\})\equiv 0\; \backslash pmod\; m$，

也即 $a_i\equiv S-a_j(\mathrm{m}\mathrm{o}\mathrm{d}m)a\_\{i\}\equiv S-a\_\{j\}\; \backslash pmod\; m$，

枚举 $jj$，在模意义下寻找 $ii$ 即可，可以使用 $mapmap$.

不过由于值域是 $[1,m][1,m]$ 而不是 $[0,m-1][0,m-1]$，这里的取模需要特殊处理一下 $(0->m)(0->m)$.

• 代码

// Problem: 牛牛
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/41173/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define lowbit(x) ((x)&(-(x)))
#define lg2(x) ((int)(__lg(x)/__lg(2)))
typedef long long LL;
typedef unsigned long long ull;
const int N=1e6+10,INF=2e9+10;
inline int read(){
    int ret=0,f=1; 
	char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-f; ch=getchar(); }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void write(int x){        
    if(x<0){ putchar('-'); x=-x; }      
    if(x>9) write(x/10);     
    putchar(x%10+'0');     
}
int T,n,m,s,s0,a[N];
bool flag;
inline int mod(int x,int m){
	if(x%m!=0) return x%m;
	return m;
}
signed main(){
	T=read();
	while(T--){
		n=read(),m=read(),s=0,flag=0;
		for(int i=1;i<=n;++i) a[i]=read(),s+=a[i];
		map<int,int> mp;
		mp[a[1]]=1;
		for(int j=2;j<=n;++j){
			if(mp.find(mod(s-a[j],m))!=mp.end()){
				int i=mp[(s-a[j])%m];
				flag=1;
				s0=a[i]+a[j];
				break;
			}
			mp[a[j]]=j;
		}
		if(flag) write(mod(s0,m));
		else write(0);
		puts("");
	}
	return 0;
}

D-数学考试

• 题目链接 D-数学考试
• 题目分析

入门 $DPDP$ 题.

定义 $d{p}_{i,j}dp\_\{i,j\}$ 表示做完第 $ii$ 份作业后，压力指标为 $jj$ 时可积累的最大经验，

考虑如何使得压力指标在做完第 $ii$ 份作业后变为 $jj$，

根据题意，

要么做完 $i-1i-1$ 份时压力 $P_{last}=jP\_\{last\}=j$；

要么 $P_{last}+Q_{i}P\_\{last\}+Q\_\{i\}$ 是 $jj$，即 $P_{last}=j-Q_{i}P\_\{last\}=j-Q\_\{i\}$；

要么 $P_{last}-W_{i}P\_\{last\}-W\_\{i\}$ 是 $jj$，即 $P_{last}=j+W_{i}P\_\{last\}=j+W\_\{i\}$；

故 $d{p}_{i,j}=\max \{d{p}_{i-1,j}+w_1,d{p}_{i-1,j-Q_i}+w_2,d{p}_{i-1,j+W_i}+w_3\}dp\_\{i,j\}=\backslash max\backslash \{dp\_\{i-1,j\}+w\_\{1\},dp\_\{i-1,j-Q\_\{i\}\}+w\_\{2\},dp\_\{i-1,j+W\_\{i\}\}+w\_\{3\}\backslash \}$.

注意 $0\le j\le K0\; \backslash le\; j\; \backslash le\; K$，转移时特判一下就好.

由于初始的压力值没有确定，不妨都赋上初值（容易发现是 $00$），以便于后继状态可以从前面的任意一个状态转移过来，最终的答案也即是考虑所有可能的初值的正确答案.

至于空间限制，滚动数组滚一下就好了.

• 代码

// Problem: 数学考试
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/41173/D
// Memory Limit: 131072 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define lowbit(x) ((x)&(-(x)))
#define lg2(x) ((int)(__lg(x)/__lg(2)))
typedef long long LL;
typedef unsigned long long ull;
const int N=1e6+10,INF=2e10+10,MIN=-INF;
inline int read(){
    int ret=0,f=1; 
	char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-f; ch=getchar(); }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void write(int x){        
    if(x<0){ putchar('-'); x=-x; }      
    if(x>9) write(x/10);     
    putchar(x%10+'0');     
}
int n,k,a[N],b[N],q[N],w[N],dp[2][N];
int get(int x,int i){
	return x<=b[i]?a[i]*x:0;
}
signed main(){
	n=read(),k=read();
	for(int i=1;i<=n;++i){
		a[i]=read(),b[i]=read();
		q[i]=read(),w[i]=read();
	}
	for(int i=0;i<=1;++i){
		for(int j=0;j<=k;++j){	
			if(i==0) dp[i][j]=0;
			else dp[i][j]=MIN;
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<=k;++j){
			int tmp=MIN;
			if(dp[(i-1)&1][j]!=MIN) tmp=max(tmp,dp[(i-1)&1][j]+get(j,i));
			if(j-q[i]>=0&&dp[(i-1)&1][j-q[i]]!=MIN) tmp=max(tmp,dp[(i-1)&1][j-q[i]]+get(j-q[i],i));
			if(j+w[i]<=k&&dp[(i-1)&1][j+w[i]]!=MIN) tmp=max(tmp,dp[(i-1)&1][j+w[i]]+get(j+w[i],i));
			dp[i&1][j]=tmp;
		}
	}
	int cnt=MIN;
	for(int j=0;j<=k;++j) cnt=max(cnt,dp[n&1][j]);
	write(cnt);
	return 0;
}

E-法力无边

• 题目链接 E-法力无边
• 题目分析

考虑按位统计答案，

在二进制下我们不进行进位，

对于第 $tt$ 位的答案 $sumsum$，

对答案贡献为 .

按位计算后，问题就简化为每一个数 只可能是 $00$ 或 $11$ 的情况，

我们在这个条件下对同或的性质进行研究，

如果能 $O(n)O(n)$ 计算出 $sum={\sum }_{i=1}^n{\sum }_{j=i}^n{M}_{i,j}sum=\backslash sum\backslash limits\_\{i=1\}^n\{\backslash sum\backslash limits\_\{j=i\}^n\{M\_\{i,j\}\}\}$ ，

这一题就解决了.

根据真值表，我们发现 $x\odot 1=xx\odot 1=x$，即 $11$ 对于同或的结果没有影响，

那么同或的结果就只和参与运算的 $00$ 的个数有关.

进一步地分析可知：

如果参与运算的 $00$ 为奇数个，同或的结果为 $00$；

如果参与运算的 $00$ 为偶数个，同或的结果为 $11$；

于是，

我们记 $Su{f}_{0,i}Suf\_\{0,i\}$ 表示以 $b_{i}b\_\{i\}$ 为结尾的所有子串中同或和为 $00$ 的个数，

相应地 $Su{f}_{1,i}Suf\_\{1,i\}$ 表示以 $b_{i}b\_\{i\}$ 为结尾的所有子串中同或和为 $11$ 的个数，

那么以 $a_{i}a\_\{i\}$ 为结尾的所有子串对 $sumsum$ 的贡献就是 $Su{f}_{1,i}Suf\_\{1,i\}$.

考虑转移，

(i). 如果 $b_{i}b\_\{i\}$ 为 $11$:

那么阶段 $ii$ 的答案与 $i-1i-1$ 的答案的唯一差异在于，

以 $b_{i}b\_\{i\}$ 为结尾的所有同或和为 $11$ 的子串中，

多出了一个长度为 $11$ 的子串 $11$，

也即 $b_{i}b\_\{i\}$ 本身，

因此转移为 $Su{f}_{1,i}=Su{f}_{1,i-1}+1,Su{f}_{0,i}=Su{f}_{0,i-1}Suf\_\{1,i\}=Suf\_\{1,i-1\}+1,Suf\_\{0,i\}=Suf\_\{0,i-1\}$；

(ii). 如果 $b_{i}b\_\{i\}$ 为 $00$:

(1). 阶段 $ii$ 的答案中同或和为 $11$ 的所有子串，

在消去结尾的 $00$ 之后，

就是在 $i-1i-1$ 阶段中同或和为 $00$ 的那些子串，

因此转移为 $Su{f}_{1,i}=Su{f}_{0,i-1}Suf\_\{1,i\}=Suf\_\{0,i-1\}$；

(2). 阶段 $ii$ 的答案中同或和为 $00$ 的所有子串（除了子串 $00$），

在消去结尾的 $00$ 之后，

就是在 $i-1i-1$ 阶段中同或和为 $11$ 的那些子串，

由于还多了一个子串 $00$，

因此转移为 $Su{f}_{0,i}=Su{f}_{1,i-1}+1Suf\_\{0,i\}=Suf\_\{1,i-1\}+1$.

• 代码

// Problem: 法力无边
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/41173/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define lowbit(x) ((x)&(-(x)))
#define lg2(x) ((int)(__lg(x)/__lg(2)))
typedef long long LL;
typedef unsigned long long ull;
const int N=1e6+10,INF=2e9+10;
inline int read(){
    int ret=0,f=1; 
	char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-f; ch=getchar(); }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void write(int x){        
    if(x<0){ putchar('-'); x=-x; }      
    if(x>9) write(x/10);     
    putchar(x%10+'0');     
}
int n,m,a[N],sum,suf[2][N],ans;
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int t=0;t<=m-1;++t){
		sum=0;
		for(int i=1;i<=n;++i){
			if((a[i]>>t)&1){
				suf[1][i]=suf[1][i-1]+1;
				suf[0][i]=suf[0][i-1];
			}else{
				suf[1][i]=suf[0][i-1];
				suf[0][i]=suf[1][i-1]+1;
			}
			sum+=suf[1][i];
		}
		ans+=(sum<<t);
	}
	write(ans);
	return 0;
}

F-草方块与牛排

• 题目链接 F-草方块与牛排
• 题目分析

小清新构造题.

首先，我们讨论何时有解.

这要求使用的牛排数量 $r=\frac{n^2-4}{4}=\frac{n^2}{4}-1r=\backslash frac\{n^2-4\}\{4\}=\backslash frac\{n^2\}\{4\}-1$ 是整数，

也即 $n^{2}n^2$ 是 $44$ 的倍数，

故 $nn$ 需是 $22$ 的倍数，故 $nn$ 模 $44$ 必为 $00$ 或 $22$.

考虑对棋盘进行染色，奇数行填 $00$ ，偶数行填 $11$，

那么一个牛排内要么有 $33$ 个 $00$ 、$11$ 个 $11$， 要么有 $33$ 个 $11$ 、$11$ 个 $00$；

设第一种牛排有 $xx$ 个，第二种有 $yy$ 个，则 $r=x+yr=x+y$，

那么除去草坪之后，整个棋盘上 $00$ 有 $3x+y3x+y$ 个， $11$ 有 $3y+x3y+x$ 个，

由于 $00$ 的个数应等于 $11$ 的个数，

因此 $3x+y=3y+x3x+y=3y+x$，

也即 $x=yx=y$，

因此 $r=2xr=2x$ 为偶数.

假若 $nn$ 模 $44$ 余 $00$，即 $n=4pn=4p$，

带入得 $r=4p^2-1=(2p+1)(2p-1)r=4p^2-1=(2p+1)(2p-1)$，

这说明 $rr$ 是两个奇数的乘积，故 $rr$ 是奇数，

这与前面的论证矛盾，因此假设错误，

这表明 $nn$ 只可能是 $4k+24k+2$ 型数字.

下证明 $n=4k+2n=4k+2$ 一定存在构造方案：

容易发现两个牛排可拼成一个 $4\times 24\backslash times\; 2$ 或 $2\times 42\backslash times\; 4$ 的长方形，

用这个长方形可以把挖去的 $2\times 22\backslash times\; 2$ 的草坪的两侧填满（因为剩下的是 $2\times 4k2\backslash times\; 4k$ 与 $4k\times 24k\backslash times\; 2$ 的区域），

那么就只剩下一个 $4k\times 4k4k\backslash times4k$ 的正方形，

显然，使用两个 $4\times 24\backslash times\; 2$ 的长方形可以拼成一个 $4\times 44\backslash times\; 4$ 的正方形，

$4k\times 4k4k\backslash times4k$ 的正方形只需扩大 $kk$ 倍，证毕.

代码就蛮好写的了 qwq

• 代码

// Problem: 草方块与牛排
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/41173/F
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-(x)))
#define lg2(x) ((int)(__lg(x)/__lg(2)))
typedef long long LL;
typedef unsigned long long ull;
const int N=1e6+10,INF=2e9+10;
inline int read(){
    int ret=0,f=1; 
	char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') f=-f; ch=getchar(); }
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline void write(int x){        
    if(x<0){ putchar('-'); x=-x; }      
    if(x>9) write(x/10);     
    putchar(x%10+'0');     
}
int n;
inline int get(int x,int y){
	return (x-1)*n+y;
}
void print1(int x,int y){
	write(get(x,y)),putchar(' ');
	write(get(x,y+1)),putchar(' ');
	write(get(x,y+2)),putchar(' ');
	write(get(x+1,y)),putchar('\n');
	
	write(get(x+1,y+3)),putchar(' ');
	write(get(x+1,y+2)),putchar(' ');
	write(get(x+1,y+1)),putchar(' ');
	write(get(x,y+3)),putchar('\n');
}
void print2(int x,int y){
	write(get(x,y)),putchar(' ');
	write(get(x+1,y)),putchar(' ');
	write(get(x+2,y)),putchar(' ');
	write(get(x,y+1)),putchar('\n');
	
	write(get(x+3,y+1)),putchar(' ');
	write(get(x+2,y+1)),putchar(' ');
	write(get(x+1,y+1)),putchar(' ');
	write(get(x+3,y)),putchar('\n');
}
int main(){
	n=read();
	if(n%4==2){
		write((n*n-4)/4),putchar('\n');
		for(int j=3;j<=n;j+=4)
			for(int i=1;i<=n;i+=2)
				print1(i,j);
		for(int i=3;i<=n;i+=4) print2(i,1);
	}else write(-1);
	return 0;
}

总结：

这次的小白月赛比较偏向思维与基础，感觉难度其实偏低了一些 qwq

点个赞再走喵 awa

作者：$\text{Christophe or 【Diana】}\backslash text\{Christophe\; or\; 【Diana】\}$