2022年寒假ACM练习1

题目

A——互异字符串

题目描述
请实现一个算法，确定一个字符串的所有字符是否全都不同。
给定一个字符串，请返回一个True代表所有字符全都不同，False代表存在相同的字符。

输入
输入一个字符串。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。
输出
如果所有字符全都不同输出“True”，如果存在相同的字符则输出“False”。
样例输入
aeiou
BarackObama
样例输出
True
False

分析：模拟题，直接用map容器装入元素再遍历，判断是否每个元素数量都满足不大于1即可
代码如下：

#include<bits/stdc++.h>usingnamespace std;#definelllonglong
map<char,int>m;intmain(){
    string s;int flag;while(cin>>s){
        m.clear();
        flag=0;for(int i=0;i<s.size();i++)
            m[s[i]]++;for(map<char,int>::iterator it=m.begin();it!=m.end();it++)if(it->second>1)flag=1;if(flag)printf("False\n");elseprintf("True\n");}}

B——第K个数

题目描述
有一些数的素因子只有3、5、7，请设计一个算法，找出其中的第k个数。
输入
给定一个正整数k，保证k小于等于100。
输出
输出第k个数。
样例输入
1
3
4
5
样例输出
3
7
9
15

分析：按题目意思模拟即可，需要注意以下几点：
①素因子满足只有3 5 7，不能没有素因子或者存在素因子不为这三个。
②注意，是素因子，如果一个数字有一个因子为9，这一点并不影响判断，因为9不是素数，因此还需要注意判断素数。
③注意先打表到数组中，然后再根据用户输入直接得出答案。
④想直接暴力模拟这几个过程：找到因子以及确认该因子为素数，还得确定素数因子只可能是3 5 7而没有其它情况。用六素数法判断素数能极大地简化效率。实际上，在找因子之前可以“把把关”，比如一个数就是偶数即n&1等于0，那么肯定不满足题目要求，就没有必要找因子了。

代码如下：

#include<bits/stdc++.h>usingnamespace std;int num[105];booljudge1(int n){//六素数法if(n==2||n==3||n==5)returntrue;if(n%2==0||n%3==0)returnfalse;for(int i=5;i<=sqrt(n);i+=6)if(n%i==0||n%(i+2)==0)returnfalse;returntrue;}booljudge(int n){if(n==3||n==5||n==7)returntrue;if((n&1)==0)returnfalse;//把把关for(int i=11;i<n;i++)if(n%i==0&&judge1(i))//找到除了3 5 7之外的素因子，不满足题意returnfalse;returntrue;}voidsolve(){//打表int i=1,x=3;while(i<=100){if((x%3==0||x%5==0||x%7==0)&&judge(x))
            num[i++]=x;
        x++;}}intmain(){int k;solve();while(~scanf("%d",&k))printf("%d\n",num[k]);}

C——2的个数

题目描述
请编写一个程序，输出0到n(包括n)中数字2出现了几次。
输入
输入一个正整数n。
输出
输出0到n的数字中2出现了几次。
样例输入
2
10
20
样例输出
1
1
3

分析：直接暴力模拟就好了
代码如下：

#include<bits/stdc++.h>usingnamespace std;intmain(){int n;while(~scanf("%d",&n)){int num=0;for(int i=2;i<=n;i++){int k=i;while(k){if(k%10==2)num++;
                k/=10;}}printf("%d\n",num);}}

D——外星人的语言

题目描述
Kimi费了很大劲，终于和地外文明联系上。
我们地球人通常有10根手指，因此我们习惯用10进制的数，而外星人的手指有16跟、8根等不等的数目，因此他们使用与我们不同的进制。
为了方便沟通，需要你开发一款工具，把地球人的10进制转换成外星人的R进制形式。

输入
输入有多行。
每行包括两个正整数n和R，其中2≤R≤16。
输入直到文件结束为止。
输出
对于每个用例，输出n对应的R进制形式。
超过10进制的数，10用A表示、11用B表示，依次类推。
样例输入
1989 2
1119 16
样例输出
11111000101
45F

分析：转换进制一个循环处理就可以实现，但是输出的时候是逆序的，所以这里我用了个vector数组，逆序一下就行了。
代码如下：

#include<bits/stdc++.h>usingnamespace std;
vector<char>v;intmain(){int n,r;while(~scanf("%d%d",&n,&r)){int i=0;
        v.clear();while(n){if(n%r>=10)v.push_back(n%r-10+'A');else v.push_back(n%r+'0');
            n/=r;}reverse(v.begin(),v.end());for(vector<char>::iterator it=v.begin();it!=v.end();it++)printf("%c",*it);printf("\n");}}

E——3n+1猜想

题目描述
卡拉兹(Callatz)猜想：

对任何一个自然数n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把(3n+1)砍掉一半。这样一直反复砍下去，最后一定在某一步
得到n=1。卡拉兹在1950年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，
结果闹得学生们无心学业，一心只证(3n+1)，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……

我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过1000的正整数n，简单地数一下，需要多少步（砍几下）才能得到n=1？
输入
每个测试输入包含1个测试用例，即给出自然数n的值。
输出
输出从n计算到1需要的步数。
样例输入
3
样例输出
5

分析：一道水题，按题目意思简单模拟一下即可
代码如下：

#include<bits/stdc++.h>usingnamespace std;
vector<char>v;intmain(){int n;while(~scanf("%d",&n)){int num=0;while(n){if(n==1)break;if((n&1)==1)n=3*n+1,n/=2;else n/=2;
            num++;}printf("%d\n",num);}}

F——狗狗大绝杀

题目描述

这是 10 月 32 日发生的事情。抽筋流高手布置了一个非常 BT 的作业。他说要在一定时间内把屏幕上的所有小狗布成一条直线。而这个时间非常之短！！！众人大呼 BT，但是抽筋流高手是非常严格的，所以大家只好遵从他的命令。

众所周知，只有达达的 APM 在 190 以上，所以最后完成作业的只有他一个。他受到了 抽筋流高手的表扬。

然而罗小松觉得不爽，于是他趁达达去 WC 的时候在那一条直线上放了一系列机枪兵， 对可爱的狗狗们进行了残忍的屠杀。

已知个机枪兵有一定的射程。然而这是一种特殊的星际版本，机枪升攻击的时候也 可以升射程！所以每个机枪的射程不一定相同。现在一列狗兵排成直线，一次一个机枪兵打掉一定范围内的所有狗狗，每个狗狗有一个编号，每次给出一个杀伤区间， 其中的小狗将会被全部杀掉。最后，让你统计一共杀了多少个。

简而言之，给出数轴上 N 条线段，条线段用两个数表示 A , B（-109<=A<B<=109）， 表示从 a 到 b 的一条线段。现在请求出它们覆盖数轴上的多长距离。

输入
第一行：N （N ≤ 20000）。

以后 N 行，行两个数：Ai Bi 。
输出
一个数，表示覆盖长度 。
样例输入
3
2 8
-1 1
5 10
样例输出
10

分析：这是一道区间覆盖问题，需要理解如何覆盖，既然有两个要素，我们就用结构体变量。接下来从正向和逆向思维一起阐述，有助于更深刻的理解这道题：

①如果从正向思维来理解，先把区间的左端即A按从小到大排列，那么上面样例就会被排序为(-1,1)，(2,8)，(5,10)，第一个直接覆盖，覆盖长度加2，然后判断第一个区间的右端点和第二个区间的左端点的位置关系，可以发现1<2，因此直接对第二个区间覆盖，覆盖长度加6，再看第二个区间的右端点和第三个区间的左端点的关系，明显8>5，那么也就是说5 6 7这一部分实际上已经被覆盖过了，无须再覆盖，直接把第三个区间近似看为(8,10)，那么覆盖长度再加2，因此覆盖总长度为2+6+2=10。

②接着从逆向思维理解，先把区间的右端按从大到小排序，那么样例就会被排序为(5,10)，(2,8)，(-1,1)，第一个区间直接覆盖就好，覆盖长度加5，然后判断第一个区间的左端点和第二个区间的右端点的位置关系，可以发现5<8，那么实际上6 7 8已经被前面的区间覆盖过了，无须再覆盖，可以抽象第二个区间为(2,5)，那么覆盖长度加3，然后再按如上判断方法继续判断，易得对(-1,1)这个区间直接覆盖即可，答案和正向思维是一样的。

下面的代码用的是逆序，为了更好的抽象这些区间，我把区间的右端点从小到大排序，然后再逆序遍历。

代码如下：

#include<bits/stdc++.h>usingnamespace std;#defineINF0x3f3f3f3ftypedefstruct{int a,b;}Node;boolcmp(Node m,Node n){return m.b<n.b;}intmain(){int n,m,len;
    cin>>n;
    Node *node=new Node[n+1];for(int i=1;i<=n;i++)scanf("%d%d",&node[i].a,&node[i].b);sort(node+1,node+n+1,cmp);
    len=node[n].b-node[n].a;
    m=node[n].a;
    n--;while(n>=1){
        m=min(node[n].b,m);if(m>node[n].a)len+=m-node[n].a,m=node[n].a;
        n--;}printf("%d\n",len);}

G——折纸

题目描述
小s很喜欢折纸。

有一天，他得到了一条很长的纸带，他把它从左向右均匀划分为N个单位长度，并且在每份的边界处分别标上数字0~N。

然后小s开始无聊的折纸，每次他都会选择一个数字，把纸带沿这个数字当前所在的位置翻折（假如已经在边界上了那就相当于什么都不做）。

小s想知道M次翻折之后纸带还有多长。
输入
第一行包含两个正整数 N 和 M ，表示纸带的长度和操作的次数。(N ≤ 10^18，M ≤ 3000)。

接下来的一行包含 M 个整数 Di ，其中 Di 表示第 i 次选择的数字。
输出
输出文件只有一个数字，即纸带最后的长度。
样例输入
5 2
3 5
样例输出
2

分析：这道题比较难模拟，借鉴了别人的思路好好捉摸了一下。一开始的长度为5，长度怎么算的呢？直接右端点减去左端点即可。实际上，这个右端点可以看成标号，但是更应该被视为是位置信息。为什么呢？比如样例中先按3位置折叠过去（从左往右折叠），那么2和4重合，1和5重合，0跑到6那个位置去了（6是位置，并没有标号6），这时候纸张的左端位置就是2的位置，右端位置为6的位置，那么这时候的长度就是6-2=4了。接下来再折5，那么4于6重合，3跑到7那个位置去了，那么此时左端位置为5右端位置为7，长度就变味2了。
但是有这么一个特殊情况需要注意，假如折的两次操作中，某一次折的编号比之前的某次折的编号小，那么实际上以编号来理解是不能模拟出对折的，比如两次对折顺序为3 2，折完3后，要折2，实际上也就是折4那个位置，那么以3为对称轴，很明显3-2=4-3，放到一般情况就为x-a=b-x，因此b=2*x-a，这样下次对折才能找到位置信息。

代码如下：

#include<bits/stdc++.h>#definelllonglongusingnamespace std;
ll a[3005];intmain(){
    ll n,l,r;int m;while(~scanf("%lld%d",&n,&m)){
        l=0,r=n;for(int i=1;i<=m;i++)scanf("%lld",&a[i]);for(int i=1;i<=m;i++){for(int j=i+1;j<=m;j++)if(a[j]<a[i])
                    a[j]=2*a[i]-a[j];
            r=max(r,2*a[i]-l);
            l=a[i];}printf("%lld\n",r-l);}}

H——加一

题目描述
你的任务是很简单，给你一个非负整数 N，输出 N+1。

唯一的复杂之处在于给出的整数是一个 2~36 进制（包括边界）中一个未知进制的整数。（大家知道的，从 10 开始的数字分别用 A,B,C,……来表示）

因此，你的程序必须按字典序递增输出所有可能的结果。
输入
一行，包含一个由数字 0 至 9 与大写字母 A 至 Z 组成的整数 N，数据保证没有前导零。 （N包含1~200位数字）
输出
输出所有的可能结果，每个结果占一行。
样例输入
9
样例输出
10
A

分析：这里要注意分析，首先，当最低位不是最大值的时候，比如71，要求它的加1值，直接就为92，不存在进位，只需输出一个答案即可。当最低位就是最大值的时候，那就有两种情况了，就比如样例所示，如果是10进制，很明显这时候需要进位了！因此最低位置0，向前进位并循环实现+1运算，如果是11进制、12进制等等情况，那么9不是最高位，可以直接+1，那么就是A。还要注意遇到Z的+1情况时肯定是要进位的。比如Z的加1只可能有一种情况就是10。

代码如下：

#include<bits/stdc++.h>usingnamespace std;#defineINF0x3f3f3f3fint a[1005],b[1005],maxn=0;char s1[1005],s2[1005];intmain(){
    string s;
    cin>>s;reverse(s.begin(),s.end());int len=s.size();for(int i=0;i<len;i++){if(s[i]>='A'&&s[i]<='Z')a[i]=s[i]-'A'+10;else a[i]=s[i]-'0';
        b[i]=a[i];if(a[i]>maxn)maxn=a[i];}if(s.size()==1){if(s[0]=='0')printf("1\n");elseif(s[0]>'0'&&s[0]<'9')printf("10\n%c\n",s[0]+1);elseif(s[0]=='9')printf("10\nA\n");elseif(s[0]>='A'&&s[0]<'Z')printf("10\n%c\n",s[0]+1);elseif(s[0]=='Z')printf("10\n");}else{if(a[0]==maxn){
            a[0]=0,a[1]++;for(int i=1;i<len-1;i++)if(a[i]<=maxn)break;else a[i]=0,a[i+1]++;if(a[len-1]>maxn)a[len-1]=0,a[len]=1,len++;for(int i=len-1;i>=0;i--)if(a[i]>=0&&a[i]<=9)s1[len-i-1]=a[i]+'0';elseif(a[i]>=10)s1[len-i-1]=a[i]+'A'-10;
            s1[len]='\0';}
        b[0]++,len=s.size();if(b[0]!=36){for(int i=len-1;i>=0;i--)if(b[i]>=0&&b[i]<=9)s2[len-i-1]=b[i]+'0';elseif(b[i]>=10)s2[len-i-1]=b[i]+'A'-10;
            s2[len]='\0';if(strlen(s1)==0)printf("%s\n",s2);elseif(strcmp(s1,s2)<0)printf("%s\n%s\n",s1,s2);elseif(strcmp(s1,s2)>0)printf("%s\n%s\n",s2,s1);}elseif(b[0]==36)printf("%s\n",s1);}}

I——爱的日期

题目描述
Inter和AMD刚刚在上个学期确定了恋爱关系，但是由于要期末考试，他们没法have a appointment。
所以他们打算在2月14日情人节那天一起出去。恰恰最近疫情爆发，Inter和AMD都被关在机箱里面不准出来。
于是Inter就想找一个普通而又特殊的日子再次和AMD约会。 要是个周五，然后这个周五是当月的20号岂不美哉？
你能帮帮Inter找出当年中既是周5，又是20号的月份吗。（找不到Inter就只能伤心的回去挤牙膏了）

输入
输入包含多组数据，每组数据包含一个正整数year（2000≤year≤9999）。
输出
对应每一组数据，输出所有符合条件的月份，月份之间用空格隔开。
如果当年不存在20号是星期五的月份，就输出一行jiyagao。
样例输入
2000
2001
2002
样例输出
10
4 7
9 12

分析：2000年1月1号是星期6，直接暴力模拟，能够ac

代码如下：

#include<bits/stdc++.h>usingnamespace std;int num;voidfun(int year){int yeap,i,j,k;int m=6;for(i=2000;i<=year;i++){if(i%4==0&&i%100!=0||i%400==0)yeap=29;else yeap=28;for(j=1;j<=12;j++){if(j==1||j==3||j==5||j==7||j==8||j==10||j==12)k=31;elseif(j==2)k=yeap;else k=30;
            m=(m+19)%7;if(i==year&&m==5)printf("%d ",j),num++;
            m=(m+k-19)%7;}}printf("\n");}intmain(){int year;while(~scanf("%d",&year)){
        num=0;fun(year);if(num==0)printf("jiyagao\n");}}

J——乒乓球筐

题目描述
Kimi有两盒（A、B）乒乓球，有红双喜的、有亚力亚的……现在他需要判别A盒是否包含了B盒中所有的种类，并且每种球的数量不少于B盒中的数量，该怎么办呢？
输入
输入有多组数据。
每组数据包含两个字符串A、B，代表A盒与B盒中的乒乓球，每个乒乓球用一个大写字母表示，即相同类型的乒乓球为相同的大写字母。
字符串长度不大于1000。
输出
每一组输入对应一行输出：如果B盒中所有球的类型在A中都有，并且每种球的数量都不大于A，则输出“Yes”；否则输出“No”。
样例输入
ABCDFYE CDE
ABCDGEAS CDECDE
样例输出
Yes
No

很简单，直接上代码
代码如下：

#include<bits/stdc++.h>usingnamespace std;
map<char,int>m1,m2;intmain(){
    string s1,s2;while(cin>>s1>>s2){
        m1.clear(),m2.clear();for(int i=0;i<s1.size();i++)m1[s1[i]]++;for(int i=0;i<s2.size();i++)m2[s2[i]]++;
        map<char,int>::iterator it;for(it=m2.begin();it!=m2.end();it++)if(!(m1.find(it->first)!=m1.end()&&m1[it->first]>=it->second))break;if(it==m2.end())printf("Yes\n");elseprintf("No\n");}}

K——最难的问题

题目描述
Kimi生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是军团中的一名军官，需要把发送来的消息破译出来、并提供给你的将军。
消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A 都分别替换成字母F），其他字符不变，并且消息原文的所有字母都是大写的。密码中的字母与原文中的字母对应关系如下。
密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
输入
输入包括多组数据，每组数据一行，为收到的密文。
密文仅有空格和大写字母组成。（长度<=1000）
输出
对应每一组数据，输出解密后的明文。
样例输入
HELLO WORLD
SNHJ
样例输出
CZGGJ RJMGY
NICE

模拟题，直接上代码
代码如下：

#include<bits/stdc++.h>usingnamespace std;intmain(){
    string s;while(getline(cin,s)){for(int i=0;i<s.size();i++){if(s[i]==' ')continue;else{if(s[i]-5<'A')s[i]='Z'-(5-s[i]+'A')+1;else s[i]-=5;}}
        cout<<s<<endl;}}

L——快乐的木头

题目描述
现有一堆快乐的木头，它们排成一行，对于它们而言，快乐是无价的，因此它们各自都有一个快乐值a，而快乐值低的木头总想与比它更快乐的木头玩成一团，
而对于快乐值高的木头也总是乐意与在它邻近的快乐值比它低的左边的木头玩成一团。
这也就是说，对于某个区间[l,r]内的木头，它们的快乐值如果是单调递增的，那么它们就会作为一个小团体，一起快乐的玩耍，注意这个小团体一定是不能再
继续左右扩大的，也就是说，对于l和r满足a(l+1) >= a(l) && a® >= a(r+1)。现在河神想问你，这些木头将会分成多少个团体。
(至于你问为啥一块木头不会和左边比它一样或者更快乐的木头玩成一团emmm，这是个值得深思的问题。)
输入
第一行输入一个T(T<=5)，表示测试数据总数。
每组测试数据仅一行，每行首先输入一个n(n <= 1000000)，接下来输入n个正整数ai。(ai <= 1000000)
输出
输出分成的快乐团体个数。
样例输入
1
5
2 7 2 3 3
样例输出
3
提示
样例中分为三个团体:(2,7)，(2,3)，(3)

代码如下：

#include<bits/stdc++.h>usingnamespace std;#defineINF0x3f3f3f3f#definelllonglongintmain(){int t,n,newn,dn;scanf("%d",&t);while(t--){int num=0;dn=0;scanf("%d",&n);while(n--){scanf("%d",&newn);if(newn>dn)dn=newn;else num++,dn=newn;}printf("%d\n",num+1);}}

M——努力的木头

题目描述
现有一堆努力的木头，它们非常的努力学习，于是问题来了，它们中有的擅长空间几何(有a块木头)，有的擅长高等代数(有b块木头)，
有的擅长数学分析(有c块木头)，现在你有d道空间几何题，e道高等代数题，f道数学分析题，现在你想让这些木头帮助你做这些题目，
但是它们做空间几何需要g分钟，做高等代数需要h分钟，做数学分析需要i分钟，你当然想直接把题目交给他们，然后开始玩游戏，
但是在它们完成之前，你都必须监督它们，否则它们将消极怠工，请问你需要监督它们做多久。注意每块木头只能完成自己擅长的题目，
并且在做某一题的时间内不能停下来去做别的。
输入
第一行输入一个T(T<=10)，表示有测试数据的数目。
每组测试数据仅一行，一行包括9个正整数a，b，c，d，e，f，g，h，i(a,b,c,d,e,f,g,h,i<=100)
输出
输出你所需要监督它们的最少时间。
样例输入
1
2 3 4 5 6 7 8 9 10
样例输出
24

代码如下：

#include<bits/stdc++.h>usingnamespace std;#defineINF0x3f3f3f3f#definelllonglongintmain(){int t,a,b,c,d,e,f,g,h,i;scanf("%d",&t);while(t--){scanf("%d%d%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&g,&h,&i);int max=0;int time1=d/a,time2=e/b,time3=f/c;if(d%a!=0)time1++;
        time1*=g;max=time1;if(e%b!=0)time2++;
        time2*=h;if(max<time2)max=time2;if(f%c!=0)time3++;
        time3*=i;if(max<time3)max=time3;printf("%d\n",max);}}

N——神奇的木头

题目描述
现有一堆神奇的木头，他们之所以是神奇的，是因为他们有自己的智商值，而他们能够通过两种途径改变你的智商，第一种就是让你的智商值加上它的智商
值，第二种就是让你的智商值乘以它的智商值。但是河神告诉你，你必须从左往右使用这些木头，否则，它们不但不会改变你的智商，反而会让你成为传说
中智商为0的RZ，当然咯，那你的目的当然是让你自己的智商最高最好。
输入
第一行输入一个T(T<=5)，表示测试数据组数。
每组测试数据有2行，第一行首先输入一个正整数n，表示有n块神奇的木头，接下来从左往右输入木头的智商值，注意：0<=木头的智商值<=10，n<=10。
第二行输入你的初始智商值k：0<=k<=10。
输出
输出你经过改变后的智商最高值。(答案不会出现为0的情况哈)
样例输入
1
4 1 2 3 4
0
样例输出
36
提示
对于样例我们显然可以(0+1+2)34 = 36

分析：很明显这题不能直接从总体来分析，也不能随便想当然运算加法乘法，这属于一道比较简单的动态规划题。用数组f[]来表示所能得到的智商最大值，f[i]就代表前i个木头所能带给我们的智商的最大值，很明显f[0]就是我们的初始智商值，f[i]有两种可能，一种是f[i-1]加上第i块木头的价值，还有一种是f[i-1]乘以第i块木头的价值。

代码如下：

#include<bits/stdc++.h>usingnamespace std;#defineINF0x3f3f3f3fint f[15],num[15];intmain(){int t,n;
    cin>>t;while(t--){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&num[i]);scanf("%d",&f[0]);for(int i=1;i<=n;i++)
            f[i]=max(f[i-1]+num[i],f[i-1]*num[i]);printf("%d\n",f[n]);}}

O——无聊的木头

题目描述
现有一堆无聊的木头，它们的长度已知且排成一行，突然有一天，第一块木头突发奇想，它想要知道在它的右边比它长度次小的木头是哪一块，于是
它把这个想法告诉了其他木头，而其他木头对于它这个想法也十分好奇,但是木头实在太多了，因此你需要告诉它们在它们右边的哪一块木头的长度比它次小，也就是找到
比它次小的那块木头的位置。
输入
第一行输入一个T(T <= 20)，表示测试数据组数。
接下来T行，每行首先输入一个n(n <= 100000)，表示木头的个数，之后输入n个正整数，分别表示木头的长度(木头长度<=1000000)
输出
输出n个满足条件的答案，注意如果没有满足条件的答案你只需要输出0就好了，如果对于某块木头有多个满足条件的答案，你需要输出答案尽量小的那一个。
样例输入
1
6 10 9 26 10 10 18
样例输出
2 0 6 0 0 0

分析：一种最暴力的模拟，直接先找每个木头的右端的次小值，但是我这么做是超时了，而后也没有想着优化，而是更想用set容器。先从后往前加入set容器，边加入边找，这样就可以直接模拟题目所谓的从其右边找的特点。再加上lower_bound函数，可以直接找到这个迭代器的位置，它的前一个就是了。除此之外，用id数组来记录元素的位置。如果返回的迭代器就是s.begin()，明显就是不存在这样的木头了，比如倒序插入的18 10 10，都无法找到，插入26以后set自动排序，就可以找到18了，通过id数组找到位置。
实际上在这里set容器更体现妙用了，比如两次插入10，我们当然是更想知道它的更前面的位置了，set又不能重复，非常方便id数组的更新。

代码如下：

#include<bits/stdc++.h>usingnamespace std;constint maxn=1e6+10;int a[maxn],b[maxn],id[maxn];
set<int>s;
set<int>::iterator it;intmain(){int n,t;scanf("%d",&t);while(t--){
        s.clear();scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=n;i>=1;i--){
            s.insert(a[i]);
            it=s.lower_bound(a[i]);if(it==s.begin())b[i]=0;else b[i]=id[*(--it)];
            id[a[i]]=i;}for(int i=1;i<=n;i++)printf("%d%c",b[i],i==n?'\n':' ');}}

P——值钱的木头

题目描述
现有一堆值钱的木头，它们排成一行，河神给了你一个可以改变一个区间内的木头的价值的机会(注意这个区间不能越过边界)，因为这是河神给你的选择，因此你必须要把握这次机会，也就是说你必须改变一个区间内木头的价值。
当然你的目的是让这堆木头的总价值最高。
输入
第一行输入一个T(T <= 5)，表示测试数据总数。
接下来2*T行，每组数据有2行。
每组数据第一行首先输入一个n(n <= 100000)，接下来输入n个整数，分别表示这些木头的价值(-1000<=木头价值<=1000)
每组数据第二行输入两个整数x，y，其中x表示可以改变的区间的大小，y表示你可以把这个区间内的木头价值变为y(1<= x <= n,-1000<=y<=1000)
输出
你需要输出你所能获得的最大价值(这个价值可能为负数，表明你可能被河神给坑了)
样例输入
1
5
2 -5 -5 23 -11
1 3
样例输出
18
提示
显然你只需要把-11改为3就可以得到最大价值18。

分析：这道题无论如何都是最想先找到和最小的区间，把这个区间的数替换了就好，看完题目可以在这里直接简化，找到区间以后，该区间的数之和本为a，换成了b，b=x*y，因此直接替换和就好了，不需要做不必要的遍历数组改元素。有一大问题就是，如何找到这个和最小的区间？一开始我直接遍历下去，每x个来一次accumulate函数求和，然后找到最小区间。emmmm可惜超时了。这种题可以多留意一下，就是用前缀和，我的代码和前缀和的处理有相似之处，利用的是滚动区间，同样可以ac，题目说了一定会有替换，我们用sum表示替换后的和，s表示替换前的和，显然sum=s-a+b，接下来就是a的计算处理了。第一个区间也就是[1,x]，这里直接for循环就好，也可以用accumulate函数，然后就往下，第二个区间是[2,x+1]，那么a就直接变为a+num[x+1]-num[1]，在求解完第一个区间的a值后遍历右端点知道最右端，放到一般情况就是a+num[i]-num[i-x]。如果利用前缀和思想，除了num数组来存储每个木头的价值，还可以开辟一个数组pre来实现前缀和，初始pre[i]都表示前i个木头相加的和，那么pre[i]=pre[i-1]+num[i]，处理完后，要想知道i到j区间的和，直接就等于pre[j]-pre[i-1]。那么替换某个区间长度为x的区间后的总和就为sum-(pre[i]-pre[i-x])+b，找最大值就好了。

滚动区间代码如下：

#include<bits/stdc++.h>usingnamespace std;#defineINF0x3f3f3f3fint num[100005];intmain(){int t,n,x,y;
    cin>>t;while(t--){int sum,a=0,b,s=0;scanf("%d",&n);memset(num,0,sizeof(num));for(int i=1;i<=n;i++)scanf("%d",&num[i]),s+=num[i];scanf("%d%d",&x,&y);
        b=x*y;for(int i=1;i<=x;i++)a+=num[i];
        sum=s-a+b;for(int i=x+1;i<=n;i++){
            a+=num[i]-num[i-x];
            sum=max(sum,s-a+b);}printf("%d\n",sum);}}

前缀和代码如下：

#include<bits/stdc++.h>usingnamespace std;constint maxn=1e5+10;int num[maxn],pre[maxn];intmain(){int n,b,sum,s,t,x,y;scanf("%d",&t);while(t--){
        s=0;scanf("%d",&n);memset(pre,0,sizeof(pre));for(int i=1;i<=n;i++)scanf("%d",&num[i]),s+=num[i];scanf("%d%d",&x,&y);for(int i=1;i<=n;i++)pre[i]=pre[i-1]+num[i];
        b=x*y;
        sum=s-pre[x]+b;for(int i=x+1;i<=n;i++)
            sum=max(sum,s-pre[i]+pre[i-x]+b);printf("%d\n",sum);}}