前言
思维难度不大，$190/300$ 分，$Rank 2$ ，$Rating +96$ 。
题目
P1 – Container With Most Water
题面
给定数组 $h_n$ ，求 $\text{min}(h_i,h_j)\times |i-j|\ ,\ 1\le i,j\le n$ 的最大值。
保证 $n\le 10^7, 1 \leq a_i \leq 10^9$ 。
思路
首先暴力，枚举 $h_i$ 和 $h_j$ ，然后取最大值。
考虑倒着枚举 $h_j$ ，我们发现随着 $j-i$ 的不断减小，如果 $\text{min}(h_i,h_j)$ 大于之前的，结果才有可能比之前的大。
所以一开始令 $i=1 , j=n$ ，然后往高度低的那边缩进就好了。
代码
#include<bits/stdc++.h>
using namespace std;
inline long long read(){
long long ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
long long n,s[10000005],l,r;
long long ans=-2147483647;
int main(){
n=read();
l=1;
r=n;
for (register int i=1;i<=n;i++){
s[i]=read();
}
while (l<r){
long long now=1LL*min(s[l],s[r])*1LL*(r-l);
ans=max(ans,now);
if(s[l]<s[r]){
l++;
}else{
r--;
}
}
cout<<ans;
}
P2 – 迷失代码库
题面
Description
这是一道提交答案题。
现在你迷失在一个代码库里面。
这里面有 $100$ 份来自真实世界的代码，对于每份代码你需要判断哪些代码和它出自同一人之手。
Input Format
输入文件为
c1.in，因为一些奇妙的原因，它是一个空文件。$100$ 份代码
c*.cpp包含在下发文件中。Output Format
输出文件为
c1.out，你需要提交它。共有任意行，其中每一行
- 第一个数 $idx \in [1,100]$ ，表示你将要开始描述第 $idx$ 份代码。
- 第二个数 $tot \in [1,100]$ ，表示你猜测共有 $tot$ 份代码与之是同一人写的。
- 接下来 $tot$ 个数 $lst_{1\cdots tot}$，表示第 $lst_i$ 份代码与之是同一个人写的，$lst$ 中包括 $idx$ 本身。
注意
- $idx$、$tot$ 必须符合范围
- 相同的 $idx$ 不能重复出现多次，但是顺序任意
- 同一个 $lst$ 中，不能出现重复数字，但是顺序任意
否则你将得 $0$ 分。
Sample
如果你认为
c1.cpp、c2.cpp、c4.cpp是同一个人写的，c3.cpp、c5.cpp、c6.cpp、c7.cpp是另一个人写的（当然你的猜测不一定是正确的），那么你可以如下输出。output
1 3 1 2 4 3 4 3 5 6 7 6 4 3 6 5 7 4 3 1 2 4 2 3 1 4 2 5 4 3 7 6 5 7 4 3 5 6 7Scoring
对于每一份代码，满分为 $1.0$，实际得分为
$${\ln|A\cap B|\over \ln| A\cup B|}\times 1.0$$
其中 $A$ 表示你给出的 $lst$ 代表的集合，$B$ 表示
std给出的集合。若 $A=\emptyset $，得 $0.0$ 分，保证 $B\neq \emptyset $。共 $100$ 份代码，满分 $100.0$
在下发文件中，我们给出了可执行文件
scoring，你可以在终端下运行scoring或./scoring，来判断你的输出是否合法，并得知你的得分。
思路
根据码风比较吧。
$scoring$ 在 $win$ 下跑不起来，好像可以写脚本通过这个套数据。
P3 – Letter Gaps
题面
记得做过这样一道题
Ponder This Challenge:
In the string CABACB, each letter appears exactly twice and the number of characters between the “A”s is one, between the “B”s is two, and between the “C”s is three.
The same problem with the letters A-E cannot be solved, but adding a space (in the form of a hyphen) allows it to be solved.
For example, in the string ADAEC-DBCEB, the number of characters between the “A”s is one, between the “B”s is two, between the “C”s is three (counting the space), between the “D”s is four, and between the “E”s is five.
Find a string of letters (A-Z) and “-” whose length is no more than 53 characters, where each of the 26 letters A-Z appears exactly twice, and there is one character between the “A”s, two between the “B”s … and 26 between the “Z”s.
现在输入 $n\le 26$，你需要输出一个对于前 $n$ 个大写字母的长度不超过 $2n+1$ 的解。
空格（space）用连字符（hyphen） – 表示。
输入格式
一行，一个整数，表示$n$。
输出格式
一行，长度不超过 $2n+1$ 的任意一个合法解。
思路
还是比较简单的，$dfs$ 搜每一个字母，每重 $dfs$ 中枚举字母存在的位置。
具体见代码。
代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
int n,t[70];
char s[300];
void dfs(char x){
if (x=='A'-1){
for (int i=1;i<=2*n+1;i++){
if (s[i]=='*'){
s[i]='-';
}
cout<<s[i];
}
exit(0);
}
for (int i=1;i<=2*n+1;i++){
if (s[i]!='*'){
continue;
}
s[i]=x;
if (i+x-'A'+2<=2*n+1){
if (s[i+x-'A'+2]=='*'){
s[i+x-'A'+2]=x;
dfs(x-1);
s[i+x-'A'+2]='*';
}
}
if (i-(x-'A'+2)>=1){
if (s[i-(x-'A'+2)]=='*'){
s[i-(x-'A'+2)]=x;
dfs(x-1);
s[i-(x-'A'+2)]='*';
}
}
s[i]='*';
}
}
int main(){
cin>>n;
for (int i=0;i<=70;i++){
s[i]='*';
}
dfs('A'+n-1);
}
