2022-10-03 10:56 已编辑中国人民大学附属中学分校 C++ 发布于江苏

关注

【题解】牛客小白月赛58

【题解】牛客小白月赛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-2$ 个转化为选 $2$ 个，

记 $n$ 张卡牌总和为 $S$ ，

选的两个数为 $a_{i},a_{j}$ ，

$s_{0}=a_{i}+a_{j}$ ，

则有 $S-(a_{i}+a_{j})≡0 \pmod m$ ，

也即 $a_{i}≡S-a_{j} \pmod m$ ，

枚举 $j$ ，在模意义下寻找 $i$ 即可，可以使用 $map$ .

不过由于值域是 $[1,m]$ 而不是 $[0,m-1]$ ，这里的取模需要特殊处理一下 $(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-数学考试
题目分析

入门 $DP$ 题.

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

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

根据题意，

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

要么 $P_{last}+Q_{i}$ 是 $j$ ，即 $P_{last}=j-Q_{i}$ ；

要么 $P_{last}-W_{i}$ 是 $j$ ，即 $P_{last}=j+W_{i}$ ；

故 $dp_{i,j}=\max\{dp_{i-1,j}+w_{1},dp_{i-1,j-Q_{i}}+w_{2},dp_{i-1,j+W_{i}}+w_{3}\}$ .

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

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

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

代码

// 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-法力无边
题目分析

考虑按位统计答案，

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

对于第 $t$ 位的答案 $sum$ ，

对答案贡献为 $sum<<t$ .

按位计算后，问题就简化为每一个数 $b_{i}=(a_{i}>>t)\&1$ 只可能是 $0$ 或 $1$ 的情况，

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

如果能 $O(n)$ 计算出 $sum=\sum\limits_{i=1}^n{\sum\limits_{j=i}^n{M_{i,j}}}$ ，

这一题就解决了.

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

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

进一步地分析可知：

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

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

于是，

我们记 $Suf_{0,i}$ 表示以 $b_{i}$ 为结尾的所有子串中同或和为 $0$ 的个数，

相应地 $Suf_{1,i}$ 表示以 $b_{i}$ 为结尾的所有子串中同或和为 $1$ 的个数，

那么以 $a_{i}$ 为结尾的所有子串对 $sum$ 的贡献就是 $Suf_{1,i}$ .

考虑转移，

(i). 如果 $b_{i}$ 为 $1$ :

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

以 $b_{i}$ 为结尾的所有同或和为 $1$ 的子串中，

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

也即 $b_{i}$ 本身，

因此转移为 $Suf_{1,i}=Suf_{1,i-1}+1,Suf_{0,i}=Suf_{0,i-1}$ ；

(ii). 如果 $b_{i}$ 为 $0$ :

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

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

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

因此转移为 $Suf_{1,i}=Suf_{0,i-1}$ ；

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

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

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

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

因此转移为 $Suf_{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}-1$ 是整数，

也即 $n^2$ 是 $4$ 的倍数，

故 $n$ 需是 $2$ 的倍数，故 $n$ 模 $4$ 必为 $0$ 或 $2$ .

考虑对棋盘进行染色，奇数行填 $0$ ，偶数行填 $1$ ，

那么一个牛排内要么有 $3$ 个 $0$ 、 $1$ 个 $1$ ，要么有 $3$ 个 $1$ 、 $1$ 个 $0$ ；

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

那么除去草坪之后，整个棋盘上 $0$ 有 $3x+y$ 个， $1$ 有 $3y+x$ 个，

由于 $0$ 的个数应等于 $1$ 的个数，

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

也即 $x=y$ ，

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

假若 $n$ 模 $4$ 余 $0$ ，即 $n=4p$ ，

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

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

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

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

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

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

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

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

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

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

代码就蛮好写的了 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;
}