A blog about programming

0%

发表于 更新于 分类于

PKUWC 2018

day 0

报到日（话说北大营连胸牌都不发，就发了张时间安排的纸？）

day 1

上午考了数学，题目涉及很多方面，从小学数学到大学数学，从数论到几何，题型分选择题（30道）和证明题（4道），感觉两个小时的时间不太够，证明题都来不及想出证法，只能随便写点过程（数学还是菜啊……）

下午是第一场上机考试，赛制是实时评测+公开排名，排名的第二关键字是提交次数……第一题是一道树形DP题，正解应该是线段树合并，但我没有想到，就先写了40分暴力，再试图进行（常数）优化，想至少得50分，然而交了十次左右也没调出来，排名下跌了不少……最后只能放弃这题去做第二题了。第二题是个计数问题，我一开始没什么思路，写了个10分暴力，然后就去优化第一题了，等再回来做第二题时已经只剩一个小时出头了，发现m=k的二十分部分分很好写，是个简单的DP，很快拿到，但之后时间已经不多，来不及想其他情况了，就只得了30分。第三题是个不可做题，是斗地主判断地主能否春天，全场无人得分……（手动@jiry_2）

最终得分40+30+0=70，因提交次数排在100名左右。

day 2

上午是第二场上机考试。第一题是个状压DP题，比较简单。我先写了暴力，再写正解，一开始只得了90分，后来卡了卡常就过了，只用了一个多小时。第二题是个概率题，先写了简单的10分暴力，再写了30分的状压DP暴力，然后就不会做了，此时考试才过去一个半小时。第三题是个算期望的题，我连最简单的情况和暴力都不会，也不敢乱搞（提交次数会影响排名），就几乎无所事事了三个小时……

最终得分100+30+0=130，排名70名左右。

下午是面试，一个小时一轮，共三轮，面试官总是问一些莫名其妙的无聊甚至是重复的问题，让我不禁怀疑这个面试有没有实际作用。

day 3

上午是闭幕式，北大的老师讲解了六道题目，大家还合了影。中午是签约，我拿了张有很多很多条件的约，基本就是废纸一张。所有人都拿了一张“约”结束了北大营。

WC2018

day 0

领了胸牌和材料（包括一本讲义，印有讲课课件），这个学校全校都有wifi诶！（虽然宿舍没有……）晚上是开幕式，节目乏善可陈，CCF主席杜子德也没来，唯一有用的消息是今年wc要考交互题。（啊，还有我加入了wc的同学群，这也是非常重要的）

day 1

上午是lzz讲课，讲了两道ioi2017题+一个叫competitive analysis的东西+中美oi的差异。讲到后面competitive analysis的时候感觉已经睡倒一片了……毕竟是纯英文的幻灯片+夹杂不少英文的讲课，我并不知道这个东西有什么用……直到最后谈中美oi差异时才有精神过来。

下午是myy讲课。他一个湖(hu)南(lan)人，咋就去mit了呢？他主要讲了如何在TC上出题，他的出题经历及他出的题。故事还是挺有趣的，myy炫耀了他出题卡掉tourist和Petr的经历，但题目听不太懂。据说他出的那轮SRM的rank1yanQval也在现场，感觉非常厉害。最后他谈了谈在mit但经历并介绍了一下mit。

晚上是试机。并没有试机题，所以很快就回宿舍了。这里的键盘回车键好短，用着很怪，差评。

day 2

上午是jiry讲去年PA的题。首先他接受了来自去过pkuwc的同学们的嘘声（并没有，只是在群里吐槽了而已）。前几道题目还能勉强听懂，后面就听不懂了。最后两道题是分布式计算的题目，我总算是知道啥是分布式计算了……

下午是钟知闲讲NP-Hard问题的做法，讲了一堆多项式算法和非确定性算法，基本跟不上节奏，回去看课件吧。（不过好像也没几个人在认真听课）

晚上是营员交流，lca讲了卷积定理。他真的认为在ppt上摆那么多数学公式我们真的看的懂吗……不过他在讲课中提到的子集卷积，在最后的考试中有用到。除此以外，zgg介绍了交互题的解答方式。

day 3

上午是wys讲傅立叶变换。他认为傅立叶变换需要从物理的角度来解释，还举了几个例子。不过我们并不知道这些例子与傅立叶变换的关系，只记得他总是在放的一首歌（的前两句），通过听歌识曲功能得知那首歌叫《水木道》，一首清华人自己写的歌，他还因此获得了“电音之王”的称号，从此大家提到wys就不总是想到缓存优化和卡常数了……然后他推导了fft，没多少人在听，但一讲到如何优化fft，大家都精神起来了……不过他并没有告诉我们要用缓存优化，而是一些正常的优化方式，看来他改过自新了。（btw，今年wc的第三题那道交互题就是他出的，他确实改过自新了）

下午分两场。一场是immortalCO讲他的圆方树和动态动态规划，我感觉他经常讲圆方树这个东西，不过这次他主要讲的是一般图上的圆方树和树上的DP，没怎么提仙人掌。另一场是dyh讲博弈，并不能听懂，只知道后来杜教发现自己推错了浪费不少时间，最后好多张幻灯片没来及讲（我觉得他不说他推错了也没几个人能发现的了……）还有就是他居然穿一件短袖讲课……身体真好。

晚上是第二次试机。这次有题目了，两道noi2017原题+一道弱智级的交互题。我随便写了写代码就回宿舍了，反正也没有地方评测。结果宿舍停电了，只好回机房又呆了一个小时才回去。

day 4

上午是yjq讲图论算法。一开始讲的mst的算法，tarjan、kosaraju算法基本没人不会，但后来讲的东西我估计就没有人会了。

下午是xmk讲lzz剩下的四道ioi题+计算几何。可能是因为这是最后一次讲课的缘故，大家发言都比较积极，尤其是对一道初中几何题的时候……

晚上有两组营员交流。一组是包括了大名鼎鼎的wxh（我并不知道他为什么这么出名……）的三个人讲一道集训队互测的字符串题，另一组是张宇博讲了平面图上的算法。都没有怎么听懂，而且由于第二天要考试的缘故，体育馆里也稀稀拉拉的，不少人回去准备考试了，没有来听课。回到宿舍发现密码条在枕头下面……

day 5

考试日。第一题的暴力看起来挺好写，数据类型为0的也很简单，一共能拿44分。难道wc变简单了？我立刻写了这44分的程序，然后去做第三题。第三题的暴力似乎又能拿40分？赶紧写赶紧写。链的情况随机一下也能过？赶紧写赶紧写。这样就有60分了。然后看第二题。没看懂什么意思。写个暴力试试。小样例调了半天才调出来，结果大样例WA了。难道是题目理解错了？改改改。结果大样例TLE了。我决定放弃第二题，随便交个暴力，因为时间也不多了。中午吃饭时听说第二题题面出错了，但只通知了集训队员。卧槽？还有这种事情？主办方后来想了个解决方案，造两套数据，原题面的和正确题面的，然后取最大值，但很多事情已经无法挽回了。这应该是oi史上最大的出题事故吧（SkyDec说这锅我不背，应该广播来背，但您老能别总出计数题吗，pkuwc没出够吗？）。

下午出分数推迟了很久，因为要重造数据。最终得分28+0+70=98.T1暴力少了16分，当时很不解，后来想想好像确实写错了。在wc这种高难度的比赛中，每一分都很重要，因为这种简单错误丢掉分数是很不应该的。T3比预期多得了几分，挺高兴。但好像其他人总分至少都在100+，感觉自己滚Cu了。讲题没怎么听懂，只是觉得T2如果题意清楚50分暴力应该很好写，加上那50分就有望Ag甚至Au了，感觉有些失望。

晚上是文艺演出，十分有趣。我第一次了解到原来qq聊天的内容也能做为弹幕投射到屏幕上。许多同学唱了歌，其中有两首是oi改编歌曲，还有dyh和wys合唱水木道（其实只有dyh一人在唱233），还观看了集训队的滚榜情况，在高兴之余想到没进侯选队的集训队员就要就此退役，还是有一点点点伤感吧，不过更多的是获得了继续学习oi的动力。

day 6

上午参观了湖南省博物馆。人很多，时间却只有一个小时，不太够，所以没怎么认真看。不过文物看起来也确实不咋样，也不是很多，那个马王堆的女尸看起来也没什么特别的地方。

下午是闭幕式。果然得了三等奖，大概是三等奖的中等水平。总之wc结束了，该回家了，这次wc收获还是挺大的。

发表于 分类于

感谢悠悠库提供的解决方法

今天运行yum突然错误提示No module named sqlite，之前一直都好好的，没办法，Google去，搜了很多，有的说nss模块没全更新，按照他们的处理并没有解决问题。

运行rpm安装升级软件包也出错误：Header V3 RSA/SHA1 Signature, key ID c105b9de: BAD

找了好久也没找到办法，但又实在不想重装系统。。。。

后来用命令history查看，在yum错误之前到底干了什么，突然发现： 

mv /usr/lib64/libsqlite3.so.0.8.6 /usr/lib64/libsqlite3.so.0.8.6.bak

只是为了解决wordpress后台页面出现502 Bad Gateway错误，在网上搜到的解决方法。

迅速改回来： 

mv /usr/lib64/libsqlite3.so.0.8.6.bak /usr/lib64/libsqlite3.so.0.8.6

再测试yum，OK了。。。网上那个解决wordpress问题的方法真坑，wordpress问题解决了，但系统yum不能用了，大家注意哦。

发表于 更新于 分类于

这题不愧“下金蛋的母鸡”，解法确实多种多样，下面我就来总结一下这题的各种算法。

莫队算法

  • 两种实现：
    1. 数组（“后缀和”），复杂度\(O(n\sqrt{n})\)
    2. BIT维护前缀和，复杂度\(O(n\sqrt{n}\log_2{n})\)
  • 是最容易想到的算法，且实现简单效率高

启发式合并（非平衡树）

  • 可用数组、map、vector等实现，复杂度\(O(n\log_2{n})\)
  • 代码最短，但实现不好可能会TLE

启发式合并（平衡树）

  • 用Treap即可
  • 复杂度\(O(n\log_2^2{n})\)
  • 容易想到，但实现复杂，且容易TLE

树分治

  • 复杂度从\(O(n\log_2{n})\)到\(O(n\log_2^2{n})\)不等，取决于实现
  • 用的人较少，在思维难度、代码难度和效率上均不占明显优势

其他

  • 大点预处理小点暴力形分块
  • 带合并的哈希表+LCA
  • 其他某些奇怪的离线处理树上询问的方式（奇怪排序、二分、LCA等等）
  • 以上算法均不如前三种算法（至少给定的程序中以上算法没有人AC）

注意事项及总结

  • 对于其中很多种方法，只要把BIT维护前缀和改为纯数组维护“后缀和”就可以去掉一个\(\log_2{n}\)，效率提升不少（虽然BIT常数很小）
  • 不要盲目运用平衡树等数据结构，往往存在着更为简单好写的做法

发表于 更新于 分类于

题目链接

此题有多种方法能够AC，其中最短的是用vector暴力： 

#include <bits/stdc++.h>
#define pos lower_bound(v.begin(),v.end(),x)
using namespace std;
int n,x;
vector<int> v;
int main() {
	cin>>n;
	while(n--){
		string s;
		cin>>s;
		if(s[0]=='s'){
			long long r=0;
			for(int i=2;i<v.size();i+=5)r+=v[i];
			cout<<r<<endl;
		}
		else{
			cin>>x;
			if(s[0]=='a')v.insert(pos,x);
			else v.erase(pos);
		}
	}
	return 0;
}

这也是Codeforces上最短的代码。

第二种方法是用线段树，每个节点保存模5余0～4的和以及区间长度（当然需要离散化），答案就是根结点模5余3的和。代码如下： 

#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define set0(x) memset((x),0,sizeof(x))
#define setINF(x) memset((x),63,sizeof(x))
using namespace std;
int n,cnt,sz[400005],rev[100005];
long long sgt[400005][5];
pair<string,int> q[100005];
map<int,int> disc;
void modify(int x,int l,int r,int t,int v){
	if(l==r){
		sgt[x][1]=v*rev[t];
		sz[x]=v;
		return;
	}
	int mid=(l+r)>>1;
	if(t<=mid)modify(x*2+1,l,mid,t,v);
	else modify(x*2+2,mid+1,r,t,v);
	sz[x]=sz[x*2+1]+sz[x*2+2];
	for(int i=0;i<5;i++){
		sgt[x][i]=sgt[x*2+1][i]+sgt[x*2+2][(i-sz[x*2+1]%5+5)%5];
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>q[i].first;
		if(q[i].first[0]!='s')cin>>q[i].second;
		disc[q[i].second];
	}
	for(auto &i:disc){
		i.second=++cnt;
		rev[cnt]=i.first;
	}
	for(int i=0;i<n;i++){
		if(q[i].first[0]=='a')modify(0,1,cnt,disc[q[i].second],1);
		else if(q[i].first[0]=='d')modify(0,1,cnt,disc[q[i].second],0);
		else cout<<sgt[0][3]<<endl;
	}
	return 0;
}

还可以用Treap来维护，这样就可以在线做，不用离散化了，但是代码难度也要大不少。旋转版本的Treap代码如下（这是我第一次写Treap）: 

#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define set0(x) memset((x),0,sizeof(x))
#define setINF(x) memset((x),63,sizeof(x))
using namespace std;
int n;
struct node{
	int v,r,sz;
	node* ch[2];
	long long sum[5];
	void maintain(){
		int pre=0,s=1;
		if(ch[0]!=NULL)s+=ch[0]->sz;
		pre=s;
		if(ch[1]!=NULL)s+=ch[1]->sz;
		sz=s;
		set0(sum);
		sum[(pre%5)]=v;
		for(int i=0;i<5;i++){
			if(ch[0]!=NULL)sum[i]+=ch[0]->sum[i];
			if(ch[1]!=NULL)sum[(pre+i)%5]+=ch[1]->sum[i];
		}
	}
	node(int x){
		this->v=x;
		this->r=rand();
		this->sz=1;
		this->ch[0]=this->ch[1]=NULL;
		set0(sum);
		this->sum[1]=x;
	}
};
node* rt;
void rotate(node* &x,int d){
	node* k=x->ch[d^1];
	x->ch[d^1]=k->ch[d];
	k->ch[d]=x;
	x->maintain();
	k->maintain();
	x=k;
}
void add(node* &x,int v){
	if(x==NULL){
		x=new node(v);
		return;
	}
	bool nxt=v>(x->v);
	add(x->ch[nxt],v);
	if((x->ch[nxt]->r)>(x->r))rotate(x,nxt^1);
	if(x!=NULL)x->maintain();
}
void del(node* &x,int v){
	if((x->v)==v){
		if(x->ch[0]!=NULL && x->ch[1]!=NULL){
			bool nxt=(x->ch[0]->r)>(x->ch[1]->r);
			rotate(x,nxt);
			del(x->ch[nxt],v);
			if(x!=NULL)x->maintain();
		}
		else if(x->ch[0]!=NULL)x=x->ch[0];
		else x=x->ch[1];
	}
	else{
		del(x->ch[v>(x->v)],v);
		if(x!=NULL)x->maintain();
	}
}
int main(){
	srand((unsigned)time(NULL));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	while(n--){
		string opt;
		cin>>opt;
		if(opt[0]=='s'){
			if(rt==NULL)cout<<"0\n";
			else cout<<(rt->sum[3])<<endl;
		}
		else{
			int x;
			cin>>x;
			if(opt[0]=='a')add(rt,x);
			else del(rt,x);
		}
	}
	return 0;
}

下面是非旋Treap的代码: 

#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1024000000,1024000000") 
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EPS 1e-10
#define set0(x) memset((x),0,sizeof(x))
#define setINF(x) memset((x),63,sizeof(x))
using namespace std;
int n;
struct node{
	int v,w,sz;
	node *l,*r;
	long long sum[5];
	void maintain(){
		int pre=0,s=1;
		if(l!=NULL)s+=l->sz;
		pre=s;
		if(r!=NULL)s+=r->sz;
		sz=s;
		set0(sum);
		sum[(pre%5)]=v;
		for(int i=0;i<5;i++){
			if(l!=NULL)sum[i]+=l->sum[i];
			if(r!=NULL)sum[(pre+i)%5]+=r->sum[i];
		}
	}	
	node(int x){
		this->v=x;
		this->w=rand();
		this->sz=1;
		this->l=this->r=NULL;
		set0(sum);
		this->sum[1]=x;
	}
};
node* rt;
void Split(node *x,node **l,node **r,int v){
	if(x==NULL)(*l)=(*r)=NULL;
	else if(x->v<v){
		*l=x;
		Split(x->r,&x->r,r,v);
	}
	else{
		*r=x;
		Split(x->l,l,&x->l,v);
	}
	if((*l)!=NULL)(*l)->maintain();
	if((*r)!=NULL)(*r)->maintain();  
}
void Merge(node **x,node *l,node *r){
	if(l==NULL || r==NULL){
		*x=(l==NULL)?r:l;
		return;
	}
	if(l->w<r->w){
		*x=l;
		Merge(&(*x)->r,(*x)->r,r);
	}
	else{
		*x=r;
		Merge(&(*x)->l,l,(*x)->l);
	}
	if((*x)!=NULL)(*x)->maintain();
}
void add(node **x,int v){
	node *l,*r,*m;
	Split(*x,&l,&r,v);
	Merge(&m,l,new node(v));
	Merge(x,m,r);
}
void del(node **x,int v){
	node *l,*m,*r,*tmp;
	Split(*x,&l,&tmp,v);
	Split(tmp,&m,&r,v+1);
	Merge(x,l,r);
}
int main(){
	srand((unsigned)time(NULL));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	while(n--){
		string opt;
		cin>>opt;
		if(opt[0]=='s'){
			if(rt==NULL)cout<<"0\n";
			else cout<<(rt->sum[3])<<endl;
		}
		else{
			int x;
			cin>>x;
			if(opt[0]=='a'){
				if(rt==NULL)rt=new node(x);
				else add(&rt,x);
			}
			else del(&rt,x);
		}
	}
	return 0;
}