a157: NOI2007 Day2.1.项链工厂
標籤 :
通過比率 : 77% (10 人 / 13 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2014-11-01 03:18

內容

T 公司是一家专门生产彩色珠子项链的公司,其生产的项链设计新颖、款式
多样、价格适中,广受青年人的喜爱。最近T 公司打算推出一款项链自助生产
系统,使用该系统顾客可以自行设计心目中的美丽项链。


该项链自助生产系统包括硬件系统与软件系统,软件系统与用户进行交互并
控制硬件系统,硬件系统接受软件系统的命令生产指定的项链。该系统的硬件系
统已经完成,而软件系统尚未开发,T 公司的人找到了正在参加全国信息学竞赛
的你,你能帮助T 公司编写一个软件模拟系统吗?


一条项链包含N 个珠子,每个珠子的颜色是1, 2, …, c 中的一种。项链被固
定在一个平板上,平板的某个位置被标记位置1,按顺时针方向其他位置被记为
2,3,…,N。 

 

你将要编写的软件系统应支持如下命令:

 
命令参数限制内容
R k0<k<N意为Rotate k。将项链在平板上顺时针旋转k个位置, 即原来处于位置1的珠子将转至位置k+1,处于位置2的珠子将转至位置k+2,依次类推。
F 意为Flip。将平板沿着给定的对称轴翻转,原来处于位置1的珠子不动,位置2上的珠子与位置N上的珠子互换,位置3上的珠子与位置N-1上的珠子互换,依次类推。
S i j1≤i , j≤N意为Swap i , j。将位置i上的珠子与位置j上的珠子互换。
P i j x1≤i , j≤N, x≤c意为Paint i , j , x。将位置i沿顺时针方向到位置j的一段染为颜色x
C 意为Count。查询当前的项链由多少个部分组成,我们称项链中颜色相同的一段为一个部分
CS i j1≤i , j≤N意为CountSegment i , j。查询从位置i沿顺时针方向到位置j的一段中有多少个部分组成。
輸入說明
输入文件第一行包含两个整数N, c,分别表示项链包含的珠子数目以及颜色
数目。第二行包含N 个整数,x1, x2…, xn,表示从位置1 到位置N 的珠子的颜色,
1 ≤ xi ≤ c。第三行包含一个整数Q,表示命令数目。接下来的Q 行每行一条命令,
如上文所述。
輸出說明

对于每一个C 和CS 命令,应输出一个整数代表相应的答案。

範例輸入
5 3
1 2 3 2 1
4
C
R 2
P 5 5 2
CS 4 1
範例輸出
4
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 4.0s , <1K
公開 測資點#1 (10%): 4.0s , <1K
公開 測資點#2 (10%): 4.0s , <1M
公開 測資點#3 (10%): 4.0s , <1M
公開 測資點#4 (10%): 4.0s , <1M
公開 測資點#5 (10%): 4.0s , <1M
公開 測資點#6 (10%): 4.0s , <10M
公開 測資點#7 (10%): 4.0s , <10M
公開 測資點#8 (10%): 4.0s , <10M
公開 測資點#9 (10%): 4.0s , <10M
提示 :
对于60%的数据,N ≤ 1 000,Q ≤ 1 000;
对于100%的数据,N ≤ 500 000,Q ≤ 500 000,c ≤ 1 000。
標籤:
出處:
NOI2007Day2第一题 [編輯:
liouzhou_101 (王启圣)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」