北华大学第九届程序设计竞赛 题解

5.14和队友VP一场，第二次VP，状态明显比第一次好很多，总共A了7题，基本是能做出来的都做出来了，最后还剩下接近2小时的时间。。。。。

A "北华"有几何

思路：数图片中“北华”的数量，直接输出即可

B 学霸题 II

思路：二分+前缀和(缺少任何一个都会超时)

首先输入数组a(正视图每列的个数)然后对其进行排序，计算数组a的前缀和，再输入数组b(侧视图每列的个数)，数组b每个数只能小于或者等于数组a的每一个数。这样想，假如开始按正视图的个数堆满，那么考虑每列侧视图时，正式图只要大于当前列侧视图的都要削减到和当前列侧视图同高，所以每输入一个b，二分数组a，在数组a中查找第一个大于b的数，前半部分不变，直接是前缀和即可，后半部分都等于当前列侧视图b

lower_bound(begin,end,num);                        查找第一个大于等于num的数字upper_bound(begin,end,num);                       查找第一个大于num的数字

AC代码： 

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;const int N=300005;
int a[N],b[N],sum[N];
signed main(){int n,m,ans=0,pos;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);for(int i=1;i<=n;i++){sum[i]=sum[i-1]+a[i];}cin>>m;for(int i=1;i<=m;i++){cin>>b[i];pos=upper_bound(a+1,a+n+1,b[i])-a;ans+=(n-pos+1)*b[i]+sum[pos-1];}cout<<ans;return 0;
}

C 小杜的字符串

思路：模拟

对字符串的每列进行遍历，将每列的字符都变成在每列中出现次数最多的字符，因为只有三行，所以记录字符出现次数，每次答案加上3-最大字符数即可

AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;string s[5];
int sum[30];
int main(){int n,ans=0;cin>>n;for(int i=1;i<=3;i++){cin>>s[i];}for(int i=0;i<n;i++){memset(sum,0,sizeof(sum));for(int j=1;j<=3;j++){sum[s[j][i]-'a']++;}	sort(sum,sum+26);ans+=3-sum[25];}cout<<ans;return 0;
}

D 矿石精炼场

思路：模拟题

因为只能购买一台矿石精炼器，所以分析两种情况取最大值即可。第一种情况，不购买矿石精炼器，最后的金钱即为当前手里的金钱+矿资源的价值。第二种情况，购买矿石精炼器，若要购买矿石精炼器，首先电力资源要满足，所以要修建发电站，要修建发电站，首先要看钱满不满足，所以要先判断电力资源满不满足，计算需要修建发电机需要的钱数(注意不能出现负的)，矿产资源数和当前手里的钱数减去需要的钱数，剩下的再通过矿石精炼

AC代码：

#include<iostream>
#include<cmath>
using namespace std;int main(){double T,w,m,E,D,c0,d,p,c1,e,sum1,sum2,nm;cin>>T;while(T--){cin>>w>>m>>E>>D>>c0>>d>>p>>c1>>e;sum1=w+m;nm=max(0.0,ceil((D+d-E)/e))*c1+c0;if(nm<=m){sum2=w*(1+p*0.01)+m-nm;}else{sum2=(w+m-nm)*(1+p*0.01);}printf("%.2lf\n",max(sum1,sum2));}return 0;
}

E 天空岛

优先队列的自定义不会写！！！！！仿函数啥的啊啊啊啊！！！带结构体的优先队列。。。

开始只考虑BFS，未考虑优先队列，所以总是想不出来这样写为什么会AC，之后才慢慢理解。。

思路：BFS+优先队列

先将第一个点加入队列，然后只要队列非空，取出一个点(因为是优先队列，所以取出的点为当前队列中w，即承重极限最大的)，注意货物必须首先满足重量小于等于该单元格的承重极限，所以每次结果为队列中承重极限最大的，同时单独计算精灵分担的货物重量

AC代码：

#include<iostream>
#include<queue> 
#define int long long
using namespace std;const int N=1005;
int w[N][N],val[N][N];
bool vis[N][N];
int dx[]{-1,1,0,0};
int dy[]{0,0,-1,1};
struct Node{int x;int y;int z;
};struct cmp{bool operator()(Node a,Node b){return a.z<b.z;}
};signed main(){int n,m,k,x,y,v,ans=0x3f3f3f3f,sum=0;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>w[i][j];}}cin>>k;for(int i=1;i<=k;i++){cin>>x>>y>>v;val[x][y]=v;}priority_queue<Node,vector<Node>,cmp> q;q.push({1,1,w[1][1]});while(!q.empty()){Node t=q.top();int a=t.x,b=t.y,c=t.z;q.pop();//防止队列中出现多次同一个元素！！！//某个在队列中间的元素被多次压入！！ if(vis[a][b]){continue;}vis[a][b]=1;ans=min(ans,c+sum);sum+=val[a][b];if(a==n&&b==m){break;}for(int i=0;i<4;i++){int nx=a+dx[i],ny=b+dy[i];if(vis[nx][ny]||nx<1||nx>n||ny<1||ny>m){continue;}q.push({nx,ny,w[nx][ny]});}}cout<<ans;return 0;
}

F Karashi的树 II 

思路：并查集+最短路

不会。。。。

G 114514国

思路：思维题，因为给一张45找回四张11相当于支付1，注意要求：0≤A,B,C,a,b,c≤，所以先支付45面值的，取余45即可，剩下的再使用一张45找回四张

AC代码：

#include<iostream>
using namespace std;int main(){long long n,ans=0;cin>>n;ans+=n/45;n%=45;cout<<0<<' '<<ans+n<<' '<<0<<'\n';cout<<n*4<<' '<<0<<' '<<0<<'\n';return 0;
}

H 杰哥的激光炮

思路：也算是思维题吧。。。先求长和宽的最大公约数，答案即为：最大公约数*(长/最大公约数+宽/最大公约数-1)

AC代码：

#include<iostream>
#include<algorithm>
using namespace std;int main(){int T,x,y;cin>>T;while(T--){cin>>x>>y;if(x==y){cout<<x<<'\n';}else{int t=__gcd(x,y);cout<<t*(x/t+y/t-1)<<'\n';}}return 0;
}

I TAROT I 

思路：容斥

不会。。。

L Karashi的电灯泡 

思路：大模拟。。。理解不了。。。。。

M 超时空传送！！偷袭

思路：水题。。。输出九个战斗力最大的和即可(不足九个输出和)

#include<iostream>
#include<algorithm>
using namespace std;const int N=105;
int a[N];bool cmp(int x,int y){return y<=x;
}
int main(){int n,ans=0;cin>>n;string s;for(int i=0;i<n;i++){cin>>s>>a[i];}sort(a,a+n,cmp);for(int i=0;i<9;i++){ans+=a[i];}cout<<ans;
}