求助,Subtask #1 爆RE,但是#0全通过了
查看原帖
求助,Subtask #1 爆RE,但是#0全通过了
1313809
gemini_ae楼主2024/4/8 00:04

如题,Substak#1 一直是RE 没想明白为什么,也没发现有哪里会溢出的 求大佬解惑

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace::std;

long long INF = 1ull<<63-1;

int main() {
	int n;
	long long l, r ,a;
	cin >> n >> l >> r;
	vector<int> A;
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		A.push_back(a);
	}
	sort(A.begin(), A.end());
	vector<long long> dis(A[0],INF);
	dis[0] = 0;
	bool flag = true;

	queue<int> q;
	q.push(0);
	vector<int>vis(A[0], 0);
	vis[0] = 1;
	int cur;
	while (!q.empty())
	{
		cur = q.front();
		q.pop(), vis[cur] = 0;

		for (int j = 1; j < A.size(); j++)
		{
			if (dis[(cur + A[j]) % A[0]] > dis[cur] + A[j])
			{
				dis[(cur + A[j]) % A[0]] = dis[cur] + A[j];
				if (!vis[(cur + A[j]) % A[0]])
				{
					vis[(cur + A[j]) % A[0]] = 1;
					q.push((cur + A[j]) % A[0]);
				}
			}
		}
	}

	//while (flag)
	//{
	//	flag = false;

	//	for (int i = 0; i < dis.size(); i++)
	//	{
	//		if (dis[i] == INF)
	//			continue;
	//		for (int j = 1; j < A.size(); j++)
	//		{
	//			if (dis[(i + A[j]) % A[0]] > dis[i] + A[j])
	//			{
	//				dis[(i + A[j]) % A[0]] = dis[i] + A[j];
	//				flag = true;
	//			}
	//		}
	//	}
	//}
	long long ans=0;
	for (int d = 0;d <dis.size();d++)
	{
		if (dis[d] == INF)
			continue;
		if (dis[d] < l)
		{
			long long  L = (l-d-1) / A[0] * A[0] +d;
			ans += (r - L) / A[0];
		}
		else if (dis[d] >= l&& dis[d] <=r)
			ans += (r - dis[d]) / A[0] + 1;
	}

	cout << ans;

}
2024/4/8 00:04
加载中...