A.The Good Array
题意：定义一个数组是good的要求有：
从左往右所有的i，前i个数中至少有[i/k]个数是1
从右往左所有的i，前i个数中至少有[i/k]个数是1
问good数组对于n而言最少需要多少个1
Solution
先从左往右填1，直到满足第一个条件，然后从右往左填1，直到满足第二个条件
void solve()
{
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)a[i]=0;
for(int i=1;i<=n;i++)
{
if(i%k==1)a[i]=1;
}
int s=0;
for(int i=n;i>=1;i--)
{
int z=n-i+1;
if(a[i]==1)s++;
if((z+k-1)/k>s)
{
a[i]=1;
s++;
}
}
int sum=0;
for(int i=1;i<=n;i++)
{
if(a[i]==1)sum++;
}
cout<<sum<<"\n";
}
B.Lamps
题意：有一些灯，一开始都是关闭的，它们各有值a[i]和b[i]，开启第i个灯会获得b[i]的分数，如果当前的有k个灯开着，则所有a[i]<=k的灯会立马毁掉，坏的灯无法开启，也不被视为开启，如何点灯会使得获得的点数最大
Solution
排两个优先队列，一个存剩下的灯，一个存开启的灯，剩下的灯里面把a[i]小的并且b[i]更大的放在前面，开启的灯把a[i]小的放在前面，每次点灯后判断一下即可
struct node
{
int x,y;
bool operator <(const node &t)const&{
if(x!=t.x)return x > t.x;
return y < t.y;
}
};
void solve()
{
int n;cin>>n;
priority_queue<node>q;
priority_queue<pii,vector<pii>,greater<pii> >p;
int cnt=0;
for(int i=1;i<=n;i++)
{
int a,b;cin>>a>>b;
q.push({a,b});
}
int ans=0;
while(q.size())
{
node t=q.top();
q.pop();
p.push({t.x,t.y});
int z=p.size();
ans+=t.y;
while(p.size()&&p.size()>=p.top().first)p.pop();
while(q.size()&&z>=q.top().x)q.pop();
}
cout<<ans<<"\n";
}
C.Insert Zero and Invert Prefix
题意：有一串01序列a，现在你有一个空的序列b，每次可以选一个位置加入0，这个位置左边的数会异或上1，右边不变，构造一系列操作使得a=b
Solution
我们可以发现，每一串1后面必须跟上一个0，不然就无法变为a，所以不成立的条件仅为a[n]为1的情况，其它情况必有解，那么我们可以每次在位置1加0，然后在这串0的右边加一个0，这样就会使得左边的0全变为1，而右边不变
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
if(a[n]!=0)
{
cout<<"NO\n";
return;
}
int pos=n;
int op=0;
int cnt=0;
while(pos>=0)
{
if(pos==0||a[pos]==0)
{
for(int i=1;i<=cnt;i++)
{
ans[++op]=0;
}
if(cnt!=0)ans[++op]=cnt;
else if(pos!=n)ans[++op]=0;
cnt=0;
}else
{
cnt++;
}
pos--;
}
cout<<"YES\n";
for(int i=1;i<=op;i++)
{
cout<<ans[i]<<" ";
}
cout<<"\n";
}
D.Ball Sorting
题意：给一个由[1...n]组成的序列，对于k=1,2,...,n，可以使用k个0，将其插入序列后，0的相邻数字可以调整到任意位置，这样的调整操作可以进行无数次，结束操作后所有0都会消失，问对于每一个k，最少需要多少次操作才能使得序列变为升序
Solution
这里是要找最大上升子序列，假设一条上升子序列可以把原序列分为k块，那么一个合法的答案就是n-len(子序列)
这里用dp处理出所有的情况
令dp[i][j]表示为以第i个数结尾，把前i个数分为j块的最长上升子序列的最大长度
转移方程为
dp[i][j]=dp[i-1][j]+1(当a[i]>a[i-1]时)
dp[i][j]=dp[k][j-1]+1(当a[i]>a[k]时)
void solve()
{
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=(i+1)/2;j++)
{
if(a[i]>a[i-1]&&dp[i-1][j]!=-1)dp[i][j]=max(dp[i][j],dp[i-1][j]+1);
if(j>0)
{
for(int k=0;k<i-1;k++)if(a[k]<a[i]&&dp[k][j-1]!=-1)dp[i][j]=max(dp[i][j],dp[k][j-1]+1);
}
}
}
int last=dp[n][0];
for(int k=1;k<=n;k++)
{
int ans=0;
for(int i=1;i<n;i++)
{
ans=max(ans,dp[i][k-1]);
}
ans=max(ans,dp[n][k]);
ans=max(ans,last);
last=ans;
cout<<n-ans<<" ";
}
cout<<"\n";
}