D. Vessels

　

vessels

http://codeforces.com/problemset/problem/371/D 

题意：给一个多层的漏斗，当一层满后会流向下一层，最后一层满后漏出；

n(<=2e5)层数,a[]每层大小,m询问次数，op=1表示添加下标为p的层k升水，op=2表示询问p层的水有多少；

思路：并查集，将满了的建边，查询就会快点；

C++：

#include<iOStream>
#include<algorithm>
#include<set>
#include<vector>
#include<queue>
#include<cmath>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<ctime>
#include<map>
#include<stack>
#include<string>
using namespace std;

#define sfi(i) scanf("%d",&i)
#define sfl(i) scanf("%I64d",&i)
#define pri(i) printf("%d\n",i)
#define sff(i) scanf("%lf",&i)
#define ll long long
#define mem(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define eps 1e-6
#define PI acos(-1)
#define lowbit(x) ((x)&(-x))
#define fl() printf("flag\n")
ll gcd(ll a,ll b){while(b^=a^=b^=a%=b);return a;}
const ll mod=1e9+7;
const int maxn=2e6+100;

int pre[maxn];
int n;
struct A
{
    int cap;
    int val;
}a[maxn];

int Find(int x)
{
    int r=x;
    while(r!=pre[r])
    {
        r=pre[r];
    }

    int i=x;
    int j;
    while(pre[i]!=r)
    {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}

void join(int x,int y)
{
    int jx=Find(x);
    int jy=Find(y);

    if(jx!=jy)
    {
        if(jx>jy) pre[jy]=jx;
        else pre[jx]=jy;
    }
}

void add(int p,int x)
{
    int r=Find(p);
    while(r<=n&&x>0)
    {
        if(a[r].cap>=a[r].val+x)
        {
            a[r].val+=x;
            x=0;
        }
        else
        {
            x-=(a[r].cap-a[r].val);
            a[r].val=a[r].cap;
            join(r,r+1);
        }
        r=Find(r);
    }
}
int main()
{
    sfi(n);
    for(int i=1;i<maxn;i++) pre[i]=i;//n的话连接n+1不行，会tle
    for(int i=1;i<=n;i++)
    {
        A tmp;
        sfi(tmp.cap);
        tmp.val=0;
        a[i]=tmp;
    }
    int m;
    sfi(m);
    while(m--)
    {
        int op;
        sfi(op);
        if(op==1)
        {
            int p;
            int x;
            sfi(p);
            sfi(x);
            add(p,x);
        }
        else
        {
            int p;
            sfi(p);
            printf("%d\n",a[p].val);
        }
    }
    return 0;
}

Python：

虽然写了出来但tle8了，不知道怎么优化了，刚学不久；

类的类似c++数组创建搞炸我了，列表创建会是每个地址相同，每次改都全部改=-=；不定长输入也试了很多波；

总结：多尝试才是王道！

import math

maxn = 2000009
"""""
def gcd(x,y):
    if y: return gcd(y,x%y)
    return x

def P():
    isp=[True]*(maxn+10)
    pri=[]
    for i in range(2,maxn):
        if isp[i]:
            pri.APPend(i)
            for j in range(i*i,maxn,i):
                isp[j]=False
    return pri
"""""

class A:
    def __init__(self,x,y):
        self.cap=x
        self.val=y

cnt=1
a={}

pre=[0]*(maxn+20)##赋值0，不然无法从指定位置赋值
n=0

def Find(x):
    r=x
    while r!=pre[r]:
        r=pre[r]
    i=x
    j=0
    while pre[i]!=r:
        j=pre[i]
        pre[i]=r
        i=j
    return int(r)

def join(x,y):
    jx=Find(x)
    jy=Find(y)
    if jx!=jy:
        if jx>jy: pre[jy]=jx
        else: pre[jx]=jy

def add(p,x):
    r=Find(p)
    while r<=n and x>0:
        if a[r].cap>=a[r].val+x:
            a[r].val+=x
            x=0
        else :
            x-=(a[r].cap-a[r].val)
            a[r].val=a[r].cap
            join(r,r+1)
        r=Find(r)

n=int(input())

for i in range(1,n+9):
    pre[i]=i

k=input()
k=k.split()

for i in range(len(k)):
    a[cnt]=A(int(k[i]),0)
    cnt+=1

##for z in range(1,3):
##        print(z,a[z].cap,a[z].val,end=' ')
##        print()

m=int(input())
while m:
    m-=1
    op=input()
    op=op.split()
    for i in range(len(op)):
        op[i]=int(op[i])
    if op[0]==1:
        p=op[1]
        x=op[2]
        add(p,x)
    else:
        p=op[1]
        print(int(a[p].val))

相关阅读