ゼロから

作者: shad0w_walker(admin) 分类: 空分类 发布时间: 2016-10-26 00:36 ė 6 没有评论

 

11/1

补了一下午编译原理作业,大三上学期快过去一半了,专业课都没怎么听。

hdu 5942

杭州没做出来的题目,f(x)表示x所有素因子个数,g(x)=2^f(x),求sigma(g(i))

把g(n)看成1~n中gcd(x,y)=1且x*y=n的点对(x,y)数量,那最终答案就是求满足以下条件的(x,y)对数:gcd(x,y)=1,x*y<=n。假设x<=y,枚举x,对x的所有素因子进行容斥,求得对应的y的数量。最后得到的答案不知道为什么总是比样例少1,那就+1,蛤?

越来越菜了。

 

10/31

今天尝试用py打了场div2,反正不掉分,随便浪

Codeforces #378

A 水题

B 水题

C 从左到右贪心,每次找到和相同的一段,找该段的一个最大位置先向一边吃,再向另一边吃。比赛时没考虑到第一个串用完而第二个串没用完的情况,FST了

D 考虑了一下还是用C++写了,用一个map<pair<int, int>, pair<int, int> >,前一个pair保存长方体的一对长和宽,后面的保存高以及标号,瞎搞即可。比赛时我的做法是第一维离散化,第二维存入map,可是数组开小RE了,FST

我好菜啊

 

10/29

Bestcoder #89

1001 题意:在一个字符串中取下标为等比数列的三项为yrx的方法数

傻逼题然而AC率超低,因为比着比着出题人发现存在4、6、9这样的等比数列,于是强行加了个公比为整数的条件。记得要从后面往前考虑一遍。

1002 题意:给x,k,t,每次能将x减1~t中的数,或者在x整除k的情况下除以k,问将x变为1的最小步数。

f[i]为该项前t项以及f[i/k]中的最小值+1,用单调队列维护前t项中的最小值。

1003 题意:有以1为根的数,每个点都有个颜色黑/白,每次可以将i点子树中深度小于等于a[i]的节点颜色反转,问将所有点变白的期望。

从上往下可以求出如果每个点最多操作一次,需要操作哪些数全白,并且解法是唯一的。f[x]表示x个点正确的翻了,f[x]由f[x-1]和f[x+1]转移过来,一个是翻正确的点,一个是翻错误点,列出所有式子做高斯消元。

 

10/27

不得不吐槽学院好坑,今天开始每门课都要点名了,翘课刷题这么高尚的想法只好落空。好难,继续努力吧。

Codeforces #278 DIV1

A 直接在0-1000内枚举a1和d1的改变量,算出对应情况下h1的最小值,不断更新最小的答案。

一开始我是在0-200内枚举a1、d1、h1的,但是太年轻,WA了。

B 题意:给一个数列,要将这个数列分成若干段,每段长度至少为L,其中最小值和最大值的差不能大于S,求最少的段数。

首先求出以每个位置开始,能够取到子段的最右端位置,然后用dp[i]表示以i结尾的数列能分成的最大段数,对于位置i,能够到达的右端点j的dp[j]由dp[i-1]+1转移过来,并且dp数组每个位置只需要被赋值一次。注意判断无解的情况。

C 题意:构造一个1~n的排列,使得这个排列的n个前序积对n取模的结果是0~n-1的排列。

首先发现n只能放在最后,并且第n-1个积一定是n的倍数,所以猜测n为合数的情况是无解的,接着随便写了2、3、5、7的解,猜测总是可以构造一个模完n的数列是1,2,3,…,n-1,0,于是尝试构造,第i-1位模后的结果是i-1,设第i位是x,那么x*(i-1)%n=i,也就是x*(i-1)≡i(mod n),这是一个同余方程,用拓展欧几里得解出来就行。最后需要注意,不只是素数有解,1和4也有解,需要特判。

在网上发现了另一个思路,令第i位是i/(i-1)那么从第1位到第i位的积就是i,i/(i-1)表现为整数形式就是乘一个逆元,求逆元可以用快速幂和拓展欧几里得,用拓展欧几里得的话就和我上面一个做法一模一样了。

D 题意:给一个最大1e5*10的棋盘,每格有上左右中的一个方向,每次放一个物体在某个格子,它会随着方向不断走,要求它最后出棋盘的位置,如果出不去输出-1。多次询问,询问有两种,给出放的位置求答案或者是修改一个位置的方向。

据说是一个分块乱搞的线段树,Orz线段树水平还不够,下次补。贴个题解慢慢看:

分块很好写:

m很小,所以按照n分为sqrt(n)块,维护在每一块中能走到哪里,修改也只修改所在块。

注意修改的时候对于这一块的最上层要特判一下,因为上面那层也许还没更新。

因此每一个询问复杂度O(n/sqrt(n))=O(sqrt(n));

每一个修改复杂度O(m*sqrt(n))

线段树是按照n分段的,每个节点x维护tree[x][i]:表示从(r,i)能走到(l,tree[x][i]),l和r分别是左右子树,然后修改就是区间合并区间查询的问题了。

 

10/26

TopCoder SRM 699 DIV2

250 水题。暴力枚举最后的答案然后check一下

500 水题。显然这个操作得到的结果是递增的,二分一下

1000 题意:给两个数组a,b,对于有N个点的图,编号X和Y的节点有边的条件是存在一个i使得X|a[i]且Y|b[i],求S到T的最短路

用一个队列保存当前可取的b[i],通过b[i]到达点p,如果接来下取a[j],那么p一定是b[i]和a[j]的lcm的倍数,所以对于当前考虑的b[i],lcm(b[i], a[j])<=N就可以把b[j]放入队列,如果T%b[i]==0,那就到达终点了。一开始需要先将S出发的b处理出来。

1000(div1) 题意:给一个01方阵,每次可以选取一个子方阵将里面的数字反转,可以操作0或1或2次,求最后最多能有多少个1

暂时不会

 

10/25

 

Codeforces #337 DIV2

A 水题。答案在0-10中,枚举。

B 水题。扫一遍,保证当前的和前一个和为k。

C 水题。就是在按bds无限循环的字符串中截取一段,假设最大的字符有x个,那只有三种情况,x、x、x和x、x、x-1和x、x-1、x-1,枚举一下。

D 二分答案,从后往前找每门考试最后出现的一天作为这门课的考试的时间,然后从前往后check一下是否满足。

E 题意:有n个电脑和m个插座配对,每次操作可以使插座电压取一半向上取整,求最多配对的电脑数以及在最大配对下的最小操作数。

贪心,将电脑的值放入set然后对插座的值从小到大排序,依次不断折半到set中找配对,能配对就尽量配对,这样就找到最优解。

F 题意:有n个点m条边的联通无向图,要使每条边都变成单向边,对于新的有向边每个点的权值r是从它出发能够到达的点的数量,要使所有点的权值最小值最大,安排一种方案。

首先求出图中的所有桥,切断桥后图变成许多联通子图,最后所有点最小权值的最大值即ans必为这些子图里最大子图的点数(稍微理解一下),然后就以这个最大子图中任意一个点开始DFS,访问一条边时,如果这条边没有访问过,就以当前访问点向边的另一个点连边,图就构建出来了。但是这样做完之后我发现看我错了题意,我做的权值是能够访问到这个点的点数,还好机智的我接着把所有边都反一下方向,就好了。

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/523.html

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部