2014
01-05

# Stock

After years of hard work Optiver has developed a mathematical model that allows them to predict wether or not a company will be succesful. This obviously gives them a great advantage on the stock market.

In the past, Optiver made a deal with a big company, which forces them to buy shares of the company according to a fixed schedule. Unfortunately, Optiver’s model has determined that the company will go bankrupt after exactly n days, after which their shares will become worthless.

Still, Optiver holds a large number of sell options that allows them to sell some of the shares before the company goes bankrupt. However, there is a limit on the number of shares Optiver can sell every day, and price Optiver receives for a share may vary from day to day. Therefore, it is not immediately clear when Optiver should sell their shares to maximize their profit, so they asked you to write a program to calculcate this.

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with an integer n (1 <= n <= 100 000): the number of days before the company goes bankrupt.

n lines with three integers xi (0 <= xi <= 100), pi (0 <= pi <= 100) and mi (0 <= mi <= 10 000 000): the number of shares Optiver receives on day i, the (selling) price per share on day i, and the maximum number of shares Optiver can sell on day i, respectively.

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with an integer n (1 <= n <= 100 000): the number of days before the company goes bankrupt.

n lines with three integers xi (0 <= xi <= 100), pi (0 <= pi <= 100) and mi (0 <= mi <= 10 000 000): the number of shares Optiver receives on day i, the (selling) price per share on day i, and the maximum number of shares Optiver can sell on day i, respectively.

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

76

#include <cstdio>
#include <cstdlib>
#include <cstring>
const int N = 30005;
int set[N];
int high[N]; //i元素上面（加上i）的元素个数
int low[N];  //i元素下面的元素个数
int findset(int x){
if(x == set[x])
return set[x];
int tm = set[x];
set[x] = findset(set[x]);
low[x] += low[tm];
return set[x];
}
void unionset(int x,int y){
int fx = findset(x);
int fy = findset(y);
if( fx == fy)
return ;
set[fx] = fy;
low[fx] += high[fy];
high[fy] += high[fx];
}
int main(){
int n;
while(scanf("%d",&n) != EOF){
for(int i = 1; i <= N; i++){
set[i] = i;
high[i] = 1;
}
memset(low,0,sizeof(low));
char op;
int x,y;
getchar();
for(int i =1 ; i <= n; i++){
scanf("%c",&op);
if(op == 'C'){
scanf("%d",&x);
findset(x);
printf("%d\n",low[x]);
}
else{
scanf("%d%d",&x,&y);
unionset(x,y);
}
getchar();
}
}
return 0;
}

1. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

2. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

3. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

4. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

5. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

6. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

7. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

8. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

9. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

10. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

11. 纵观历史,宇宙黑暗森林状态对各大宗教,特别是基督教,是一个沉重的打击。其实这种打击在危机纪元初就出现了,在得知三体文明的存在时,基督徒们立刻发现,在伊甸园里没有三体人的位置,在创世纪里上帝也从来没有提到过三体人。 教会和神学家开始了长达一个多世纪的

12. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

13. 我没看懂题目
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
第二个是7 0 6 -1 1 -6 7输出是14 7 7
不知道题目例子是怎么得出来的