VP 情况：
solve：4/5
rank：431st
评价：
VP 了一下，我这个 shaber B 直接 5 发罚时，耽误了二十多分钟，以及被 D 各种细节差点搞死。
A.Ezzat and Two Subsequences（*800）
题目描述：
给定一个序列，将其分为 \(2\) 个组，要求这两个组的平均值之和最大，组内的数不要求在原序列中连续。
题目分析：
我们肯定是将最大值分为一个组，其他的分为另一个组最优。
可以自己列列式子就可以证明出来了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
const int INF = 1e9+7;
int a[N];
int main(){
int T;scanf("%d",&T);
while(T--){
int n;scanf("%d",&n);
double ans = 0;
int mx = -INF;
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);mx = max(mx,a[i]);
ans += a[i];
}
ans -= mx;ans = 1.0 * ans / (n - 1);
ans += mx;
printf("%.7f\n",ans);
}
return 0;
}
B.Moamen and k-subarrays（*1100）
题目描述：
将一个不含重复元素的序列划分为 \(k\) 个子区间，要求连续，然后将这 \(k\) 个子区间按它们的字典序拼接（注意不是内部的排序），询问是否存在一种划分方式使得拼接后的序列是单调递增的。
题目分析：
不得不说这个题意太神仙了，老是读错就一直寄。
因为我们子区间内部顺序是不会改变也不会插入删除什么的，所以我们每一个子区间一定是对应排序后的序列的一个连续段。
此时我们要求最小的划分数量是好求的，就是能连在一起就连在一起就是最小的。
要求是否存在一个划分数为 \(k\) 的方案，其实就是判断一下最小划分数是否小于等于 \(k\) 就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int cnt[N],a[N],b[N],tot;
int main(){
int T;scanf("%d",&T);
while(T--){
int n,k;scanf("%d%d",&n,&k);
tot = 0;
for(int i=1; i<=n; i++){
scanf("%d",&a[i]);
b[++tot] = a[i];
}
sort(b+1,b+tot+1);tot = unique(b+1,b+tot+1) - b - 1;
for(int i=1; i<=n; i++) a[i] = lower_bound(b+1,b+tot+1,a[i]) - b;
int tmp = 1;
for(int i=2; i<=n; i++){
if(a[i] != a[i-1] + 1) ++tmp;
}
if(tmp <= k) printf("Yes\n");
else printf("No\n");
}
return 0;
}
C.Moamen and XOR（*1700）
题目描述：
要求构造一个长度为 \(n\) 的序列，每个数都小于 \(2^k\)，满足序列内所有元素按位与的值大于等于按位异或的值。
求有多少种构造的方案数。
题目分析：
一开始按照大于等于去算的然后发现讨论有点复杂，就差分了一下求小于的情况。
经典套路，小于的情况其实就是：从大到小枚举每一位 \(i\)，满足前 \(i-1\) 位都是相等，第 \(i\) 位小于，第 \(i\) 位之后的位无所谓。
因为每一位都是独立的，所以其实只要特殊算算当前位相等的方案数和小于的方案数然后乘一下就好了。
当前位相等包含两种情况：
- 都为 \(0\)：此时即 \(n\) 个数里当前位有偶数个 \(1\) 且不全部为 \(1\)，直接组合数就好了
- 都为 \(1\)：此时即 \(n\) 个数里当前位全部为 \(1\)，且 \(n\) 为奇数，直接判一下就好了。
小于只有一种情况：
- 按位与为 \(0\) 且按位异或为 \(1\)：此时即 \(n\) 个数里有奇数个 \(1\) 且不全为 \(1\)，直接组合数就好了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5+5;
const int MOD = 1e9+7;
int fac[N],inv[N];
int mod(int x){
return (x % MOD + MOD)%MOD;
}
int power(int a,int b){
int res = 1;
while(b){
if(b & 1) res = mod(res * a);
a = mod(a * a);
b >>= 1;
}
return res;
}
int binom(int n,int m){
if(n < m || n < 0 || m < 0) return 0;
return mod(fac[n] * mod(inv[m] * inv[n-m]));
}
signed main(){
int t;scanf("%lld",&t);
while(t--){
int n,k;scanf("%lld%lld",&n,&k);
fac[0] = 1;
for(int i=1; i<=n; i++) fac[i] = mod(fac[i-1] * i);
inv[n] = power(fac[n],MOD-2);
for(int i=n-1; i>=0; i--) inv[i] = mod(inv[i+1] * (i+1));
int tmp1 = 0,tmp2 = 0;
//考虑等于的情况
for(int i=0; i<n; i+=2) tmp1 = mod(tmp1 + binom(n,i));
if(n & 1) tmp1++;
//考虑小于的情况
for(int i=1; i<n; i+=2) tmp2 = mod(tmp2 + binom(n,i));
int res = 1,ans = 0;
for(int i=1; i<=k; i++){
ans = mod(ans + res * tmp2 %MOD* power(power(2,k-i),n));
res = mod(res * tmp1);
}
ans = mod(power(power(2,k),n) - ans);
printf("%lld\n",ans);
}
return 0;
}
D.Ezzat and Grid（*2200）
题目描述：
给定一个 \(n\) 行的矩阵，有 \(m\) 次操作，每次操作是将第 \(i\) 行的 \([l,r]\) 列染黑。
现在要求你删除 \(n\) 行中的一些行，要求留下来的行相邻两个之间都存在某一列，使得这一列在两行中均染黑。
要求最小化删的行数，并且要求构造方案。
题目分析：
发现其实关键问题在于我们对于这个最小一无所知，所以啥都不能干。
那么就考虑强行知道一些东西，即我们设 \(f[i]\) 表示前 \(i\) 行中第 \(i\) 行必须不删，要满足条件的最小删除行数。
显然我们只需要倒序一下序列然后求出 \(g[i]\) 表示后 \(i\) 行中第 \(i\) 行必须不删，要满足条件的最小删除行数，直接两个数组一合并就是答案。
考虑 \(f[i]\) 的转移其实就是从前 \(i-1\) 行与当前行的黑色有交集的行转移，所以不妨先将所有的操作按操作的行从小到大排序，这样就能保证做到第 \(i\) 行时前 \(i-1\) 行都完成了。
具体写一下转移其实就是：
\[f[i] = \max\{f[j] + (i - j + 1)\} = \max\{f[j] - j\} + i + 1 \]这个东西看上去就需要用数据结构优化，有交集放到线段树上是很好表示的，也就是可以对于每一个区间维护与这个区间有交集的所有行的 \(f[j] - j\) 的最大值，这样查询直接正常的线段树查询就可以完成了。
代码：
点击查看代码
#include<bits/stdc++.h>
#define PII pair<int,int>
#define mp make_pair
using namespace std;
const int N = 1e6+5;
const int INF = 1e9+5;
struct node{
int pos,l,r;
}a[N];
PII mn[4*N],tag[4*N];
PII f[N],g[N];
bool flag[N];
int b[2*N];
bool cmp(node a,node b){
return a.pos < b.pos;
}
void update(int now,PII val){
mn[now] = min(mn[now],val);
tag[now] = min(tag[now],val);
}
void pushdown(int now){
update(now<<1,tag[now]);update(now<<1|1,tag[now]);
tag[now] = {INF,0};
}
void pushup(int now){
mn[now] = min(mn[now<<1],mn[now<<1|1]);
}
void modify(int now,int now_l,int now_r,int l,int r,PII val){
if(l <= now_l && r >= now_r){
update(now,val);
return;
}
pushdown(now);
int mid = (now_l + now_r)>>1;
if(l <= mid) modify(now<<1,now_l,mid,l,r,val);
if(r > mid) modify(now<<1|1,mid+1,now_r,l,r,val);
pushup(now);
}
PII query(int now,int now_l,int now_r,int l,int r){
if(l <= now_l && r >= now_r) return mn[now];
pushdown(now);
int mid = (now_l + now_r)>>1;
PII ans = {INF,0};
if(l <= mid) ans = min(ans,query(now<<1,now_l,mid,l,r));
if(r > mid) ans = min(ans,query(now<<1|1,mid+1,now_r,l,r));
pushup(now);
return ans;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,m;scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) scanf("%d%d%d",&a[i].pos,&a[i].l,&a[i].r);
int tot = 0;
for(int i=1; i<=m; i++) b[++tot] = a[i].l,b[++tot] = a[i].r;
sort(b+1,b+tot+1);tot = unique(b+1,b+tot+1) - b - 1;
for(int i=1; i<=m; i++) a[i].l = lower_bound(b+1,b+tot+1,a[i].l) - b,a[i].r = lower_bound(b+1,b+tot+1,a[i].r) - b;
sort(a+1,a+m+1,cmp);
memset(mn,0x3f,sizeof(mn));memset(tag,0x3f,sizeof(tag));memset(f,0x3f,sizeof(f));
for(int i=1; i<=m; i++){
PII tmp = query(1,1,tot,a[i].l,a[i].r);tmp.first += a[i].pos-1;
f[a[i].pos] = min(f[a[i].pos],tmp);
if(a[i].pos != a[i+1].pos){
f[a[i].pos] = min(f[a[i].pos],mp(a[i].pos-1,0));
for(int j=i; a[j].pos == a[i].pos; j--)
modify(1,1,tot,a[j].l,a[j].r,{f[a[j].pos].first - a[j].pos,a[j].pos});
}
}
memset(mn,0x3f,sizeof(mn));memset(tag,0x3f,sizeof(tag));memset(g,0x3f,sizeof(g));
for(int i=m; i>=1; i--){
PII tmp = query(1,1,tot,a[i].l,a[i].r);tmp.first -= a[i].pos;
g[a[i].pos] = min(g[a[i].pos],tmp);
if(a[i].pos != a[i-1].pos){
g[a[i].pos] = min(g[a[i].pos],mp(n-a[i].pos,n+1));
for(int j=i; a[j].pos == a[i].pos; j++)
modify(1,1,tot,a[j].l,a[j].r,{g[a[j].pos].first + a[j].pos - 1,a[j].pos});
}
}
for(int i=1; i<=n; i++) g[i] = min(g[i],mp(n-i,n+1)),f[i] = min(f[i],mp(i-1,0));
PII ans = mp(INF,0);
for(int i=1; i<=n; i++) ans = min(ans,mp(f[i].first + g[i].first,i));
printf("%d\n",ans.first);
int now = ans.second;
while(now != 0) flag[now] = true,now = f[now].second;
now = ans.second;
while(now != n+1) flag[now] = true,now = g[now].second;
for(int i=1; i<=n; i++){
if(!flag[i]) printf("%d ",i);
}
return 0;
}
E.Assiut Chess（*2800）
题目描述：
本题是一道交互题。
本题需要你编写一个国际象棋中单后杀王的程序，和交互库对弈。 本题的规则和一般国际象棋中的规则有所不同，请认真阅读。
国际象棋棋盘是 \(8\times 8\) 的正方形网格。本题中，所有行从上到下分别编为 \(1\sim 8\) 行，所有列从左到右分别编为 \(1\sim 8\) 列；记同时处在第 \(r\) 行、第 \(c\) 列的格子为格子 \((r,c)\)。
在游戏的开始，你需要确定并告知交互库皇后的初始坐标。接着，交互库会秘密地把国王放至棋盘上任何一个格子。然后，游戏开始，双方轮流走棋，由交互库先行。
皇后的 行走范围 为所有和皇后同行、同列或者同在一条 \(45^\circ\) 斜线上的格子。也就是说，设皇后当前在格子 \((r,c)\)，则皇后下一步能走到格子 \((x,y)\)，当且仅当 \((r,c)\neq (x,y)\)，且 \(r=x\) 或 \(c=y\) 或 \(|r-x|=|c-y|\)。注意：在一步棋中，不允许将皇后停在原地不动。
国王的 行走范围 为其紧邻的 \(8\) 个格子。也就是说，也就是说，设国王当前在格子 \((r,c)\)，则国王下一步能走到格子 \((x,y)\)，当且仅当 \((r,c)\neq (x,y)\)，且 \(\max \{|r-x|,|c-y|\}=1\)。国王不能停在原地不动，不能走入皇后所在的格子，也不能走入皇后的行走范围中。 如果国王无法移动，那么游戏结束，你获得胜利。特别地，如果游戏开始时国王和皇后处于同一位置，那么你直接获胜。
游戏开始后，你和交互库将通过输入输出交流各自走棋的位置（具体格式见下文）。你需要在 \(130\) 步内获得胜利，如果你在行走 \(130\) 步后国王仍有合法移动，那么视作你失败。你需要写一个程序，在规定的步数内获得胜利。
交互细节：
本题一个测试点含多组测试数据。你需要首先从标准输入中读入一个正整数 \(t(1\leq t\leq 60)\)，表示测试数据组数。你们接下来将进行 \(t\) 次游戏。
每次游戏开始时，你需要先输出两个正整数 \(x\ y\)，表示你选择的皇后坐标。接着交互库会选择国王的坐标（但不会告诉你）。接着从交互库开始，双方轮流行动。
当交互库行动时，你需要读入一个字符串 \(S\)。\(S\) 的取值可能有如下几种：
Done：表示交互库无法找到合适的着法，你获胜。如果是最后一组数据则请退出程序；否则请准备下一组数据。Right，Left，Up，Down，Down-Right，Down-Left，Up-Right，Up-Left：分别表示国王向右、左、上、下、右下、左下、右上、左上走了一步。
当你行动时，你需要输出两个整数 \(x\ y\) 表示你移动到的坐标。你需要保证坐标合法。
题目分析：
第一直觉就是先确定国王的位置，但是显然很难确定，因为我们只能知道国王的移动位置，虽然可能可以但是需要巨大量的分类讨论。
那么就考虑我们去一步步堵死国王。
那么就是怎么堵死他了，我们可以从第一行开始每一次都从左到右扫一遍这一行，这样国王就一定会被我们逼到下下一行去。
这里是因为我们王后的移动范围包含下图这种东西：
而我们国王一定不能连跳两个，所以只能选择向下走。
但是还有一种情况就是：可能国王原本在当前行的下下一行，但是下一次操作跳到了当前行的下一行，那么此时我们就只能再把这一行扫一遍，把他逼到当前行的下下一行。
因为逼完以后国王肯定不可能再向上跳了，所以其实国王最多就是每一行向上跳一次，也就是跳 \(7\) 次，这样的话移动次数也是对的。
代码：
点击查看代码
//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int MAXN=131;
int n,pos;
string PLA(int x,int y) {
if(x==0||y==0) {
puts("???");
}
//please let me know the answer (((
printf("%d %d\n",x,y);
pos=y;
//fflush(stdout);
string s;
cin>>s;
return s;
}
bool patrol(int x) {
for(int i=(pos==1? 2:1);i<=8;i++) {
string s=PLA(x,i);
if(s=="Done") {
return 1;
}
if(s[0]=='D') {
return 0;
}
if(s[0]=='U') {
return patrol(x);
}
}
return 0;
}
void work() {
pos=1;
for(int i=1;i<=8;i++) {
if(PLA(i,pos)=="Done") {
return ;
}
if(patrol(i)) {
return ;
}
}
}
signed main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int t=read();
while(t--) {
work();
}
//fclose(stdin);
//fclose(stdout);
return 0;
}