0320校队蓝桥杯积分训练赛补题记录
A:
A题面.png
思路：
动态规划，用一个二维数组 dp [ i ] [ j ] 记录。
dp [ i ] [ j ] 表示在 i 时 gameboy 在位置 j 背包中有 dp [ i ] [ j ] 个煎饼
代码：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int dp[100005][15];
int main(){
int n;
int x,t;
int mt=0;
while(cin>>n,n){
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++){
scanf("%d %d",&x,&t);
dp[t][x]++;
mt=max(mt,t);
}
for(int i=mt;i>=0;i--){
for(int j=10;j>=0;j--){
dp[i][j]+=max(dp[i+1][j-1],max(dp[i+1][j],dp[i+1][j+1]));
}
}
printf("%d\n",dp[0][5]);
}
return 0;
}
心得：
下次再做不出来腿打断！！！
B:
B题面.png
思路：
动态规划，用一个二维数组 dp [ i ] [ j ] 记录。
dp [ i ] [ j ] 表示小智使用了 i 个精灵球 j 个体力后能最多能捕捉到 dp [ i ] [ j ] 个小精灵
代码：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
int dp[1005][505];
int main(){
int n,m,k;
cin>>n>>m>>k;
int a,b;
for(int i=0;i<k;i++){
cin>>a>>b;
for(int j=n;j>=a;j--){
for(int l=m-1;l>=b;l--){
dp[j][l]=max(dp[j][l],dp[j-a][l-b]+1);
}
}
}
cout<<dp[n][m-1]<<" ";
int t=m-1;
while(t>0&&dp[n][t-1]==dp[n][m-1])
t--;
cout<<m-t;
return 0;
}
心得：
我是笨逼 over
C:
C题面.png
思路：
动态规划，用一个一维数组 dp [ i ] 记录。
dp [ i ] 表示阿福偷到第i家店时到手的现金数量最多为 dp [ i ]
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100005];
int dp[100005];
int main(){
int T,n;
cin>>T;
while(T--){
cin>>n;
for(int i=0;i<n;i++)
scanf("%d",a+i);
memset(dp,0,sizeof(dp));
dp[0]=a[0];
dp[1]=max(a[0],a[1]);
for(int i=2;i<n;i++)
dp[i]=max(dp[i-2]+a[i],dp[i-1]);
cout<<dp[n-1]<<endl;
}
return 0;
}
心得：
马哥太强了
D:
D题面.png
思路：
并查集模板题
代码：
#include<iostream>
using namespace std;
int fa[1005];
int get(int x){
if(fa[x]==x)
return x;
return fa[x]=get(fa[x]);
}
void merge(int x,int y){
fa[get(x)]=get(y);
}
int main(){
int t;
cin>>t;
int n,m;
int x,y,ans;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++){
cin>>x>>y;
merge(x,y);
}
ans=0;
for(int i=1;i<=n;i++)
if(fa[i]==i)
ans++;
cout<<ans<<endl;
}
return 0;
}
心得：
555 这次一定记住了
E:
E题面.png
思路：
图论 dijkstra算法模板题
代码：
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=2010,M=100010;
int head[N],edge[M],ver[M],Next[M],tot;
int d[N],v[N],n,m,s[N][N];
queue<int>q;
void add(int x,int y,int z){
if(s[x][y]){
for(int i=head[x];i;i=Next[i]){
int now=ver[i];
if(now==y) {
edge[i]=min(edge[i],z);
return;
}
}
}
ver[++tot]=y;
edge[tot]=z;
Next[tot]=head[x];
head[x]=tot;
s[x][y]=1;
}
void spfa(){
memset(d,0x3f,sizeof(d));
memset(v,0,sizeof(v));
d[1]=0;
v[1]=1;
q.push(1);
while(q.size()){
int x=q.front();q.pop();
v[x]=0;
for(int i=head[x];i;i=Next[i]){
int y=ver[i],z=edge[i];
if(d[y]>d[x]+z){
d[y]=d[x]+z;
if(!v[y]){
v[y]=1;
q.push(y);
}
}
}
}
}
int main(){
cin>>m>>n;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
spfa();
cout<<d[n];
return 0;
}
心得：
好滴吧 这题我没有认真看 我摊牌了
F:
F题面.png
思路：
签到题 复习一下欧式筛
代码：
#include<iostream>
using namespace std;
int n;
int is_prime[100005];
int prime[100005];
void p(){
int t=0;
is_prime[0]=is_prime[1]=1;
for(int i=2;i<100005;i++){
if(! is_prime[i])
prime[++t]=i;
for(int j=1;j<=t && i*prime[j]<100005;j++){
is_prime[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
}
int main(){
cin>>n;
p();
for(int i=2;i<n;i++){
if(is_prime[i]==0&&is_prime[n-i]==0){
cout<<n<<"="<<i<<"+"<<n-i;
break;
}
}
return 0;
}
心得：
null
G:
签到题 最大公约数 略了略了
H:
H题面.png
思路：
记忆化搜索
代码：
#include<iostream>
using namespace std;
const int N=105;
int n,m;
int maze[N][N],f[N][N];
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
int dfs(int x,int y){
if(f[x][y]) return f[x][y];
for(int k=0;k<4;k++){
int nx=x+dx[k];
int ny=y+dy[k];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&maze[nx][ny]<maze[x][y]){
dfs(nx,ny);
f[x][y]=max(f[x][y],f[nx][ny]+1);
}
}
return f[x][y];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>maze[i][j];
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=max(ans,dfs(i,j));
cout<<ans+1;
return 0;
}
心得：
终于结束了 告辞(狗头)
