ARC100 E Or Plus Max

其中,\(f[k]\)表示递推到第i位的最大值。
那么,\(f[k]\)显然是可以从\(f[k-1]\)递推来的。
这时候只要考虑\(i|j==k\)的值。
枚举k的子集,求最大值。
这样做是\(O(松松松)\)的。
考虑优化。
我们可以发现,对于k的每一个子集,它的子集的最大值是已经求过的。
那么我们只需要考虑枚举每一个k子集的一部分,可以考虑每一次把它反与上一个\(2^l\),并求Max和次Max。
这样有解,复杂度\(O(n*2^n)\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Swap(_A,_B) ((_A)^=(_B)^=(_A)^=(_B))
using namespace std;
//mx[i][0]表示最大值,mx[i][1]表示次大值。 
int f[1<<18],n,a[1<<18];
int nw,mxx,lmxx,sa,sb,st;
struct data{
    int v;
    int nm;
    bool operator ==(const data &x)const{
        return this->v==x.v&&this->nm==x.nm;
    }
}lst[40],mx[1<<18][2];
inline bool cmp(const data &x,const data &y){
    return x.v>y.v;
}
//处理第k个数,它的最大值和次大值。 
int wrk(int k){
    nw=0,mxx=0,lmxx=0,sa=-1,sb=-1,st=0;
    lst[++st]=(data){a[k],k};
    for(int i=0;(1<<i)<=k;++i){
        if((k>>i)&1){
            nw=k^(1<<i);
        }else{
            continue;
        }
        lst[++st]=mx[nw][0];
        lst[++st]=mx[nw][1];
    }
    sort(lst+1,lst+1+st,cmp);
    unique(lst+1,lst+1+st);
    mx[k][0]=lst[1],mx[k][1]=lst[2];
    return mx[k][0].v+mx[k][1].v;
}
void init(){
    scanf("%d",&n);
    const int MAX=1<<n;
    for(int i=0;i<MAX;++i){
        scanf("%d",&a[i]);
    }
    f[0]=0,mx[0][0].v=a[0],mx[0][1].v=0,mx[0][0].nm=0,mx[0][1].nm=-1;
    for(int k=1;k<MAX;++k){
        f[k]=wrk(k);
        f[k]=Max(f[k],f[k-1]);
        printf("%d\n",f[k]);
    }
}
int main(){
    init();
    return 0;
} 

 

WordPress-Twenty Seventeen 设定仅显示文章摘要

之前首页一直都是显示全篇文章,确实看起来有些难受,这里使用了一个方法魔改了一下主题,令其显示摘要:

在主题的content.php中找到这一段

<?php
	/* translators: %s: Name of current post */
	the_content( sprintf(
	        __( 'Continue reading<span class="screen-reader-text"> "%s"</span>', 'twentyseventeen' ),
	        get_the_title()
	) );
?>

将其注释掉。

改为:

<?php if(!is_single()) {
	the_excerpt();
} else {
	the_content(__('(more…)'));
} 
?>

即可实现仅显示摘要。

不过可能更换/更新主题的时候要重新魔改。正在摸索更有效的方法。

lp2467 SDOI2010 地精部落

这一题的题面很复杂,但形式化地概括则很简单:

对于一个长度为n的全排列,求出其中有多少排列A满足,对于任意i属于n,$$(A_{i}-A{i-1})*(A_{i}-A_{i+1})>=0;$$

然后我们观察排列的特点,我们可以发现,对于排列A中的一个元素\(A_{i}\),我们可以发现,如果\(A_{i}\)是山峰,那么将\(A_{i}\)的值无论添加多少,都不改变这个序列的可居住性;对于山谷,则反之。
于是,我们可以发现,一个合法的排列,如果我们要在它末尾添上一个数让它形成一个新的合法排列,对于除了最后一个数以及这个数是属于山峰以及山谷以外,我们不关心其他的属性。
因此我们可以用\(f[i][j][k]\)表达当前长度为i,最后一个数为j,最后一个数的状态为k的时候的状态数。其中k==0表示山谷,而k==1表示山峰。
则很容易可以得到状态转移方程:
$$f[i][j][k]+=f[i-1][l][k\ xor\ 1](k?(0<l<=j-1):(j-1<l<=i))$$
但是这样子的复杂度是N^3的,对于4200的数据显然是不能通过的。这时候考虑优化。
我们发现求和的东西是一段区间,因此我们可以考虑前缀优化。
这样子就将复杂度从\(n^3\)降低到了\(n^2\),于是可以通过。
但是这样子需要的空间是3E7的,对于128MB的空间是非常危险的,这时候考虑滚动数组优化,这样是可以通过的。

#include<iostream>
#include<cstdio>
using namespace std;
long long n,p,f[4205][2],pre[4205][2];
void init(){
    scanf("%lld%lld",&n,&p);
    int l,r;
    f[1][1]=f[1][0]=pre[1][0]=pre[1][1]=1;
    for(int i=2;i<=n;++i){
        pre[i][0]=pre[i-1][0],pre[i][1]=pre[i-1][1];
        for(int j=1;j<=i;++j){
            for(int k=0;k<=1;++k){
                l=k?0:j-1;
                r=k?j-1:i;
                f[j][k]=(pre[r][k^1]-pre[l][k^1]+p)%p;
//                printf("(%d,%d)[%d,%d]%lld|",l,r,pre[l][k^1],pre[r][k^1],f[j][k]);
            }
//            printf(" ");
        }
        pre[0][0]=pre[0][1]=0;
        for(int j=1;j<=i;++j){
            pre[j][0]=(pre[j-1][0]+f[j][0])%p;
            pre[j][1]=(pre[j-1][1]+f[j][1])%p;
        }
//        puts("");
    }
    long long ans=(pre[n][0]+pre[n][1])%p;
    printf("%lld",ans);
}
int main(){
    init();
    return 0;
}

 

Q:为什么这个方程不会重复统计呢?
如果只关心上一个元素的大小,排列中的元素可能重复出现了。

A:不会重复统计,感性证明如下:

首先我们假定对于上一个A,使得:

$$ |A|==i-1 $$

并没有重复统计。
那么我们插入一个新的元素\(i\)时,产生的新序列必然是 本质不同 的。
我们对于\(A_{i-1}\)是山峰和山谷分别讨论。
如果\(A_{i-1}\)是山峰,那么新插入的元素,必然比\(A_{i-1}\)小,并且一定是由将序列中大等于【某个小于等于\(A_{i-1}\)的一个数\(l\)】的所有数提升一,然后将新插入的元素定义为\(l\)。
这时候,\(i-1\)位上的数是\(A_{i-1}+1\),而\(i\)位上的数则是\(l\)。
在这种情况下,最后两位是\(A_{i-1}+1\)与\(l\)。显然对于每一个本来已有的\(A_{i-1}\),它们在新的序列中都会加且仅加1。
这样,所有新增的组合的最后两位都是 本质不同 的,因此序列本质不同。
对于山谷,情况类同于山峰,同样可以证明不会产生重复的后两位,进而不会产生本质相同的数列。

而对于 $$|A|==1$$ ,结果显然是1,没有重复统计。
从而归纳得出全部都没有重复统计。

LaTeX成功启用

为了能在博客上使用公式,我先后进行了许多尝试。
总之,首先在本地安装MathJax服务。这个服务可以轻松地下载并安装,详见[原创]用LaTeX for WordPress插件在WordPress中写数学公式一帖。

安装的目录正如帖子中所说的,/wp-content/下即可。

然后,在WordPress的商店里面我们可以找到一个名叫MathJex-LaTeX的插件,并将其安装,并在Settings中访问它的设置界面,然后将“Use MathJax CDN Service?”选项关闭,并在“Custom MathJax location?”一项中填写

/wp-content/MathJax/MathJax.js

于是LaTeX环境安装完成。

当我们要使用LaTeX代码的时候,我们只需要用[ latex]代码[/latex ]或者\$\$代码\$\$或\$latex E=mc^2\$来插入LaTeX代码。

Test:

\(E=mc^2\)
$$E=mc^2$$

\(E=mc^2\)

lp2331 SCOI2001 最大子段和

看起来是一道很简单的题,但是细节巨多,消耗了我大量的提交次数。如果是比赛我怕不是凉了。

很显然是一道DP题。
很容易可以想到的是暴力枚举,然而这样做的复杂度是O(n^2*n^2k)的,很很很很显然可以发现是不可行的。
观察数据范围,我们可以注意到, m<=2,因此很容易可以想到状压DP。
具体来说,当m==2时,用f[i][j][l]表示,当前处于第i行,第i行的状态为j,已经使用了l个子矩阵时,最大的和。
则状态转移方程是:

f[i][0][l]=Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l]));
f[i][1][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l]))+b[i];
f[i][2][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l]))+a[i];
f[i][3][l]=Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l]))+a[i]+b[i];

并且我们很容易可以得到边界条件,即:

f[1][0][0]=0,f[1][1][1]=b[1],f[1][2][1]=a[1],f[1][3][1]=a[1]+b[1];

另外需要考虑m==1的情况,事实上这种情况更容易考虑:状态转移方程是:

f[i][0][l]=Max(f[i-1][0][l],f[i-1][1][l]);
f[i][1][l]=Max(f[i-1][0][l-1],f[i-1][1][l])+a[i]; 

初始化f[1][0][0]=0,f[1][1][1]=a[1];

然而交上去全wa
回头考虑这个问题我们可以发现一个很尴尬的事情:当上一行两个取的时候,我们并不知道它到底是「两列分别取」还是「两列一起取」。
因此,对于11的状态,我们应当拆成两个部分:
f[i][3][l]表示上一行的两列是分别取的。于是得到状态转移方程。
f[i][4][l]表示上一行的两列是合在一起取的。

f[i][0][l]=Max(Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l]);
f[i][1][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-1])+b[i];
f[i][2][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l-1])+a[i];
f[i][3][l]=Max(Max(Max(f[i-1][0][l-2],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-2])+a[i]+b[i];
f[i][4][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l-1])),f[i-1][4][l])+a[i]+b[i];

然而这样子还是全WA。
仔细观察一下我们的状态转移方程,我们发现存在一些l-2的状态,那么我们应该分两类讨论:l==1或l>=2.
这样大概就能通过了。

#include
#include
#include
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
int n,m,k,f[105][5][15],a[105],b[105];

void slv1(){
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    f[1][0][0]=0,f[1][1][1]=a[1];
    for(int i=1;i<=n;++i){
        f[i][0][0]=f[i][1][0]=0;
        for(int l=1;l<=k;++l){
            f[i][0][l]=Max(f[i-1][0][l],f[i-1][1][l]);
            f[i][1][l]=Max(f[i-1][0][l-1],f[i-1][1][l])+a[i]; 
        }
    }
    int ans=-0x3f3f3f3f;
    printf("%d",Max(f[n][0][k],f[n][1][k]));
    return;
}
void slv2(){
    for(int i=1;i<=n;++i){
        scanf("%d%d",&a[i],&b[i]);
    }
    f[0][0][0]=0;
    f[1][0][0]=0,f[1][1][1]=b[1],f[1][2][1]=a[1],f[1][3][2]=a[1]+b[1],f[1][4][1]=a[1]+b[1];
    for(int i=1;i<=n;++i){
        f[i][0][0]=f[i][1][0]=f[i][2][0]=f[i][3][0]=f[i][4][0]=0;
        for(int l=1;l<=k;++l){
                f[i][0][l]=Max(Max(Max(f[i-1][0][l],f[i-1][1][l]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l]);
                f[i][1][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-1])+b[i];
                f[i][2][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l],f[i-1][3][l])),f[i-1][4][l-1])+a[i];
                f[i][4][l]=Max(Max(Max(f[i-1][0][l-1],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l-1])),f[i-1][4][l])+a[i]+b[i];
                if(l<2){
                    continue;
                }
                f[i][3][l]=Max(Max(Max(f[i-1][0][l-2],f[i-1][1][l-1]),Max(f[i-1][2][l-1],f[i-1][3][l])),f[i-1][4][l-2])+a[i]+b[i];
        }
    }
    /*
    for(int i=1;i<=n;++i){
        for(int l=0;l<=k;++l){
            for(int j=0;j<5;++j){
                printf("%d ",f[i][j][l]);
            }
            puts("");
        }
        puts("");
    }*/
    int ans=-0x3f3f3f3f;
    for(int i=0;i<5;++i){
        ans=Max(ans,f[n][i][k]);
    }
    printf("%d",ans);
}
void init(){
	scanf("%d%d%d",&n,&m,&k);
	memset(f,-1,sizeof(f));
	if(m==1){
	    slv1();
    }
    if(m==2){
        slv2();
    }
}
int main(){
	init();
	return 0;
}

WordPress博客搭建笔记

为了搭建这个博客,遇到了很多麻烦。折腾了两天才上线。
几个主要的问题解决了,几个主要的问题没有解决。
其实目前来说最大的问题是域名以及域名备案的问题,不过那个可以放到其他地方讲。
我就讲讲搭建过程中遇到三个折磨我很久的坑点吧。
第一个坑点就在于wordpress.com和wordpress.org的区别。事实上两者几乎是在同一个开发组下的,不过需要注意的是,前者提供的是一个博客服务,类似于早年的领地网;而后者才是我们需要的博客框架。
后面两个坑点在于数据迁移。我遇到这两个坑点的主要原因是我一开始是在本地搭建博客的。
第二个坑点就是,数据迁移之后之前的所有链接都应该更改到迁移之后的地址。比较简易的解决方法是强行打开sql文件然后批量替换其中的地址。
第三个坑点在于环境问题带来的伪静态页面问题。在Xampp包下,服务器环境使用的是Apache,而在Lnmp包下,服务器环境使用的是Nginx。两者环境的不同带来的是配置的不同。Apache的伪静态页面是使用一个自动生成的.htacces文件,而Nginx服务器下使用的配置则位于/usr/local/nginx/conf/wordpress.conf,并且不会自动生成。
解决方案是,将

if (-f $request_filename/index.html){
rewrite (.*) $1/index.html break;
}
if (-f $request_filename/index.php){
rewrite (.*) $1/index.php;
}
if (!-f $request_filename){
rewrite (.*) /index.php;
}
location /子目录/ {
index index.html index.php;
if (-f $request_filename/index.html){
rewrite (.*) $1/index.html break;
}
if (-f $request_filename/index.php){
rewrite (.*) $1/index.php;
}
if (!-f $request_filename){
rewrite (.*) /子目录/index.php;
}
}

字段覆盖至wordpress.conf中,并在同一目录下的nginx.conf文件下约66行处

listen 80 default_server;
#listen [::]:80 default_server ipv6only=on;
server_name _;
index index.html index.htm index.php;
root /home/wwwroot/default;
#error_page 404 /404.html;
# Deny access to PHP files in specific directory
#location ~ /(wp-content|uploads|wp-includes|images)/.*\.php$ { deny all; }

一段中,

root /home/wwwroot/default;

一句后方添加

include wordpress.conf;

字段。
然后重启nginx,即可解决第三个问题。

总之,搭博客确实是一段艰辛又有趣的经历,也重新让我温习了一下生疏已久的「疯狂百度找资料」操作。

NOIP2018 福建赛区 初赛游记

初赛前状态不是很好。先是忘记带身份证,然后发现自己笔只带了一只、很方。
直到考前都比较紧张,然后对着窗外调整了一下呼吸,念了两句诗,稍微恢复了一些状态。
拿到卷子以后感觉不错。前面几道常识题有些不是很会做。鬼知道第一届NOI是什么时候举办的(不过我现在知道了,是1984)红球、篮球那道题其实和以前在知乎上看到过的一个问题:【生男孩、生女孩,生了一个男孩以后就不再生,那么这个社会男女比例是否会因此不均衡】很像。
事实上是没有改变的——接在一起即可。
然后关于长度为一的线段上任取两点的期望长度,比较合理的做法是硬上一个积分套积分,最后可以发现是一个二次函数从而得到三分之一的答案。另外一种做法就是,可以发现最大值不会超过二分之一、最小值不会小于四分之一,而符合条件的答案仅有三分之一,于是得解。
卡特兰数那一题,A选项没注意到是n+1个节点的二叉树排布,所以做错了。
还有就是那个数二进制1的个数的,x&=x-1,玄学位运算,吉如一tql。
姚期智是唯一一个华人图灵奖得主,是我记错了,尴尬。
阅读程序写结果,所有输入写在一行简直是个坑人设定。反正我一开始也被它搞糊涂了。据说第四题很多人错了,不过我好想检查出来了。
考了一个康托展开和逆康托展开。如果按照程序模拟复杂度是O(n!k)的,相信是算不出来的(笑)

程序补充,第一题的双向链表做法简直绝妙,反正对称写就没错了。
第二题是一道复杂背包问题。不,本来未必是背包问题,但是当做背包问题来求解简直是绝妙做法。佩服出题人。但是第三个空感受了很久还是写错了。

出来的话感觉状态还行,发挥出了屡次模拟以来的最高水准。但是仍然不一定能过初赛。所以只能祈祷不要初赛退役。