NOI.AC

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#213429	#2355. Digit	STASISZHY	100	1008ms	18712kb	C++11	982b	2024-11-11 22:07:52	2024-11-11 23:10:19

answer

// Problem: D. Digit
// Contest: unde.fined - NOIP2024训练赛 02
// URL: http://119.28.3.174/contest/1154/problem/2355
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 2e5 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m, ans;
int s[N], dp[N];
PII p1, p2;

queue<PII> q;

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	memset(dp, INF, sizeof dp);
	cin >> n;
	for(int i = 1; i <= 9; i ++)
	{	
		p1.fi = i % n, p1.se = i * i;
		q.push(p1);
	}
	while(!q.empty())
	{
		p2 = q.front(); q.pop();
		if(dp[p2.fi] <= p2.se) continue;
		dp[p2.fi] = p2.se;
		for(int i = 0; i <= 9; i ++)
		{
			p1.fi = (10 * p2.fi + i * i) % n, p1.se = p2.se + i * i;
			q.push(p1);
		}
	}
	cout << dp[0] << '\n';	
	return 0;
}

源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10

Accepted

time: 75ms

memory: 10028kb

input:

output:

result:

ok 1 number(s): "1"

Test #2:

score: 10

Accepted

time: 138ms

memory: 10964kb

input:

output:

result:

ok 1 number(s): "2"

Test #3:

score: 10

Accepted

time: 183ms

memory: 17424kb

input:

output:

result:

ok 1 number(s): "3"

Test #4:

score: 10

Accepted

time: 93ms

memory: 13184kb

input:

output:

result:

ok 1 number(s): "18"

Test #5:

score: 10

Accepted

time: 76ms

memory: 13776kb

input:

output:

result:

ok 1 number(s): "27"

Test #6:

score: 10

Accepted

time: 28ms

memory: 4228kb

input:

output:

result:

ok 1 number(s): "5"

Test #7:

score: 10

Accepted

time: 81ms

memory: 11316kb

input:

output:

result:

ok 1 number(s): "36"

Test #8:

score: 10

Accepted

time: 184ms

memory: 18712kb

input:

output:

result:

ok 1 number(s): "10"

Test #9:

score: 10

Accepted

time: 83ms

memory: 10356kb

input:

output:

result:

ok 1 number(s): "14"

Test #10:

score: 10

Accepted

time: 67ms

memory: 11260kb

input:

output:

result:

ok 1 number(s): "15"

Extra Test:

score: 0

Extra Test Passed