111qqz的小窝

老年咸鱼冲锋!

【施工完成】CSAPP data lab

CSAPP第二章的内容以前组成原理基本都学过…所以就简单翻了翻。

对应的lab是用位运算实现各种有的没的…

题目基本都很tricky…

除了用到一些常规的位运算性质,还用到了一些奇怪的条件:

  • ~0x7FFFFFFF = 0x7FFFFFFF + 1
  • 0xFFFFFFFF +1 =  0x00000000
  • 0 == ~0+1

唯一让我觉得比较有趣的是how many bits这道题

题目要求是给一个32-bit signed int,问最少用多少位能得到它的补码表示。

考虑正数,显然,高位的连续的多个0是不必要的,只需要一个符号位的0即可。

那么对于负数,高位的连续的多个1也是不必要的。 原因是,-2^k + 2^(k-1) =  -2^(k-1),也就是说,去掉两个连续的1中高位的那个,数值没有改变。

我们可以将正数和负数统一来看,都是找到最高位的0和1的交界。

这可以通过和相邻的位置求异或,找到最高位的1的方式来实现。

接下来就是如何找一个数的最高位的1的位置了。

方法是构造一个单调的函数f,假设最高位位置为a,那么f((a,32))=0,f([0,a])=1.

然后在函数f上二分。

全部问题的代码如下,思路写在注释里了。还有3个涉及浮点数的问题之后补。

 

补上三个涉及浮点数的问题…比较无聊,按照IEEE754操作即可.

 

 

 

codeforces round 530 div2

A,B,C:都很简单,不说了。

D:一棵树,给出树的结构,以及从树根到某个深度为偶数的节点的路径和,问能否构造一种所有节点点权和最小的树,输出最小点权和。

思路:

容易知道,如果想要点权和最小,那么尽可能让靠近树根的点承担更多的点权。

具体做法是,bfs,对于每个节点u,取其儿子中最小的S值求节点u的信息。

比赛的时候wa16…最后发现是答案要用long long存…因为单个路径和是<=1E9的。。多个加起来会超过int…  长时间不打连这种常见的坑都不敏感了啊。。。

 

codeforces hello 2019

好久没玩cf了,竟然还能涨分(虽然我用的小号Orz)

三题,D应该是数学+DP…数学实在是忘干净了。。。

前面三题大体还好,都是1A,不过因为没有提前配置环境。。耽误了一些时间。。。

A:给出一个扑克牌x,和另一个包含5个扑克牌的集合。问扑克牌x是否和扑克牌集合中至少一张扑克牌的花色或者数字相同。

不多说了。

B:一块钟表(只有一个指针),初始指向12点,需要拨动指针恰好n次(n<=15),每次可能顺时针,也可能逆时针,拨动的角度范围在[1,180],问是否有一种方案,使得拨动n次后,指针回到12点。

思路:观察下数据范围,n最大才15,最多也不过2^15的情况…既然如此,不如暴力。

枚举的话我记得有三种方法来着。。。但是已经不记得怎么写了。。所以用了最朴素的办法。。。

C: 给出n(n<=1E5)个括号序列,括号序列可能不合法,现在要从这n个括号序列中,组成尽可能多的有序二元组,使得有序二元组的括号序列合法,并且每个括号序列只能出现在一个有序二元组中,现在问最多能组成多少这样的有序二元组。

思路:我们先考虑一下怎样的两个括号序列组成的有序二元组才是合法的有序序列。容易想到的是,如果两个括号序列本身都是合法的,那么组合在一起也一定是合法的。进一步,对于本身不合法的括号序列,容易知道,其必须只有一种没有完成匹配的括号方向,且该括号方向的数量与相反括号方向的数量相同,才能完成匹配。

因此做法是,对于括号序列预处理,得到该括号序列的状态(本身匹配为0,正数代表'(‘的个数,负数代表’)’的个数,如果有两个方向同时存在,则直接舍弃掉,因为这种括号序列不可能组成合法的括号序列。预处理之后,用multiset搞一下。

代码写得比较乱…flag存的时候其实没必要存index…

D:初始一个数n(n<=1E15),k次操作,每次操作等概率将当前的数变为其因子中的一个。问k次操作之后,结果的期望是多少。

在@适牛的指导下,以及参考了官方题解。。写了出来。。

dp还是太弱了。。。。

比较重要的一点是,不需要考虑所有因子,只需要考虑质因子。

质因子的个数不超过50个(因为 2^50 > 1E15)

另外一个重要的是,对于每一个质因子的概率是积性函数,可以乘在一起。

因此问题变成了,对于一个质因子唯一的n,如何算所求的期望。

我们考虑dp[i][j]表示第i次操作后,质因子还剩j个的概率。

显然dp[0][tot]=1,其中 p^tot = n,p为某个质因子。

转移方程为:

dp[i][j] = sum(dp[i-1][jj]) (j=<jj<=tot)

然后最后结果的期望就是:sum(dp[k][j]*p^j) (0=<j<=tot)

还有一点,由于题目的输出要求,需要用到费马小定理求个逆元。。。

逆元相关的参考 acdreamer的博客。。。

 

 

 

 

2018 to do list

迫于最近的事情有点多,还是记录一下。 果然to do list什么的,还是要按照年份记录啊。

  • 了解linux strace命令
  • 速成go语言,并了解go于系统调用https://hackernoon.com/strace-in-60-lines-of-go-b4b76e3ecd64
  • 熟悉hustoj V2版本目前的代码
  • 看完<code in practice>
  • mit 6.828 lab1。。。感觉要咕
  • 看完<unix 系统系统手册>的20,21章信号部分, 为hustoj的重构补充基础知识.

codeforces 501 B. Obtaining the String

题目链接:http://codeforces.com/contest/1015/problem/B

题意: 给出字符串s和字符串t,问一个将s变为t的策略。 可以做的变换为,交换s中相邻的字符串,该操作最多不能超过4000次,字符串长度最大为50.

思路:

首先可以确定,当两个字符串的组成相同时(也就是有同样的字符组成,只是位置可能有所不同)一定有解。

考虑最坏情况,每个字符都要交换到最远的地方,总的操作数<50*50<4000,因此一定有解。

判断组成是否相同可以用multiset

 

 

codeforces edu #51 C. Vasya and Multisets (思维题)

题目链接

题意:有n个数,现在要分成2个集合,使得2个集合中,仅出现1次的数的个数相同,问是否有解,以及具体的分法。

思路:

一开始考虑出现多个的数的思路麻烦了,比如对于出现2次的某个数x,与其一个集合中分得一个,使得两个结合中,仅出现1次的数的个数各+1,还不如都放在同一个集合中,使得仅出现1次的数的个数不增加。

因此思路是这样的:

先考虑出现1次的数的个数,如果为偶数,那么均分,然后把其他出现多次的数全都放在第一个集合;

如果出现1次的数的个数为奇数,我们还是尽可能均分,然后不妨假设第一个集合中的只出现1次的数的个数比第二个集合中多1个。

我们现在需要让第二个集合中,仅出现一次的数增加一个。

什么样的数可以满足这个条件呢? 出现2次的数是不行的,因为这会使得两个集合中的数字各自+1

因此需要至少有一个出现3次或者以上的数。

具体见代码:

 

gRPC学习笔记

gRPC 是 google 最新发布的开源 RPC 框架, 声称是”一个高性能,开源,将移动和HTTP/2放在首位的通用的RPC框架.”. 技术栈非常的新, 基于HTTP/2, netty4.1, proto3, 拥有非常丰富而实用的特性, 堪称新一代RPC框架的典范.

//上面这段话是我抄的,其实我之前连RPC是什么都不知道,

关于RPC,如果你和我一样根本不知道是什么,请参考这里 

我对RPC的理解就是,一层封装,使得不在同一个机器上的程序A可以一个调用另一个程序B,而不需要考虑这两台机器,以及这两个程序使用的语言的不同。

而gRPC是诸多RPC框架中比较新,也比较好用的一个。

学习gRPC需要会使用protobuf3,关于protobuf,可以参考protobuf学习笔记

官方文档 还是要给出的,虽然我没怎么看就是了orz

gRPC的安装

参考这个,从源码编译安装

如果出现

参考

Compile fails on Ubuntu 14.04 ?  发现是protobuf的锅,需要手动编译一下:

 

gRPC的使用

grpc/examples下有一些例子,自己搞搞就会写基本的了。(已经硬着头皮用gRPC写了一个项目的通信部分了orz…其实还挺容易的。但是项目的代码没办法放上来。。。所以。。直接看examples的代码就好了。

8102年了,来更新一波vim配置

现在用的vim配置还是2015年7月的时候写的。

三年过去了,vim到了8.0,很多功能也有了更多选择。因此打算来更新一波vim配置。目前还在更新过程中。。。等差不多折腾完再来记录一些信息。

 

2014 Xi’An ACM-ICPC Regional Contest Problem G. The Problem to Slow Down You (回文自动机(模块化写法))

http://codeforces.com/gym/100548

题意:

切换面板:标签
标签
添加新标签

回文自动机、 给2个字符串,问2个字符串中,相等并且都是回文串的对数。

思路:

构建2个PAM.然后奇偶起点分别跑dfs即可。

PAM写成了模块化的形式orz

bzoj 2160: 拉拉队排练 (回文自动机+快速幂)

2160: 拉拉队排练

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 1938  Solved: 743
[Submit][Status][Discuss]

Description

艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点,好的拉拉队往往能帮助球队增加士气,赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道,帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束,在雨荨和校长的挑选下,n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起,和对手抗衡,为艾利斯顿篮球队加油助威。一个阳光明媚的早晨,雨荨带领拉拉队的队员们开始了排练。n个女生从左到右排成一行,每个人手中都举了一个写有26个小写字母中的某一个的牌子,在比赛的时候挥舞,为小伙子们呐喊、加油。雨荨发现,如果连续的一段女生,有奇数个,并且他们手中的牌子所写的字母,从左到右和从右到左读起来一样,那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体,并且按照女生的个数降序排序之后,前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大,雨荨只要你告诉她,答案除以19930726的余数是多少就行了。

Input

输入为标准输入。第一行为两个正整数n和K,代表的东西在题目描述中已经叙述。接下来一行为n个字符,代表从左到右女生拿的牌子上写的字母。

Output

输出为标准输出。输出一个整数,代表题目描述中所写的乘积除以19930726的余数,如果总的和谐小群体个数小于K,输出一个整数-1。

Sample Input

5 3
ababa

Sample Output

45
【样例说明】
和谐小群体女生所拿牌子上写的字母从左到右按照女生个数降序排序后为ababa, aba, aba, bab, a, a, a, b, b,前三个长度的乘积为。

HINT

总共20个测试点,数据范围满足: 

 

 

思路:

直接PAM.

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

需要注意的是,PAM构建之后,再按照逆拓扑序更新一遍得到的cnt才是实际的cnt

ural 1960. Palindromes and Super Abilities (回文自动机,统计本质不同的回文串个数)

http://acm.timus.ru/problem.aspx?space=1&num=1960

题意:

给一个字符串S,依次输出字符串S的所有前缀中,本质不同的回文串个数。

思路:

考虑构建PAM是一个增量算法…所以一边构建一边输出答案就好了。。。

某一时刻本质不同的回文串个数就是sz-1 (标号是从0..sz,一共sz+1个,减去2个根,所以是sz-1)

 

 

BZOJ 2565: 最长双回文串 (回文自动机)

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。
输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S

Output

一行一个整数,表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

12

HINT

样例说明

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分,且两者都是回文串。

对于100%的数据,2≤|S|≤10^5

2015.4.25新加数据一组

Source

 

 

思路:

我们考虑增量构建PAM的时候

构建到pos,当前的状态的len其实就是到以pos位置结尾的最长回文串的长度。

那么我们只需要正着做一遍,再倒着做一遍,然后枚举断点就行了。

时间复杂度O(n)

 

hdu 3948 | 2011 Multi-University Training Contest 11 The Number of Palindromes (回文自动机模板题)

http://acm.hdu.edu.cn/showproblem.php?pid=3948

题意:

给一个字符串,问本质不同的回文子串的个数。

思路:

考虑回文自动机。

我们知道,对于PAM上的一个节点,表示的就是一个本质不同的回文串。

UPDATE: 弃用了这种代码风格,新的写法见下面。

那么sz-2就是本质不同的回文子串个数了orz(减掉2是因为PAM有2个根,这2个根不表示回文串)

 

对于新的代码风格,节点数标号是从0到siz,其中标号为0和标号为1的是2个根。

因此答案是siz-1

新的代码风格:

 

 

UOJ #103. 【APIO2014】Palindromes (回文自动机模板题)

http://uoj.ac/problem/103

题意:

给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 s,求所有回文子串中的最大存在值。

思路:

回文自动机,也叫回文树,但其实并不是树2333,所以以后还是称为回文自动机,缩写为PAM

学会了(?)SAM之后再看PAM真是简单得一逼。

学习笔记之后补。

对于这道题,PAM中一个状态的cnt表示的该状态所表示的回文串出现的次数

len表示的是该状态所表示的回文串的长度

UPDATE:

下面的代码风格太丑了,打算弃用。

更新的代码风格见最后

 

 

 

codeforces 123D. String(后缀自动机)

题目链接:http://codeforces.com/problemset/problem/123/D

题意:

如果字符串y在字符串x中出现n次,那么F(x,y)=n*(n+1)/2

现在给一个字符串,求所有的F(s,x)的和,x为字符串的所有不相同的子串.

思路:

这道题可以考虑用后缀数组做,麻烦一点:codeforces-123D-解题报告(SA)

直接SAM

right[v]就是SAM上状态表示的所有字符串出现的次数。

那么每个状态的答案就是right[v](right[v]+1)/2(st[v].len-st[st[v].link].len)

累加即可。