比赛中最简单的送分题,基本没有任何算法,就是求网格中每一条横轴(或竖轴)上的价值总和,然后取其中最大值输出.
但是,题目中有一个很重要的信息:不同礼物可能会在同一个格子。所以,应该是给这个格子加价值(+=),而不是赋价值(=).否则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;
}
这题已经稍微有点难了,毕竟对于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;
}
首先看到这种求方案数超大的题目,基本可以推断出这是一道数论题.
这个数论到底是什么呢,先列两组数据看看.
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;
}
完结,撒花！！！(溜了溜了,太难了)
xushuoxin的博客
