文章目录
- A. Kids Seating
- B. Saving the City
- C. The Delivery Dilemma
- D. Extreme Subtraction
- E. Long Permutation
- F. Identify the Operations
A. Kids Seating
是要整个序列不满足上述条件，一种方案就是从4*n开始，选4*n,4*n-2,4*n-4…选n个，我们发现最后一个被选的是2*n+2，其两倍比4*n大，可见这个方案必然是可行的。
#include <bits/stdc++.h>
using namespace std;
int T;
int n;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;++i)
{
printf("%d ",4*n-2*i);
}
puts("");
}
return 0;
}
B. Saving the City
我们先算一下仅引爆炸弹所需要的总花费，然后，再看每次使两个炸弹段相连的花费，是否可以小于一次引爆炸弹的花费，如果小于，就将两个炸弹段相连，此时总花费-一次引爆的花费+连通的花费。最后就是答案。
#include <bits/stdc++.h>
using namespace std;
int t,a,b;
char s[100005];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&a,&b);
scanf("%s",s);
int len1=0;//1
int len2=0;//0
int ans=0;
for(int i=0;s[i];++i)
{
if(s[i]=='1')
{
len1++;
}
else
{
if(len1)
{
len1=0;
ans+=a;
}
}
}
if(len1)
{
len1=0;
ans+=a;
}
bool flag=0;
for(int i=0;s[i];++i)
{
if(s[i]=='0')
{
len2++;
}
else
{
if(!flag)
{
flag=1;
len2=0;
}
else
if(len2)
{
if(len2*b<=a)
{
ans+=len2*b;
ans-=a;
}
len2=0;
}
}
}
printf("%d\n",ans);
}
return 0;
}
C. The Delivery Dilemma
首先，答案满足单调性，即对于一个时间可以完成的话，那么比他长的时间肯定可以完成。同理，如果对于一个时间不可以完成的话，那么比他短的时间必定不可以完成。因此，考虑二分答案，然后将大于当前时间的送餐改成自己去取，判断一下其和是否超过当前时间即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int t;
int n;
ll a[N];
ll b[N];
bool check(ll x)
{
ll res=0;
for(int i=1;i<=n;++i)
{
if(a[i]>x)
res+=b[i];
}
if(res>x)
return false;
else
return true;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
scanf("%d",&b[i]);
ll l=1;
ll r=2e14;
ll ans=r+1;
while(l<=r)
{
ll mid=(l+r)>>1;
if(check(mid))
{
ans=min(ans,mid);
r=mid-1;
}
else
{
l=mid+1;
}
}
printf("%lld\n",ans);
}
return 0;
}
D. Extreme Subtraction
贪心的思想，对于操作一，可以产生一个非递增的序列a，对于操作二，可以产生一个非递减的序列b。显然，ai+bi=vi(原序列)。对于序列a，ai<=ai-1，对于序列b，bi>=bi-，那么可以将bi和bi-用ai和ai-1换掉，即vi-ai>=vi-1-ai-1 可推出 ai<=vi-vi-1+ai-1。那么对于ai其必须满足 ai<=min(ai-1,vi-vi-1+ai-1)。而且对于ai，必须大于等于0。我们发现为了要让之后尽可能满足，对于每个ai要尽可能取最大。所以我们从前往后扫，如果此时ai小于0了，说明就不满足了。如果扫完都没有不满足，那么必然成立。
#include <bits/stdc++.h>
using namespace std;
const int N=3e4+5;
int v[N];
int a[N];
int t;
int main()
{
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&v[i]);
}
a[1]=v[1];
bool flag=0;
for(int i=2;i<=n;++i)
{
a[i]=min(a[i-1],v[i]-v[i-1]+a[i-1]);
if(a[i]<0)
{
flag=1;
break;
}
}
if(flag)
puts("NO");
else
puts("YES");
}
return 0;
}
E. Long Permutation
我们发现，其实序列是{1,2,…,n}，就算每次都进行二操作，最多也就是对该序列操作2e10，我们知道15！肯定大于2e10，所以其实我们只需要考虑最后15个数字的排列即可。前面的根本就不会便，用前缀和记录一下即可。那么，对于一个序列，怎么知道其下x个nextpermutation呢。我们知道，如果现在有m个数，如果as<at，那么对于as开头的序列的字典序肯定小于at开头的序列的字典序。其后面会有(m-1)!种排列方式。对于一个x，我们要求{1,2,…n}的下x个nextpermutation，我们先用floor(x/(n-1)!)(向下取整)，就能确定第一个数取什么了。比如此时算出来是2，那么就取3，然后把已经贡献的减去，再看第二个数取什么。以此类推，当x=0时，就可以结束了，后面的数直接按序放入就好。
这里给一个例子。
如7个数的集合为{1, 2, 3, 4, 5, 6, 7}，要求出第n=1654个排列。
(1654 / 6!)取整得2，确定第1位为3，剩下的6个数{1, 2, 4, 5, 6, 7}，求第1654 % 6!=214个序列；
(214 / 5!)取整得1，确定第2位为2，剩下5个数{1, 4, 5, 6, 7}，求第214 % 5!=94个序列；
(94 / 4!)取整得3，确定第3位为6，剩下4个数{1, 4, 5, 7}，求第94 % 4!=22个序列；
(22 / 3!)取整得3，确定第4位为7，剩下3个数{1, 4, 5}，求第22 % 3!=4个序列；
(4 / 2!)得2，确定第5为5，剩下2个数{1, 4}；由于4 % 2!=0，故第6位和第7位为增序<1 4>；
因此所有排列为：3267514。
知道这个方法后，就很简单了，我们记录一个now，为一共继续nextpermutation多少次，然后每次查询前，进行一次更新，在查询，查询，就是前面的用前缀和求，后15个，直接依次加就行。
#include <bits/stdc++.h>
using namespace std;
int n,q;
vector<int>ans_string,init_string;
typedef long long ll;
const int N=2e5+5;
ll fac[20];
int cnt;
ll sum[N];
void nextpermutation(ll x)
{
cnt=0;
init_string.clear();
for(int i=max(n-14,1);i<=n;++i)
{
init_string.push_back(i);
++cnt;
}
ans_string.clear();
int t=1;
// cout<<init_string.size()<<endl;
for(int i=0;i<cnt;++i)
{
ll tmp=x/fac[cnt-t];
x%=fac[cnt-t];
t++;
// cout<<tmp<<" "<<x<<endl;
//cout<<init_string[tmp]<<endl;
ans_string.push_back(init_string[tmp]);
init_string.erase(init_string.begin()+tmp);
//cout<<init_string.size()<<endl;
if(x==0)
break;
}
for(int i=0;i<init_string.size();++i)
{
ans_string.push_back(init_string[i]);
}
// for(int i=0;i<ans_string.size();++i)
// cout<<ans_string[i]<<" ";
// cout<<endl;
}
ll query(int l,int r)
{
ll res=0;
if(r>=max(n-14,1))
for(int i=max(0,l-max(n-14,1));i<=r-max(n-14,1);++i)
res+=ans_string[i];
if(l<max(n-14,1))
res+=sum[min(r,max(n-14,1)-1)]-sum[l-1];
return res;
}
int main()
{
scanf("%d%d",&n,&q);
fac[0]=1;
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+i;
for(int i=1;i<=min(n,15);++i)
fac[i]=fac[i-1]*i;
// cout<<init_string.size()<<endl;
// cout<<cnt<<endl;
// cout<<fac[cnt]<<endl;
int opt,l,r,x;
ll now=0;
while(q--)
{
scanf("%d",&opt);
if(opt==1)
{
scanf("%d%d",&l,&r);
nextpermutation(now);
printf("%lld\n",query(l,r));
}
else
{
scanf("%d",&x);
now+=x;
}
}
return 0;
}
F. Identify the Operations
首先判断一下能否找到方案，如果不能找到方案，那么就是对于a序列的一个数ai，其在b序列里，且其左右ai-1ai+1都在b序列里，且其左右ai-1ai+1在b序列的顺序都在ai之后。那么肯定不满足，因为如果此时要获得ai必须要删ai-1和ai+1其中一个，但其都在b序列且在ai之后，删完之后就获得不了了。其它情况，都能找到方案使满足条件。那么方案数怎么算呢。我们把一段在b序列出现的连续a序列数当作一个连通块，且只有单独一个数的就当作一种特殊连通块，其个数为n(在头尾的不算)。总方案数就是 2n。简单证明在下面。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int inf=2e5+5;
const int N=2e5+5;
int t;
bool vis[N];
int a[N];
int b[N];
int main()
{
scanf("%d",&t);
while(t--)
{
int n,k;
scanf("%d%d",&n,&k);
a[0]=a[n+1]=0;
b[0]=inf;
vis[0]=1;
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
//pos[a[i]]=i;
vis[i]=0;
}
for(int i=1;i<=k;++i)
{
int x;
scanf("%d",&x);
b[x]=i;
vis[x]=1;
}
bool flag=0;
for(int i=1;i<=n;++i)
{
if(vis[a[i]]&&vis[a[i-1]]&&vis[a[i+1]]&&b[a[i]]<b[a[i-1]]&&b[a[i]]<b[a[i+1]])
{
flag=1;
break;
}
}
if(flag)
{
puts("0");
continue;
}
ll ans=1;
int len=0;
int pos=1;
if(vis[a[1]])
for(int i=1;i<=n;++i)
{
if(!vis[a[i]])
{
len=0;
pos=i;
break;
}
else
len++;
}
for(int i=pos;i<=n;++i)
{
if(!vis[a[i]]&&len)
{
len=0;
ans<<=1;
ans%=mod;
}
else
if(vis[a[i]])
{
len++;
}
}
printf("%lld\n",ans);
}
return 0;
}
![【数据结构】 医院选址[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)