是时候开刷NOI了

整天挨着毛爷爷，压力好大。。

看毛爷爷即将炖完NOI，我的确也该刷了

原则是从头到尾自己想（虽然看了一次题解），可以不A掉。

NOI2009

day1：

题目略神，我还是不讲了。。。（就这题我WA了好多遍 TAT）

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <bitset>
 5 #include <vector>
 6  
 7 #define N 20010
 8  
 9 using namespace std;
10  
11 struct edge{
12     int x,to;
13 }E[N<<2];
14  
15 int n,a[N],pre[N],totE,g[N];
16 bitset<N> v;
17 vector<int> G[N];
18  
19 #define p G[x][i]
20  
21 void ade(int x,int y){
22     G[x].push_back(y);
23 }
24  
25 int find(int x){
26     v[x]=1;
27     int len=G[x].size();
28     for(int i=0;i<len;i++)
29         if(!v[p]){
30             v[p]=1;
31             if(!pre[p]||find(pre[p])){
32                 pre[p]=x; pre[x]=p;
33                 return 1;
34             }
35         }
36     return 0;
37 }
38  
39 int main(){
40     freopen("transform.in","r",stdin);
41     freopen("transform.out","w",stdout);
42     scanf("%d",&n);
43     for(int i=1;i<=n;i++){
44         scanf("%d",&a[i]);
45     }
46     for(int i=1;i<=n;i++){
47         if(i-a[i]>=1) G[i].push_back(n+i-a[i]);
48         else G[i].push_back(n+i-a[i]+n);
49         if(i+a[i]<=n) G[i].push_back(n+i+a[i]);
50         else G[i].push_back(i+a[i]);
51     }
52     for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end());
53     int ans=0;
54     for(int i=n;i>=1;i--){
55         v.reset();
56         if(find(i)) ans++;
57     }
58     if(ans!=n){
59         puts("No Answer");
60     }
61     else{
62         for(int i=1;i<n;i++) printf("%d ",pre[i]-n-1);
63         printf("%d
",pre[n]-n-1);
64     }
65     return 0;
66 }

View Code

脑补一下，这个应该是一个单峰函数，果断三分。

爆long long QAQ，这要是NOI我就被坑死啦，long double过。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4  
 5 #define LL long long
 6 #define N 200010
 7 #define LD long double
 8  
 9 using namespace std;
10  
11 int n,P;
12 int len[N],pre[N];
13 LL L;
14 LD f[N];
15 char S[N][52];
16  
17 LD qpow(LD x,LL n){
18     LD ans=1;
19     for(;n;n>>=1,x*=x)
20         if(n&1) ans*=x;
21     return ans;
22 }
23  
24 LD Abs(LL x){
25     if(x<0) return -(LD)x;
26     return (LD)x;
27 }
28  
29 LD F(int i,int j){
30     return f[j]+
31         qpow(Abs(L-(len[i]-len[j]+i-j-1LL)),P); 
32 }
33  
34 int find(int i){
35     int l=0,r=i-1,m1,m2;
36     while(r-l>10){
37         m1=l+(r-l)/3;
38         m2=r-(r-l)/3;
39         if(F(i,m1)<F(i,m2)) r=m2;
40         else l=m1;
41     }
42     LD ans=F(i,0);
43     int pos=0;
44     for(int t=l;t<=r;t++)
45         if(F(i,t)<ans){
46             ans=F(i,t);
47             pos=t;
48         }
49     return pos;
50 }
51  
52 void print(int t){
53     if(pre[t]) print(pre[t]);
54     for(int i=pre[t]+1;i<t;i++){
55         printf("%s ",S[i]);
56     }
57     printf("%s
",S[t]);
58 }
59  
60 int main(){
61     freopen("noi09_poet.in","r",stdin);
62     freopen("noi09_poet.out","w",stdout);
63     int T;
64     scanf("%d",&T);
65     while(T--){
66         scanf("%d %lld %d",&n,&L,&P);
67         for(int i=1;i<=n;i++){
68             scanf("%s",S[i]);
69             len[i]=strlen(S[i]);
70         }
71         for(int i=2;i<=n;i++) len[i]+=len[i-1];
72         memset(f,127,sizeof(f));
73         f[0]=0;
74         for(int i=1;i<=n;i++){
75             int j=find(i);
76             f[i]=f[j]+qpow(Abs(L-(len[i]-len[j]+i-j-1LL)),P);
77             pre[i]=j;
78         }
79         if(f[n]>1e18){
80             puts("Too hard to arrange");
81         }
82         else{
83             printf("%lld
",(LL)(f[n]));
84             print(n);
85         }
86         puts("--------------------");
87     }
88     return 0;
89 }

View Code

QAQ好难，膜毛爷爷。

首先所谓 (频度 x 深度) 我们可以每过一层就加上当前的频度得到答案。

利用先序遍历的特殊性质（TAT 其实想到这个就差不多了），考虑dp。

f[i][j][k] 表示先序遍历从 i 到 j 作为一个子树（可能多个），而且满足所有权值小于等于k的最小花费。

转移分两种情况，修改当前root权值，修改子树权值。

$O(n^4)$ dp即可。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5  
 6 #define N 80
 7 #define LL long long
 8 #define INF 0x7f7f7f7f7f7f7f7fLL
 9 #define debug(x) cout<<#x<<" = "<<x<<endl;
10  
11 using namespace std;
12  
13 int n,tot0;
14 int a[N],b[N],c[N],X[N];
15 LL K;
16 LL dp[N][N][N];
17 LL s[N][N];
18  
19 /*
20 O(n^5)
21  
22 f[i][j][k]
23 i到j之间的所有数值大于k，
24 消灭当前点    f[i][j][k] = min{ f[i][p-1][k] + f[p+1][j][k] + s[i][j] + K }
25 不消灭当前点    f[i][j][k] = min{ f[i][p-1][b[p]] + f[p+1][j][b[p]] + s[i][j] }
26 */
27  
28 LL F(int i,int j,int k){
29     if(i>j) return 0;
30 //    printf("%d %d %d
",i,j,k);
31     if(dp[i][j][k]) return dp[i][j][k];
32     if(i==j) return dp[i][j][k]=b[i]<k ?K+c[i]:c[i];
33     dp[i][j][k]=INF;
34     for(int p=i;p<=j;p++){    //改当前点权 
35         dp[i][j][k]=min(dp[i][j][k],F(i,p-1,k) + F(p+1,j,k) + s[i][j] + K);
36         if(b[p]>=k){    //不改当前点权
37             dp[i][j][k]=min(dp[i][j][k],F(i,p-1,b[p]) + F(p+1,j,b[p]) + s[i][j]);
38         }
39     }
40     return dp[i][j][k];
41 }
42  
43 void init(){
44     for(int i=1;i<n;i++)
45         for(int j=i+1;j<=n;j++)
46             if(a[i]>a[j]){
47                 swap(a[i],a[j]);
48                 swap(b[i],b[j]);
49                 swap(c[i],c[j]);
50             }
51     sort(X+1,X+n+1);
52     tot0=1;
53     for(int i=2;i<=n;i++)
54         if(X[i]!=X[i-1]) X[++tot0]=X[i];
55     for(int i=1;i<=n;i++)
56         b[i]=lower_bound(X+1,X+tot0+1,b[i])-X;
57     for(int i=1;i<=n;i++){
58         s[i][i]=c[i];
59         for(int j=i+1;j<=n;j++)
60             s[i][j]=s[i][j-1]+c[j];
61     }
62 }
63  
64 int main(){
65     freopen("treapmod.in","r",stdin);
66     freopen("treapmod.out","w",stdout);
67     scanf("%d%d",&n,&K);
68     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
69     for(int i=1;i<=n;i++){
70         scanf("%d",&b[i]);
71         X[i]=b[i];
72     }
73     for(int i=1;i<=n;i++) scanf("%d",&c[i]);
74     init();
75     LL ans=INF;
76     for(int i=1;i<=n;i++){
77         ans=min(ans,F(1,n,b[i]));
78     }
79     cout<<ans<<endl;
80     return 0;
81 }

View Code

day2

T1：

裸网络流，注意要拓扑一下，还要判环，环内的植物不能碰。

T2：

又是一道$dp$，思路很神（TAT 实在不会，看了题解）。

就是将平方和转化为结果相同的方案对数（自己也算）

然后裸dp上。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4  
 5 #define N 510
 6 #define mod 1024523
 7  
 8 using namespace std;
 9  
10 /*
11 f[i][j][k]表示上面取了上i下j，上k。 
12 */
13  
14 char S1[N],S2[N];
15 int f[N][N][N],n,m;
16  
17 int add(int a,int b){
18     if(a+b<mod) return a+b;
19     return a+b-mod;
20 }
21  
22 int main(){
23     freopen("ballb.in","r",stdin);
24     freopen("ballb.out","w",stdout);
25     scanf("%d%d%s%s",&n,&m,S1,S2);
26     reverse(S1,S1+n);
27     reverse(S2,S2+m);
28     f[0][0][0]=1;
29     for(int i=0;i<=n;i++){
30         for(int j=0;j<=m;j++){
31             for(int k=0;k<=n;k++){
32                 if(!f[i][j][k]) continue;
33                 int l = i+j-k;
34                 if(l<0) break;
35                 //printf("f[%d][%d][%d] = %d
",i,j,k,f[i][j][k]);
36                 if(i<n && k<n && S1[i]==S1[k]){
37                     f[i+1][j][k+1] = add(f[i+1][j][k+1],f[i][j][k]);
38                 }
39                 if(i<n && l<m && S1[i]==S2[l]){
40                     f[i+1][j][k] = add(f[i+1][j][k],f[i][j][k]);
41                 }
42                 if(j<m && k<n && S2[j]==S1[k]){
43                     f[i][j+1][k+1] = add(f[i][j+1][k+1],f[i][j][k]); 
44                 }
45                 if(j<m && l<m && S2[j]==S2[l]){
46                     f[i][j+1][k] = add(f[i][j+1][k],f[i][j][k]);
47                 }
48             }
49         }
50     }
51     printf("%d
",f[n][m][n]);
52     return 0;
53 }

View Code

T3：

很好的提交答案题。

做好了70分吧。

NOI 2008

TAT QAQ QWQ TWT

题出这么难也是醉了。

day1:

找环然后分类讨论，情况不多就三种。

可是好多细节呀，蒟蒻我是调不出来的。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4  
 5 using namespace std;
 6  
 7 template<typename T> T abs(T x){
 8     if(x>0) return x;
 9     return -x;
10 }
11 template<typename T> T gcd(T x, T y){
12     for(T t;x!=0;t=x,x=y%x,y=t);
13     return y;
14 }
15  
16 const int Maxn =2000010;
17 const int Maxm =2000010;
18  
19 struct edge{
20     int to,x,v;
21 }Edges[Maxm];
22  
23 int totE=0,head[Maxn];
24  
25 void addedge(int u,int v,int w){
26     Edges[++totE]=(edge){head[u],v,w};
27     head[u]=totE;
28 }
29  
30 int n,m,ans=0,d[Maxn],maxt,mint;
31 bool vis[Maxn];
32  
33 void dfs(int x){
34     vis[x]=1;
35     for(int i=head[x];i;i=Edges[i].to){
36         int p=Edges[i].x;
37         if(vis[p]) ans=gcd(ans,abs(d[x]+Edges[i].v-d[p]));
38         else d[p]=d[x]+Edges[i].v,dfs(p);
39     }
40 }
41  
42 void find(int x){
43     vis[x]=1;
44     maxt=max(maxt,d[x]);
45     mint=min(mint,d[x]);
46     for(int i=head[x];i;i=Edges[i].to){
47         int p=Edges[i].x;
48         if(!vis[p]) d[p]=d[x]+Edges[i].v,find(p);
49     }
50 }
51  
52 int main(){
53     freopen("party2008.in","r",stdin);
54     freopen("party2008.out","w",stdout);
55     scanf("%d%d",&n,&m);
56     int u,v,tmp;
57     for(int i=1;i<=m;i++){
58         scanf("%d%d",&u,&v);
59         addedge(u,v,1);
60         addedge(v,u,-1);
61     }
62     for(int i=1;i<=n;i++)
63         if(!vis[i]) d[i]=0,dfs(i);
64     if(ans){
65         for(tmp=3;tmp<ans&&ans%tmp;tmp++);
66         //cout<<"case 1
";
67     }
68     else{
69         memset(vis,0,sizeof(vis));
70         tmp=3;
71         for(int i=1;i<=n;i++)
72             if(!vis[i]){
73                 maxt=mint=d[i]=0;
74                 find(i);
75                 ans+=maxt-mint+1;
76             }
77     }
78     if(ans<3) ans=tmp=-1;
79     printf("%d %d
",ans,tmp);
80     return 0;
81 }

View Code

相对温暖的一道题。

可以发现一个条件：答案是 $O(logn)$ 级的（为啥我也不知道）。

然后变成了经典问题，直接枚举【不便利值】树形dp方案数，$f[i][j]$表示 $i$ 这个点向下连 $j$ 条边的方案数，直到方案数不为0为止。

注意0和mod后为0不同，因为要判断是否有方案，所以如果是因为mod而变成的0记做mod。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <queue>
 6  
 7 #define Maxn 100010
 8 typedef long long LL;
 9  
10 using namespace std;
11  
12 int n,m,Q,dep[Maxn];
13 LL f[Maxn][21][3];
14 vector<int> G[Maxn];
15  
16 /*
17 link = f[p][j][0] + f[p][j][1]
18 not_link = f[p][j-1][0] + f[p][j-1][1] + f[p][j-1][2]
19  
20 f[i][j][2] = f[i][j][2] * not_link + f[i][j][2]
21 f[i][j][1] = f[i][j][1] * not_link + f[i][j][0] * link
22 f[i][j][0] = f[i][j][0] * not_link
23 */
24  
25 bool find_circle(int x,int tp){
26     for(int i=0;i<G[x].size();i++){
27         if(G[x][i]==tp) continue;
28         if(dep[G[x][i]]) return 1;
29         dep[G[x][i]]=dep[x]+1;
30         if(find_circle(G[x][i],x)) return 1;
31     }
32     return 0;
33 }
34  
35 bool not_a_tree(int x){
36     dep[x]=1;
37     if(find_circle(x,0)) return 1;
38     for(int i=1;i<=n;i++)
39         if(!dep[i]) return 1;
40     return 0;
41 }
42  
43 LL Mod(LL x){
44     if(x==0) return 0;
45     if(x%Q==0) return Q;
46     return x%Q;
47 }
48  
49 LL dp(int x,int tp,int j){
50     f[x][j][1]=f[x][j][2]=0LL;
51     f[x][j][0]=1LL;
52     for(int i=0;i<G[x].size();i++){
53         int p=G[x][i];
54         if(p==tp) continue;
55         dp(p,x,j);
56         int not_link=0,link=0;
57         link =Mod(f[p][j][0]+f[p][j][1]);
58         if(j>0) not_link =Mod(f[p][j-1][0]+Mod(f[p][j-1][1]+f[p][j-1][2]));
59         f[x][j][2] =Mod(f[x][j][2]*not_link)+Mod(f[x][j][1]*link);
60         f[x][j][2] =Mod(f[x][j][2]);
61         f[x][j][1] =Mod(f[x][j][1]*not_link)+Mod(f[x][j][0]*link);
62         f[x][j][1] =Mod(f[x][j][1]);
63         f[x][j][0] =Mod(f[x][j][0]*not_link);
64     }
65     return Mod(f[x][j][0]+Mod(f[x][j][1]+f[x][j][2]));
66 }
67  
68 int main(){
69     freopen("design.in","r",stdin);
70     freopen("design.out","w",stdout);
71     scanf("%d%d%d",&n,&m,&Q);
72     int u,v,tmp=0;
73     LL ans=0;
74     for(int i=1;i<=m;i++){
75         scanf("%d%d",&u,&v);
76         G[u].push_back(v);
77         G[v].push_back(u);
78     }
79     if(n!=m+1||not_a_tree(1)){
80         puts("-1
-1");
81         return 0;
82     }
83     while(ans<=0) ans=dp(1,0,tmp++);
84     printf("%d
%lld
",tmp-1,ans==Q? 0:ans);
85     return 0;
86 }

View Code

蒟蒻表示自己图论超级渣。

以前看题解过了，现在还不懂。

day2

妈呀，基环外向树上dp，醉了，还是概率dp。

用贪心水到了40分，好像有人说可以70分，咦是我交的题库上的数据太强了吗。

day2的温暖题。

QAQ 但是好寒冷。

直接转化一下，二维树状数组。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4  
 5 #define Maxn 1010
 6 #define Maxc 1000010
 7  
 8 typedef int Se[Maxn*3][Maxn<<2];
 9  
10 using namespace std;
11  
12 int n,T,len,m;
13 Se a,b;
14 struct Cloud{
15     int t,p;
16 }clou[Maxc];
17  
18 void Add(Se a,int x,int y,int d){
19     for(int i=x+1;i<len*3+2;i+=i&-i)
20         for(int j=y+1;j<(len<<2)+1;j+=j&-j)
21             a[i][j]+=d;
22 }
23  
24 int Ask(Se a,int x,int y){
25     int ans=0;
26     for(int i=x+1;i;i-=i&-i)
27         for(int j=y+1;j;j-=j&-j)
28             ans+=a[i][j];
29     return ans;
30 }
31  
32 void Add1(int x,int y,int d){
33     Add(a,x,x+y,d);
34 }
35  
36 void Add2(int x,int y,int d){
37     Add(b,x-len,y-x+m,d);
38 }
39  
40 void update(int c,int d){
41     int t=clou[c].t,p=clou[c].p;
42     Add1(t,p,d);
43     if(t<=len) Add1(t+n,p,d);
44     Add2(t+n,p,d);
45     if(t>=len) Add2(t,p,d);
46 }
47  
48 int Ask1(int x0,int y0,int x1,int y1){
49     return Ask(a,x1,x1+y1) - Ask(a,x0-1,x1+y1)
50     - Ask(a,x1,x0+y0-1) + Ask(a,x0-1,x0+y0-1);
51 }
52  
53 int Ask2(int x0,int y0,int x1,int y1){
54     return Ask(b,x1-len,y1-x1+m) - Ask(b,x0-len-1,y1-x1+m)
55         - Ask(b,x1-len,y0-x0+m-1) + Ask(b,x0-len-1,y0-x0+m-1);
56 }
57  
58 int query(int t,int L,int R){
59     int ans=Ask1(t,L,t+R,len),d=len==R;
60     if(!R) return ans;
61     return ans+=Ask2(t+n-R+d,L-R+d,t+n-1,len+R-1);
62 }
63  
64 int main(){
65     freopen("noi2008_candy.in","r",stdin);
66     freopen("noi2008_candy.out","w",stdout);
67     scanf("%d%d",&T,&len);
68     n=2*len; m=2*n;
69     for(int i=1;i<=T;i++){
70         int K,t,c,L,R,d;
71         scanf("%d%d",&K,&t);
72         t%=n;
73         if(K==1){
74             scanf("%d%d%d%d",&c,&L,&R,&d);
75             clou[c].t=(t-d*L+n)%n;
76             clou[c].p=R-L;
77             update(c,1);
78         }
79         else if(K==2){
80             scanf("%d%d",&L,&R);
81             printf("%d
",query(t,L,R));
82         }
83         else{
84             scanf("%d",&c);
85             update(c,-1);
86         }
87     }
88     return 0;
89 }

View Code

提交答案题，还没做

继续

NOI2010

Day1

T1:能量采集：SB题，随便搞

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4  
 5 #define LL long long
 6 #define Maxn 100010
 7  
 8 using namespace std;
 9  
10 LL n,m,ans;
11 LL phi[Maxn]={0,1,0};
12  
13 int main(){
14     freopen("energy2010.in","r",stdin);
15     freopen("energy2010.out","w",stdout);
16     scanf("%lld%lld",&n,&m);
17     if(n<m) swap(n,m);
18     for(int i=2;i<=m;i++){
19         if(phi[i]) continue;
20         for(int j=i;j<=m;j+=i){
21             if(!phi[j]) phi[j]=j;
22             phi[j]=phi[j]*(i-1)/i;
23         }
24     }
25     for(int i=1;i<=m;i++){
26         ans+=(n/i)*(m/i)*phi[i];
27     }
28     ans=(ans-m*n)*2+m*n;
29      printf("%lld
",ans);
30     return 0;
31 }

View Code

T2:超级钢琴。

区间裂解，就是找到前K大的子区间和

ST+堆，随便搞。

#include <cstdio>
#include <queue>
using namespace std;
 
typedef long long LL;
 
const int maxn = 500010;
 
struct Node {
    LL x; int l, r, i;
    bool operator < (const Node &A) const {
        return x < A.x;
    }
};
priority_queue<Node> pq;
 
int n, K, L, R;
LL S[maxn];
int rmq[20][maxn];
 
void RMQ_init() {
    int k = 0; for (; (1 << k+1) < n+1; ++ k);
    for (int i = 0; i <= n; ++ i) rmq[0][i] = i;
    
    for (int j = 1; j <= k; ++ j)
        for (int i = 0; i+(1<<j)-1 <= n; ++ i) {
            int p = rmq[j-1][i], q = rmq[j-1][i+(1<<j-1)];
            rmq[j][i] = S[p] < S[q] ? p : q;
        }
}
int RMQ(int l, int r) {
    int z = r-l+1;
    int k = 0; for (; (1 << k+1) < z; ++ k);
    int p = rmq[k][l], q = rmq[k][r-(1<<k)+1];
    return S[p] < S[q] ? p : q;
}
 
int main() {
    freopen("piano.in", "r", stdin);
    freopen("piano.out", "w", stdout);
    
    scanf("%d%d%d%d", &n, &K, &L, &R);
    
    for (int i = 1; i <= n; ++ i) {
        int x; scanf("%d", &x);
        S[i] = S[i-1] + x;
    }
    RMQ_init();
    
    for (int i = 1; i <= n; ++ i) {
        int a = i-R, b = i-L; if (a < 0) a = 0;
        if (b >= 0) pq.push((Node){S[i] - S[RMQ(a, b)], a, b, i});
    }
    
    LL res = 0;
    while (K --) {
        if (pq.empty()) break;
        Node x = pq.top(); pq.pop();
        res += x.x; int t = RMQ(x.l, x.r);
        if (x.l <= t-1) pq.push((Node){S[x.i] - S[RMQ(x.l, t-1)], x.l, t-1, x.i});
        if (t+1 <= x.r) pq.push((Node){S[x.i] - S[RMQ(t+1, x.r)], t+1, x.r, x.i});
    }
    printf("%lld
", res);
    
    fclose(stdin); fclose(stdout);
    return 0;
}

View Code

T3：海拔

不想写对偶图，懒癌犯了，dinic 80何必呢。

Day2

T1：航空管制

很神，但是是贪心。拓扑一下然后直接贪心。

在不看题解下拿了80（二分答案+乱搞）

T2：旅行路线

很懒，裸插头dp，不想捉。

NOI2011

Day1

T1：兔农

很久以前过的了，忘了。

T2：智能车比赛

很SB的水题，最短路，建图叉积一下，貌似我写麻烦了。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <queue>
  6 #include <cstdlib>
  7  
  8 #define LL long long
  9 #define sqr(x) ((x)*(x))
 10 #define N 8010
 11 #define p E[i].x
 12  
 13 using namespace std;
 14  
 15 struct edge{
 16     int x,to;
 17     long double v;
 18 }E[2000010];
 19  
 20 struct node{
 21     int x,y,id;
 22     
 23     void print(){
 24         printf("(%d,%d)",x,y);
 25     }
 26     
 27     void scan(){
 28         scanf("%d%d",&x,&y);
 29     }
 30 }S,T,P[100010];
 31  
 32 int tot;
 33 queue<int> q;
 34  
 35 struct road{
 36     node Lu,Ld,Ru,Rd;
 37     
 38     void scan(){
 39         Ld.scan();
 40         Ru.scan();
 41         Lu=(node){Ld.x,Ru.y};
 42         Rd=(node){Ru.x,Ld.y};
 43         Ld.id=++tot; P[tot]=Ld;
 44         Lu.id=++tot; P[tot]=Lu;
 45         Rd.id=++tot; P[tot]=Rd;
 46         Ru.id=++tot; P[tot]=Ru;
 47     }
 48 }L[N];
 49  
 50 int n,totE;
 51 int g[N];
 52 double V;
 53 long double dis[N];
 54 bool v[N];
 55  
 56 double dist(node a,node b){
 57     return sqrt(sqr((LL)(a.x-b.x))+sqr((LL)(a.y-b.y)));
 58 }
 59  
 60 LL cross(node a,node b,node c){
 61     return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
 62 }
 63  
 64 bool cut(node a,node b,node c,node d){
 65     if(cross(a,c,b)*(LL)cross(a,d,b)>=0) return 0;
 66     if(cross(c,a,d)*(LL)cross(c,b,d)>=0) return 0;
 67     return 1;
 68 }
 69  
 70 bool check(node a,node b){
 71     for(int i=1;i<=n;i++){
 72         if(cut(a,b,L[i].Ld,L[i].Lu)) return 0;
 73         if(cut(a,b,L[i].Lu,L[i].Ru)) return 0;
 74         if(cut(a,b,L[i].Rd,L[i].Ru)) return 0;
 75         if(cut(a,b,L[i].Ld,L[i].Rd)) return 0;
 76     }
 77     return 1;
 78 }
 79  
 80 void addedge(node a,node b){
 81     int x=a.id,y=b.id;
 82     long double d=dist(a,b);
 83     E[++totE]=(edge){y,g[x],d}; g[x]=totE;
 84     E[++totE]=(edge){x,g[y],d}; g[y]=totE;
 85 }
 86  
 87 void buildgraph(node now){
 88     node up=(node){now.x,now.y+1},down=(node){now.x,now.y-1};
 89     for(int j=1;j<=tot;j++){
 90         if(cross(now,P[j],up)<=0 && cross(now,P[j],down)>=0);
 91         if((j&1)==0 && cross(now,P[j],up)<0) up=P[j];
 92         if((j&1) && cross(now,P[j],down)>0) down=P[j];
 93         if((j&1)==0 && P[j].x>=T.x){
 94             if(cross(now,T,up)<=0 && cross(now,T,down)>=0){
 95                 printf("%.10lf
",dist(S,T)/V);
 96                 exit(0);
 97             }
 98         }
 99     }
100 }
101  
102 void buildgraph2(node now){
103     node up=(node){now.x,now.y+1},down=(node){now.x,now.y-1};
104     for(int j=tot;j>=1;j--){
105         if(cross(now,P[j],up)>=0 && cross(now,P[j],down)<=0)
106             addedge(now,P[j]);
107         if((j&1)==0 && cross(now,P[j],up)>0) up=P[j];
108         if((j&1) && cross(now,P[j],down)<0) down=P[j];
109     }
110 }
111  
112 int main(){
113 //    freopen("car2.in","r",stdin);
114     freopen("noi2011_car.in","r",stdin);
115     freopen("noi2011_car.out","w",stdout);
116     scanf("%d",&n);
117     for(int i=1;i<=n;i++) L[i].scan();
118     S.scan(); S.id=tot+1;
119     T.scan(); T.id=tot+2;
120     if(S.x>T.x) swap(S,T);
121     scanf("%lf",&V);
122     for(int i=1;i<=tot;i++){
123         node up=(node){P[i].x,P[i].y+1},down=(node){P[i].x,P[i].y-1};
124         for(int j=i+1;j<=tot;j++){
125             if(cross(P[i],P[j],up)<=0 && cross(P[i],P[j],down)>=0)
126                 addedge(P[i],P[j]);
127             if((j&1)==0 && cross(P[i],P[j],up)<=0) up=P[j];
128             if((j&1) && cross(P[i],P[j],down)>=0) down=P[j];
129         }
130     }
131     int st=0,ed=0;
132     for(int i=1;i<=tot;i++){
133         if(P[i].x==S.x&&P[i].y==S.y) st=i;
134         if(P[i].x==T.x&&P[i].y==T.y) ed=i;
135     }
136     buildgraph(S);
137     for(int i=1;i<=tot+2;i++) dis[i]=1e50;
138     q.push(st); dis[st]=0;
139     while(!q.empty()){
140         int x=q.front(); q.pop();
141         v[x]=0;
142         for(int i=g[x];i;i=E[i].to)
143             if(dis[p]>dis[x]+E[i].v){
144                 dis[p]=dis[x]+E[i].v;
145                 if(!v[p]) q.push(p),v[p]=1;
146             }
147     }
148     printf("%.10lf
",(double)(dis[ed]/V));
149     return 0;
150 }

View Code

T3：阿狸的打字机

树链剖分维护fail树，不错的经典题

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #include <vector>
  6  
  7 #define N 100010
  8 #define MP(x,y) make_pair(x,y)
  9 #define debug(x) cout<<#x<<" = "<<x<<endl;
 10 #define fir first
 11 #define sec second
 12  
 13 using namespace std;
 14  
 15 void file(){
 16     freopen("noi2011_type.in","r",stdin);
 17     freopen("noi2011_type.out","w",stdout);
 18 }
 19  
 20 struct node{
 21     node *ch[26],*fail,*fa,*next[26];
 22     int v,id;
 23 }*root,*pre[N];
 24  
 25 int n,tot,sumv[N],L[N],R[N],g[N],totE,cnt,tott,ansv[N];
 26 char S[N];
 27 vector<pair<int,int> > ask[N];
 28  
 29 struct edge{
 30     int x,to;
 31 }E[N<<1];
 32  
 33 queue<node*> q;
 34  
 35 void ade(int x,int y){
 36     E[++totE]=(edge){y,g[x]}; g[x]=totE;
 37 }
 38  
 39 int qsum(int x){
 40     int ans=0;
 41     for(;x>0;x-=(x&-x)) ans+=sumv[x];
 42     return ans;
 43 }
 44  
 45 void add(int x,int v){
 46     for(;x<=tot;x+=(x&-x)) sumv[x]+=v;
 47 }
 48  
 49 void getfail(){
 50     q.push(root);
 51     while(!q.empty()){
 52         node* tmp=q.front(); q.pop();
 53         tmp->id=++tot;
 54         if(tmp!=root) ade(tmp->fail->id,tmp->id);
 55         for(int t=0;t<26;t++){
 56             if(tmp->ch[t]!=NULL){
 57                 if(tmp==root) tmp->ch[t]->fail=root;
 58                 else tmp->ch[t]->fail=tmp->fail->ch[t];
 59                 q.push(tmp->ch[t]);
 60             }
 61             else{
 62                 if(tmp==root) tmp->ch[t]=root;
 63                 else tmp->ch[t]=tmp->fail->ch[t];
 64             }
 65         }
 66     }
 67 }
 68  
 69 #define p E[i].x
 70  
 71 void dfs(int x){
 72     L[x]=++tott;
 73     for(int i=g[x];i;i=E[i].to) dfs(p);
 74     R[x]=tott;
 75 }
 76  
 77 void solve(node* x){
 78     add(L[x->id],1);
 79     for(int i=ask[x->id].size()-1;~i;i--){
 80         int t=ask[x->id][i].fir;
 81         ansv[ask[x->id][i].sec]=qsum(R[t])-qsum(L[t]-1);
 82     }
 83     for(int t=0;t<26;t++)
 84         if(x->next[t]!=NULL) solve(x->next[t]);
 85     add(L[x->id],-1);
 86 }
 87  
 88 int main(){
 89     file();
 90     scanf("%s",S);
 91     root=new node();
 92     node* tmp=root;
 93     for(int i=0,len=strlen(S);i<len;i++){
 94         if(S[i]=='P') pre[++cnt]=tmp;
 95         else if(S[i]=='B') tmp=tmp->fa;
 96         else{
 97             int t=S[i]-'a';
 98             if(tmp->ch[t]==NULL){
 99                 tmp->ch[t]=new node();
100                 tmp->next[t]=tmp->ch[t];
101             }
102             tmp->ch[t]->fa=tmp;
103             tmp=tmp->ch[t];
104         }
105     }
106     getfail();
107     dfs(root->id);
108     scanf("%d",&n);
109     for(int i=1,x,y;i<=n;i++){
110         scanf("%d%d",&x,&y);
111         ask[pre[y]->id].push_back(MP(pre[x]->id,i));
112     }
113     solve(root);
114     for(int i=1;i<=n;i++)
115         printf("%d
",ansv[i]);
116     fclose(stdin);
117     fclose(stdout);
118     return 0;
119 }

View Code

Day2

T1：道路修建

233这题。。。。

T2：NOI 嘉年华

读不懂

T3：兔子和蛋蛋

没看