A. Searching Local Minimum (*1700)
题意
交互题
有一个长度为(n(1leq nleq 1e5))的排列(a)，要求询问小于等于(100)次，找到一个极小值点，极小值点(i)即为满足(a_i<min{a_{i-1},a_{i+1} })的点。定义(a_0=a_{n+1}=+infty)
题解
通过二分维护包含极小值点的区间([l,r])，令(a_{l-1}>a_l)并且(a_r<a_{r+1})，初始时(l=1,r=n)
case 1: (a_{mid}<a_{mid+1})，区间变成([l,mid])
case 2: (a_{mid}>a_{mid+1})，区间变成([mid+1,r])
询问次数为(2lceil{log_2{n}}
ceil< 34<100)
#include<bits/stdc++.h>
#define LL long long
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
int n;
bool check(int mid){
int x,y;
printf("? %d
",mid);
fflush(stdout);
scanf("%d",&x);
printf("? %d
",mid+1);
fflush(stdout);
scanf("%d",&y);
return x<y;
}
int main(){
scanf("%d",&n);
int l=1,r=n;
while(r>l){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("! %d
",r);
fflush(stdout);
}
B1. Painting the Array I (*1900)
题意
给出一种构造方案，将一个给定的长度为(n(1leq nleq 1e5))的数组(a)拆分成两个子序列，子序列中连续的相同的数合并成一个，使得两个子序列长度之和最大，计算最大的长度之和
题解
贪心
设两个队列分别为(s)和(t)，扫描数组(a)，设当前扫描到的元素为(x)，队列(s)和(t)的末尾元素分别为(y)和(z)
case 1：(x)与(y)或者(z)的其中一个相同，另外一个不同，则将(x)添加到不同的那个数所在队列的末尾。
case 2：(x)与(y)和(z)都不相同，则将(x)添加到待扫描的元素中(y)或者(z)出现更早的队列中
#include<bits/stdc++.h>
#define LL long long
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=100010;
int n,a[maxn],pos[maxn],nxt[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=0;i<=n;i++) pos[i]=n+1;
for(int i=n;i>=0;i--){
nxt[i]=pos[a[i]];
pos[a[i]]=i;
}
int j=0,k=0,ans=0;
for(int i=1;i<=n;i++){
if(a[i]==a[j]){
ans+=a[i]!=a[k];
k=i;
}
else if(a[i]==a[k]){
ans+=a[i]!=a[j];
j=i;
}
else{
ans++;
if(nxt[j]<nxt[k]){
j=i;
}
else{
k=i;
}
}
}
printf("%d
",ans);
}
B2. Painting the Array II (*2100)
题意
给出一种构造方案，将一个给定的长度为(n(1leq nleq 1e5))的数组(a)拆分成两个子序列，子序列中连续的相同的数合并成一个，使得两个子序列长度之和最小，计算最小的长度之和
题解
方法一：贪心
与(B1)的构造相反
设两个队列分别为(s)和(t)，扫描数组(a)，设当前扫描到的元素为(x)，队列(s)和(t)的末尾元素分别为(y)和(z)
case 1：(x)与(y)或者(z)的其中一个相同，则将(x)添加到相同的那个数所在队列的末尾。
case 2：(x)与(y)和(z)都不相同，则将(x)添加到待扫描的元素中(y)或者(z)出现更晚的队列中
#include<bits/stdc++.h>
#define LL long long
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=100010;
int n,a[maxn],pos[maxn],nxt[maxn];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=0;i<=n;i++) pos[i]=n+1;
for(int i=n;i>=0;i--){
nxt[i]=pos[a[i]];
pos[a[i]]=i;
}
int j=0,k=0,ans=0;
for(int i=1;i<=n;i++){
if(a[i]==a[j]){
j=i;
}
else if(a[i]==a[k]){
k=i;
}
else{
ans++;
if(nxt[j]>nxt[k]){
j=i;
}
else{
k=i;
}
}
}
printf("%d
",ans);
}
方法二：dp
扫描数组(a)，对于(1leq j<i)，设(a[j-1])与(a[i])在同一个队列中相邻，则将下标为([j,i-1])的元素移动到另一个队列中，考虑一个(O(n^2))的dp：
(f[i]=min_{1leq j<i}{ f[j]+(i-j-1)+[a[j-1]
eq a[i]]})
优化成(O(n))：
设(g(i,j)=f(j)+(i-j-1)+[a[j-1]
eq a[i]])
转移有两种情况：
1.从((i-1))处转移，(f[i]=min(f[i],g(i,i-1)))
2.设之前出现过(a[i])的最近位置为(last[i])，则从(last[i]+1)处转移，(f[i]=min(f[i],g(i,last[i]+1)))
#include<bits/stdc++.h>
#define LL long long
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;
const int maxn=100010,inf=1e9+10;
int n,m,a[maxn],f[maxn],pos[maxn],last[maxn];
int g(int i,int j){
return f[j]+(i-j-1)+(a[j-1]!=a[i]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
if(a[i]!=a[i-1]) a[++m]=a[i];
}
for(int i=1;i<=m;i++){
last[i]=pos[a[i]];
pos[a[i]]=i;
}
f[1]=1;
for(int i=2;i<=m;i++){
f[i]=g(i,i-1);
if(last[i]){
int j=last[i]+1;
f[i]=min(f[i],g(i,j));
}
}
printf("%d
",f[m]);
}