10.8 wtx模拟题题解

填坑

orz w_x_c_q

w_x_c_q的模拟赛(150pts，炸了)

money

题目背景：

王小呆又陷入自己的梦里。（活在梦里。。。）

题目描述：

王小呆是一个有梦想的小菜鸡，那就是赚好多好多的钱。现在机会来了，在他面前是一个迷宫，一共有N个点，M条路，王小呆可以在这些路上随便走，并且最重要的是，这些路上都有着数额不同的钱，王小呆每走过一条路，就可以得到这条路上所有的钱（我们认为王小呆特别贪婪，所以他用来装钱的袋子是无穷大的。。。），因为王小呆的梦很神奇，所以当一条路上的钱被他取走之后，这条路上又会出现一些新的钱，数量为原来钱的数量乘上这条路的“恢复系数”，向下取整。

比如，一条路上有4块钱，这条路的“恢复系数”为0.7，则先后四次经过这条路能得到的钱分别为：4,2,1,0。

现在王小呆在第S个点。因为王小呆还没有意识到自己活在梦里，所以他依旧十分兴奋，然而他的智商又不够，只能请聪明的你帮助他计算出他一共能够拿到多少钱。

注意：所有的边全部是单向边。不然岂不是沙比题？？？

输入输出格式：

输入格式：第一行，N和M。

第2……M+1行，每行四个数字，分别表示一条路的起点，终点，初始钱数，恢复系数。

第M+2行，一个整数S。

输出格式：一个数字，表示最多能拿到多少钱。

输入输出样例：

输入样例：

3 3
1 2 4 0.5
1 3 7 0.1
2 3 4 0.6
1

输出样例:

8

对于 0％的数据，保证是样例

对于 30％ 的数据 保证n<=10

对于另外 30％ 的数据 保证恢复系数为0（良心）

对于 100％ 的数据，保证N<=50000,M<=100000,0.1<=恢复系数<=0.8且仅有一位小数

保证 1<=S<=N不保证数据没有坑。std没有考虑自边和重边以及不连通，是过掉的...所以请大家当做无重边无自环做即可。

题解：

在同一强连通分量里所有点之间的边可以全部吃光。

所以我们Tarjan缩点成一个DAG，点权为强连通分量内所有边的吃光的权值，边权为原来的边的第一次权值，在DAG上拓扑排序DP即可。

Tarjan第一次默写，弹栈写错了。气死。。。

这里放一个tarjan弹栈的代码，以做备忘

if (dfn[x] == low[x])
{
    v[x] = false;
    cnt++;
    f[x] = cnt;
    while (s[top] != x)
    {
        f[s[top]] = cnt;
        v[s[top]] = false;
        top--;
    }
    top--;
}

dream

题目背景：

意识到自己活在梦里，是一件多么痛苦的事情。
活在梦里就像温水煮青蛙，慢慢地麻痹自己，慢慢地忘记自己的梦想和追求。王小呆意识到自己处在多么可怕的处境，所以他决心要逃出自己的梦，可是要逃出自己的梦，可没有那么简单。

题目描述：

为什么王小呆会困在自己的梦里，因为他被自己的畏惧所困住。（因为他困。。。）他在畏惧什么？他在畏惧一道难题，因为这道题太难了，但是这只是对于王小呆这个菜鸡，其他的大佬很快就切掉了这道题，就只有王小呆苦苦徘徊一直想不出正解，然后他就选择了麻痹自己，让自己进入了梦里。现在，王小呆逃出梦境的唯一方法就是解决这道难题，打破自己的恐惧，可是他的实力确实有限，于是来请教你，你能帮助他解决难题吗？

这道难题是求出：(a^xequiv1pmod n)的最小整数解

那么现在请你帮助王小呆完成任务，帮助他逃离梦境。

如果不存在方案使得 整除n，则输出“w_x_c_q is living in a dream”。

输入输出格式：

输入格式：第一行输入t，表示一共有t组数据。接下来t行，每行两个整数a和n

输出格式：共t行，一行一个数字表示方案数，若不存在符合条件的方案，输出“w_x_c_q is living in a dream”（不含双引号）。

输入输出样例：

输入样例

1
2 3

输出样例

2

所有数据保证 t=100

对于 0％的数据，保证是样例。

对于 10％ 的数据，保证a,n<=10

对于 30％ 的数据，保证a,n<=1000

对于 60％ 的数据，保证a,n<=10000

对于 100％ 的数据，保证a,n<=100000

另外，保证第一个测试点数据没有不合法情况。（即不会输出“w_x_c_q is living in a dream”）保证第二个测试点只有一组数据合法。保证第三个测试点所有数据均不合法。不保证数据没坑。

题解：

出题人说这是一道欧拉定理结论题。

欧拉定理：(a^{varphi(n)}equiv1pmod n)，当(gcd(a,n)=1)成立。

证明过程一搜一大把，不写了。

这道题就是枚举(varphi(n))的所有约数(x)，找最小的满足(a^xequiv1pmod n)的约数。

至于原因，出题人说无可奉告。。。

我写了个exbsgs的（第一次默写bsgs），但是根号向下取整，而且枚举得过少，直接挂掉70pts。最后数据出水了，那些暴力的都AC了。事实证明我的做法比std慢，但是比暴力快得不知道哪里去了。

考场上不要写您没写过的东西(除了您闲的没事)

hope

题目背景

人是要有梦想的，对吧。

现在呢，王小呆终于不再活在梦里，但是他还是一个有梦想的人，现在他的机房又要考试了，然而他又特别地想要考好。所以说，现在王小呆的梦想就是考好喽。知己知彼百战百胜，所以王小呆想要知道所有人的实力水平。我们约定：机房内的每一个人都有一个能力值记作(a_i) ，同时，每个人不可能总是在一个水平，总会有爆发的时候不是吗，所以每一个人还有一个激进值记作(b_i)，也就是说每个人的水平可以由(a_i)变为(a_i+b_i)。现在王小呆把所有人的数据都找来了，但是他却犯难了，笨笨的王小呆哪里有脑子去从这些数据中找出他想知道的东西，所以他只好又厚着脸皮来找你帮忙了，那么现在你能帮助她再一次解决问题吗？

题目描述

现在王小呆已经准备好了每个人的数据分别为(a_i)和(b_i)。那么我们定义：
如果有两个人A和B，那么若出现了A的普通水平低于B的普通水平，但是A的高水平高于B的普通水平，然而B的高水平又高于A的高水平，则对答案产生一的贡献。

也就是说，现在你要求的是有多少对人 满足：(a_A<a_B<a_A+b_A<a_B+b_B)另外，我们认为在任何情况下，都不会出现两个人水平相同。

输入输出格式：

输入格式：第一行一个整数n，表示一共有n个人

接下来n行每行两个整数(a_i,b_i),意义同题。

输出格式：一行一个整数ans，表示一共有ans对符合条件的人。

输入输出样例：

输入样例：

3
1 2
2 2
5 1

输出样例：

1

样例解释，第一个人和第二个人是符合题目中的要求的，所以答案是1。

对于 30%的数据，保证n<=100

对于60%的数据，保证n<=1000

对于100%的数据，保证n<=30000

题解：树状数组，设(x_i=a_i)，(y_i=a_i+b_i)，那么要求的就是所有满足(x_i<x_j<y_i<y_j)的方案数。我们假设j的坐标确定，那么i的坐标满足：(x_i<x_j,x_j<y_i<y_j)，先按这是一个区域。我们把坐标按照x排序，y用树状数组维护即可。

这其实是一道二维偏序的题。二维偏序一般都是第一维排序，第二维树状数组即可。

//树状数组就是一个不让你写线段树的东西