最后更新时间
2023/12/22
温馨提示
右下角有展开目录索引的功能。
由于是做题记录，所以作为题解的话可能有些地方的表达不是特别好，请见谅。
[ARC104C] Fair Elevator
\(2n\) 个位置，要不重复地填 \(2n\) 个数，所以可以发现题目中给的区间里面带 \(-1\) 的都是没有用的，因为反正最后肯定要填，所以它不能提供任何信息。也就是说只有完整的区间是有用的区间信息，但是给出的端点信息也是有用的，因为它确定了某个位置只能作为左端点或者右端点。
首先在输入的时候排除一些显然无解的情况，然后接下来有两种做法：
-
发现题目中的限制条件意味着如果一些区间它们有交，那么会形成形如 \([x,y],[x+1,y+1],[x+2,y+2]\dots\) 这样的形式，那么我们考虑假设我们现在要加一个区间 \([l,r]\)，怎样判断它加进去是否合法。我们枚举 \(i\in [l,r)\)，如果 \(i\) 已经被作为了题目中给出的完整区间的左端点，并且它的右端点不是 \([i+r-l]\)（即违反了我们上面提到的那种形式），就不合法，\(i\) 作为右端点的情况类似。还有就是如果不能存在 \([i,i+r-l]\) 这个区间也是不行的，即 \(i\) 和 \(i+r-l\) 都已经被定为端点了，但它们没有匹配。于是可以 \(O(n^3)\) 暴力处理出每个区间是否合法，然后再 \(O(n^3)\) 暴力做区间 \(dp\)，枚举断点看是否能分成左右两个合法区间，答案即是 \(f_{1,2n}\)。
代码参考这篇题解的实现，懒得写了。 -
考虑判断一段连续的位置能否被合法地填满，这里只考虑填上文提到的那种相交的形式，因为如果不相交的话显然可以拆开，互不影响。假设我们要填的连续段为 \([l,r]\)，记 \(len=r-l+1\)，显然此处 \(len\) 应为偶数（保证每个区间左右端点配对），并且里面填的每个区间的长度应为 \(\frac{len}{2}+1\)（想象一下或者动手画一下就明白了）。那么考虑双指针 \(i,j\) 扫，枚举往里面填的区间的左右端点，如果 \(i\) 被确定为了右端点或者 \(j\) 被确定为了左端点或者 \(i,j\) 都被确定了但它们没有配对，那么就是不合法的。扫完之后若仍然合法则合法。然后就可以 \(dp\) 了，记 \(f_i\) 表示是否能合法地填完前缀 \(i\)。转移就枚举前面的 \(j\)，如果存在 \(f_j\land Check(j+1,i)\)，那么 \(f_i=true\)。
$\texttt{Code}$
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
const int N=205;
int n,a[N],b[N],p[N];
bool f[N];
il int read(){
re int x=0;re char c=getchar(),f=0;
while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f?-x:x;
}
il bool Calc(int l,int r){
int len=(r-l+1)>>1;
for(re int i=l,j=l+len;j<=r;i++,j++){
if(p[i]&&p[j]&&p[i]^p[j])return 0;
if(p[i]&&b[p[i]]==i)return 0;
if(p[j]&&a[p[j]]==j)return 0;
}
return 1;
}
int main(){
n=read();
for(re int i=1;i<=n;i++){
a[i]=read(),b[i]=read();
if(a[i]!=-1){
if(p[a[i]])return puts("No"),0;
else p[a[i]]=i;
}
if(b[i]!=-1){
if(p[b[i]])return puts("No"),0;
else p[b[i]]=i;
}
}
f[0]=1;
for(re int i=2;i<=(n<<1);i++)
for(re int j=i-2;j>=0;j-=2)
if(f[j]&&Calc(j+1,i)){
f[i]=1;
break;
}
puts(f[n<<1]?"Yes":"No");
return 0;
}
[ARC105C] Camels and Bridge
数据范围提示我们枚举全排列，然后考虑计算一个排列的答案，可以对一段连续的骆驼去 \(check\) 它们在一起通过桥的话至少应该有多少长度，记这些骆驼的总重为 \(sum\)，那么显然只有限重 \(\lt sum\) 的桥会产生影响，影响的结果是每个这样的桥的长度都要对这一段骆驼的最短长度贡献一个 \(\max\)，然后发现这就是一个前缀 \(\max\) 的形式，那么把桥按照限重从大到小排序，排完序之后处理处前缀 \(\max\)，每次我们计算时直接把 \(sum\) 丢进去 \(lower_bound\) 即可。
然后就可以 \(dp\) 了，\(f_i\) 表示考虑前 \(i\) 个骆驼的最短长度，\(f_i=max_{j=1}^{i-1}\{f_j+Calc(j,i)\}\)。
$\texttt{Code}$
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=10,M=1e5+5;
int n,m,a[N],ans=1e18,l[M],v[M],s[N],f[N];
il int read(){
re int x=0;re char c=getchar(),f=0;
while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f?-x:x;
}
struct bridge{
int l,v;
}b[M];
il bool cmp(bridge x,bridge y){
return x.v<y.v;
}
il void check(){
memset(f,0,sizeof f);
for(re int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
for(re int i=2;i<=n;i++)
for(re int j=1;j<i;j++)
f[i]=max(f[i],f[j]+l[lower_bound(v+1,v+1+m,s[i]-s[j-1])-v-1]);
ans=min(ans,f[n]);
}
signed main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
n=read(),m=read();
int mx=0,mn=1e9;
for(re int i=1;i<=n;i++)a[i]=read(),mx=max(mx,a[i]);
for(re int i=1;i<=m;i++)b[i].l=read(),b[i].v=read(),mn=min(mn,b[i].v);
if(mx>mn)return puts("-1"),0;
sort(b+1,b+1+m,cmp);
for(re int i=1;i<=m;i++)l[i]=b[i].l,v[i]=b[i].v;
for(re int i=1;i<=m;i++)l[i]=max(l[i],l[i-1]);
sort(a+1,a+1+n);
do{
check();
}while(next_permutation(a+1,a+1+n));
cout<<ans;
return 0;
}
[ARC106C] Solutions
先判掉一车无解：
-
\(m\lt 0\) 无解，因为 \(A\) 是正解贪心。
-
\(m=n\) 无解，因为 \(B\) 至少会选一个。
-
\(m=n-1\)，说明 \(ansB=1,ansA=n\)，此时若 \(n\neq 1\)，说明这 \(n\) 条线段互不相交，那么 \(ansB\) 也应为 \(n\)，矛盾，所以 \(m=n-1\land n\neq 1\) 时无解。
然后考虑什么时候 \(A\) 会少选。即是按左端点排序之后选到了一个左端点小但右端点巨大的线段，导致它包含了很多线段，然后都不能选了，但是 \(B\) 就可以不选这个线段，去选里面的更多的线段。
于是就显然了。先放一条巨长的线段，再在这个线段里面放 \(m+1\) 条互不相交的小线段，这样 \(A\) 会选到里面的 \(m+1\) 条线段，\(B\) 只会选到这条很长的线段，然后就满足题意了。最后在外面补上 \(n-m-2\) 条互不相交的线段即可。
注意特判 \(m=0\)，直接放 \(n\) 条互不相交的线段。
$\texttt{Code}$
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
const int N=2e5,star=5e5;
int n,m;
il int read(){
re int x=0;re char c=getchar(),f=0;
while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15),c=getchar();
return f?-x:x;
}
int main(){
n=read(),m=read();
if(m<0||m==n||(m==n-1&&n>=2))return puts("-1"),0;
if(!m){
for(re int i=1;i<=n;i++)cout<<(i<<1|1)<<' '<<((i+1)<<1)<<'\n';
return 0;
}
cout<<1<<' '<<star<<'\n';
for(re int i=1;i<=m+1;i++)cout<<(i<<1|1)<<' '<<((i+1)<<1)<<'\n';
for(re int i=1;i<=n-m-2;i++)cout<<(i<<1|1)+star<<' '<<((i+1)<<1)+star<<'\n';
return 0;
}