?

?

T1

?

Problem 1. spread
Input file:spread.in
Output file:spread.out
Time limit:1 second
Memory limit:256 MB
Darrell 所在的國家有 N 個城市，共有 N 1 條輸水管道連接它們，使得任意兩個城市都可以通過這些
輸水管道連接起來。
有一種破壞力極強的病毒被發現帶入了境內，但不知道在哪個城市，現在已知如果病毒在 u 號城市爆發，
則其會隨著輸水管道向向周圍的城市不斷擴散，但因為一些原因，擴散的速度有可能不一致。
問題是，如果 u 號城市爆發病毒，則一段時間后可能的擴散情況有多少種？你需要對每個城市回答該問
題。（答案可能很大，你只需要輸出取模 10
9
+ 7 的結果即可）。
Input
第 1 行，有 1 個整數 N，表示城市數目。
接下來 N 1 行，每行 2 個整數：u v，表示城市 u 和 v 之間有輸水管道。
Output
輸出 1 行，包含 N 個整數，第 i 個整數表示 i 號城市爆發病毒對應的答案。
Sample
spread.inspread.out
4
1 2
2 3
2 4
5 8 5 5
Note
樣例中，如果 1 號城市爆發病毒，則可能的擴散情況有：[1],[1;2],[1;2;3],[1;2;4],[1;2;3;4]，共 5 種。
如果 2 號城市爆發病毒，則可能的擴散情況有：[2],[2;1],[2;3],[2;4],[2;1;3],[2;3;4],[2;1;4],[2;1;3;4]，共 8
種。

DP+換根

//By SiriusRen #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N=200500,mod=1000000007; int n,a[N],first[N],next[N],v[N],tot,xx,yy,f[N],g[N]; void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;} void dfs(int x,int fa){f[x]=1;int r=1;for(int i=first[x];~i;i=next[i])if(v[i]!=fa){dfs(v[i],x);r=(1ll*r*f[v[i]])%mod;}f[x]=(f[x]+r)%mod; } int pow(int x,int y){int r=1;while(y){if(y&1)r=1ll*r*x%mod;x=1ll*x*x%mod,y>>=1;}return r; } void dfs2(int x,int fa){for(int i=first[x];~i;i=next[i])if(v[i]!=fa){g[v[i]]=((1ll*(g[x]-1+mod)%mod*pow(f[v[i]],mod-2)%mod+1)%mod*((f[v[i]]-1+mod)%mod)+1)%mod;dfs2(v[i],x);} } int main(){freopen("spread.in","r",stdin);freopen("spread.out","w",stdout);memset(first,-1,sizeof(first));scanf("%d",&n);for(int i=2;i<=n;i++)scanf("%d%d",&xx,&yy),add(xx,yy),add(yy,xx);dfs(1,0);g[1]=f[1];dfs2(1,0);for(int i=1;i<=n;i++)printf("%d ",(g[i]-1+mod)%mod); }

T2

Problem 2. sing
Input file:sing.in
Output file:sing.out
Time limit:1 second
Memory limit:256 MB
Darrell 在學唱歌。
Darrell 已經學會了一些發音技巧，比如剛唱完 u 號音符就可以接著唱 v 號音符。
因為一些特殊的原因，如果 Darrell 能夠連續唱出 u1;u2;u3;:::;un，且 u1= u2，那么保證 u1到 un之間
至多有 5 種不同的音符。
Darrell 想自己編一首自己唱的歌，為了獨特，他希望歌中不出現重復的音符，并且想讓歌聲中包含的音
符盡量多，所以，請你告訴他最多能唱多少個音符。
Input
第 1 行，包含 2 個整數：N M，分別表示 Darrell 會唱的音符數及已經掌握了的發音技巧數。
接下來 M 行，每行 2 個整數：u v，表示 Darrell 在唱完 u 后能夠接著唱 v。
Output
輸出 1 個整數，表示答案。
Sample
sing.insing.out
4 5
1 2
2 3
3 4
3 1
2 4
4
樣例解釋：可以連續唱出：3;1;2;4 的音符，所以最多為 4 個音符。
sing.insing.out
7 7
1 2
2 3
3 4
4 5
5 2
4 6
5 7
6
樣例解釋：可以連續唱出 1;2;3;4;5;7 的音符，并且無法不重復地唱出更多的音符，所有所以最多為 6
個音符

?

Tarjan+Topsort+next_permutation

//By SiriusRen #include <bits/stdc++.h> using namespace std; const int N=1000050; vector<int>vec[N];queue<int>q; int n,m,xx,yy,first[N],next[N],v[N],tot,cnt,T,mp[5][5],f[5],d[N][5],ans; int low[N],dfn[N],vis[N],stk[N],p[N],id[N],bl[N][5],sz[N],top,du[N],tmp[N],dis[N]; void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;} void tarjan(int x){dfn[x]=low[x]=++cnt,stk[++top]=x,vis[x]=1;for(int i=first[x];~i;i=next[i])if(!dfn[v[i]])tarjan(v[i]),low[x]=min(low[x],low[v[i]]);else if(vis[v[i]])low[x]=min(low[x],dfn[v[i]]);if(low[x]==dfn[x]){T++;do vis[xx=stk[top--]]=0,bl[T][sz[T]]=xx,p[xx]=T,id[xx]=sz[T]++;while(xx!=x);} } int main(){freopen("sing.in","r",stdin);freopen("sing.out","w",stdout);memset(first,-1,sizeof(first));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d",&xx,&yy),add(xx,yy);for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=T;i++){memset(mp,0,sizeof(mp));for(int j=0;j<sz[i];j++)for(int k=first[bl[i][j]];~k;k=next[k])if(p[v[k]]==i)mp[j][id[v[k]]]=1;for(int j=0;j<sz[i];j++)f[j]=j;do{for(int j=0;j<sz[i];j++){d[bl[i][f[0]]][f[j]]=max(d[bl[i][f[0]]][f[j]],j);if(!mp[f[j]][f[j+1]])break;}}while(next_permutation(f,f+sz[i]));}for(int i=1;i<=n;i++)for(int j=first[i];~j;j=next[j])if(p[v[j]]!=p[i])du[p[v[j]]]++;for(int i=1;i<=T;i++)if(!du[i])q.push(i);while(!q.empty()){int t=q.front();q.pop();for(int i=0;i<sz[t];i++)for(int j=0;j<sz[t];j++)if(i!=j)tmp[bl[t][j]]=max(tmp[bl[t][j]],dis[bl[t][i]]+d[bl[t][i]][j]);for(int i=0;i<sz[t];i++)dis[bl[t][i]]=max(dis[bl[t][i]],tmp[bl[t][i]]);for(int i=0;i<sz[t];i++)for(int j=first[bl[t][i]];~j;j=next[j])if(p[v[j]]!=t){dis[v[j]]=max(dis[v[j]],dis[bl[t][i]]+1),du[p[v[j]]]--;if(!du[p[v[j]]])q.push(p[v[j]]);}}for(int i=1;i<=n;i++)ans=max(ans,dis[i]);printf("%d\n",ans+1); }

T3

Memory limit:256 MB
Darrell 在思考一道計算題。
給你一個尺寸為 1 N 的長條，你可以在上面切很多刀，要求豎直地切并且且完后每塊的長度都是整數。
在這種限制下其實只有 N 1 個位置可以切。
對于一種切的方案，假如切完后每塊的寬度分別是：w1;w2;w3;:::;w
k
（
∑
wi= N），那么該種方案對應
的完美值為：
k∏
i=1
w
2
i
那么問題來了，給出 M 個位置不能切（如果用 x 表示一個位置，那么切完該位置后長條變為 1 x 和
1 (N x) 兩塊），
那么所有合法切法對應的完美值的和是多少呢？（只需要輸出模 10
9
+ 7 的結果）
Input
第 1 行，有 2 個整數：N M，表示長條的總長度及不能切的位置數
第 2 行，有 M 個整數：x1;x2;x3;:::;xM表示不能切的位置。
Output
輸出 1 行，包含 1 個整數，表示滿足要求的所有切法對應的完美值和。（對 10
9
+ 7 取模后的結果）
Sample
count.incount.out
3 1
2
13
樣例解釋：一共有兩種切法（用切完后的塊的寬度表示）：1;2 和 3，則對應答案為：1 2
2
+ 3
2
= 13
count.incount.out
5 2
2 3
66
樣例解釋：一共有四種切法：1;3;1、1;4、4;1 和 5，則對應答案為：1 3
2
1+1 4
2
+4
2
1+5
2
= 66
count.incount.out
10 9
1 2 3 4 5 6 7 8 9
100
因為所有能切的位置都不能切，所以只有一種切法（就是不切）：10，對應答案為：10
2

?

構造一發矩陣+矩陣快速冪

//By SiriusRen #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define int long long const int mod=1000000007,N=100050; int n,m,xx,a[N]; struct Matrix{int a[3][3];void init(){memset(a,0,sizeof(a));} void Ch(){a[0][0]=a[1][0]=a[1][2]=2,a[0][1]=a[0][2]=a[1][1]=a[2][0]=a[2][2]=1;} void Ch2(){a[0][0]=a[0][1]=a[0][2]=a[1][1]=a[2][2]=1,a[1][2]=2;} }cng,cng2,jy; Matrix operator*(Matrix a,Matrix b){Matrix c;c.init();for(int k=0;k<3;k++)for(int i=0;i<3;i++)for(int j=0;j<3;j++)(c.a[i][j]+=a.a[i][k]*b.a[k][j])%=mod;return c; } Matrix operator^(Matrix a,int b){Matrix r;r.init();r.a[0][0]=r.a[1][1]=r.a[2][2]=1;while(b){if(b&1)r=r*a;a=a*a,b>>=1;}return r; } signed main(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);scanf("%lld%lld",&n,&m);for(int i=1;i<=m;i++)scanf("%lld",&a[i]);jy.a[0][0]=1;cng.Ch(),cng2.Ch2();for(int i=1;i<=m;i++)jy=(jy*(cng^(a[i]-a[i-1]-1)))*cng2;jy=jy*(cng^(n-a[m]));printf("%lld\n",jy.a[0][2]); }

?

滿滿的智障氣息.

?

轉載于:https://www.cnblogs.com/SiriusRen/p/7028514.html

總結

以上是生活随笔為你收集整理的0616考试的全部內容，希望文章能夠幫你解決所遇到的問題。

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