A.有理数
签到题：直接用floor函数就行了，详细看代码
#define debug
#include<stdio.h>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<functional>
#include<iomanip>
#include<map>
#include<set>
#define f first
#define s second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>PLL;
typedef pair<int,ll>Pil;
const ll INF = 0x3f3f3f3f;
const double inf=1e8+100;
const double eps=1e-8;
const ll maxn =1e3+200;
const int N = 1e4+10;
const ll mod=1e9+7;
//define
//--solve
void solve() {
int i,j,tt=1;
cin>>tt;
while(tt--){
ll p,q;
ll tmp;
cin>>p>>q;
if(p%q==0){
tmp=floor(p*1.0/q)-1;
}
else tmp=floor(p*1.0/q);
cout<<tmp<<endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
#ifdef debug
freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
cin.tie(0);
cout.tie(0);
solve();
/*
#ifdef debug
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
*/
return 0;
}
B。硬币，实际上50，10都是有5的倍数，所以可以直接吧50，10元的看成是数个5元构成硬币，那问题就容易了，假设一个物品要v元，remain=v%5，就为剩下的还要给少个硬币才能凑够买一个v元物品，然后k=5-remain，这这个k其实就是找回的1元硬币数，详细看代码
#define debug
#include<stdio.h>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<functional>
#include<iomanip>
#include<map>
#include<set>
#define f first
#define s second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>PLL;
typedef pair<int,ll>Pil;
const ll INF = 0x3f3f3f3f;
const double inf=1e8+100;
const double eps=1e-8;
const ll maxn =1e3+200;
const int N = 1e4+10;
const ll mod=1e9+7;
//define
ll c[maxn];
//
ll gcd(ll a,ll b) {
return b==0?a:gcd(b,a%b);
}
//--solve
void solve() {
int i,j,tt=1;
cin>>tt;
ll c1,c2,c4,c3,v;
while(tt--){
ll ans=0ll,sum=0;
cin>>c1>>c2>>c3>>c4>>v;
sum=c2*5+c3*10+c4*50;
ll remain=v%5;
ll k=0ll;
if(remain){
k=5-remain;
v+=k;
}
ans=k*(sum/v)+c1;
cout<<ans<<endl;
}
}
int main() {
ios_base::sync_with_stdio(false);
#ifdef debug
freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
cin.tie(0);
cout.tie(0);
solve();
/*
#ifdef debug
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
*/
return 0;
}
C.腰带环
D.迷宫
比赛的时候用bfs，tle了，然后群里大佬说是用最小分割（听的一头雾水），然后今天看了别人博客的时候发现了跟我想法一样，而他的过的原因：数组没我只开的大。至于最小分割的，以后学了再补上。
分析：实际上就是让你求从上边或者右边到下边或者左边的最短路
#define debug
#include<stdio.h>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<functional>
#include<iomanip>
#include<map>
#include<set>
#define f first
#define s second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>PLL;
typedef pair<int,ll>Pil;
const ll INF = 0x3f3f3f3f;
const double inf=1e8+100;
const double eps=1e-8;
const ll maxn =3e2+300;
const int N = 1e4+10;
const ll mod=1e9+7;
//define
struct node {
int x,y;
ll cost;
node(int x=0,int y=0,ll cost=0):x(x),y(y),cost(cost) {}
bool operator<(const node &a)const {
return cost>a.cost;
}
};
ll d[510][510];
ll mp[600][600];
int dir[4][2]= {0,1,1,0,0,-1,-1,0};
int t,n,m;
priority_queue<node>q;
//ok
bool ok(int x,int y) {
if(x>=1&&x<=n&&y>=1&&y<=m&&mp[x][y]!=0) {
return 1;
}
return 0;
}
//bfs
ll bfs() {
ll ans=-1ll;
while(!q.empty()) {
node now=q.top();
q.pop();
if(now.x==n||now.y==1) {
if(ans==-1)
ans=now.cost;
ans=min(ans,now.cost);
continue;
}
for(int i=0; i<4; i++) {
int xx=now.x+dir[i][0];
int yy=now.y+dir[i][1];
if(xx<1||yy<1||xx>n||yy>m||!mp[xx][yy])
continue;
if(mp[xx][yy]==-1) {
if(d[xx][yy]==-1||d[xx][yy]>now.cost) {
d[xx][yy]=now.cost;
q.push(node(xx,yy,now.cost));
// cout<<xx<<" "<<yy<<" "<d[xx][yy]<<endl;
}
} else {
if(d[xx][yy]==-1||d[xx][yy]>now.cost+mp[xx][yy]) {
d[xx][yy]=now.cost+mp[xx][yy];
q.push(node(xx,yy,d[xx][yy]));
// cout<<xx<<" "<<yy<<" "<d[xx][yy]<<endl;
}
}
}
}
return ans;
}
//--solve
void solve() {
int i,j,tt=1;
// cin>>t>>n>>m;
scanf("%d%d%d",&t,&n,&m);
while(t--) {
for(i=1; i<=n; i++) {
for(j=1; j<=m; j++) {
// cin>>mp[i][j];
scanf("%lld",&mp[i][j]);
}
}
memset(d,-1,sizeof(d));
for(j=1; j<=m; j++) {
if(mp[1][j]) {
d[1][j]=(mp[1][j]==-1?0:mp[1][j]);
q.push(node(1,j,d[1][j]));
}
}
for(i=2; i<=n; i++) {
if(mp[i][m]) {
d[i][m]=(mp[i][m]==-1?0:mp[i][m]);
q.push(node(i,m,d[i][m]));
}
}
// for(i=1; i<=n; i++) {
// for(j=1; j<=m; j++) {
// cout<<mp[i][j]<<" ";
// }
// cout<<endl;
// }
printf("%lld
",bfs());
}
}
int main() {
// ios_base::sync_with_stdio(false);
#ifdef debug
freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
// cin.tie(0);
// cout.tie(0);
solve();
/*
#ifdef debug
fclose(stdin);
fclose(stdout);
system("out.txt");
#endif
*/
return 0;
}