【题解】牛客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 的帮助以及选手们的努力!