QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#350949#5460. Sum of NumbersatgcTL 1ms3696kbC++172.3kb2024-03-11 10:42:182024-03-11 10:42:18

Judging History

你现在查看的是最新测评结果

  • [2024-03-11 10:42:18]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3696kb
  • [2024-03-11 10:42:18]
  • 提交

answer

#include<bits/stdc++.h>
#define lb(x) (x&-x)
#define mid ((l+r)>>1)
#define ls (x<<1)
#define rs (ls|1)
#define int long long
#define pii pair<int,int>
using namespace std;
const int maxn = 2e6+10;
struct INT{
	static constexpr int D = 100000, Dc = log10(D);
	int a[maxn],n; //[1...n]
	void clear() {
		memset(a+1,0,(n)*sizeof a[0]);
		n=0;
	}
	void add_equal(INT const&rhs) {
		// infun(*this,rhs);
		int m = rhs.n; auto&b=rhs.a;
		// deb(n,m,a[0],a[1],a[2],a[3],a[4],a[5]);
		// deb(b[1],b[2],b[3],b[4]);
		int i = 1,gg=0;
		for(;i <= max(n,m) || a[i+1];++i) {
			a[gg=i] += b[i];
			if(a[i] >= D) a[i] -= D, ++a[gg=i+1];
		}n=gg;
		// deb(i);

		// debf(a[1],a[2],a[3],a[4]);

	}
	void operator=(INT const&rhs){
		clear();
		n=rhs.n;
		memcpy(a+1,rhs.a+1,n*sizeof a[0]);
		// debf(a[1],a[2],a[3],a[4]);

	}
	bool operator<(INT const&rhs)const{
		int m = rhs.n; auto&b=rhs.a;
		if(n != m) return n < m;
		for(int i = n;i;--i)
			if(a[i]!=b[i]) return a[i] < b[i];
		return 0;
	}
	friend ostream&operator<<(ostream&cout,INT const&va) {
		int n=va.n; auto&a=va.a;
		cout<<a[n];
		while(--n>0)cout<<setw(Dc)<<setfill('0')<<a[n];
		return cout.clear(),cout;
	}
	void setval(char* beg,char* end) {
		clear();
		n = 1; int W=1;
		while(end!=beg) {
			--end;
			if(W >= D)++n,W=1;
			(a[n])+=W*(*end&15);W*=10;
		}
		// debf(a[1],a[2],a[3],a[4]);
	}
	// void setval(auto rang){setval(rang.begin(),rang.end());}
}ans,res,cur;
int T;
int n,k;
char a[maxn];
int la;
int ds[maxn];
void cal() {
	res.clear();//, cur.clear();
	for(int i = 0;i <= k;++i) {
		// deb(i,g);
		// deb(res);
		cur.setval(a+ds[i]+1,a+ds[i+1]+1);
		// deb(res,cur);
		res.add_equal(cur);
		// deb(res);
	}
	// assert(g == n);
	// deb(res);
	if(res < ans || !ans.n) ans = res;
}
void dfs(int d,int pre) {
	if(pre <= 0)return;
	// infun(d,pre);
	if(d == k+2 && ds[d-1] == n) {
		cal();
		return;
	}
	if(d > k+1) return;
	ds[d]=ds[d-1]+pre;
	dfs(d+1,pre);
	ds[d]=ds[d-1]+pre-1;
	dfs(d+1,pre-1);
	ds[d]=ds[d-1]+pre+1;
	dfs(d+1,pre+1);
}
void sol() {
	ans.clear();
	cin>>n>>k>>(char(&)[maxn])a[1];
	la = n/(k+1);
	for(int a=sqrt(n)/3;a <= la*10;++a) dfs(1,a);
	cout<<ans<<'\n';
}
signed main() {
	// freopen("E.in","r",stdin);
	// freopen("E.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;while(T--)sol();
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3696kb

input:

2
8 1
45455151
2 1
42

output:

9696
6

result:

ok 2 lines

Test #2:

score: -100
Time Limit Exceeded

input:

10
1301 6
56328399613959594774559774218276494124991536454496431869449134772679831477279356599352619469813771742358572734317965823527349354276551857226632977613336815474383422853946661428822284645652423563864641261338984158269966469425994769486371736593879954275146732544891889693921182364554588732946...

output:

2861837555106640794797067737879913860686764066159587941287350938727749577629356630565034353414526438507603808735990935008225192080065174423508575377930722196909797866802717925250679901255
1330897896655974774035586406544907434842835048336411271110427836483063457950873824562288934364096546537492367401...

result: