标签 - 好题

矩阵乘法 期望与概率 好题    2016-10-29 17:13:00    244    1    2

10月3日,在杭州市西湖景区,一只小松鼠不停地接受一道道食物,花生、玉米、饼干,可谓来者不拒,憨态可掬的模样吸引了众多围观者…

数论 好题    2016-10-29 16:42:18    289    -2    0

3884: 上帝与集合的正确用法

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 1214  Solved: 558
[Submit][Status][Discuss]

Description

 
根据一些书上的记载,上帝的一次失败的创世经历是这样的:
第一天, 上帝创造了一个世界的基本元素,称做“元”。
第二天, 上帝创造了一个新的元素,称作“α”。“α”被定义为“元”构成的集合。容易发现,一共有两种不同的“α”。
第三天, 上帝又创造了一个新的元素,称作“β”。“β”被定义为“α”构成的集合。容易发现,一共有四种不同的“β”。
第四天, 上帝创造了新的元素“γ”,“γ”被定义为“β”的集合。显然,一共会有16种不同的“γ”。
如果按照这样下去,上帝创造的第四种元素将会有65536种,第五种元素将会有2^65536种。这将会是一个天文数字。
然而,上帝并没有预料到元素种类数的增长是如此的迅速。他想要让世界的元素丰富起来,因此,日复一日,年复一年,他重复地创造着新的元素……
然而不久,当上帝创造出最后一种元素“θ”时,他发现这世界的元素实在是太多了,以致于世界的容量不足,无法承受。因此在这一天,上帝毁灭了世界。
至今,上帝仍记得那次失败的创世经历,现在他想问问你,他最后一次创造的元素“θ”一共有多少种?
上帝觉得这个数字可能过于巨大而无法表示出来,因此你只需要回答这个数对p取模后的值即可。
你可以认为上帝从“α”到“θ”一共创造了10^9次元素,或10^18次,或者干脆∞次。
 
一句话题意:

 

 

Input

 
接下来T行,每行一个正整数p,代表你需要取模的值

 

Output

T行,每行一个正整数,为答案对p取模后的值

 

Sample Input

3
2
3
6

Sample Output

0
1
4

HINT

 

对于100%的数据,T<=1000,p<=10^7
 

Source

By PoPoQQQ

 

Solution

设 p = 2^k * t

原式 = 2^k * (2^(原式-k)) % t

        = 2^k * (2^((原式-k) % φ(t))) % t

这样递归下去,最终φ(t)=1,代回去即可

时间复杂度O(T log P sqrt(P))

 

Source code

/*{{{*/

//#define MULTI_DATA
//#pragma GCC optimi
树链剖分 zkw线段树 图论 好题 最小生成树    2016-10-25 21:51:44    143    0    0

Problem

雪之国度有N座城市,依次编号为1到N,又有M条道路连接了其中的城市,每一条道路都连接了不同的2个城市,任何两座不同的城市之间可能不止一条道路。雪之女王赋予了每一座城市不同的能量,其中第i座城市被赋予的能量为Wi。
如果城市u和v之间有一条道路,那么只要此刻雪之女王的能量不小于|Wu-Wv|,这条道路就是安全的。如果城市u和v之间存在两条没有重复道路的安全路径(其中每一段道路都是安全的),则认为这两座城市之间有着良好的贸易关系。
最近,雪之女王因为情感问题,她的能量产生巨大的波动。为了维持雪之国度的经济贸易,她希望你能帮忙对Q对城市进行调查。对于第j对城市uj和vj,她希望知道在保证这两座城市之间有着良好贸易关系的前提之下,自己最少需要保持多少的能量。
N≤100,000 Q≤500,000

Solution

因为最小生成树是最小瓶颈生成树,我们建出最小生成树,然后就只要再有一条路径了
在最开始时,将所有边权设为+∞,表示不联通
每加入一条边(u,v,w),就把路径(u,v)上的边权与w取min
询问的答案就是(qu,qv)上边权的最大值

可以用树链剖分维护
比较卡常,线段树用zkw+lc即可

Source code

  1. /*{{{*/
  2. #include <bits/stdc++.h>
  3. #ifdef __linux__
  4. #define getchar getchar_unlocked
  5. #define putchar putchar_unlocked
  6. #endif
  7. using namespace std;
  8. typedef long long ll;
  9. typedef pair<int, int> pii;
  10. string program_name = __FILE__;
  11. string iput = program_name.substr(0, program_name.length() - 4) + ".in";
  12. string oput = program_name.substr(0, program_name.length() - 4) + ".out";
  13. template <class T> inline bool
分治 MST 好题    2016-10-14 21:35:16    229    -1    0

2001: [Hnoi2010]City 城市建设

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 1094  Solved: 536
[Submit][Status][Discuss]

Description

PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和, Louis决定求助于你来完成这个任务。

Input

文件第一行包含三个整数N,M,Q,分别表示城市的数目,可以修建的道路个数,及收到的消息个数。 接下来M行,第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi,Yi≤n, 0≤Zi≤50000000),表示在城市Xi与城市Yi之间修建道路的代价为Zi。接下来Q行,每行包含两个数k,d,表示输入的第k个道路的修建代价修改为d(即将Zk修改为d)。

Output

输出包含Q行,第i行输出得知前i条消息后使城市连通的最小花费总和。

Sample Input

5 5 3
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3

Sample Output

14
10
9

HINT

 

【数据规模】 对于20%的数据, n≤1000,m≤6000,Q≤6000。 有20%的数据,n≤1000,m≤50000,Q≤8000,修改后的代价不会比之前的代价低。 对于100%的数据, n≤20000,m≤50000,Q≤50000。

 

Solution

题意就是维护动态最小生成树。。

考虑分治,但是看起来并不满足分治的条件

我们想办法缩小点集和边集的大小。

对于q个询问里修改的边,我们设这个边集为Q,全集为E,那么对于E-Q中的边,做一遍MST,MST中的边集设为G,那么对于E-Q-G中的边,不论询问怎么改变,这些边都不会在MST中,所以我们可以删除这些边。

这样边集大小变成n - 1 + q,  点集大小仍为n

之后将Q中的边的边权都赋值为-INF,这时做一遍MST,如果E-Q的边在MST中,这时代表就算修改的边

2/2