社区讨论

dalao求调啊 求求各位了 WA后5个点 貌似爆了 有负数输出(悬关

P1080[NOIP 2012 提高组] 国王游戏参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo23ll3z
此快照首次捕获于
2023/10/23 07:26
2 年前
此快照最后确认于
2023/11/03 07:47
2 年前
查看原帖
rt rp++ 蒟蒻调了两天了 都不知道到底哪里爆了 想死呜呜呜
CPP
#include <iostream>
#include <string>
#include <cstdio>
#include <vector> 
#include <algorithm>
#define int long long 
using namespace std;
//容器内的数位顺序是倒序 
int n;
struct node{
	int x,y;
}q[1005];
bool cmp(node x,node y){
	return x.x*x.y<y.x*y.y; 
}
void input(vector <int> &x,string s){
	for(int i=s.size()-1;i>=0;--i)
		x.push_back(s[i]-'0');
}
void output(vector <int> x){
	for(auto i:x)
			printf("%d",i);
	printf(" ");
}
vector <int> add(vector <int> a,vector<int> b){
	vector <int> c;
	int t=0,lena=a.size(),lenb=b.size();
	for(int i=0;i<min(lena,lenb);++i){
		c.push_back((a[i]+b[i]+t)%10);
		if(a[i]+b[i]+t>=10)
			t=1;
		else t=0;
	}
	int i=min(lena,lenb);
	while(i<lena){
		c.push_back((a[i]+t)%10);
		if(a[i]+t>=10)
			t=1;
		else t=0;
		++i;
	}
	while(i<lenb){
		c.push_back((b[i]+t)%10);
		if(b[i]+t>=10)
			t=1;
		else t=0;
		++i;
	}
	if(t==1)	c.push_back(1);
	return c;
}
vector <int> simple_multiply(int x,vector <int> a){
	vector <int> c;
	int t=0,lena=a.size();
	for(int i=0;i<lena;++i){
		c.push_back((x*a[i]+t)%10);
		t=(x*a[i]+t)/10;
	}
	if(t)	c.push_back(t);
	return c;
}
vector <int> devide(vector <int> x,int y){
	vector <int> ans,tmp;
	ans.clear(); 
	tmp.clear();
	int t=0;
	for(int i=0;i<x.size();++i){
		ans.push_back((t*10+x[i])/y);
		t=(t*10+x[i])%y;
	}
	bool f=0;
	for(int i=0;i<ans.size();++i){
		if(ans[i]!=0)
			f=1;
		if(f)
			tmp.push_back(ans[i]);
	}
	return tmp;
} 
vector <int> max_for_BIGINTEGER(vector<int> a,vector <int> b){
	if(a.size()!=b.size())
		return (a.size()>b.size() ? a : b);
	for(int i=a.size();i>=0;i--){
		if(a[i]!=b[i])
			return	(a[i] > b[i] ? a : b); 
	}
	return a;
} 
signed main(){
	cin>>n;
	int leftt,rightt;
	cin>>leftt>>rightt;
	for(int i=1;i<=n;++i){
		cin>>q[i].x>>q[i].y;
	}
	sort(q+1,q+1+n,cmp);
	vector <int> s,ans;
	input(s,to_string(leftt));
	input(ans,"0");
	for(int i=1;i<=n;++i){
	//	output(s);
	//	cout<<q[i].x<<' '<<q[i].y<<' ';
		vector <int> tmp;
		tmp=s;
		reverse(tmp.begin(),tmp.end());
	//	output(devide(tmp,q[i].y));
	//	cout<<endl;
		ans=max_for_BIGINTEGER(devide(tmp,q[i].y),ans);
		s=simple_multiply(q[i].x,s); 
	}
	output(ans);
	return 0;
} 

回复

2 条回复,欢迎继续交流。

正在加载回复...