codeforces 酱游记
Codeforces Round #263 Div.1:
B. Appleman and Tree
题目大意：给一棵树，每个点可能是黑色或白色。求有多少种方案使得这棵树被分成k份，每份有且仅有一个黑点。
一看就知道是树形dp，可是不会做...题解思路很巧妙，很有借鉴意义。用dp[v][0]表示当前点及与它同一块的点没有黑点，dp[v][1]表示当前点及与它同一块的点有且仅有一个黑点。然后就是dp了。dp时有一个技巧：当前点为白色，而我们要求dp[v][1]时，我们必须只连接一个dp[child[i]][1]。我们可以直接用dp[v][0]来得到这时候的dp[v][1]。这样做既简洁又方便。实在是很神奇！
1 //7697563 2014-09-07 04:12:28 moxiaomo B - Appleman and Tree GNU C++ Accepted 31 ms 8200 KB 2 #include <bits/stdc++.h> 3 using namespace std; 4 typedef long long LL; 5 const int maxn=100001; 6 const LL MOD=1000000007; 7 8 int pos,lin[maxn],ta[maxn],sd[maxn]; 9 inline void biu(int s,int t) { ++pos; lin[pos]=ta[s]; ta[s]=pos; sd[pos]=t; } 10 11 int n; 12 int color[maxn]; 13 LL dp[maxn][2]; 14 void dfs(int v) 15 { 16 dp[v][color[v]]=1; 17 for (int i=ta[v];i;i=lin[i]) 18 { 19 dfs(sd[i]); 20 if (color[v]==1) 21 { 22 //dp[v][0]=0; 23 dp[v][1]=dp[v][1]*(dp[sd[i]][0]+dp[sd[i]][1])%MOD; 24 } 25 else 26 { 27 dp[v][1]=dp[v][1]*(dp[sd[i]][0]+dp[sd[i]][1])%MOD; 28 dp[v][1]=(dp[v][1]+dp[v][0]*dp[sd[i]][1])%MOD; 29 dp[v][0]=dp[v][0]*(dp[sd[i]][0]+dp[sd[i]][1])%MOD;//-- 30 } 31 } 32 } 33 int main() 34 { 35 scanf("%d",&n); 36 for (int i=0,p;i<n-1;i++) scanf("%d",&p),biu(p,i+1); 37 for (int i=0;i<n;i++) scanf("%d",color+i); 38 dfs(0); 39 cout<<dp[0][1]<<endl; 40 }
C. Appleman and a Sheet of Paper
简单题。细节的地方需要好好想想。
关于mid那里为什么错还不清楚...
1 //7698314 2014-09-07 08:34:09 moxiaomo C - Appleman and a Sheet of Paper GNU C++ Accepted 62 ms 760 KB 2 //iostream，bits/stdc++.h等头文件会导致g++编译变慢 3 #include <cstdio> 4 using namespace std; 5 const int maxn=100001; 6 7 int n; 8 int len[maxn]; 9 int sh[maxn]; 10 void modify(int p,int v) { len[p]+=v; for (int i=p;i<=n;i+=i&(-i)) sh[i]+=v; } 11 int sum(int p) 12 { 13 int ret=0; 14 for (int i=p;i;i-=i&(-i)) ret+=sh[i]; 15 return ret; 16 } 17 int main() 18 { 19 int q; 20 scanf("%d%d",&n,&q); 21 for (int i=1;i<=n;i++) modify(i,1); 22 for (int d,l=1,r=n,flag=0,p,a,b;q--;) 23 { 24 scanf("%d",&d); 25 if (d==1) 26 { 27 scanf("%d",&p); 28 int gs=r-l+1; 29 //if (flag) p=gs-p;//-- 30 /*int mid=(l+r>>1)-l+1;//-- 31 if (mid<=p)// 32 { 33 p=gs-p; 34 flag=!flag; 35 }*/ 36 if (gs<p*2) 37 { 38 p=gs-p; 39 flag=!flag; 40 } 41 if (!flag) 42 { 43 l+=p; 44 for (int i=1;i<=p;i++) modify(l+i-1,len[l-i]); 45 } 46 else 47 { 48 r-=p; 49 for (int i=1;i<=p;i++) modify(r-i+1,len[r+i]); 50 } 51 //cout<<sum(r)-sum(l-1)<<endl; 52 //printf("%d %d %d ",l,r,flag); 53 } 54 else 55 { 56 scanf("%d%d",&a,&b); 57 printf("%d ",!flag?sum(b+l-1)-sum(a+l-1):sum(r-a)-sum(r-b)); 58 } 59 } 60 }