寫這幾個題解我覺得我就像在按照官方題解抄一樣

陰陽

題解

將題目中給的陰陽看作黑色和白色

首先我們觀察到最后生成圖中某種顏色必須是豎著單調遞增或豎著單調遞減

類似這樣

否則不滿足這個條件

但合法染色方案必須滿足任意兩個同顏色格子之間的格子也必須是該顏色。

然后我們分四種情況統計，

1.黑色居于左側而且分界點單調不降，

2.黑色居于左側而且分界點單調不升，

3.白色居于左側而且分界點單調不降，

4.白色居于左側而且分界點單調不升。

我們發現這樣會算重，

dp然后手動容斥，

1，2會算重左面每列全是黑色

類似于

類似的3，4會算重左面全是白色

那么上面全是黑色我們也會算重（2，3）

上面全是白色我們仍然會算重

手動容斥

題解應該都能看懂，實現稍難（不用說了我碼力太弱）

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1111 const ll mod=1e9+7; ll can[A][A][10],f[A][A][2],up[A][A],down[A][A]; //can定義為i行從1--j染成B剩下染成W是否合法 char ch[A][A]; ll n,m,flag1,flag2,ans; int main(){scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)scanf("%s",ch[i]+1);for(ll i=1;i<=n;i++){ll maxpos=0;for(ll j=1;j<=m;j++){if(ch[i][j]=='W') break;if(ch[i][j]=='B') maxpos=j;}for(ll j=maxpos+1;j<=m;j++)if(ch[i][j]=='B'){maxpos=m+1; break;}ll now=maxpos;while(ch[i][now]!='W'&&now<=m)can[i][now][1]=1,now++;}for(ll i=1;i<=n;i++){ll maxpos=m+1;for(ll j=m;j>=1;j--){if(ch[i][j]=='W') break;if(ch[i][j]=='B') maxpos=j;}for(ll j=maxpos-1;j>=1;j--)if(ch[i][j]=='B'){maxpos=-1; break;}ll now=maxpos;while(ch[i][now]!='W'&&now>=0)can[i][m-now+1][2]=1,now--;}for(ll i=0;i<=m;i++)up[0][i]=1,down[0][i]=1;for(ll i=1;i<=n;i++){for(ll j=0;j<=m;j++){if(!can[i][j][1]) continue;f[i][j][0]=up[i-1][j];f[i][j][1]=down[i-1][j]; // printf("up[%lld][%lld]=%lld down=%lld\n",i-1,j,up[i-1][j],down[i-1][j]); }for(ll j=0;j<=m;j++)up[i][j]=(up[i][j-1]+f[i][j][0])%mod/*,printf("f=%lld up=%lld\n",f[i][j][0],up[i][j])*/;for(ll j=m;j>=0;j--)down[i][j]=(down[i][j+1]+f[i][j][1])%mod; // printf("up=%lld down=%lld\n",up[n][m],down[n][0]); } /* for(ll i=1;i<=n;i++,puts("")){for(ll j=1;j<=m;j++){printf("%lld ",can[i][j][1]);}} */ memset(f,0,sizeof(f));ans=(ans+up[n][m]+down[n][0]+mod)%mod; // printf("ans=%lld\n",ans);for(ll i=1;i<=n;i++){for(ll j=0;j<=m;j++){if(!can[i][j][2]) continue;f[i][j][0]=up[i-1][j];f[i][j][1]=down[i-1][j];}for(ll j=0;j<=m;j++)up[i][j]=(up[i][j-1]+f[i][j][0])%mod;for(ll j=m;j>=0;j--)down[i][j]=(down[i][j+1]+f[i][j][1])%mod;} // printf("up=%lld down=%lld\n",up[n][m],down[n][0]);ans=(ans+up[n][m]+down[n][0]+mod)%mod; // printf("ans=%lld\n",ans);memset(f,0,sizeof(f));//減去左右重復for(ll i=1;i<m;i++){ll flag=0;for(ll j=1;j<=n;j++)if(!can[j][i][1]){flag=1;break;}if(!flag) ans--;}for(ll i=1;i<m;i++){ll flag=0;for(ll j=1;j<=n;j++)if(!can[j][i][2]){flag=1;break;}if(!flag) ans--;}//減去上下//若上面為B下面只能為Wfor(ll i=1;i<n;i++){ll flag=0;for(ll j=1;j<=i;j++)if(!can[j][m][1]){flag=1;break;}for(ll j=i+1;j<=n;j++)if(!can[j][0][1]){flag=1;break;}if(flag)continue;ans--;}for(ll i=n;i>=2;i--){ll flag=0;for(ll j=1;j<=i-1;j++)if(!can[j][0][1]){flag=1;break;}for(ll j=i;j<=n;j++)if(!can[j][m][1]){flag=1;break;}if(flag)continue;ans--;}for(ll i=1;i<=n;i++){if(!can[i][0][1]) flag1=1;if(!can[i][m][1]) flag2=1;}if(!flag1) ans-=3;if(!flag2) ans-=3;printf("%lld\n",(ans+mod)%mod); } View Code

虎

題解

我們發現一條性質我們子樹內兩個點要變成黑色我們同時經過樹外的邊不會使次數變優（除了直接與lca相連的邊）

然后根據這條性質，我們發現我們一定存在一種最優方案使任意兩條染色路徑互不相交

然后我們進行貪心

首先題目中給的無要求的邊我們進行縮邊

我們統計到當前子樹都已經全部染成黑色了，那么我們只用考慮與它相連就行

拿下面這個圖舉例（假設全部為白邊）

你考慮3時你6的子樹都處理完了，然后你遇到兩個白色邊（3，6）（3，7）你貪心直接染色就行，那么如果最后剩下一個沒有染色怎么辦，顯然我們不用管，我們發現與3相連的邊（1，3）這條邊是必定被染色的，2本來要和3進行染色讓（1，2）（1，3）進行染色，我們現在把這個邊拉過來變成（2，8）進行染色就行了

那么依據上文說的，我們只需要讓與3相連白邊個數（除了父親與它相連邊）/2就行了

推廣到所有點統計白邊個數/2即可

然后這樣做對于根來說會出錯，特判一下就AC了（對于根來說沒有辦法再讓自己父親拉邊過來）

?

?

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; #define R register #define ll long long inline ll read()//------- {ll aa=0;char cc=getchar();while(cc<'0'||cc>'9') cc=getchar();while(cc<='9'&&cc>='0'){aa=(aa<<3)+(aa<<1)+(cc^48);cc=getchar();}return aa; } const int N=1000005; struct tree{int v,last; }tr[N<<1]; int tot,first[N]; inline void add(int x,int y) {tr[++tot]=(tree){y,first[x]};first[x]=tot;return; } int n,ans,mp[N],vi[N]; int dfs(int x,int fa) {int sum=0;vi[x]=1;for(R int i=first[x],v;i;i=tr[i].last){v=tr[i].v;if(v==fa)continue;dfs(v,x);sum^=1;if(!sum)++ans;}return sum; } int main() {//freopen("tight.in","r",stdin);//freopen("tight.out","w",stdout);n=read();mp[1]=++mp[0];for(R int i=2,x,y,z;i<=n;++i){x=read();y=read();z=read();if(!z){if(mp[i])mp[x]=mp[i];else if(mp[x])mp[i]=mp[x];else mp[i]=mp[x]=++mp[0];continue;}if(!mp[i])mp[i]=++mp[0];if(!mp[x])mp[x]=++mp[0];if(y)continue;add(mp[i],mp[x]);add(mp[x],mp[i]);}for(R int i=1;i<=mp[0];++i)if(!vi[i])if(dfs(i,i))++ans;printf("%d",ans);return 0; } View Code

?

轉載于:https://www.cnblogs.com/znsbc-13/p/11424317.html

總結

以上是生活随笔為你收集整理的NOIP模拟测试28「阴阳·虎·山洞」的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。