May-Day训练赛题解
这套题难度还是挺适合省赛训练的，脑洞+数学+模拟都有
A题：脑洞题，题意是说一根L米长的木头，我是一只蚂蚁，运动速度是vcm/s，这个木头会以m米/s的速度均匀变长，问我能不能从这头到那头
注意到均匀这个词，相当于这个木头是按比例拉伸的，只要我有速度，我总一天能够到，跟长度V和m没有关系，只需要判断v是不是0
B题：得去链接中看懂题意
看到所有的下划线，所有的答案是根据下划线的位置和其下面所有相邻的数值和右边所有相邻的数值而得来。如果初始矩阵中有数，那么是输出7个句号；否则，第一个值是一直往下走走到第一个下划线为止的所有数的和；第二个值是一直往右走。
所以，对于每个地方的值，直接暴力往下计算就好，注意好输出格式
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+50;
int n,m,T;
char mp[maxn][maxn],x;
char s[10];
int ans1[maxn][maxn],ans2[maxn][maxn];
int main(){
//freopen("inputB.txt","r",stdin);
scanf("%d",&T);
//printf("%d\n",T);
while(T--){
memset(ans1,0,sizeof(ans1));
memset(ans2,0,sizeof(ans2));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%s",s);
mp[i][j]=s[0];
}
/*
printf("%d %d\n",n,m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
printf("%c%c",mp[i][j],j==m?'\n':' ');
*/
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if (mp[i][j]=='_'){
for(int k=i+1;k<=n;k++)
if (mp[k][j]!='_')
ans1[i][j]+=mp[k][j]-'0';
else break;
for(int k=j+1;k<=m;k++)
if (mp[i][k]!='_')
ans2[i][j]+=mp[i][k]-'0';
else break;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if (mp[i][j]!='_') printf(".......");
else{
if (ans1[i][j]==0&&ans2[i][j]==0) printf("XXXXXXX");
else{
if (ans1[i][j]==0) printf("XXX");
else printf("%03d",ans1[i][j]);
printf("\\");
if (ans2[i][j]==0) printf("XXX");
else printf("%03d",ans2[i][j]);
}
}
if (j==m) puts("");
else printf(" ");
}
puts("");
}
return 0;
}C题：一个bfs的广搜题，坑点在需要用优先队列+数据维护最优值
因为不同的地方耗费能量值不一样，有可能步数最近的地方，耗费的能量值很大，而导致走完这个路径之后剩下的能量值很小，比如这个：
Y R R R R R ……………… R
. . . . . . . . . . . . . .. . . . .. . . . .
很明显看到第一行耗费太多能量了，所以要优先队列维护能量最优
题目中还有个坑点是样例中给出来了：当起点与敌人相邻时，没有关系，可以正常走，在bfs的时候特判
剩下的就是基本bfs，注意好边界和题目中的能量耗费就好
#include<bits/stdc++.h>
using namespace std;
char mapp[101][101];
int v[101][101],vis[101][101];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int mark[101][101];
int n,m,mv;
int startx,starty;
typedef struct node{
int x,y,jing;
}node;
struct cmp{
bool operator()(const node &e1, const node &e2){
if (e1.jing < e2.jing)
return true;
return false;
}
};
priority_queue< node, vector<node> , cmp > value;
int inmap(int xxx,int yyy){
if(xxx>n||xxx<1||yyy>m||yyy<1) return 0;
return 1;
}
void bfs(){
int xxx,yyy,jjj;
while(!value.empty()){
xxx=value.top().x;
yyy=value.top().y;
jjj=value.top().jing;
value.pop();
if(vis[xxx][yyy]==1) continue;
if(mapp[xxx][yyy]=='E') continue;
v[xxx][yyy]=1;
vis[xxx][yyy]=1;
int down=0;
for(int i=0;i<4;i++){
if(inmap(xxx+dir[i][0],yyy+dir[i][1])){
if(mapp[xxx+dir[i][0]][yyy+dir[i][1]]=='E'){
down=1;
break;
}
}
}
if(xxx==startx&&yyy==starty) down=0;
// cout<<xxx<<" "<<yyy<<" "<<jjj<<" "<<down<<endl;
// cout<<endl;
if(down==1) continue;
//cout<<value.size()<<endl;
for(int i=0;i<4;i++){
if(inmap(xxx+dir[i][0],yyy+dir[i][1])&&v[xxx+dir[i][0]][yyy+dir[i][1]]==0&&mapp[xxx+dir[i][0]][yyy+dir[i][1]]!='#'){
int lost=0;
if(mapp[xxx+dir[i][0]][yyy+dir[i][1]]=='.'||mapp[xxx+dir[i][0]][yyy+dir[i][1]]=='P') lost=1;
else if(mapp[xxx+dir[i][0]][yyy+dir[i][1]]=='T') lost=2;
else if(mapp[xxx+dir[i][0]][yyy+dir[i][1]]=='R') lost=3;
if(jjj>=lost&&mark[xxx+dir[i][0]][yyy+dir[i][1]]<jjj-lost){
node vvvv;
vvvv.x=xxx+dir[i][0];
vvvv.y=yyy+dir[i][1];
vvvv.jing=jjj-lost;
mark[xxx+dir[i][0]][yyy+dir[i][1]]=jjj-lost;
// cout<<vvvv.x<<" "<<vvvv.y<<" "<<vvvv.jing<<" "<<down<<endl ;
// cout<<endl<<endl;
value.push(vvvv);
}
}
}
// cout<<value.size()<<endl;
}
}
int main(){
//freopen("input.txt","r",stdin);
int t;
node vvv;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&mv);
getchar();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%c",&mapp[i][j]);
if(mapp[i][j]=='Y'){
startx=i;
starty=j;
}
}
getchar();
}
while(!value.empty()) value.pop();
memset(v,0,sizeof(v));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
mark[i][j]=-1;
}
}
vvv.x=startx;
vvv.y=starty;
vvv.jing=mv;
mark[startx][starty]=mv;
value.push(vvv);
//cout<<startx<<" "<<starty<<endl;
bfs();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(v[i][j]==1&&mapp[i][j]!='P'&&mapp[i][j]!='E'&&mapp[i][j]!='Y'){
cout<<"*";
}
else {
cout<<mapp[i][j];
}
}
cout<<endl;
}
cout<<endl;
}
return 0;
}D题：暴力题，分解每个数位去计算就好，手速
#include <iostream>
#include <cstdio>
using namespace std;
int cacl(int a){
int sum=0;
while(a>0){
sum+=a%10;
a=a/10;
}
return sum;
}
int cacl2(int a){
int sum=0;
while(a>0){
sum+=(a%10)*(a%10);
a=a/10;
}
return sum;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
int a;
scanf("%d",&a);
int b=cacl(a);
//cout<<b<<endl;
int c =cacl2(a);
//cout<<c<<endl;
if(a%8==0 || b%8==0 || c%8==0)
cout<<"Lucky number!"<<endl;
else
cout<<"What a pity!"<<endl;
}
return 0;
}E题：模拟，注意当字符串出现重复时，值会覆盖其前一个（即第一个Sample）
#include<iostream>
#include<map>
#include<string.h>
using namespace std;
const int MAX=1000000;
string str,var;
int n;
int Str2Int(string s)
{
int end=0,a=1;
if(s[0]=='-')
end=1;
int res=0;
for(int i=s.size()-1;i>=end; i--)
{
res += (s[i]-'0')*a;
a *= 10;
}
if(end) return -res;
return res;
}
int main()
{
map<string,int> m;
int T,i,value;
char c;
cin>>T;
while(T--)
{
cin>>n;
for(i=0;i<n-1;i++)
{
cin>>var>>c>>value;
m[var]=value;
}
int tmp,ans=0;
bool plus=true;
while(cin>>str)
{
if(str=="?") break;
else if(str=="+") plus=true;
else if(str=="-") plus=false;
else if(str=="=") continue;
else if(str[0]>='a' && str[0]<='z')
{
if(plus) ans += m[str];
else ans -= m[str];
}
else
{
tmp=Str2Int(str);
if(plus) ans += tmp;
else ans -= tmp;
}
}
cout<<ans<<endl;
}
return 0;
}F题：我们现在有1，5，10，50，100的钱币若干，想要得到S
问最小钱币数和最大钱币数
贪心判断最小：能取多少100的，全部拿完；然后是50的，然后是10的，依次类推
如果剩下的是0，那么合法（否则不合法）
这里有个坑点是不能用总和去判断，因为可能尾数中构成不了，即：我有11个5块的，要构成54是构造不出来的，需要找1块钱。。。
最大钱币数这里wa了好多发，是因为贪心思路是：
尽可能把大的，转为小的：这个小的，指的是后面所有的，而不能一级一级的转
即：比如我们用了3张100的，我们要判断，第一个100能不能往后转的条件不是有没有2张50，而是后面的所有的加起来够不够100
说得有点绕，比如我们剩下了1张50，4张10块，1张5，5张1，这些加起来是可以构成100的，所以可以转化
这里数组的名称一定要命名好，因为涉及到原来的钱币数、用过的钱币数、还剩下的钱币数的数***算，一不小心就会搞糊涂的
这里写得很挫，但至少AC了，先放着
#include<bits/stdc++.h>
using namespace std;
long long p,a1,a5,a10,a50,a100;
long long has[6];
long long value[6]={0};
int price[6]={0,100,50,10,5,1};
long long maxx,minn;
int main(){
//freopen("input.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld%lld%lld%lld",&p,&a1,&a5,&a10,&a50,&a100);
has[1]=a100;
has[2]=a50;
has[3]=a10;
has[4]=a5;
has[5]=a1;
long long temp=p;
value[1]=temp/100;
if(value[1]>a100){
value[1]=a100;
temp-=100*a100;
}
else {
temp%=100;
}
value[2]=temp/50;
if(value[2]>a50){
value[2]=a50;
temp-=50*a50;
}
else {
temp%=50;
}
value[3]=temp/10;
if(value[3]>a10){
value[3]=a10;
temp-=10*a10;
}
else {
temp%=10;
}
value[4]=temp/5;
if(value[4]>a5){
value[4]=a5;
temp-=5*a5;
}
else {
temp%=5;
}
value[5]=temp;
if(value[5]>a1){
value[5]=a1;
temp-=1*a1;
}
else {
temp%=1;
}
if(temp==0){
minn=value[1]+value[2]+value[3]+value[4]+value[5];
}
else {
cout<<-1<<" "<<-1<<endl;
continue;
}
//cout<<value[1]<<" "<<value[2]<<" "<<value[3]<<" "<<value[4]<<" "<<value[5]<<endl;
long long temp1,temp2;
for(int i=1;i<5;i++){
for(int j=i+1;j<=5;j++){
temp1=has[j]-value[j];
temp2=temp1/(price[i]/price[j]);
if(value[i]>temp2){
value[i]-=temp2;
value[j]+=temp2*(price[i]/price[j]);
}
else{
value[j]+=value[i]* (price[i]/price[j]);
value[i]=0;
}
}
int ttt=20;
if(value[i]>0){
while(ttt--&&value[i]>0){
int use[6]={0};
int target=price[i];
long long temp4;
for(int k=i+1;k<=5;k++){
temp4=target/price[k];
if(temp4>has[k]-value[k]){
target-=(has[k]-value[k])*price[k];
use[k]=has[k]-value[k];
}
else {
use[k]+=temp4;
target-=temp4*price[k];
}
if(target==0){
value[i]--;
for(int kk=1;kk<=5;kk++){
value[kk]+=use[kk];
}
break;
}
}
}
}
//cout<<value[1]<<" "<<value[2]<<" "<<value[3]<<" "<<value[4]<<" "<<value[5]<<endl;
}
maxx=value[1]+value[2]+value[3]+value[4]+value[5];
cout<<minn<<" "<<maxx<<endl;
}
return 0;
} G题：数学题，必须把本子的重心点落在桌子上，比较正方形边长和矩形的宽的比例关系，推理公式计算即可
三种情况：
A：放一个小角
B：露一个小角
C：全部在里面
分类计算，判断条件记得eps
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
int T;
double L,a,b,ans;
int main(){
scanf("%d",&T);
while(T--){
scanf("%lf%lf%lf",&L,&a,&b);
if (a<b) swap(a,b);
if (L>=sqrt(2)/2.0*b+eps) ans=0.25*b*b;
else if (L<=sqrt(2)*0.25*b+eps) ans=L*L;
else ans=L*L-(sqrt(2)*L-b/2.0)*(sqrt(2)*L-b/2.0);
printf("%.4lf\n",ans);
}
return 0;
}
