社区讨论
求助二进制警报器实现问题
P7603[THUPC 2021] 鬼街参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi8w0c8n
- 此快照首次捕获于
- 2025/11/21 21:19 3 个月前
- 此快照最后确认于
- 2025/11/21 22:09 3 个月前
如题,我根据 的二进制警报器算法思想尝试写了一个实现。按照道理来说二进制警报器的复杂度和常数应该是很小的,但是下面的代码在第 个点运行了 秒多(未卡常)。
奇怪的是这个代码无论是在 上还是本地运行该测试点只需要跑两秒,并且我确信我的电脑不会和洛谷有接近 倍的运行效率差异。
求好心人帮忙看看是哪里出了问题?
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 条回复,欢迎继续交流。
正在加载回复...