Wannafly交流赛1（施工中）

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\n",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;

}