2023牛客暑假多校训练营2

D.The Game of Eating

贪心

题目说每个人只关心自己享用的菜肴,而不考虑他人,每个人的目标都是使得自己喜欢的菜肴尽可能多

也就是说每个人都很鸡贼,它们当下都是做出最有利于自己的选择,对于某一个人,他首先会算在他之后他最喜欢的菜是否会被选择,如果会被选择,那么他就不选自己最喜欢的菜,然后再看次喜欢的菜,看是否会被选,以此类推,直到发现后面没人选时,他才会选,这样当k个菜都选完时,他喜欢的菜的数量可以达到最大,每个人都会这么想,按这样的话,对于最后一个选菜的人,他自己最喜欢的菜如果没人选的话,他自己肯定会选,所以前面的人算到最后一个人会选,所以前面的人故意不选这道菜,最后只能让最后一个人选这道菜,所以倒过来贪心即可

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#define endl '\n'
using namespace std;
const int N=2010;
int a[N][N];
int flag[N];
void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    memset(flag,0,sizeof flag);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    //从第一个人开始选菜,一人选一道菜,一共选k道菜,现从k往前遍历
    for(int i=k;i;i--){
        int t=(i-1)%n+1;//选第i道菜轮到了编号为t的人
        int x=0;
        for(int j=1;j<=m;j++){
            if(!flag[j]&&a[t][j]>a[t][x]) x=j;
        }
        flag[x]=1;
    }
    for(int i=1;i<=m;i++){
        if(flag[i]) cout<<i<<" ";
    }
    cout<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}

E.square 

题意是找到一个y(大于等于x),使得x是y的平方的前缀(前缀的位数只有可能是1到9,因为x最大才1e9,所以只需要枚举一下10的幂,i从0到9)

(y^2)/(10^i)=x -->x*10^i<=y^2,所以要保证y^2大于等于x*10^i,如果y^2小于x*10^i的话,x不可能是y^2的前缀的

然后如果y的平方的前缀是x的话(先将x,y^2分别转为字符串并存储,取y^2字符串的前x位和字符串x比较是否相等),那么就符合

比如说x=12,x*10=120,sqrt(x*10)=10,10*10小于120,不可能

11*11=121,发现可以

x*100=1200,sqrt(x*100)=34,34*34小于1200,不可能

35*35=1225,发现可以,然后35*35=1296,发现也可以

说明要想可以,首先得保证y^2大于等于x*10^i,然后从符合条件最小的y开始找,如果y符合,后面可能还有符合的y,但是最小的y不符合,那么后面就更不可能符合了,因为比如说x为12,然后x*10^i,某个最小的y,y^2的前两位是13,已经不符合前缀12了,所以y更大的话就更不可能符合前缀12了

法一:

 AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
LL solve()
{
    LL x;
    cin>>x;
    if(x==0) return 0;
    string xx=to_string(x);
    string s;
    int len=xx.size();
    int res=-1;
    for(int i=0;i<10;i++){
        LL y=sqrt(x*pow(10,i));
        if(y*y<x*pow(10,i)) y++;
        s=to_string(y*y);
        if(s.substr(0,len)==xx) return y;
    }
    return res;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    cout<<solve()<<endl;
    return 0;
}

法二:

AC代码：

#include <iostream>
#include <cmath>
#define int long long
using namespace std;
int solve()
{
    int x;
    cin>>x;
    int z=x+1;
    int y;
    int flag=0;
 //最多循环10次,为了保证x不超出long long范围,从而导致溢出,发生错误
    for(int i=0;i<10;i++){
        y=sqrt(x*pow(10,i));
  //这边改成y*y<pow(10,i)而不是y*y!=pow(10,i),因为pow有精度问题,可能数太大了开根号不一定会下取整,可能上取整
        if(y*y<x*pow(10,i)) y++;
  //如果y*y大于等于x*10的幂并且y*y小于(x+1)*10的幂
        if(y*y>=x*pow(10,i)&&y*y<z*pow(10,i)){
            flag=1;
            break;
        }
    }
    if(flag==1) return y;
    else return -1;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    cout<<solve()<<endl;;
    return 0;
}

K.Box

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int N=1e6+10;
int f[N][3];
//只需考虑当前枚举到的i是否有盖子,以及它的盖子左移,还是它的前一个盖子右移
//f[i][0]表示当前状态没有盖子,本来就没有盖子也有可能是把盖子给了左边,1到i获得的最大分数
//f[i][1]表示当前状态有盖子,而且是本来就有盖子,1到i获得的最大分数
//f[i][2]表示当前状态有盖子,但是是左边给了它盖子,1到i获得的最大分数
int a[N],b[N];
int n;
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        //如果当前有盖子
        if(b[i]){
            //f[i][0]表示i没盖子,所以需要把i的盖子左移,f[i-1][0]表示i-1没盖子,1到i-1获得的最大分数,
            //然后加上a[i-1]即为f[i][0],1到i获得的最大分数
            f[i][0]=f[i-1][0]+a[i-1];
            //f[i][1]表示i当前状态有盖子,而且是本来就有盖子,所以前面i-1三种状态只需取最大值即可,再加上a[i]
            f[i][1]=max({f[i-1][0],f[i-1][1],f[i-1][2]})+a[i];
        }
        //如果当前没有盖子
        else {
            //只要取i-1三种状态最大的就行
            f[i][0]=max({f[i-1][0],f[i-1][1],f[i-1][2]});
        }
        //如果前一个有盖子,这个情况单独考虑,因为把前一个盖子右移,就不需要考虑当前位置有无盖子了
        //f[i][2]表示当前状态有盖子,但是是左边给的盖子,可以是前面i-1本来就有盖子,然后将盖子右移,导致自己没有盖子了,也可以是
        //前面i-1本来就有盖子,然后将盖子右移,但是i-2的盖子又给了i-1
        if(b[i-1]) f[i][2]=max(f[i-1][1]+a[i]-a[i-1],f[i-1][2]+a[i]);
    }
    cout<<max({f[n][0],f[n][1],f[n][2]})<<endl;
}
signed main()
{
    solve();
    return 0;
}

I.Link with Gomoku 

五子棋,双方博弈,轮流下,首先得保证双方数量相等或者差一个(这很关键)

然后就是保证横着竖着斜着不能有连续5个相同

行数为0到n-1,列数为0到m-1

可以以4行为1个循环,前两行偶数列放o,奇数列放x,后两行偶数列放x,奇数列放o(这样的好处是不需要管列数是奇数还是偶数,在一行中数量是相当的)

最后要保证双方数量相等或者差一个,需要在最后特殊处理一下,如果n%4得到完整的k个4行后还有几行,如果还有一行,那么数量相当,不需要考虑,如果还有三行

如图,x会比o多一个,所以也不要考虑

所以只需要考虑还有两行的情况,只要将最后一行反置就行

AC代码： 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e3+10;
char s[N][N];
int n,m;
void solve()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i%4<2){
                if(j&1) s[i][j]='o';
                else s[i][j]='x';
            }
            else{
                if(j&1) s[i][j]='x';
                else s[i][j]='o';
            }
        }
    }
    if(n%4==2){
        for(int j=0;j<m;j++){
            if(j&1) s[n-1][j]='x';
            else s[n-1][j]='o';
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<s[i][j];
        }
        cout<<endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    solve();
    return 0;
}