A题 礼物 题目链接

比赛中最简单的送分题,基本没有任何算法,就是求网格中每一条横轴(或竖轴)上的价值总和,然后取其中最大值输出.

但是,题目中有一个很重要的信息:不同礼物可能会在同一个格子。所以,应该是给这个格子加价值(+=),而不是赋价值(=).否则70分.

还有一点:数据保存时必须用long类型,int类型会超出范围,不然80分.(比赛时无意之举,直接加上20分)

接着,上代码！！！

#include<iostream>
using namespace std;
long n,m,mx,s,a[1005][1005],x,y,v;
int main(){
    cin>>n>>m;
    for(int i=0;i<m;a[x][y]+=v,i++)
        cin>>x>>y>>v;
    for(int i=1;i<=n;i++){
        s=0;
        for(int j=1;j<=n;j++)
            s+=a[i][j];
        mx=max(mx,s);
    }
    for(int i=1;i<=n;i++){
        s=0;
        for(int j=1;j<=n;j++)
            s+=a[j][i];
        mx=max(mx,s);
    }
    cout<<mx;
    return 0;
}

B题 数字游戏 题目链接

这题已经稍微有点难了,毕竟对于100%的数据,T≤20,n_i≤1000000 数据有点大

首选深搜做法(一开始我就这么做的) 超时,30分.

#include<iostream>
using namespace std;
int T,s,mi;
void dfs(int x,int ans){
    if(x==0){
        mi=min(mi,ans);
        return;
    }    
    if(x%3==0)
        dfs(x/3,ans+1);
    if(x%2==0)
        dfs(x/2,ans+1);
    dfs(x-1,ans+1);
}
int main(){
    cin>>T;
    for(int i=0;i<T;i++){
        cin>>s;mi=s;
        dfs(s,0);
        cout<<mi<<" ";
    }
    return 0;
}

后来测数据时发现有很多都超时了,既然这样,就空间换时间,动规换搜索,用上刚学的dp,100分.

#include<iostream>
using namespace std;
int T,s,dp[1000005];
int main(){
    cin>>T;
    for(int i=0;i<T;i++){
        cin>>s;
        dp[1]=1;
        for(int j=2;j<=s;j++){
            dp[j]=dp[j-1]+1;
            if(j%2==0)
                dp[j]=min(dp[j],dp[j/2]+1);
            if(j%3==0)
                dp[j]=min(dp[j],dp[j/3]+1);
        }
        cout<<dp[s]<<" ";
    }
    return 0;
}

C题 苹果gcd 题目链接

二分做法 60分,待会再看看(好吧,看不出来,是不是不能二分最大公约数啊?).

#include<bits/stdc++.h>
using namespace std;
int n,s,l,m,h=1e+7,a[1000005];
long long k;
bool check(){
    long long sum=0;
    for(int i=0;i<n;i++)
        sum+=a[i]%m;
    return sum<=k;
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;h=min(h,a[i]),i++)
        cin>>a[i];
    while(l<=h){
        m=(l+h)/2;
        if(check())
            s=m,l=m+1;
        else
            h=m-1;
    }
    cout<<s;
    return 0;
}

D题 通关游戏 题目链接

首先看到这种求方案数超大的题目,基本可以推断出这是一道数论题.

这个数论到底是什么呢,先列两组数据看看.

input 1

3

0 1 2

1 2 3

output 1

0 4(方案BAA,BAB,BBA,BBB四种)

input 2(数据纯自拟)

4

0 1 4 5

0 2 3 4

output 2

1 8(方案ABAA,ABAB,ABBA,ABBB,BBAA,BBAB,BBBA,BBBB八种)

第一步就很明了了,给数组从小到大排序(但要用结构体把A班i号同学擅长的关号和B班i号同学擅长的关号捆绑在一起,不然排序就排乱了)

第二步根据题意,在面对A班i号同学和B班i号同学时,肯定要选择一个,如果只有一位(或者没有)同学擅长当前算的能到的最小关卡,则不可行,因为可以选其中不擅长这个最小关卡的同学,而如果两位同学都擅长,就一定可以进入下一关(选哪个都行).这样过一遍我们就可以得出通关游戏能到的最小关卡编号了.

第三步,相信直接可以看出,两组(应该是所有,不信可以再列几组看看)数据中能到最小关卡的选择方案数都是2的正整数次幂.但只看两组数据的话,肯定会有小白说,那这个公式是不是2^(n-1)啊?NO,NO,NO.首先,我们要搞清楚,两个班选一半同学的总方案数,如果不受限制,总共应该是2^n个,而如果i号的A班同学,或B班同学擅长的关是前面算出的能到的最小关卡,那选人时就要避开他,选另一个班的同学,而这样的选择对于增加方案数毫无意义,因为选哪个都早固定了,选了,等于没选,不计入结果.反之,你就有两种选择(选A班或选B班),总方案数就乘2(注意一开始总方案数设为1,常识).

不知道听没听懂,有点难理解,只可意会,不可言传.

反正先把AC代码上了

#include<bits/stdc++.h>
using namespace std;
long n,s,ans=1;
struct node{
    int x,y;
}a[1000005];
bool cmp(node q,node p){
    return min(q.x,q.y)<min(p.x,p.y);
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i].x;
    for(int i=0;i<n;i++)
        cin>>a[i].y;
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)
        if(a[i].x==s&&a[i].y==s)
            s++;
    cout<<s<<endl;
    for(int i=0;i<n;i++)
        if(a[i].x!=s&&a[i].y!=s)
            ans*=2,ans%=998244353;
    cout<<ans;
    return 0;
}

完结,撒花！！！(溜了溜了,太难了)