Codeforces 380A Sereja and Prefixes(模拟）

题目链接：Codeforces 380A Sereja and Prefixes

题目大意：给出m次操作，分别有1：在序列最后加上x；2：复制1~x，y次，添加在序列尾部。然后给出n次查询，问说在第k[i]个位置上的数事多少。

解题思路：因为x不会大于10^5,就是说复制的部分最多就10^5，那么久可以在一开始将前10^5个数记录下来，后面只需要遍历n的同时移动m即可，但是字节很恶心，表示这辈子再也不想敲这种题了。

#include <stdio.h>
#include <string.h>
#include <iostream>

using namespace std;
const int N = 100005;
typedef long long ll;

struct order {
	int s;
	ll x, y;
}o[N];
int n, m, num[N], ans[N], c, cnt;
ll k[N];

void handle () {
	c = 0;
	for (int i = 0; i < m; i++) {
		if (o[i].s == 1) {
			num[c++] = o[i].x;
			if (c >= 100000) return;
		} else {
			for (ll t = 0; t < o[i].y; t++) {
				for (ll j = 0; j < o[i].x; j++) {
					num[c++] = num[j];
					if (c >= 100000) return;
				}
			}
		}
	}
}

void init () {
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d", &o[i].s);
		if (o[i].s == 1) cin >> o[i].x;
		else cin >> o[i].x >> o[i].y;
	}

	handle();
	scanf("%d", &n);
	for (int i = 0; i < n; i++) cin >> k[i];
}

void solve () {


	int i = 0, j = 0;
	ll p = 0;
	while (i < n) {
		while (j < m) {
			if (o[j].s == 1) {
				p++;  j++;
				if (p == k[i]) {
					ans[i] = o[j-1].x; i++;
					if (i >= n) return;
					break;
				}
			} else {
				ll q = p;
				p += o[j].x * o[j].y;
				if (p >= k[i]) {
					while (i < n) {
						if (k[i] <= p) {
							ans[i] = num[(k[i] - q - 1) % o[j].x % 100000];
							i++;
							if (i >= n) return ;
						} else {
							j++; break;
						}
					}
				} else j++;
			}
		}
	}
}

int main () {
	init ();
	solve ();
	printf("%d", ans[0]);
	for (int i = 1; i < n; i++) printf(" %d", ans[i]);
	printf("\n");
	return 0;
}

Codeforces 380A Sereja and Prefixes(模拟）

原文：http://blog.csdn.net/keshuai19940722/article/details/19016703