牛客多校第七場 B

2020-08-09 00:33:44

題意: 給定 n,m 構造出一個方案,可以組合成 n個m,和m個n。

n<m, 如果一個箱子大於了n,則後面m個n的情況這個不能用這個箱子,故不能滿足,則最多裝n個
1: 當有n個醫院,m個口罩時, 每個醫院最多分配 floor(m/n)個裝着n個口罩的箱子,此時,分配的箱子總數爲floor(m/n) * n->這個既可以表示每個醫院分配floor個箱子,有n個醫院,故有floor(m/n) * n個箱子,也可以表示一個醫院分配floor個箱子,每個箱子有n個口罩,故爲每個醫院當前分配的口罩 個,每一個醫院還需要 m%(n*floor(m/n)) ->等價於 m%n(這裏floor(m/n)*n 是小於m的)
2:當有m個醫院,n個口罩,之前已經分配了floor(m/n)*n 個箱子,且每個箱子都爲n個,故有了floor(m/n)*n 個醫院已經得到了 , 剩下 m - floor(m/n)*n ->這裏因爲floor(m/n)*n <= m && floor(m/n)*n > m/2 ,所以m%(floor(m/n)*n)等價於m%n個醫院需要得到 n個口罩
3 上面的提出來就是, 有 n個醫院缺 m%n個口罩 和 m%n 個醫院缺n個口罩

類似gcd,dfs處理一下就行了。
c++ 程式碼:

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<bits/stdc++.h>
#define int long long
#define sc scanf
#define pf printf
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
 
const int INF = 0x3f3f3f3f;
const double eps = 1e-4;
const int mod = 1e9+7;
const int N = 20000000;

vector<int> ans;

void dfs(int n,int m){
	if(n == 0) return ;
	for(int i=0;i<m/n*n;i++) ans.push_back(n);
	dfs(min(m%(m/n*n),n),max(m%(m/n*n),n));
}

signed main(){
//	IOS;
	#ifdef ddgo
		freopen("C:/Users/asus/Desktop/ddgoin.txt","r",stdin);
	#endif
	
	int tt; cin>>tt;
	while(tt --){
		ans.clear();
		int n,m; cin>>n>>m;
		dfs(min(n,m),max(n,m));
		cout<<(int)ans.size()<<"\n"<<ans[0];
		for(int i=1;i<(int)ans.size();i++) cout<<" "<<ans[i];
		puts("");
	}
	
    return 0;
}