求助 CF919(Div. 2) 的 D 题
  • 板块学术版
  • 楼主Pigsyy
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/1/14 11:04
  • 上次更新2024/1/14 13:38:03
查看原帖
求助 CF919(Div. 2) 的 D 题
936147
Pigsyy楼主2024/1/14 11:04

思路大概是这样的:

记录每一个多次复制的位置,然后倒着来看,对于每一个位置考虑当前的 kk(表示要求第 kk 个数),如果 kk 是比当前位置数字的个数大的,说明就在这个位置之后,就直接输出 kk 个位置的数;反之,说明在这么多个复制里面,就对 Bk−1B_{k-1} 取模(BiB_i 表示到第 ii 个点的数字个数,Bk−1B_{k-1} 就是复制的长度),如果取模后为 00,就更新为 Bk−1B_{k-1},因为 00 就相当于最后一个。

自己试了几个数据,好像都没问题,然后就 WA 了!

大家能不能帮忙指出错误,或给个错误数据也行呀~~~ qwq 求求了

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int SIZE = 1e5 + 10;

int N, Q;
int B[SIZE], Op[SIZE], Id;
map<int, int> A;

void solve()
{
	Id = 0;
	cin >> N >> Q;

	A.clear();
	int P, X, Flag = 0, Flag2 = 0;
	std::vector<int> Pos;
	Pos.push_back(0);
	for (int i = 1; i <= N; i ++)
	{
		cin >> P >> X;
		if (P == 2 && 2e18 / B[i - 1] < X + 1) Flag = i - 1, Flag2 = 1;
		if (Flag) continue;
		if (P == 1)
			B[i] = B[i - 1] + 1, A[B[i]] = X, Op[i] = 1;
		else
			B[i] = B[i - 1] + (B[i - 1] * X), Op[i] = 2, Pos.push_back(i);
		if (B[i] > 1e18) Flag = i;
	}

	reverse(Pos.begin(), Pos.end());

	while (Q --)
	{
		int X;

		cin >> X;

		if (Flag2 && X > B[Flag]) X %= B[Flag];
		if (!X) X = B[Flag];
		for (auto c : Pos)
			if (X > B[c])
			{
				cout << A[X] << " ";
				break;
			}
			else
			{
				X %= B[c - 1];
				if (!X) X = B[c - 1];
			}
	}

	cout << endl;
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int Data;

	cin >> Data;

	while (Data --)
		solve();

	return 0;
}
2024/1/14 11:04
加载中...