第 157 场周赛（8月3日）
5838. 四舍五入
给定一个两位正整数 n，请你输出其四舍五入到十位后的结果。
输入格式
一个正整数 n。
输出格式
一个整数，表示 n
四舍五入到十位后的结果。
数据范围
所有测试点满足 10≤n≤99
输入样例1：
13
输出样例1：
10
输入样例2：
98
输出样例2：
100
题解
额，送分
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
int x=n%10;
if(x>=5)cout<<(n/10+1)*10<<endl;
else cout<<n/10*10<<endl;
return 0;
}
5839. 四舍五入II
给定一个实数，保证该数为正数，其小数点后至少包含一位非零的数字，且小数点后不含多余末尾 0。
如果将该实数转化为字符串，则字符串的长度为 n。
现在，你可以对该实数进行不超过 t 次（也可以零次）四舍五入操作。
每次操作可以将当前数四舍五入到小数点后的任意位置（也可以四舍五入到最接近的整数）。
例如，1.645 四舍五入到小数点后两位可以得到 1.65，1.141 四舍五入到小数点后一位可以得到 1.1，3.762 四舍五入到最接近的整数可以得到 4。
我们希望通过四舍五入操作，将给定实数变得尽可能大。
请你输出通过上述操作可以得到的最大可能值。
输入格式
第一行包含两个整数 n,t。
第二行包含给定正实数，保证其既包含整数部分也包含小数部分，且小数点后至少包含一位非零的数字，且小数点后不含多余末尾 0。如果将该实数转化为字符串，则字符串的长度为 n。
输出格式
输出一个实数，表示可以得到的最大可能值。
输出答案不应包含小数点后多余末尾 0。
如果答案是整数，则直接输出整数。
数据范围
前 4 个测试点满足 1≤n≤12，1≤t≤100。
所有测试点满足 1≤n≤2×105，1≤t≤109。
输入样例1：
6 1
10.245
输出样例1：
10.25
输入样例2：
6 2
10.245
输出样例2：
10.3
输入样例3：
3 100
9.2
输出样例3：
9.2
题解
这道题真的超级超级麻烦，思路简单，小数点后面找5然后进行调整，额细节太多写俩小时没写对。。。。。参考下别人代码吧，改对了来填坑
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int s[N];
int main()
{
int tmp,n,t,i,num,m,flag=1;
char ch;
cin>>n>>t;
for(i=0;i<n;i++)
{
cin>>ch;
num=int(ch)-48;
if(num>=0)s[i]=num; //'.'的ASCII码是46 如果ch不是'.',将num存入数组
else tmp=i; //否则记录'.'的位置
}
m=tmp+1;//m记录小数点后一位的位置，即将开始对小数部分四舍五入
while(t--)
{
//从第一位小数从前往后找第一个大于5的数，且要保证m所指位置不超过小数部分
while(s[m]<5&&flag&&m<n-1) m++;
//while后找到了第一个≥5的数，此时进行四舍五入后的数是最大的，后面就不需要再往后找≥5的数了，所以令flag=0
flag=0;
//如果小数部分没有数≥5，退出循环
if(!flag&&s[m]<5)break;
//如果是第一位小数≥于5，m指向个位数
if(m-1==tmp)m-=2;
//否则指向前一位小数
else m--;
//这条语句针对的是个位数，如果个位数原来是9，++后就是10，所以令其为0，十位数要+1，这个后面再处理
if(s[m]+1==10)s[m]=0;
//否则当前位置的数字+1
else s[m]++;
}
//处理整数部分的进位问题，如果当前位数字为0，且不是最高位，继续循环
while(s[m]==0&&m-1>=0)
{
//当前位的高位+1
s[--m]++;
//这里也是在判断是不是要进位
if(s[m]==10)s[m]=0;
}
//如果第一位是0，说明是从9进位到了10，则整数最高位是1，输出1
if(s[0]==0) cout<<"1";
//输出所有数字，注意输出小数点
for(int j=0;j<=m;j++)
{
if(j!=tmp)cout<<s[j];
else cout<<".";
}
//整数部分缺0补0
if(m>=0)
{
for(int j=m+1;j<tmp;j++)cout<<"0";
}
return 0;
}
作者：PPH
链接：https://www.acwing.com/solution/content/249970/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
5840. 封印序列
给定一个长度为 n 的非负整数序列 a1,a2,…,an。
其中的所有元素将被逐个封印。
具体封印顺序可以用一个 1∼n 的排列 b1,b2,…,bn 来描述，第 i 个被封印的元素即为 abi。
你需要完成 n 个任务（编号 1∼n），其中第 i 个任务是：对于完成前 i 次封印的序列，请你找到序列中的一个连续子序列（可以为空），使得该子序列不含任何被封印的元素，且子序列内各元素之和尽可能大，输出这个子序列元素和的最大可能值。
空序列的元素和视为 0。
输入格式
第一行包含整数 n。
第二行包含 a1,a2,…,an。
第三行包含 b1,b2,…,bn。
输出格式
共 n 行，第 i 行输出第 i 个任务的结果。
数据范围
前 4 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤105，0≤ai≤109，b1∼bn 是一个 1∼n 的排列。
输入样例1：
4
1 3 2 5
3 4 1 2
输出样例1：
5
4
3
0
输入样例2：
5
1 2 3 4 5
4 2 3 5 1
输出样例2：
6
5
5
1
0
输入样例3：
8
5 5 4 4 6 6 5 5
5 2 8 7 1 3 4 6
输出样例3：
18
16
11
8
8
6
6
0
题解
额，想不到
竟然需要并查集
然后我看有的人用线段树/线段数组也能写出来
不过对比了下好像老师给的方法还是最简单的。
https://www.acwing.com/video/5480/
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p[100005],st[100005],s[100005];
int find(int x)
{
if(x==p[x]) return p[x];
return p[x]=find(p[x]);
}
int a[100005],b[100005],ans[100005];
signed main()
{
int i,j,k;
cin>>n;
for(i=1;i<=n+1;i++) p[i]=i;
for(i=1;i<=n;i++) cin>>a[i];
for(i=1;i<=n;i++) cin>>b[i];
int res=0;
for(i=n;i>=1;i--)
{
ans[i]=res;
int pos=b[i];
st[pos]=1;
s[pos]=a[pos];
if(pos+1<=n&&st[pos+1]==1)
{
int x=find(pos),y=find(pos+1);
p[x]=y;
s[y]+=s[x];
}
if(pos-1>=1&&st[pos-1]==1)
{
int x=find(pos),y=find(pos-1);
p[y]=x;s[x]+=s[y];
}
res=max(res,s[find(pos)]);
}
for(i=1;i<=n;i++) cout<<ans[i]<<endl;
return 0;
}