## [ZJOI2015]诸神眷顾的幻想乡

7 3
0 2 1 2 1 0 0
1 2
3 4
3 5
4 6
5 7
2 5

30

 #include<bits/stdc++.h> using namespace std; int v[100005],head[100005],tot,d[100005]; struct node{ node *fa,*go[11];int max; }*root,pool[4000005],*cnt; struct edge{ int go,next; }e[100005]; void add(int x,int y){e[++tot]=(edge){y,head[x]};head[x]=tot; e[++tot]=(edge){x,head[y]};head[y]=tot;} void initsam(){cnt = root = pool + 1;} node* newnode(int _val){(++cnt)->max=_val;return cnt;} ostream& operator,(ostream &os,int a){} node* extend(node *p,int c){ node* np = newnode(p->max+1); while(p&&!p->go[c])p->go[c]=np,p=p->fa; if(!p)np->fa=root; else{ node* q = p->go[c]; if(p->max+1==q->max)np->fa=q; else{ node * nq = newnode(p->max+1); memcpy(nq->go,q->go,sizeof q->go); nq->fa=q->fa; np->fa=q->fa=nq; while(p&& p->go[c]==q)p->go[c]=nq,p=p->fa; } } return np; } long long solve(){ long long ans=0; for(node *i=root+1;i<=cnt;i++) ans+=i->max-i->fa->max; return ans; } void dfs(int x,int fa,node* p){ node *t = extend(p,v[x]); for(int i=head[x];i;i=e[i].next) if(e[i].go!=fa) dfs(e[i].go,x,t); } int n,c,x,y; int main(){ initsam(); scanf("%d%d",&n,&c); for(int i=1;i<=n;i++)scanf("%d",&v[i]); for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); add(x,y); d[x]++,d[y]++; } for(int i=1;i<=n;i++) if(d[i]==1)dfs(i,0,pool+1); printf("%lld",solve()); } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 #include<bits/stdc++.h>using namespace std;int v[100005],head[100005],tot,d[100005];struct node{    node *fa,*go[11];int max;}*root,pool[4000005],*cnt;struct edge{    int go,next;}e[100005];void add(int x,int y){e[++tot]=(edge){y,head[x]};head[x]=tot;e[++tot]=(edge){x,head[y]};head[y]=tot;}void initsam(){cnt = root = pool + 1;}node* newnode(int _val){(++cnt)->max=_val;return cnt;}ostream& operator,(ostream &os,int a){}node* extend(node *p,int c){    node* np = newnode(p->max+1);    while(p&&!p->go[c])p->go[c]=np,p=p->fa;    if(!p)np->fa=root;    else{        node* q = p->go[c];        if(p->max+1==q->max)np->fa=q;        else{            node * nq = newnode(p->max+1);            memcpy(nq->go,q->go,sizeof q->go);            nq->fa=q->fa;            np->fa=q->fa=nq;            while(p&& p->go[c]==q)p->go[c]=nq,p=p->fa;        }    }    return np;}long long solve(){    long long ans=0;    for(node *i=root+1;i<=cnt;i++)        ans+=i->max-i->fa->max;    return ans;}void dfs(int x,int fa,node* p){    node *t = extend(p,v[x]);    for(int i=head[x];i;i=e[i].next)        if(e[i].go!=fa)            dfs(e[i].go,x,t);}int n,c,x,y;int main(){    initsam();    scanf("%d%d",&n,&c);    for(int i=1;i<=n;i++)scanf("%d",&v[i]);    for(int i=1;i<n;i++){        scanf("%d%d",&x,&y);        add(x,y);        d[x]++,d[y]++;    }    for(int i=1;i<=n;i++)        if(d[i]==1)dfs(i,0,pool+1);    printf("%lld",solve());} 

 

## 交易一中集训Day[7]

WA的一声就哭了.jpg
TLE的一声就哭了.jpg
T1猜了两个小时的结论。。。。

T3二分乱搞。。。。成功TLE。。。。。
zrO ljt大佬要不是2SAT打炸了就随手A题了啊 Orz

WP自带Markdown居然会把代码块里的大于小于号转义。。。。

## HDU 4609 3-idiots

Problem Description
King OMeGa catched three men who had been streaking in the street. Looking as idiots though, the three men insisted that it was a kind of performance art, and begged the king to free them. Out of hatred to the real idiots, the king wanted to check if they were lying. The three men were sent to the king's forest, and each of them was asked to pick a branch one after another. If the three branches they bring back can form a triangle, their math ability would save them. Otherwise, they would be sent into jail.
However, the three men were exactly idiots, and what they would do is only to pick the branches randomly. Certainly, they couldn't pick the same branch - but the one with the same length as another is available. Given the lengths of all branches in the forest, determine the probability that they would be saved.
Input
An integer T(T≤100) will exist in the first line of input, indicating the number of test cases.
Each test case begins with the number of branches N(3≤N≤105).
The following line contains N integers a_i (1≤a_i≤105), which denotes the length of each branch, respectively.
Output
Output the probability that their branches can form a triangle, in accuracy of 7 decimal places.
Sample Input
2
4
1 3 3 4
4
2 3 3 4
Sample Output
0.5000000
1.0000000
Source
2013 Multi-University Training Contest 1
Recommend
liuyiding

R数组的计算不能放到外面。。。。。

 

 #include <bits/stdc++.h> using namespace std; typedef complex<double> cp; #define maxn 262145 #define F0(i, n) for (int i = 0; i < (n); i++) #define F1(i, n) for (int i = 1; i <= (n); i++) cp a[maxn * 4]; int n, m, L, R[maxn * 4]; const double pi = acos(-1); void fft(cp a[], int flag){ F0(i, n) if (i < R[i]) swap(a[i], a[R[i]]); for (int i = 1; i < n; i <<= 1) { cp wn(cos(pi / i), sin(flag * pi / i)), x, y; for (int j = 0; j < n; j += i << 1) { cp w(1, 0); for (int k = 0; k < i; k++, w *= wn) { x = a[j + k]; y = w * a[j + i + k]; a[j + k] = x + y; a[j + i + k] = x - y; } } } } int T, nd; int d[maxn * 4], e[maxn * 4]; long long sum[maxn * 4]; long long p1, p2; int main(){ scanf("%d", &T); while (T--) { int maxns = 0; F0(i, maxn) a[i] = 0; L = 0; p1 = 0; scanf("%d", &nd); memset(sum, 0, sizeof sum); F0(i, nd) scanf("%d", &d[i]), a[d[i]] += 1, sum[d[i]]++, maxns = max(maxns, d[i]); m = maxns * 2 + 1; for (n = 1; n <= m; n <<= 1) L++; F0(i, n) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1)); fft(a, 1); F0(i, n) a[i] *= a[i]; fft(a, -1); F0(i, n) e[i] = int(a[i].real() / n + 0.5); F0(i, n) e[i << 1] -= sum[i]; F0(i, n) e[i] >>= 1; F0(i, n) sum[i + 1] += sum[i]; F0(i, n) p1 += e[i] * (sum[n] - sum[i - 1]); p2 = nd * (nd - 1ll) * (nd - 2ll) / 6ll; printf("%.7f\n", 1 - p1 * 1.0 / p2); } } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 #include <bits/stdc++.h>using namespace std;typedef complex<double> cp;#define maxn 262145#define F0(i, n) for (int i = 0; i < (n); i++)#define F1(i, n) for (int i = 1; i <= (n); i++)cp a[maxn * 4];int n, m, L, R[maxn * 4];const double pi = acos(-1);void fft(cp a[], int flag){    F0(i, n) if (i < R[i]) swap(a[i], a[R[i]]);    for (int i = 1; i < n; i <<= 1) {        cp wn(cos(pi / i), sin(flag * pi / i)), x, y;        for (int j = 0; j < n; j += i << 1) {            cp w(1, 0);            for (int k = 0; k < i; k++, w *= wn) {                x = a[j + k];                y = w * a[j + i + k];                a[j + k] = x + y;                a[j + i + k] = x - y;            }        }    }} int T, nd;int d[maxn * 4], e[maxn * 4];long long sum[maxn * 4];long long p1, p2;int main(){    scanf("%d", &T);    while (T--) {        int maxns = 0;        F0(i, maxn) a[i] = 0; L = 0; p1 = 0;        scanf("%d", &nd); memset(sum, 0, sizeof sum);        F0(i, nd) scanf("%d", &d[i]), a[d[i]] += 1, sum[d[i]]++, maxns = max(maxns, d[i]);        m = maxns * 2 + 1;        for (n = 1; n <= m; n <<= 1) L++;        F0(i, n) R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));        fft(a, 1);        F0(i, n) a[i] *= a[i];        fft(a, -1);        F0(i, n) e[i] = int(a[i].real() / n + 0.5);        F0(i, n) e[i << 1] -= sum[i];        F0(i, n) e[i] >>= 1;        F0(i, n) sum[i + 1] += sum[i];        F0(i, n) p1 += e[i] * (sum[n] - sum[i - 1]);        p2 = nd * (nd - 1ll) * (nd - 2ll) / 6ll;        printf("%.7f\n", 1 - p1 * 1.0 / p2);    }} 

 

## 交易一中集训Day[6]

PJ这次快压事故也真是。。。。

7z大法好。。。。

Rank1大佬x1 金牌爷x1 队爷x1 均表示不会做。。。

## 交易一中集训Day[5]

• 开始

还不错哟

• 这是啥

• 这又是啥
• 数论？
• DP？
• 数据结构？

Wifei密码都是31415926

## 交易一中集训Day[4]

$n \leq 200000 , 0 \leq a_i \leq 10^9$

4
1 2 3 12

3.0000

T2奥妙重重的排列数 T3奥妙重重的组合数
xjb打表找规律。。。。T2在OEIS上查到了递推式。。。。
T3根本找不到。。。。。

xjk光速过ppt看得我一脸懵逼。。。。不现推一下感觉非常懵逼。。。。

FFT通过恰当地选择x降低求值和插值的复杂度

• (消去引理)对任意整数$n \geq 0,k \geq 0,d \geq 0$，有
$$\omega^{dk}_{dn}=(\mathrm{e}^{2\pi\mathrm{i}/dn})^{dk}=(\mathrm{e}^{2\pi\mathrm{i}/n})^{k}=\omega^{k}_{n}$$

• (折半引理)如果$n>0$且$n$为偶数，那么$n$个$n$次单位根的平方的集合就是$n/2$个$n/2$次单位根的集合，且每个元素恰好出现两次。

• (求和引理)对于任意整数$n\geq1$和不能被$n$整除的整数$k$，有$$\sum_{j=0}^{n-1}(\omega_n^k)^j=0$$

$$y_k=A(\omega_n^k)=\sum_{j=0}^{n-1}a_j\omega_n^kj$$

$$a_j=\frac{1}{n}\sum_{j=0}^{n-1}y_k\omega_n^{-kj}$$

cpp 

 #include<bits/stdc++.h> using namespace std; typedef complex<double> cp; #define maxn 262145 #define F0(i,n) for(int i=0;i<(n);i++) #define F1(i,n) for(int i=1;i<=(n);i++) cp a[maxn],b[maxn]; int n,m,L,R[maxn],ans[maxn]; const double pi = acos(-1); void fft(cp a[],int flag){ F0(i,n)if(i<R[i])swap(a[i],a[R[i]]); for(int i=1;i<n;i<<=1){ cp wn(cos(pi/i),sin(flag*pi/i)),x,y; for(int j=0;j<n;j+=i<<1){ cp w(1,0); for(int k=0;k<i;k++,w*=wn){ x=a[j+k]; y=w*a[j+i+k]; a[j+k]=x+y; a[j+i+k]=x-y; } } } } int main(){ ios::sync_with_stdio(0); cin>>n>>m; F0(i,n+1)cin>>a[i]; F0(i,m+1)cin>>b[i]; m+=n; for(n=1;n<=m;n<<=1)L++; F0(i,n)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); fft(a,1);fft(b,1); F0(i,n+1)a[i]*=b[i]; fft(a,-1); F0(i,m+1)cout<<int(a[i].real()/n+0.5)<<' '; } 12345678910111213141516171819202122232425262728293031323334353637 #include<bits/stdc++.h>using namespace std;typedef complex<double> cp;#define maxn 262145#define F0(i,n) for(int i=0;i<(n);i++)#define F1(i,n) for(int i=1;i<=(n);i++)cp a[maxn],b[maxn];int n,m,L,R[maxn],ans[maxn];const double pi = acos(-1);void fft(cp a[],int flag){    F0(i,n)if(i<R[i])swap(a[i],a[R[i]]);    for(int i=1;i<n;i<<=1){        cp wn(cos(pi/i),sin(flag*pi/i)),x,y;        for(int j=0;j<n;j+=i<<1){            cp w(1,0);            for(int k=0;k<i;k++,w*=wn){                x=a[j+k];                y=w*a[j+i+k];                a[j+k]=x+y;                a[j+i+k]=x-y;            }        }    }}int main(){    ios::sync_with_stdio(0);    cin>>n>>m;    F0(i,n+1)cin>>a[i];    F0(i,m+1)cin>>b[i];    m+=n;    for(n=1;n<=m;n<<=1)L++;    F0(i,n)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));    fft(a,1);fft(b,1);    F0(i,n+1)a[i]*=b[i];    fft(a,-1);    F0(i,m+1)cout<<int(a[i].real()/n+0.5)<<' ';} 

 

## 交易一中集训Day[3]

 

 Do{ 写题(); Debug(); Submit() Debug(); Submit(); Debug(); Submit(); Debug(); Submit(); Debug(); Submit(); Debug(); Submit(); }While(1); 123456789101112131415 Do{    写题();    Debug();    Submit()    Debug();    Submit();    Debug();    Submit();    Debug();    Submit();    Debug();    Submit();    Debug();    Submit();}While(1); 

  WA的一声就哭了
TLE的一声就哭了
RE的一声就哭了

Description

Input 第一行包含一个正整数n(1<=n<=5000)，表示强盗的个数。

Output

Sample Input
4
1 4 40
2 4 10
2 3 30
1 3 20
Sample Output
90
Source
By Claris

 

 C++ #include <bits/stdc++.h> using namespace std; #define N 5002 #define maxn N * 10 #define maxm N * 100 #define ey e[i].go #define INF 0x7f7f7f7f #define inf INF bitset<maxn> v; int d[maxn], from[maxn]; queue<int> q; int s, t, mincost; struct edge { int from, go, next, v, c; } e[maxm]; int head[maxn], tot = 1; ostream& operator,(ostream& os,int x){os<<setw(12)<<x;return os;} void add(int x,int y,int v,int c) { //cerr,x,y,v,c;cerr<<endl; e[++tot]=(edge){x,y,head[x],v,c};head[x]=tot; e[++tot]=(edge){y,x,head[y],0,-c};head[y]=tot; } bool spfa() { memset(d,0x7f,sizeof(d)); //for (int i=s;i<=t;i++){v[i]=0;d[i]=inf;} q.push(s);d[s]=0;v[s]=1; while(!q.empty()) { int x=q.front();q.pop();v[x]=0; for (int i=head[x],y;i;i=e[i].next) if(e[i].v&&d[x]+e[i].c<d[y=e[i].go]) { d[y]=d[x]+e[i].c;from[y]=i; if(!v[y]){v[y]=1;q.push(y);} } } return d[t]!=inf; } void mcf() { mincost=0; while(spfa()) { int tmp=inf; for(int i=from[t];i;i=from[e[i].from]) tmp=min(tmp,e[i].v); mincost+=d[t]*tmp; for(int i=from[t];i;i=from[e[i].from]){e[i].v-=tmp;e[i^1].v+=tmp;} } } #define mid ((l + r) >> 1) #define tp(x) ((x) + n + 2) int a[N], b[N], c[N]; int n; void build(int l, int r, int i){ if (l == r) { add(tp(i), t, 1, 0); return; } add(tp(i), tp(i << 1), INF, 0); add(tp(i), tp((i << 1) | 1 ), INF, 0); build(l, mid, i << 1); build(mid + 1, r, (i << 1) | 1); } int ll, lr, lp; void link(int l, int r, int i){ //cerr,l,r,i;cerr<<endl; if (ll <= l && lr >= r) { add(lp, tp(i), INF, 0); return; } if (lr > mid) link(mid + 1, r, (i << 1) | 1); if (ll <= mid) link(l, mid, i << 1); } int main(){ ios::sync_with_stdio(0); cin >> n; s = 0 ; t = n + 1; build(1, 5001, 1); for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i] >> c[i]; add(s, i, 1, -c[i]); ll = a[i]; lr = b[i] - 1; lp = i; link(1, 5001, 1); } mcf(); cout << -mincost; } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 #include <bits/stdc++.h>using namespace std;#define N 5002#define maxn N * 10#define maxm N * 100#define ey e[i].go#define INF 0x7f7f7f7f#define inf INFbitset<maxn> v;int d[maxn], from[maxn];queue<int> q;int s, t, mincost;struct edge {    int from, go, next, v, c;} e[maxm];int head[maxn], tot = 1;ostream& operator,(ostream& os,int x){os<<setw(12)<<x;return os;}void add(int x,int y,int v,int c){    //cerr,x,y,v,c;cerr<<endl; e[++tot]=(edge){x,y,head[x],v,c};head[x]=tot; e[++tot]=(edge){y,x,head[y],0,-c};head[y]=tot;}bool spfa(){    memset(d,0x7f,sizeof(d)); //for (int i=s;i<=t;i++){v[i]=0;d[i]=inf;} q.push(s);d[s]=0;v[s]=1; while(!q.empty()) { int x=q.front();q.pop();v[x]=0; for (int i=head[x],y;i;i=e[i].next) if(e[i].v&&d[x]+e[i].c<d[y=e[i].go]) { d[y]=d[x]+e[i].c;from[y]=i; if(!v[y]){v[y]=1;q.push(y);} } } return d[t]!=inf;}void mcf(){    mincost=0;    while(spfa()) { int tmp=inf; for(int i=from[t];i;i=from[e[i].from]) tmp=min(tmp,e[i].v); mincost+=d[t]*tmp; for(int i=from[t];i;i=from[e[i].from]){e[i].v-=tmp;e[i^1].v+=tmp;} }} #define mid ((l + r) >> 1)#define tp(x) ((x) + n + 2)int a[N], b[N], c[N];int n;void build(int l, int r, int i){    if (l == r) {        add(tp(i), t, 1, 0); return;    }    add(tp(i), tp(i << 1), INF, 0);    add(tp(i), tp((i << 1) | 1 ), INF, 0);    build(l, mid, i << 1);    build(mid + 1, r, (i << 1) | 1);} int ll, lr, lp;void link(int l, int r, int i){    //cerr,l,r,i;cerr<<endl;    if (ll <= l && lr >= r) {        add(lp, tp(i), INF, 0);        return;    }    if (lr > mid) link(mid + 1, r, (i << 1) | 1);    if (ll <= mid) link(l, mid, i << 1);} int main(){    ios::sync_with_stdio(0);    cin >> n; s = 0 ; t = n + 1;    build(1, 5001, 1);    for (int i = 1; i <= n; i++) {        cin >> a[i] >> b[i] >> c[i];        add(s, i, 1, -c[i]);        ll = a[i]; lr = b[i] - 1; lp = i;        link(1, 5001, 1);    }    mcf();    cout << -mincost;} 

 

## 交易一中集训Day[2]

Q:如何减少bug？
A:提高1A率
Q:如何提高1A率？
A:减少bug
Q:1A率受bug率影响，bug率又收1A率影响，这样岂不是成环了啊
A:不是啊，是你bug率减少的结果是你1A率增加啊，你提升1A率是给减少bug一个明确的目标
Q:那如何提高1A率呢
A:减少bug啊

[5,5)
(5,5)