2015 ACM/ICPC Asia Regional Shenyang Online

1001 Traversal

1002 Best Solver

1003 Minimum Cut

类似于POJ 3417的做法。

考虑每条新边对树边的覆盖次数。

每条树边被覆盖的次数其实就是断裂这条树边后还需断裂的新边数。

定义dp[i]为节点i向树根方向的边被新边覆盖次数。离线LCA后树DP。

答案为dp[2]~dp[n]中的最小值+1。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 using namespace std;
 6 # define CLR(x) memset(x,0,sizeof(x))
 7 # define INF 1000000
 8 const int maxn=20000+10,maxm=200000+10;
 9 int tot[2],h[2][maxn],dp[maxn],pa[maxn];
10 bool vis[maxn];
11 
12 struct node
13 {
14     int to,pre;
15 } edge[2][maxm<<1];
16 
17 void add(int op,int from,int to)
18 {
19     tot[op]++;
20     edge[op][tot[op]].pre=h[op][from];
21     edge[op][tot[op]].to=to;
22     h[op][from]=tot[op];
23 }
24 
25 int Find(int x)
26 {
27     return pa[x]==x?x:pa[x]=Find(pa[x]);
28 }
29 
30 void LCA(int x,int f)
31 {
32     for(int i=h[0][x];i;i=edge[0][i].pre)
33     {
34         int to=edge[0][i].to;
35         if(to==f) continue;
36         LCA(to,x);
37         pa[to]=x;
38     }
39     vis[x]=1;
40     for(int i=h[1][x];i;i=edge[1][i].pre)
41     {
42         int to=edge[1][i].to;
43         if(vis[to]) dp[Find(to)]-=2;
44     }
45     return;
46 }
47 
48 void dfs(int pos,int f)
49 {
50     for(int i=h[0][pos];i;i=edge[0][i].pre)
51     {
52         int to=edge[0][i].to;
53         if(to==f) continue;
54         dfs(to,pos);
55         dp[pos]+=dp[to];
56     }
57     for(int i=h[1][pos];i;i=edge[1][i].pre)
58     {
59         int to=edge[1][i].to;
60         if(!vis[to]) continue;
61         dp[pos]++; dp[to]++;
62     }
63     vis[pos]=0;
64     return;
65 }
66 
67 int main(void)
68 {
69     int T; cin>>T;
70     for(int kase=1;kase<=T;kase++)
71     {
72         int n,m; scanf("%d%d",&n,&m);
73         CLR(tot); CLR(h); CLR(vis); CLR(dp);
74         for(int i=0;i<n-1;i++)
75         {
76             int a,b; scanf("%d%d",&a,&b);
77             add(0,a,b); add(0,b,a);
78         }
79         for(int i=n-1;i<m;i++)
80         {
81             int a,b; scanf("%d%d",&a,&b);
82             add(1,a,b); add(1,b,a);
83         }
84         for(int i=1;i<=n;i++) pa[i]=i;
85         LCA(1,0); dfs(1,0);
86         int ans=INF;
87         for(int i=2;i<=n;i++) ans=min(ans,dp[i]);
88         printf("Case #%d: %d
",kase,ans+1);
89     }
90     return 0;
91 }
Aguin

1004 Dividing This Product

1005 Excited Database

把每条斜对角线看成一个点。主副两个方向分别建一颗线段树。

线段树的每个节点维护a[i]的和、i*a[i]的和、(2*n-i)*a[i]的和。

每次询问分别计算主副两个方向的增值。

询问的矩形拆成两个三角形和一个平行四边形。

三角形覆盖可以分别用i*a[i]与(2*n-i)*a[i]做差计算。

平行四边形覆盖直接用a[i]乘边长即可。

如图假设要用一颗线段树求虚线框内副对角线方向的贡献。

拆成两个蓝三角和一个灰色平行四边形。

左上的蓝三角用i*a[i]处理。转化成一个大三角减去黄三角再减去两个绿色平行四边形。

右下同理用(2*n-i)*a[i]类似的处理。

中间平行四边形直接用a[i]乘矩形高。

主对角线方向的一样处理。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 using namespace std;
  6 typedef long long LL;
  7 #define now tree[op][pos]
  8 #define ls tree[op][pos*2]
  9 #define rs tree[op][pos*2+1]
 10 #define maxn 400010
 11 int n;
 12 
 13 struct node
 14 {
 15     int l,r;
 16     LL a,ia,na,tag;
 17 } tree[2][maxn<<2];
 18 
 19 void build(int op,int pos,int l,int r)
 20 {
 21     now.l=l; now.r=r;
 22     now.a=now.ia=now.na=0;
 23     if(l<r)
 24     {
 25         build(op,pos*2,l,(l+r)/2);
 26         build(op,pos*2+1,(l+r)/2+1,r);
 27     }
 28     return;
 29 }
 30 
 31 void pushdown(int op,int pos)
 32 {
 33     if(now.tag)
 34     {
 35         ls.tag+=now.tag;
 36         ls.a+=(LL)(ls.r-ls.l+1)*now.tag;
 37         ls.ia+=(LL)(ls.l+ls.r)*(LL)(ls.r-ls.l+1)/2*now.tag;
 38         ls.na+=(LL)(4*n-ls.l-ls.r)*(LL)(ls.r-ls.l+1)/2*now.tag;
 39         rs.tag+=now.tag;
 40         rs.a+=(LL)(rs.r-rs.l+1)*now.tag;
 41         rs.ia+=(LL)(rs.l+rs.r)*(LL)(rs.r-rs.l+1)/2*now.tag;
 42         rs.na+=(LL)(4*n-rs.l-rs.r)*(LL)(rs.r-rs.l+1)/2*now.tag;
 43         now.tag=0;
 44     }
 45     return;
 46 }
 47 
 48 void pushup(int op,int pos)
 49 {
 50     now.a=ls.a+rs.a;
 51     now.ia=ls.ia+rs.ia;
 52     now.na=ls.na+rs.na;
 53     return;
 54 }
 55 
 56 void update(int op,int pos,int l,int r)
 57 {
 58     if(now.l>=l&&now.r<=r)
 59     {
 60         now.tag++;
 61         now.a+=(LL)(now.r-now.l+1);
 62         now.ia+=(LL)(now.l+now.r)*(LL)(now.r-now.l+1)/2;
 63         now.na+=(LL)(4*n-now.l-now.r)*(LL)(now.r-now.l+1)/2;
 64         return;
 65     }
 66     pushdown(op,pos);
 67     if(l<=(now.l+now.r)/2) update(op,2*pos,l,r);
 68     if(r>=(now.l+now.r)/2+1) update(op,2*pos+1,l,r);
 69     pushup(op,pos);
 70     return;
 71 }
 72 
 73 LL query(int op,int pos,char c,int l,int r)
 74 {
 75     if(l<=now.l&&r>=now.r)
 76     {
 77         if(c=='a') return now.a;
 78         if(c=='i') return now.ia;
 79         if(c=='n') return now.na;
 80     }
 81     LL ret=0;
 82     pushdown(op,pos);
 83     if(l<=(now.l+now.r)/2) ret+=query(op,pos*2,c,l,r);
 84     if(r>=(now.l+now.r)/2+1) ret+=query(op,pos*2+1,c,l,r);
 85     return ret;
 86 }
 87 
 88 int main(void)
 89 {
 90     int T; cin>>T;
 91     for(int kase=1;kase<=T;kase++)
 92     {
 93         int q;
 94         scanf("%d%d",&n,&q);
 95         printf("Case #%d:
",kase);
 96         build(0,1,1,2*n-1);//-1
 97         build(1,1,1,2*n-1);//+n
 98         for(int i=0;i<q;i++)
 99         {
100             int type;scanf("%d",&type);
101             if(type==1)
102             {
103                 int L,R;
104                 scanf("%d%d",&L,&R);
105                 update(0,1,L-1,R-1);
106             }
107             else if(type==2)
108             {
109                 int L,R;
110                 scanf("%d%d",&L,&R);
111                 update(1,1,L+n,R+n);
112             }
113             else
114             {
115                 int x1,y1,x2,y2;
116                 scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
117                 int w=y2-y1+1,h=x2-x1+1;
118                 LL ans=0;
119                 if(w>=h)
120                 {
121                     ans+=query(0,1,'i',x1+y1-1,x2+y1-2);
122                     ans-=query(0,1,'a',x1+y1-1,x2+y1-2)*(LL)(x1+y1-2);
123                     ans+=query(0,1,'n',x1+y2,x2+y2-1);
124                     ans-=query(0,1,'a',x1+y2,x2+y2-1)*(LL)(2*n-x2-y2);
125                     ans+=query(0,1,'a',x2+y1-1,x1+y2-1)*(LL)h;
126                     ans+=query(1,1,'i',x1-y2+n,x2-y2+n-1);
127                     ans-=query(1,1,'a',x1-y2+n,x2-y2+n-1)*(LL)(x1-y2+n-1);
128                     ans+=query(1,1,'n',x1-y1+n+1,x2-y1+n);
129                     ans-=query(1,1,'a',x1-y1+n+1,x2-y1+n)*(LL)(y1-x2+n-1);
130                     ans+=query(1,1,'a',x2-y2+n,x1-y1+n)*(LL)h;
131                 }
132                 else
133                 {
134                     ans+=query(0,1,'i',x1+y1-1,x1+y2-2);
135                     ans-=query(0,1,'a',x1+y1-1,x1+y2-2)*(LL)(x1+y1-2);
136                     ans+=query(0,1,'n',x2+y1,x2+y2-1);
137                     ans-=query(0,1,'a',x2+y1,x2+y2-1)*(LL)(2*n-x2-y2);
138                     ans+=query(0,1,'a',x1+y2-1,x2+y1-1)*(LL)w;
139                     ans+=query(1,1,'i',x1-y2+n,x1-y1+n-1);
140                     ans-=query(1,1,'a',x1-y2+n,x1-y1+n-1)*(LL)(x1-y2+n-1);
141                     ans+=query(1,1,'n',x2-y2+n+1,x2-y1+n);
142                     ans-=query(1,1,'a',x2-y2+n+1,x2-y1+n)*(LL)(y1-x2+n-1);
143                     ans+=query(1,1,'a',x1-y1+n,x2-y2+n)*(LL)w;
144                 }
145                 printf("%I64d
",ans);
146             }
147         }
148     }
149     return 0;
150 }
Aguin

1006 Fang Fang

水题。有c从c开始。没c数f。

！！注意可能有cf以外的字符。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 # define maxn 110000
 6 char s[maxn];
 7 
 8 int main(void)
 9 {
10     int T; cin>>T;
11     for(int kase=1;kase<=T;kase++)
12     {
13         scanf("%s",s);
14         int m=strlen(s);
15         int ok=1,pos=0;
16         for(int i=0;i<m;i++)
17         {
18             if(s[i]!='c'&&s[i]!='f') {ok=0;break;}
19             if(s[i]=='c') pos=i;
20         }
21         int mode=0,num=0,ans=0;
22         if(ok) for(int i=0;i<m;i++)
23         {
24             if(s[(pos+i)%m]=='c')
25             {
26                 if(mode==1&&num<2) {ok=0;break;}
27                 mode=1; ans++;
28                 num=0;
29             }
30             else
31             {
32                 if(mode==1) num++;
33                 else
34                 {
35                     if(num==0) {ans++; num++;}
36                     else num--;
37                 }
38             }
39         }
40         if(mode==1&&num<2) ok=0;
41         printf("Case #%d: %d
",kase,ok?ans:-1);
42     }
43     return 0;
44 }
Aguin

1007 Matches Puzzle Game

1008 Hold Your Hand

1009 Stability

1010 Jesus Is Here

递推。中间过程会用到每个串的长度，串中c的个数，c到左右的距离和。步步取mod。

转移式见代码。

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std;
 4 # define maxn 222222
 5 typedef long long LL;
 6 const LL mod=530600414;
 7 LL ans[maxn],l[maxn],r[maxn];
 8 LL cnt[maxn],len[maxn];
 9 
10 int main(void)
11 {
12     len[1]=1; len[2]=2; len[3]=3;
13     cnt[3]=1; r[3]=2;
14     for(int i=4;i<=201314;i++)
15     {
16         len[i]=(len[i-2]+len[i-1])%mod;
17         cnt[i]=len[i-3];
18         l[i]=(l[i-2]+l[i-1]+cnt[i-1]*len[i-2])%mod;
19         r[i]=(r[i-2]+r[i-1]+cnt[i-2]*len[i-1])%mod;
20         ans[i]=(ans[i-2]+ans[i-1]+cnt[i-2]*cnt[i-1]+cnt[i-1]*r[i-2]+cnt[i-2]*l[i-1])%mod;
21     }
22     int T; cin>>T;
23     for(int kase=1;kase<=T;kase++)
24     {
25         int x; scanf("%d",&x);
26         printf("Case #%d: %d
",kase,ans[x]);
27     }
28     return 0;
29 }
Aguin

1011 Poker

1012 Largest Point

1013 Manors

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Aguin/p/4822409.html