【题解】牛客NOIP暑期七天营-提高组4
比赛总结
本场比赛终于结束了，首先先谢谢牛客以及各位选手三个半小时的努力和支持！
恭喜28位AK的选手！
这套题目还是有一些不尽人意的地方的，大概有下面几点
1.本来应当考察一些图论知识，但是结果只有T3的树上问题有一点涉及。
2.T1的部分分和T2的正解都可以是DP，考察了重复的知识点。
3.T3没有什么思维难度，是两个不同模板的拼凑。
4.T1可能比正式比赛的T1稍难，T3可能比正式比赛稍微简单（如果您学过线性基的话。小声剧透，T3是树上启发式合并+线性基，如果您会第二个但没学过第一个，yy出来第一个算法还是可以的）。
5.有人指出部分分档数不够多...但是我实在出不到四五档，因为我的做法也只有几个...这点向大家道歉（于是比赛到一半偷偷加了一档部分分（小声）
6.T3似乎有序列上的原题，是用线段树合并，本来可以卡空间卡掉这个做法，但是最终并没有卡...其实这三道题都是原创的idea，有出现撞题实在没有办法，在这里向大家道歉...
（立flag本场比赛AK人数最多）
题解
T1 麻将
麻将题！
对于20%的数据，直接暴力枚举各种情况，再暴力（或者按照题面中的状态转移方程改一下）求出最大子矩阵
因为可以交换无数次，所以我们可以认为该矩阵的行是无序的。
考虑DP，记录lft[i][j] 为矩阵的第i行第j列的元素左边的连续1（包括它自己）的长度），这个可以在O(nm)内求出
那么 枚举列，并将该列各元素的lft值排序（可以交换），就排成了一个全1的直角三角形，接下来就是在这个三角形中找到最大的全1矩阵
下面给出std
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int maxn=5010;
inline int read() {
int res=0,fh=1;
char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return fh*res;
}
char c[maxn][maxn];
int lft[maxn][maxn];
int f[maxn];
inline int Max(int a,int b){
return a<b?b:a;
}
int main()
{
int n=read(),m=read();
memset(c,0,sizeof c);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
while(c[i][j]!='0'&&c[i][j]!='1')c[i][j]=getchar();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
lft[i][j]=c[i][j]=='0'?0:lft[i][j-1]+1;
int ans=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++) f[j]=lft[j][i];
sort(f+1,f+n+1);
for(int j=n;j>=1;j--) ans=Max(ans,(n-j+1)*f[j]);
}
return printf("%d\n",ans),0;
}
T2 卖羊驼
a[i] 表示第i个整数, dp[i][k] 表示在 i 之前将序列分为k组的最优解
jump[i][j] 表示 i 之前最后一个在二进制拆分后第j位为1的数的位置（决策点）
OR(i, j) 表示 a[i] 到 a[j] 之间的OR和
可以使用一个 O(nlogV) 的循环直接预处理出决策点，使用st表维护 i~j 的OR和
也可以在DP时处理出决策点，并且由于只需要决策点到位置i的or和，可以在决策点转移的时候同时修改
状态转移方程：dp[i][k] = max_{j = 1...32}{ dp[jump[i][j]-1][k-1] + OR(jump[i][j],\ i}
std:
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
#define type int//看情况修改返回类型
inline char nc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline type read()
{
char ch=nc();type sum=0;
while(!(ch>='0'&&ch<='9'))ch=nc();
while(ch>='0'&&ch<='9')sum=(sum<<1)+(sum<<3)+ch-48,ch=nc();
return sum;
}
const int maxn = 5e6 + 10;
const int maxv = 32;
long long n, K, a[maxn], choose[maxv], val[maxv];//dp[n][k]表示在n之前分k组的最大值，val[i]表示第i位的决策点到i的or和，choose[i]表示在第i位上的决策点
char name[100];
int main(){
//for(int iii = 1; iii <= 10; iii++){
//sprintf(name, "dp%d.in", iii);
//freopen(name, "r", stdin);
//sprintf(name, "dp%d.out", iii);
//freopen(name, "w", stdout);
memset(val, 0, sizeof(val));
memset(a, 0, sizeof(a));
memset(choose, 0, sizeof(choose));
n = read(), K = read();
const int n1 = n+1, k1 = K+1;
long long** dp = new long long *[n1];
for(int i = 0; i < n1; i++)
dp[i] = new long long[k1];
for(int i = 0; i < n1; i++)
for(int j = 0; j < k1; j++)
dp[i][j] = 0;
for(int i = 1; i <= n; i++){
a[i] = read();
dp[i][1] = dp[i-1][1] | a[i];
}
for(int i = 1; i <= n; i++){
for(int j = 0; j <= 31; j++ ){
if((a[i] >> j)&1){
val[j] = a[i];
choose[j] = i;
}
val[j] |= a[i];
}
for(int k = 2; k <= K && k <= i; k++){
for(int j = 0; j <= 31; j++)
if(choose[j] >= k)
dp[i][k] = max(dp[choose[j]-1][k-1] + val[j], dp[i][k]);
}
}//总复杂度O(nklogv) logv可认做32
cout << dp[n][K] << endl;
for(int i = 0; i < n1; i++)
delete [] dp[i];
delete [] dp;
//}
return 0;
} 对于部分分，还有一个模拟退火的写法，我将其卡到了90分
T3 清新题
首先考虑如何求几个元素的异或最大值，这个如果使用暴力，复杂度是的（所以并没有设置这部分分），这个是一个模板，可以用线性基解决。
那么对于前三组数据，我们就可以直接暴力拿出元素线性基解决了，对于后面2组，我们可以直接暴力拿出元素枚举
接下来考虑询问，如果您是数据结构大毒瘤，可以用dfs序后线段树合并解决。然而为了使这道题更加清新和有营养，我们也可以使用树上启发式合并来解决。
树上启发式合并的模板是树上数颜色，在这道题中，我们记录的是各种颜色出现的个数。类似地，我们记录相对应的数组（在std中，这个数组为）
所以这道题是树上启发式合并和线性基的模板题~
下面给出std
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int INF=(1<<30);
inline int read() {
int res=0,fh=1;
char ch=getchar();
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
if(ch=='-')fh=-1,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return fh*res;
}
const int maxn=100010;
int n,tot=0;
int p[32],val[maxn],to[maxn<<1],head[maxn],fa[maxn],nxt[maxn<<1],siz[maxn],son[maxn],ans[maxn];
inline void addedge(int x,int y){
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
to[++tot]=x;
nxt[tot]=head[y];
head[y]=tot;
}
inline void insert(int x){
for(int i=31;i+1;i--){
if(!(x>>i))
continue;
if(!p[i]){
p[i]=x;
break;
}
x^=p[i];
}
}
inline int que(){
int res=0;
for(int i=31;i+1;i--)
if((res^p[i])>res)
res^=p[i];
return res;
}
void dfs(int x,int y){
siz[x]=1;
for(int i=head[x];i;i=nxt[i]){
if(to[i]^y){
fa[to[i]]=x;
dfs(to[i],x);
if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
siz[x]+=siz[to[i]];
}
}
}
void del(){
memset(p,0,sizeof p);
}
void dfs2(int x,int y){
if(!y){
for(int i=head[x];i;i=nxt[i]){
if(fa[x]!=to[i]&&(to[i]!=son[x])){
dfs2(to[i],0);
del();
}
}
}
if(son[x]) dfs2(son[x],y);
for(int i=head[x];i;i=nxt[i])
if((to[i]!=fa[x])&&(son[x]!=to[i]))
dfs2(to[i],1);
insert(val[x]);
if(!y) ans[x]=que();
}
int main(){
n=read();
for(int i=1;i<n;i++) addedge(read(),read());
for(int i=1;i<=n;i++) val[i]=read();
dfs(1,1);
dfs2(1,0);
n=read();
while(n--) printf("%d\n",ans[read()]);
} 事实上，如果将问题改成询问区间的异或最大值，那么后者就没法解决这个问题了。
最后，再次感谢牛客的支持，验题人@emofunx 的帮助以及选手们的努力！
查看15道真题和解析
