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

全部评论
T3 不是直接线性基合并吗,两个 log ,代码也短
点赞 回复 分享
发布于 2019-08-22 12:08
T1不是BZOJ原题吗
点赞 回复 分享
发布于 2019-08-22 12:22
其实查询一个子树,就是查询dfs序序列上的一个区间异或最大值,可以直接离线线性基,复杂度一个logn
点赞 回复 分享
发布于 2019-08-22 13:32
现在出题都这么难了嘛……出三道重两道,还有一道出成裸题了。 心疼出题人
点赞 回复 分享
发布于 2019-08-22 13:54
¿¿¿T3数据过水了吧,暴力拿出元素线性基也能???
点赞 回复 分享
发布于 2019-08-22 16:03
T3可以直接树形dp维护线性基吧
点赞 回复 分享
发布于 2019-08-22 12:12
和那个是同理的吧(小声
点赞 回复 分享
发布于 2019-08-22 12:15
T1n^2log能过?
点赞 回复 分享
发布于 2019-08-22 12:16
orz codesonic
点赞 回复 分享
发布于 2019-08-22 12:42
请问T3用线段树(dfn序)+线性基是三只log的吗
点赞 回复 分享
发布于 2019-08-22 12:59
其实认为noip模拟赛不太应该考算法,考一些思维性的题目比较好.
点赞 回复 分享
发布于 2019-08-22 13:36
然后数据又贼水,我T1有一份代码输出的时候打成都能过,全是正方形。。。(逃
点赞 回复 分享
发布于 2019-08-22 14:05
其实。。。t2 i~j的or和直接预处理不就行了嘛?(顺便大喊一声“卡时大法无限好”)
点赞 回复 分享
发布于 2019-08-23 14:55
用一个桶是n^2
点赞 回复 分享
发布于 2019-08-22 12:18

相关推荐

Yushuu:你的确很厉害,但是有一个小问题:谁问你了?我的意思是,谁在意?我告诉你,根本没人问你,在我们之中0人问了你,我把所有问你的人都请来 party 了,到场人数是0个人,誰问你了?WHO ASKED?谁问汝矣?誰があなたに聞きましたか?누가 물어봤어?我爬上了珠穆朗玛峰也没找到谁问你了,我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒,在找到谁问你之前我连癌症的解药都发明了出来,我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆
点赞 评论 收藏
分享
9 2 评论
分享
牛客网
牛客企业服务