QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#135747#5460. Sum of NumberslinninsRE 0ms2136kbC++141.9kb2023-08-05 23:32:542023-08-05 23:32:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-05 23:32:55]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:2136kb
  • [2023-08-05 23:32:54]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

char Mid[200500];
int Map[200500];

int Ans[200500];
int Sum[200500];

int Anspoint = 2147483647;
int Sumpoint = 0;

void ADD(int p,int n)
{
	for(int i=1;i<=n;i++)
	{
		Sum[i] += Map[p+i];
	}
	Sumpoint = max(Sumpoint,n);
}

void clearSum(int n)
{
	int flag = Sumpoint;
	for(int i=1;i<Sumpoint;i++)
	{
		Sum[i+1] += Sum[i]/10;
		Sum[i] %= 10; 
	}
	while(Sum[flag]>10)
	{
		Sum[flag+1] = Sum[flag]/10;
		Sum[flag]%=10;
		flag+=1;
		Sumpoint = flag;
	}

}

void change()
{
	Anspoint = Sumpoint;
	for(int i=1;i<=Sumpoint;i++)
	{
		Ans[i] = Sum[i];
	}
}

void updateAns()
{
	if(Anspoint>Sumpoint)
	{
		change();
	}
	else if(Anspoint==Sumpoint)
	{
		for(int i=Anspoint;i>=1;i--)
		{
			if(Ans[i]>Sum[i])
			{
				change();
				break;
			}
			else if(Ans[i] < Sum[i])
				break;
		}
	}
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n,k;
		Anspoint = 2147483647;
		scanf("%d%d",&n,&k);
		k+=1;
		scanf("%s",Mid);
		int len = strlen(Mid);
		for(int i=len;i>=1;i--)
		{
			Map[i] = Mid[len-i] - '0';
		}
		int avg = n/k;
		int type = pow(3,k+1);
		type -= 1;
		
		for(int i = type;i>=0;i--)
		{
			int MID = i;
			int Sumn = 0;
			Sumpoint = 0;
			for(int i=1;i<=avg+1;i++)
			{
				Sum[i] = 0;
			}
			for(int j=1;j<=k;j++)
			{
				if(MID%3 == 2)
				{
					ADD(Sumn,avg-1);
					Sumn+=avg-1;
				}
				if(MID%3 == 1)
				{
					ADD(Sumn,avg+1);
					Sumn+=avg+1;
				}
				else
				{
					ADD(Sumn,avg);
					Sumn+=avg;
				}
				MID/=2;
				if(Sumn == n)
				{
					clearSum(n);
					updateAns();
				}
			}

		}
		for(int i=Anspoint;i>=1;i--)
		{
			printf("%d",Ans[i]);
		}
		printf("\n");
		
	}
}

/*
20
10 2
2156345972

20
14 3
32154512561264

20
14 6
12345678910354

*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 2136kb

input:

2
8 1
45455151
2 1
42

output:

9696
6

result:

ok 2 lines

Test #2:

score: -100
Runtime Error

input:

10
1301 6
56328399613959594774559774218276494124991536454496431869449134772679831477279356599352619469813771742358572734317965823527349354276551857226632977613336815474383422853946661428822284645652423563864641261338984158269966469425994769486371736593879954275146732544891889693921182364554588732946...

output:


result: