题目描述

你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出k次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。

宝物一共有n种，系统每次抛出这n种宝物的概率都相同且相互独立。也就是说，即使前k-1 次系统都抛出宝物1（这种情况是有可能出现的，尽管概率非常小），第k次抛出各个宝物的概率依然均为1/n。

获取第 i 种宝物将得到Pi分，但并不是每种宝物都是可以随意获取的。第i种宝物有一个前提宝物集合Si。只有当Si中所有宝物都至少吃过一次，才能吃第i 种宝物（如果系统抛出了一个目前不能吃的宝物，相当于白白的损失了一次机会）。注意，Pi 可以是负数，但如果它是很多高分宝物的前提，损失短期利益而吃掉这个负分宝物将获得更大的长期利益。

假设你采取最优策略，平均情况你一共能在奖励关得到多少分值？

题目描述

知名美食家小 A被邀请至ATM 大酒店，为其品评菜肴。 ATM 酒店为小 A 准备了 N 道菜肴，酒店按照为菜肴预估的质量从高到低给予1到N的顺序编号，预估质量最高的菜肴编号为1。

由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 M 条形如”i 号菜肴’必须’先于 j 号菜肴制作“的限制，我们将这样的限制简写为。

现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小 A能尽量先吃到质量高的菜肴：

也就是说，

(1)在满足所有限制的前提下，1 号菜肴”尽量“优先制作；

(2)在满足所有限制，1号菜肴”尽量“优先制作的前提下，2号菜肴”尽量“优先制作；

经典的不加修改的询问第k小问题

同样是线段树 但是建树方法不同
将序列排序去重以后 节点值为每个数出现次数
查第k小就像平衡树那样查就行
利用前缀和进行相减
每加一个值只用添加修改的logn个节点
其他的指向上一棵树的同样节点就行
再次引用大佬的文章

阅读全文 »

题目描述

n个别墅以及一个主建筑楼，从每个别墅都有很多种不同方式走到主建筑楼，其中不同的定义是（每条边可以走多次，如果走边的顺序有一条不同即称两方式不同）。

询问最多的不同方式是多少，以及有多少个别墅有这么多方式，按照顺序输出别墅编号。

如果最多不同方式超过了36500那么都视作zawsze

输入输出格式

输入格式：

第1行，两个正整数，n和m（n<=100000,m<=1000000）

第2至m+1行，两个正整数u和v，代表存在一条u通向v的道路

是洛谷上面的那道模板题啦

合并的本身就是利用递归不断维护
感觉有了合并很多操作都很方便了
很好的一篇论文
下面的代码只有删除与合并的操作
一切尽在code中领会

阅读全文 »

题目描述

水果姐第二天心情也很不错，又来逛水果街。

突然，cgh又出现了。cgh施展了魔法，水果街变成了树结构（店与店之间只有一条唯一的路径）。

同样还是n家水果店，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。

cgh给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去。求最多可以赚多少钱。

水果姐向学过oi的你求助。

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

基本上到要用的时候手画一下矩阵就推得出

以第i行的方程式消第i元
如果模板元(a[i][i])为0，方程组存在多解
回元的时候从n到i将每元从s中减去

阅读全文 »

Hello,World!

1
2
3
4
5
6
7

#include<iostream>
using namespace std;
int doe,dogcdt;
int main(){
	printf("Hello,World!\n");
	return 0;
}