社区讨论

求助二进制警报器实现问题

P7603[THUPC 2021] 鬼街参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mi8w0c8n
此快照首次捕获于
2025/11/21 21:19
3 个月前
此快照最后确认于
2025/11/21 22:09
3 个月前
查看原帖
如题,我根据 zky\text{zky} 的二进制警报器算法思想尝试写了一个实现。按照道理来说二进制警报器的复杂度和常数应该是很小的,但是下面的代码在第 7\text{7} 个点运行了 8\text{8} 秒多(未卡常)。
奇怪的是这个代码无论是在 loj\text{loj} 上还是本地运行该测试点只需要跑两秒,并且我确信我的电脑不会和洛谷有接近 4\text{4} 倍的运行效率差异。
求好心人帮忙看看是哪里出了问题?
CPP
/* K_crane x N_cat */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 100010;
int n, m, lastans, current; vector < int > ans; long long a[N];

int col[N], ch;
vector < int > fact[N]; bool nonp[N];
struct Checker
{
	long long base, lim; int p, h;
	Checker() {h = -1;}
}; Checker c[N]; int cn; vector < int > S[N][48];
inline long long get_next(long long x, long long d) {return (x + (d - 1)) / d * d;}
inline void set_checker(int ID)
{
	long long sum = 0;
	for(int x : fact[c[ID].p]) sum += a[x];
	if(sum >= c[ID].lim) {c[ID].h = -1; ++current; ans.push_back(ID); return ;}
	for(int i = 0; ; ++i)
	{
		long long sum = 0;
		for(int x : fact[c[ID].p]) sum += get_next(a[x] + 1, (1ll << i));
		if(sum <= c[ID].lim) c[ID].h = i;
		else break;
	}
	
	for(int x : fact[c[ID].p]) S[x][c[ID].h].push_back(ID);
}

int main()
{
//	freopen("text.in", "r", stdin);
//	freopen("prog.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 2; i <= n; ++i)
	{
		if(nonp[i]) continue;
		for(int j = i; j <= n; j += i)
			nonp[j] = true, fact[j].push_back(i);
	}
	for(int i = 1; i <= m; ++i)
	{
		int opt, p; long long num; cin >> opt >> p >> num;
		num ^= lastans;
		if(opt == 0)
		{
			++ch; vector < int > tmp;
			for(int x : fact[p])
			{
				long long lst = a[x];
				a[x] += num;
				for(int j = 0; j <= 60; ++j)
				{
					if(get_next(lst + 1, (1ll << j)) <= a[x])
					{
						for(int id : S[x][j])
						{
							if(c[id].h != j) continue;
							if(col[id] != ch)
							{
								col[id] = ch;
								tmp.push_back(id);
							}
						}
						S[x][j].clear();
					}
					else break;
				}
			}
			for(int id : tmp) set_checker(id);
			cout << (lastans = current) << " ";
			sort(ans.begin(), ans.end());
			for(int x : ans) cout << x << " "; cout << '\n';
			current = 0; ans.clear();
		}
		else
		{
			++cn; c[cn].p = p;
			for(int x : fact[p]) c[cn].base += a[x];
			c[cn].lim = c[cn].base + num;
			set_checker(cn);
		}
	}
	return 0;
}
/*
2 7
1 2 2
1 2 4
1 2 1
0 2 7
1 2 6
1 2 5
0 2 4
*/

回复

5 条回复,欢迎继续交流。

正在加载回复...