常州集训第7DAY

今天主要学了《二叉树》教材如下：树与二叉树
代码如下：

#include 
#include 
#include 
#include 
#include 

using namespace std;

const int maxn = 100005;
bool f[maxn],ans[maxn];
int a[maxn<em>2],sum[maxn</em>2],p[maxn],d[maxn],bak_p[maxn],bak_d[maxn],n;

class cmp{
    public:
    bool operator()(int i,int j){
        return sum[i] > sum[j];
    }
};

priority_queue<int,vector,cmp> q;

void work(){
    memset(f,0,sizeof(f));
    sum[0] = 0;
    for (int i=1; i<=n; ++i)
        a[i] = p[i] - d[i];
    for (int i=n+1; i<2<em>n; ++i)
        a[i] = a[i-n];
    for (int i=1; i<2</em>n; ++i)
        sum[i] = sum[i-1] + a[i];
    while (!q.empty()) q.pop();
    for (int i=1; i<n; ++i)
        q.push(i);
    for (int i=1; i<=n; ++i){
        q.push(i+n-1);
        while (!q.empty()){
            if (q.top() <i>= sum[i-1]) f[i] = true;
    }
}

int main()
{
    freopen("travel.in","r",stdin); freopen("travel.out","w",stdout);
    scanf("%d",&n);
    for (int i=1; i<=n; ++i)
        scanf("%d %d",&p[i],&d[i]);
    memcpy(bak_p,p,sizeof(p));
    memcpy(bak_d,d,sizeof(d));
    memset(ans,false,sizeof(ans));
    work();
    for (int i=1; i<=n; ++i){
        ans[i] |= f[i];
        p[i] = bak_p[n-i+1]; d[i] = bak_d[n-i+1];
    }
    work();
    for (int i=1; i<=n; ++i){
        ans[i] |= f[n-i+1];
        if (ans[i]) printf("TAK\n");
            else printf("NIE\n");
    }
    return 0;
}

很难，一点也听不懂。又要找舍友了。