SCAU2021春季个人排位赛第一场 部分题解（OI）
A题
“我们在 小 Z 面前秀个恩爱吧。”
“好的。”
小 Z 发现他身边都是人赢，这使他非常自闭。
小 Z 又看着身边的潇，不禁陷入了沉思……
题目描述
潇有一个数组 kk，下标为 11 到 nn 。
潇定义 f(x,y)=\begin{cases} \min(k_x,k_y) \times (x + y) &x \ne y \\ k_x\times x&x=y \end{cases}f(x,y)={min(kx,ky)×(x+y)kx×xx=yx=y 。
潇想知道对于任意的 1 \le x,y \le n1≤x,y≤n，f(x,y)f(x,y) 的最大值是多少。但是她不会做，于是就问了善良的 小 Z，然而非常想在妹子面前表现的 小 Z 发现他也不会做，就只能够求助善良的你了。
输入格式
第一行一个整数 nn。
第二行 nn 个整数 kk，第 ii 个整数为 k_iki。含义如上文。
输出格式
一行一个整数，表示对于任意的 1 \le x,y \le n1≤x,y≤n，f(x,y)f(x,y) 的最大值。
输入输出样例
输入 #1复制
3 3 2 1
输出 #1复制
6
输入 #2复制
5 3 4 5 4 3
输出 #2复制
28
说明/提示
数据范围
本题采用捆绑测试。
-
Subtask 1（20 points）：
-
Subtask 2（10 points）： 保证所有
都相等。
-
Subtask 3（20 points）：
-
Subtask 4（50 points）： 无特殊性质。
对于 100% 的数据，
题解：首先想到的是O(
当时我就在想，一般O(
写单调栈的时候一定要注意，当有旧的元素弹出栈之后，要记得让准备入栈的元素与目前栈顶元素算一次f（x，y），一定要记住！！
#include <iostream>
#include<stdio.h>
using namespace std;
int n;
long long a[1000006],ans,q[1000006],qi=1,qid[1000006];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
long long ai=a[i]*i;
ans=max(ans,ai);
}
q[qi]=a[qi];
qid[qi]=1;
for(int i=2;i<=n;i++)
{
if(a[i]<q[qi])
{
long long ai=a[i]*(i+qid[qi]);
ans=max(ans,ai);
}
else
{
while(a[i]>=q[qi] && qi>0)
{
long long ai=q[qi]*(i+qid[qi]);
ans=max(ans,ai);
qi--;
}
if(qi)
{
long long ai=a[i]*(i+qid[qi]);
ans=max(ans,ai);
}
}
qi++;
q[qi]=a[i];
qid[qi]=i;
}
cout<<ans;
return 0;
}
D题
题目描述
给定一个长度为 nn、元素由 00 或 11 组成的数组。
现在可以选择若干（可以为 0）个值为 00 的元素，将其修改为 11。
记：
- xx 为数组中最长连续 11 子段的长度（规定，若所有数均为 00，则 xx 为 00）；
- yy 为修改的元素的个数。
求要怎么修改才能使 x-yx−y 最大，并构造一个方案（输出修改后的数组）。
输入格式
本题含有多组数据。
第一行一个整数 TT 表示数据组数。
接下来 2\times T2×T 行，每 22 行表示一组数据。
在一组数据中，第一行一个整数 nn，表示数组的长度；
第二行 nn 个整数（0 或 1），表示给定的数组。
输出格式
共 2\times T2×T 行，每 22 行表示一组数据。
在一组数据中，第一行输出一个整数表示 x-yx−y 的最大值；
第二行 nn 个整数（0 或 1）表示修改以后的数组。如有多个方案，任意输出一种即可。
输入输出样例
输入 #1
1 1 1
输出 #1
1 1
输入 #2
2 3 1 0 1 5 0 1 0 1 0
输出 #2
2 1 1 1 2 0 1 1 1 1
说明/提示
本题采用捆绑测试。
对于所有数据，保证 T≤10,1≤n≤105，数组元素 ∈{0,1}。
- Subtask 1(70 points)：保证 1≤n≤10；
- Subtask 2(30 points)：无特殊限制。
题解：
70%数据做法
这道题我一开始没什么想法，看着70%的数据就想着，
毕竟要从0变成1，所以变成1之后的数肯定比它大，所以直接从本身开始枚举，枚举到
100%数据做法
当你看到这道题目的标签是入门，你有没有同样的小疑惑呢？
反正当时我是在发呆了，我想着入门题目需要我这么做？？然后到最后都没有想到正解。
比赛结束后才知道，正解其实贼简单。全部化成1即可。
单一串0在一起，把其中一个0变成1，那么操作数+1，连续的1也+1，所以x-y就抵消了，所以直接把全部变成1就可以了，就是正解。这才像入门题的样子嘛。
//70% 做法程序
#include <iostream>
using namespace std;
int T;
int n;
bool ki[100005];
long long mi=1,k,ans,ansi;
void read_in()
{
mi=1;k=0;ans=0;ansi=0;
cin>>n;
for(int i=1;i<=n;i++)
cin>>ki[i];
for(int i=1;i<=n;i++)
{
if(ki[i])
k+=mi;
mi=mi*2;
}
}
void work_for(int a,int b)
{
int ka=a,kb=b;
long long xi=0,y=0,x=0;
while(ka || kb)
{
if(ka%2==1 && kb%2==0)
return ;
if(ka%2==0 && kb%2==1)
y++;
ka>>=1;kb>>=1;
}
kb=b;
while( kb )
{
if(kb%2==0)
{
x=max(x,xi);
xi=0;
}
else
xi++;
kb>>=1;
}
x=max(x,xi);
if(x-y>ans)
{
ans=x-y;
ansi=b;
}
}
int main()
{
cin>>T;
while(T--)
{
int ti=0;
read_in();
for(int i=k;i<(1<<n);i++)
work_for(k,i);
cout<<ans<<endl;
while(ansi)
{
cout<<(ansi&1)<<' ';
ansi>>=1;
ti++;
}
for(ti=ti+1;ti<=n;ti++)
cout<<"0 ";
cout<<endl;
}
return 0;
}
//100% 数据做法
#include <iostream>
using namespace std;
int T;
int n;
bool ki[100005];
long long mi=1,k,ans;
void read_in()
{
cin>>n;ans=0;
for(int i=1;i<=n;i++)
{
cin>>ki[i];
if(!ki[i])
ans++;
}
}
int main()
{
cin>>T;
while(T--)
{
int ti=0;
read_in();
cout<<n-ans<<endl;
for(int i=1;i<=n;i++)
cout<<1<<' ';
cout<<endl;
}
return 0;
}
投递牛客等公司10个岗位 >
华为成长空间 551人发布