疑似数据有锅?
查看原帖
疑似数据有锅?
1412938
A7F3jK9pR0xf_楼主2025/8/29 15:18

RT, 这是我最开始提交的代码,它获得了 95 pts(提交记录):

#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const int N = 1e5 + 10, M = 1e7 + 10;
int pri[M / 10], minp[M], tot;
bool vis[M];
il void euler(int n)
{
	vis[0] = vis[1] = 1;
	for(int i = 2;i <= n;++i)
	{
		if(!vis[i]) pri[++tot] = i, minp[i] = i;
		for(int j = 1;pri[j] <= n / i;++j)
		{
			vis[i * pri[j]] = 1;
			minp[i * pri[j]] = pri[j];
			if(i % pri[j] == 0) break;
		}
	}
}
int f[N], a[N], n;
map<set<int>, int> mp;
map<set<int>, bool> tag;
set<int> s;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	euler(1e7);
	cin >> n;
	for(int i = 1;i <= n;++i) cin >> a[i];
	int ans = 0;
	for(int i = 1;i <= n;++i)
	{
		s.clear();
		int x = a[i];
		while(x > 1)
		{
			int y = minp[x], cnt = 0;
			while(x % y == 0) x /= y, cnt++;
			if(cnt & 1) s.insert(y);
		} 
		if(!tag.count(s))
		{
			if(s.empty()) f[i] = 1;
			else f[i] = 0;
		}
		else
		{
			if(s.empty()) f[i] = mp[s] + 1;
			else if(mp[s] == 0) f[i] = mp[s] + 2;
			else f[i] = mp[s] + 1;	
		} 
		mp[s] = max(mp[s], f[i]);
		tag[s] = 1;
		ans = max(ans, f[i]);
	}
	cout << ans;
	return 0;
}

但是我把 ansans 的初始化从 00 改成 11 就通过了(提交记录

我认为两者代码的区别当且仅当以下数据(即 n=1n=1 加上一个非完全平方数)

1
2

这个输出应该是 00,AC 程序输出的是 11,95 程序输出是 00

请问是我的程序有 bug 还是数据锅了?

求助,违规紫衫

2025/8/29 15:18
加载中...