A - Beautiful Sequence
题意：给出一个数组，问是否存在任意一个子区间，存在i，使得ai=i
Solution
直接比较当前的数和i的大小就行了，当前为x，如果要求答案存在，必须有i>=x
void solve()
{
int n;cin>>n;
int flag=0;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
if(i>=x)
{
flag=1;
}
}
if(flag)cout<<"YES\n";
else cout<<"NO\n";
}
B - Candies
题意：最开始有1个糖果，当前糖果数为res时，可以进行两种操作：
1.res=2*res+1
2.res=2*res-1
给出n，问能否通过任意次操作1和2使得糖果数变为n
Solution
可以由n进行倒推，如果倒推得到的是偶数就不继续进行下去，这里写了个递归
void dfs(int x,int pos)
{
if(x==1&&!flag)
{
cout<<pos<<"\n";
for(int i=pos;i>=1;i--)
{
cout<<a[i]<<" ";
}
cout<<"\n";
flag=1;
return;
}
if((((x+1)/2)&1)&&!flag)
{
a[pos+1]=1;
dfs((x+1)/2,pos+1);
}
if((((x-1)/2)&1)&&!flag)
{
a[pos+1]=2;
dfs((x-1)/2,pos+1);
}
}
void solve()
{
int n;cin>>n;
flag=0;
if(n%2==0)
{
cout<<"-1\n";
return;
}
dfs(n,0);
if(!flag)cout<<"-1\n";
}
C - Make It Permutation
题意：给出一个数组，删除任意一个数代价为c，添加任意一个数代价为d，求使得数组变为一个非空排列（长度为k的排列当且仅由1,2,..,k组成）的最小代价
Solution
对原序列排个序，然后依次以a[i]为长度的排序更新答案，将a[i]左边的重复的数都删掉，右边的也都删掉，然后再加上缺少的数即可
void solve()
{
int n,c,d;cin>>n>>c>>d;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
int ans=1e18;
set<int>st;
int cnt=0;
for(int i=1;i<=n;i++)
{
if(st.count(a[i]))
{
cnt++;
continue;
}
int x=c*(n-i+cnt)+d*max(0LL,a[i]-st.size()-1);
//cout<<(n-i+cnt)<<" "<<a[i]-st.size()-1<<"\n";
//cout<<x<<"\n";
ans=min(ans,x);
st.insert(a[i]);
}
ans=min(ans,d+c*n);
cout<<ans<<"\n";
}
D - Climbing the Tree
题意：有一只蜗牛爬树，白天爬a米，晚上掉下来b米，树高未知，有两种通知：
1 a b n表示蜗牛花了n天爬到树顶2 a b询问需要爬几天才能到树顶
有q次通知，如果当前通知1与前面的通知1相违背，则忽视当前的通知
如果当前的通知2答案确定，输出答案，反之则输出-1
Solution
对于通知1来说，我们可以求得树高的一个范围区间[l,r]
如果n=1，那么l=1，r=a
如果n≠1，那么l=(a-b)(n-2)+a+1,r=(a-b)(n-1)+a
于是我们可以通过区间来判断是否通知1是否与前面的相符合，如果与前面的有交集，则可以进一步更新h的范围，即l=max(l,ll),r=min(r,rr)
对于通知2来说，要想在第x天到树顶，第x-1天一定到不了l，即(x-2)*(a-b)+a<l
而如果答案唯一，只有一种可能，那就是(x-1)*(a-b)+a>=r
赛时交集判断错了，改了一下直接过了，麻了
void solve()
{
int q;cin>>q;
int h=-1;
int l=-1,r=-1;
while(q--)
{
int op,a,b;cin>>op>>a>>b;
if(op==1)
{
int n;cin>>n;
if(h==-1)
{
l=(a-b)*(n-2)+a+1;
if(n==1)l=1;
r=(a-b)*(n-1)+a;
h=0;
cout<<"1 ";
}else
{
int ll=(a-b)*(n-2)+a+1;
if(n==1)ll=1;
int rr=(a-b)*(n-1)+a;
if(ll>r||rr<l)
{
cout<<"0 ";
}else
{
cout<<"1 ";
l=max(ll,l);
r=min(rr,r);
}
}
}else
{
if(h==-1)
{
cout<<"-1 ";
continue;
}
int x=l-a;
if(x<0)x=0;
int last=-1;
int cnt=x/(a-b);
int now=(a-b)*cnt;
int num=0;
if(now+a>=r)cout<<cnt+1<<" ";
else if(now+a<r&&now+a>=l)cout<<"-1 ";
else if(now+a<l)
{
now+=a-b;
cnt++;
if(now+a>=r)cout<<cnt+1<<" ";
else if(now+a<r&&now+a>=l)cout<<"-1 ";
}
}
}
cout<<"\n";
}