week15课上实验csp

问题A - Q 老师的记录册

问题描述

Q 老师有 N 个学生，每个学生都有各自独立的编号，且编号范围在 1 ~ N 之间。

这一天，所有学生都在不同的时间进入教室。

Q 老师记录了当编号为 i 的学生进入教室时，教室中共有 Ai 个学生（包括编号为 i 的学生）。

现要求根据这些记录，给出学生进入教室的顺序。
1 ≤ N ≤ 1e5

1 ≤ Ai ≤ N，Ai 各不相同

所有数字均为整数

题目分析

这个就是将输入的第i个数是j，转换成第j个数是i；
所以直接用一个数组，将输入的数字shu，把那个数组的第shu个值更新为第几个输入的值即可

代码

#include<iostream>
using namespace std;
int N,a[100002],shu;
int main()
{
	cin>>N;
	for(int i=1;i<=N;i++)
	{
		cin>>shu;
		a[shu]=i;
	}
	for(int i=1;i<=N;i++)
	{
		cout<<a[i];
		if(i==N)cout<<endl;
		else cout<<" ";
	}
 } 

问题B - ZJM 的本领

问题描述

众所周知，ZJM 住在 B 站。

这一天 Q 老师来找 ZJM 玩，ZJM 决定向 Q 老师展现一下自己快速看番的本领。

ZJM 让 Q 老师任意挑选了一部番，Q老师一眼看中了《辉夜大小姐想让我告白》，已知这部番一共有 N 个精彩片段，每个精彩片段用 [L[i], R[i]] 来表示。

ZJM 从第一分钟开始看，每次可以按下快进键，快进 X 分钟，问 ZJM 最快需要多久可以看完这部番。
第一行给出两个整数 N、X（1 ≤ N ≤ 50, 1 ≤ X ≤ 1e5）

接下来 N 行，每行给出两个整数，L[i]、R[i]（1 ≤ L[i] ≤ R[i] ≤ 1e5）

数据保证，R[i-1] < L[i]

题目分析

分别用l两个数组来表示左端点和右端点，因为已经排好序，这里就不多做处理
先把总的时间拿出来，再将每一段非重要部分，尽可能的减去X，也就是先整除，知道整数能有几个X，然后再减去这几个X，注意一下最前面的多减上最开始到第一段精彩部分的时间能否跳过这个要单独算一下。

代码

#include<iostream>
using namespace std;
int N,X; 
int R[100],L[100];
int time;
int main()
{
	cin>>N>>X;
	time=0;
	for(int n1=0;n1<N;n1++)
	{
		cin>>L[n1]>>R[n1];
		
	}
	time=R[N-1];
	for(int n1=0;n1<N;n1++)
	{
		if(n1==0)
		{
			time=time-X*((L[n1]-1)/X);
			
		}
		else
		time=time-X*((L[n1]-R[n1-1]-1)/X);
		
	}
	
	cout<<time;
}

遇到的问题

本来的想法是，一次次的累加，精彩的时刻，和没法跳转的时刻一起加起来
但是不知道为啥出现了毛病，就改变了自己的思路，改成总的减去可跳过的。

问题C - TT 的神秘任务 - X

问题描述

TT 的神秘任务系列。

这一次，TT 得到了一个长度为 N 的字符串，任务要求在原字符串中至多删去一个字符，使得字符串的字典序尽可能小。

字符串字典序的比较优先级如下：

从左往右第一个不同字符的 ASCII 值的大小关系

字符串长度
第一行给出 N（2 ≤ N ≤ 2e5）。

第二行给出一个长度为 N，且仅包含小写字母的字符串。

题目分析

这个很简单，就是找到从右往左第一个左边ASCII 大于右边的，把那个删掉，这样右边那个小的就会顶替前面的位置，会变小，同时它改动的位置最为左边，会使得它的减小最大化。
如果遍历完都没有找到这么一个结果，就把最后一个字符删掉。

代码

#include<iostream>
using namespace std;
int N;
char zi[200002];
int main()
{
	scanf("%d",&N);
	int shu=-1;
	getchar();
	for(int i=0;i<N;i++)
	{
		scanf("%c",&zi[i]);
		if(zi[i]<zi[i-1]&&i!=0&&shu==-1)
		{
			shu=i-1;
		}
		
	}
	//cout<<zi<<endl;
	if(shu==-1)shu=N-1;
	//cout<<shu;
//	for(int i=0;i<N;i++)
	//{
//		 printf("%c",zi[i]);
	
//	}
//	printf("\n");
	for(int i=0;i<N;i++)
	{
		if(i==shu)continue;
		else printf("%c",zi[i]);
	
	}
	printf("\n");
}