CF 286B(Shifting-deque)

B. Shifting
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

John Doe has found the beautiful permutation formula.

Let's take permutation p = p1, p2, ..., pn.
Let's define transformation f of this permutation:

 k (k > 1) 是每段长度, r 是最大满足 rk ≤ 的整数
 把 r
段和尾剩余部分(如果有)左移.

求序列 f(f( ... f(p = [1, 2, ..., n], 2) ... , n - 1), n) .

Input

一行 n (2 ≤ n ≤ 106).

Output

Print n distinct space-separated integers from 1 to n —
a beautiful permutation of size n.

Sample test(s)
input
2
output
2 1
input
3
output
1 3 2
input
4
output
4 2 3 1
Note

A note to the third test sample:

  • f([1, 2, 3, 4], 2) = [2, 1, 4, 3]
  • f([2, 1, 4, 3], 3) = [1, 4, 2, 3]
  • f([1, 4, 2, 3], 4) = [4, 2, 3, 1]
这题我是用WJMZBMR的神模拟过的。
先普及一下deque< >
deque<int> deq;   //建立双端队列
deq.push_back(x) 
deq.push_front(x) 
deq.pop_back(x) 
deq.pop_back(x) 
然后可以模拟了,每次把每段的最后搬上来。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define MAXN (1000000+10)
deque<int> deq;
int n;
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) deq.push_back(i);
	for (int i=2;i<=n;i++)
	{
		int l=(n-1)/i*i;deq.push_back(deq[l]);
		while (l-i>=0)
		{
			deq[l]=deq[l-i];
			l-=i;
		}
		deq.pop_front();
	}
	for (int i=0;i<deq.size();i++) cout<<deq[i]<<' ';
	return 0;
}

CF 265B(行道树简化版)

B. Roadside Trees (Simplified Edition)
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

 从西向东有 n 棵树,编号 1 到 n ,树顶有nuts.第 i 棵树高 hi.
Liss 想吃所有的 nuts.

Liss 在第1棵树的高度为1的地方. Liss 做下列任意一件事情耗时1s:

  • 向树的上方或下方移动1格.
  • 吃树顶的 nut .
  • 向东边那棵树跳(不能向西跳),高度不变,注意Liss不能从高的地方往低跳。

算出Liss吃掉所有nuts最短时间.

Input

第一行为 n (1  ≤  n ≤ 105)
.

接下来n行为序列 hi (1 ≤ hi ≤ 104)
.

Output

算出Liss吃掉所有nuts最短时间.

Sample test(s)
input
2
1
2
output
5
input
5
2
1
2
1
1
output
14

注意不能往西跳(一开始以为可以,看题仔细啊!)


#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (100000+10)
#define MAXHi (10000+10)
int n,h[MAXN];
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++) cin>>h[i];h[0]=1;
	int ans=0;
	for (int i=1;i<=n;i++) ans+=abs(h[i]-h[i-1]);
/*
	int hmin=h[n];
	for (int i=n-1;i>=1;i--)
	{
		ans=min(ans,ans-abs(h[i]-h[i-1])-abs(h[i+1]-h[i])+abs(h[i-1]-h[i+1])+n-i+abs(hmin-h[i])+abs(hmin-h[n]));
	}
*/
	ans+=2*n;
	cout<<ans<<endl;
	return 0;
}

CF 265A(彩石简化版)

A. Colorful Stones (Simplified Edition)
time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

有一排彩色的石头,用字符串 s 表示,第i个为"R",
"G", or "B"表示颜色。

Liss接到操作符,用"R",
"
G",
or "
B"表示,当Liss所在的彩石与操作符相同时,Liss向前走一格,否则不动。(Liss一开始在彩石1处) 

现给定操作序列 t

请输出Liss最后所占的彩色编号(假设Liss不会走出彩石)

Input

第一行 s (1 ≤ |s| ≤ 50). 第二行 t (1 ≤ |t| ≤ 50).

Output

输出一行Liss最后所占的彩色编号.

Sample test(s)
input
RGB
RRR
output
2
input
RRRBGBRBBB
BBBRR
output
3
input
BRRBGBRGRBGRGRRGGBGBGBRGBRGRGGGRBRRRBRBBBGRRRGGBBB
BBRBGGRGRGBBBRBGRBRBBBBRBRRRBGBBGBBRRBBGGRBRRBRGRB
output
15

模拟题,各种做

注意 scanf("%s%s",&s,&t); s和t都是从0开始的

字符串长度函数为strlen(s)


#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (50+10)
char s[MAXN],t[MAXN];
int main()
{
	scanf("%s%s",&s,&t);
	int j=0;
	for (int i=0;i<strlen(t);i++)
	{
		if (t[i]==s[j]) j++;
	}
	cout<<1+j<<endl;


}

CF 254A(重复的数)

A. 数字卡片
time limit per test

1 second

memory limit per test

256 megabytes

input

input.txt

output

output.txt

2n张卡片编号为1 .. 2n.卡片数字相同可凑成一对,能否凑完?

Input

第一行1个整数n (1 ≤ n ≤ 3·105).
第二行有2n个整数a1, a2, ..., a2n (1 ≤ ai ≤ 5000)
表示第i张卡片的数字。

Output

如果凑不完,请输出 -1.否则输出 n 行,每行一对对整数,表示第i张卡片与第j张凑成一对。

输出任意方案。

Sample test(s)
input
3
20 30 10 30 20 10
output
4 2
1 5
6 3
input
1
1 2
output
-1

直接用数组记录出现次数,每遇到一对,就扔入解中。

Program Cards;
const
   maxn=300000;
var
   n,i,p,size:longint;
   a:array[1..5000] of longint;
   q1,q2:array[1..maxn] of longint;
begin
   assign(input,'input.txt');
   assign(output,'output.txt');
   reset(input);
   rewrite(output);

   read(n);
   fillchar(a,sizeof(a),0);
   size:=1;
   for i:=1 to 2*n do
   begin
      read(p);
      if a[p]>0 then
      begin
         q1[size]:=a[p];q2[size]:=i;
         inc(size);
         a[p]:=0;
      end
      else a[p]:=i;
   end;
   if size<>n+1 then writeln('-1')
   else for i:=1 to n do writeln(q1[i],' ',q2[i]);

   close(input);
   close(output);
end.

Tyvj P2068(寻宝)

P2068 - [NOIP2012P2]寻宝

From luchangzhou    Normal (OI)
总时限:10s    内存限制:128MB    代码长度限制:64KB

背景 Background

NOIP 2012 普及组 题2

描述 Description

传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏 宝楼,藏宝楼的门口竖着一个木板,上面写有几个大字:寻宝说明书。说明书的内容如下: 藏宝楼共有 N+1 层,最上面一层是顶层,顶层有一个房间里面藏着宝藏。除了顶层外, 藏宝楼另有 N 层,每层 M 个房间,这 M 个房间围成一圈并按逆时针方向依次编号为 0,…, M-1。其中一些房间有通往上一层的楼梯,每层楼的楼梯设计可能不同。每个房间里有一个 指示牌,指示牌上有一个数字 x,表示从这个房间开始按逆时针方向选择第 x 个有楼梯的房 间(假定该房间的编号为 k),从该房间上楼,上楼后到达上一层的 k 号房间。比如当前房 间的指示牌上写着 2,则按逆时针方向开始尝试,找到第 2 个有楼梯的房间,从该房间上楼。 如果当前房间本身就有楼梯通向上层,该房间作为第一个有楼梯的房间。

寻宝说明书的最后用红色大号字体写着:“寻宝须知:帮助你找到每层上楼房间的指示 牌上的数字(即每层第一个进入的房间内指示牌上的数字)总和为打开宝箱的密钥”。

请帮助小明算出这个打开宝箱的密钥。

输入格式 InputFormat

第一行 2 个整数 N 和 M,之间用一个空格隔开。N 表示除了顶层外藏宝楼共 N 层楼,M 表示除顶层外每层楼有 M 个房间。

       接下来 N*M 行,每行两个整数,之间用一个空格隔开,每行描述一个房间内的情况, 其中第(i-1)*M+j 行表示第 i 层 j-1 号房间的情况(i=1, 2, …, N;j=1, 2, … ,M)。第一个整数 表示该房间是否有楼梯通往上一层(0 表示没有,1 表示有),第二个整数表示指示牌上的数 字。注意,从 j 号房间的楼梯爬到上一层到达的房间一定也是 j 号房间。

      最后一行,一个整数,表示小明从藏宝楼底层的几号房间进入开始寻宝(注:房间编号 从 0 开始)。

输出格式 OutputFormat

输出只有一行,一个整数,表示打开宝箱的密钥,这个数可能会很大,请输出对 20123取模的结果即可。

样例输入 SampleInput [复制数据]

2 3
1 2
0 3
1 4
0 1
1 5
1 2
1

样例输出 SampleOutput [复制数据]

5

数据范围和注释 Hint

【输入输出样例说明】

第一层:

0 号房间,有楼梯通往上层,指示牌上的数字是 2;

1 号房间,无楼梯通往上层,指示牌上的数字是 3;

2 号房间,有楼梯通往上层,指示牌上的数字是 4;

第二层:

0 号房间,无楼梯通往上层,指示牌上的数字是 1;

1 号房间,有楼梯通往上层,指示牌上的数字是 5;

2 号房间,有楼梯通往上层,指示牌上的数字是 2;

小明首先进入第一层(底层)的 1 号房间,记下指示牌上的数字为 3,然后从这个房间 开始,沿逆时针方向选择第 3 个有楼梯的房间 2 号房间进入,上楼后到达第二层的 2 号房间, 记下指示牌上的数字为 2,由于当前房间本身有楼梯通向上层,该房间作为第一个有楼梯的 房间。因此,此时沿逆时针方向选择第 2 个有楼梯的房间即为 1 号房间,进入后上楼梯到达 顶层。这时把上述记下的指示牌上的数字加起来,即 3+2=5,所以打开宝箱的密钥就是 5。

【数据范围】

对于 50%数据,有 0<N≤1000,0<x≤10000;

对于 100%数据,有 0<N≤10000,0<M≤100,0<x≤1,000,000;

来源 Source

NOIP 2012

纯粹的模拟题,由于x很大但M很小,可以%tot[i]

但是这么做可能变为0.



#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (10000+10)
#define MAXM (100+10)
#define MAXX (1000000+10)
#define F (20123)
#define NDEBUG
int n,m;
int a[MAXN][MAXM],tot[MAXN]={0};
bool b[MAXN][MAXM]={0};
int main()
{
	#ifndef NDEBUG
	freopen("wealth.in","r",stdin);
	#endif
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		for (int j=0;j<=m-1;j++)
		{
			scanf("%d%d",&b[i][j],&a[i][j]);
			tot[i]+=b[i][j];
		}
	#ifndef NDEBUG
	for (int i=1;i<=n;i++) cout<<tot[i]<<' ';
	#endif
	int x,ans=0;
	scanf("%d",&x);
	for (int i=1;i<=n;i++)
	{
		ans=(ans+a[i][x])%F;
		int len=a[i][x]%tot[i];
		if (len==0) len=tot[i];
		while(len)
		{
			len-=b[i][x];
			if (len==0) break;
			x=(x+1)%m;
		}
	}
//	cout<<x<<endl;
	cout<<ans<<endl;
	return 0;
}

POJ 2190(模拟策略)

Language:
ISBN
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 13962   Accepted: 4898

Description

ISBN码满足:(10*A1+9*A2+..+1*A10) mod 11=0
A10是效验码,若它为10,则以X代替,其它位都为0..9的数字
 现在给你一个效验码,但是其中一位看不清,请求出这一位。

Input

1行ISBN码,‘?'表示看不清

Output

输出那一位,无解输-1.

Sample Input

15688?111X

Sample Output

1

Source

这题就是模拟,模拟最重要的是细节,本题值得注意的细节:

1.某1位为0的情况.

2.其它位的乘积和是11的倍数.

3.某1位为X的情况.

4.无解.

5.其它位的乘积和包含'X'.

Program ISBN;
const
   n=10;
   F=11;
var
   s:string;
   i,p,ans:longint;
begin
   ans:=0;
   readln(s);
   if s[n]='X' then s[n]:=char(58);

   p:=pos('?',s);

   for i:=1 to n do
      if i<>p then inc(ans,(ord(s[i])-48)*(10-i+1));
   // ans +p*? mod 11 =0
   ans:=ans mod F;
   ans:=(F-ans) mod F;

   for i:=0 to n do
   begin
      if ((11-p)*i) mod F=ans then
      begin
         if (p=n) and (i=10) then begin writeln('X'); halt; end;
         if (i<10) then begin writeln(i);   halt; end;
      end;
   end;

   writeln('-1');

end.



POJ 1008(模拟)

最后一天特判

Program P1008;
var
   n,i,j1,j2,j,day,month,year:longint;
   daytotal,tday,tmonth,tyear:longint;
   s,s1:string;
   mon:array[1..19] of string=('pop','no','zip','zotz','tzec','xul','yoxkin','mol','chen','yax','zac','ceh','mac','kankin','muan', 'pax', 'koyab', 'cumhu','uayet');
   tmon:array[1..20] of string=('imix', 'ik', 'akbal','kan','chicchan','cimi','manik','lamat','muluk','ok','chuen','eb','ben','ix','mem','cib','caban','eznab','canac','ahau');
begin
   readln(n);
   writeln(n);
   for i:=1 to n do
   begin
      readln(s);
      j1:=1;
      while (s[j1]<>'.') do inc(j1);
      s1:=copy(s,1,j1-1);
      val(s1,day);
      j2:=length(s);
      while (s[j2]<>' ') do dec(j2);
      s1:=copy(s,j2+1,5);
      val(s1,year);
      inc(j1);
      s1:=copy(s,j1+1,j2-j1-1);
      for j:=1 to 19 do
         if s1=mon[j] then
         begin
            month:=j;
            break;
         end;
      daytotal:=year*365+day+1+(month-1)*20;
      tyear:=(daytotal-1) div 260;
      tday:=(daytotal mod 13);
      if tday=0  then tday:=13;
      tmonth:=(daytotal mod 20);
      if tmonth=0 then tmonth:=20;
      writeln(tday,' ',tmon[tmonth],' ',tyear);
   end;

end.

POJ 1068(找规律)

(+1;(-1,用sum表示当前的值,

当sum>=1时,w[i]=i-j+1;( j 表示最后加的一段的右边结点的序数)

Program P1068;
Var
   t,i,j,n:longint;
   p:array[0..20] of longint;
function w:longint;
var
   j,sum:longint;
begin
   if p[i]-p[i-1]>0  then exit(1);
   j:=i;
   sum:=0;
   while (true) do
   begin
      inc(sum,p[j]-p[j-1]);
      if sum>=1 then exit(i-j+1)
      else dec(sum);
      dec(j);
   end;
end;
begin
   read(t);
   p[0]:=0;
   while t>0 do
   begin
      read(n);
      for i:=1 to n-1 do
      begin
         read(p[i]);
         write(w,' ');
      end;
      read(p[n]);
      i:=n;
      writeln(w);
      dec(t);
   end;
end.