湖南雅礼培训 1.1
練習賽
一、題目概覽
| 中文題目名稱 | 樹 | 紅與藍 | 猜數列 |
| 英文題目名稱 | tree | rab | hidden |
| 可執行文件名 | tree | rab | hidden |
| 輸入文件名 | tree.in | rab.in | hidden.in |
| 輸出文件名 | tree.out | rab.out | hidden.out |
| 時間限制 | 1s | 1s | 1s |
| 空間限制 | 256MB | 256MB | 256MB |
| 測試點數目 | 10 | 10 | 25 |
| 測試點分值 | 10 | 10 | 4 |
| 題目類型 | 傳統 | 傳統 | 傳統 |
| 比較方式 | 全文比較 | spj | 全文比較 |
| 是否有部分分 | 否 | 是 | 否 |
?
?
?
二、注意事項：
1.文件名（程序名和輸入輸出文件名）必須使用小寫。
2.C/C++中函數main()的返回值類型必須是int，程序正常結束時的返回值必須是0。
3.開啟O2優化，棧空間開大至256M。
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
樹（tree）
【題目描述】
??? 有n個點，第i個點的限制為度數不能超過ai。
??? 現在對于每一個s(1<=s<=n)，問從這n個點中選出s個點組成有標號無根樹的方案數。
【輸入數據】
?????? 第一行一個整數表示n。
?????? 第二行n個整數a1~an。
【輸出數據】
一個n個整數，第i個整數表示s=i時的答案。
答案模1004535809
【樣例輸入】
3
2 2 1
【樣例輸出】
?????? 3 3 2
【數據范圍】
?????? 對于20%的數據，n≤6。
對于60%的數據，n≤50。
對于100%的數據，n≤100。
?
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define maxn 101 #define mod 1004535809 using namespace std; int n,a[maxn],ans[maxn],t[maxn],num,b[maxn]; bool vis[maxn]; void dfs2(int pos){if(pos==num-1){ans[num]++;if(ans[num]>=mod)ans[num]-=mod;return;}for(int i=1;i<=num;i++){int ii=b[i];if(t[ii]!=a[ii]-1){t[ii]++;dfs2(pos+1);t[ii]--;}} } void dfs1(int pos,int id){if(pos==n+1){return;}for(int i=id;i<=n;i++){if(!vis[i]){b[pos]=i;vis[i]=1;if(pos>=3)num=pos,dfs2(1);dfs1(pos+1,i+1);vis[i]=0;}} } int main(){ // freopen("Cola.txt","r",stdin);freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1);for(int i=n;i>=1;i--){if(a[i]>n-1)a[i]=n-1;else break;}ans[1]=n;ans[2]=(n-1)*n/2;dfs1(1,1);for(int i=1;i<=n;i++)printf("%d ",ans[i]);return 0; } 暴力 #include<iostream> #include<cstdio> #define maxn 101 #define mod 1004535809 int n,m,ans,f[maxn][maxn][maxn*2],a[maxn],c[maxn*2][maxn]; int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);a[i]=min(a[i],n);a[i]--;}c[0][0]=1;for(int i=1;i<=n;i++){c[i][0]=1;for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}f[0][0][0]=1;//到第i個點，選了j個點，purfer數列中有k個點的方案數 for(int i=0;i<n;i++)for(int k=0;k<n;k++)for(int j=0;j<=n;j++)if(f[i][k][j]){f[i+1][k][j]=(f[i+1][k][j]+f[i][k][j])%mod;for(int t=0;t<=a[i+1];t++)(f[i+1][k+1][j+t]+=1LL*f[i][k][j]*c[j+t][t]%mod)%=mod;}for(int k=1;k<=n;j++){if(k==1)ans=n;else ans=f[n][k][k-2];ans=(ans+mod)%mod;printf("%d ",ans);}return 0; } 100分 purfer數列dp?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
紅與藍（rab）
【題目描述】
??? 給定一棵樹，初始時非葉節點均為無色，葉節點會是紅色、藍色或無色。
?????? 小紅和小藍輪流給無色葉子染色（小紅染紅色，小藍染藍色，小紅先染）。所有葉子染完后，非葉節點的顏色將被逐一確定：一個非葉節點的顏色是它所有兒子的顏色中出現較多的那個（保證有奇數個兒子）。最后，根是誰的顏色誰就獲勝。
?????? 求小紅是否能贏，若能贏，求出第一步選擇哪些葉子能贏。
【輸入數據】
?????? 第一行一個整數t表示數據組數。
?????? 每組數據第一行一個整數n表示節點數。
第二行n個整數，第i個整數fi表示i的父親，保證f1=0。
第三行n個整數，第i個整數gi表示i的初始顏色（0表示紅色，1表示藍色，-1表示無色）。
【輸出數據】
每組數據輸出一行。
若小紅能贏，先輸出一個整數m表示第一步可以選的葉子數，接下來m個整數表示那些葉子的編號，從小到大輸出。若你只知道小紅能贏，你可以只輸出一行一個整數0。
否則輸出一個整數-1。
【樣例輸入】
2
2
0 1
-1 -1
2
0 1
-1 1
【樣例輸出】
?????? 1 2
?????? -1
【數據范圍】
?????? 對于20%的數據，t=1，n≤20。
對于60%的數據，n≤2000。
對于100%的數據，t<=10，n≤100000。
若你只判斷對了勝負，可以獲得該測試點一半的分數。
?
?
?
?
?
?
?
?
猜數列（hidden）
【題目描述】
有一個長度為m的，由1到9之間的數構成的未知數列a。
你現在有n個線索，每個線索都是用如下方式生成的：
（1）選擇序列a的某一個位置p作為開始；
（2）選擇某個方向（向左或向右）；
（3）從p出發往你選擇的方向走，每遇到一個之前未出現的數就將它加到線索中。
現在你需要求出滿足所有線索的長度最小的序列的長度。
【輸入數據】
輸入文件的第一行為一個整數n，表示線索的數量。
接下來n行，每行有若干個以0結尾的整數，表示一條線索。保證一條線索中的數在[1,9]中且不會出現相同的數。
【輸出數據】
如果無解請輸出-1，否則輸出可能的最小長度。
【樣例輸入1】
?????? 5
1 2 0
3 4 0
1 4 3 0
3 1 4 2 0
1 2 4 3 0
【樣例輸出1】
?????? 7
【樣例輸入2】
3
1 2 0
2 3 0
3 4 0
【樣例輸出2】
?????? -1
【數據范圍】
對于20%的數據，答案不超過10。
對于另外40%的數據，保證存在一個最優解，使得所有線索都可以通過向右遍歷得到。
對于100%的數據，1≤n≤10。
轉載于:https://www.cnblogs.com/thmyl/p/8167958.html
總結
以上是生活随笔為你收集整理的湖南雅礼培训 1.1的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 第三天会议
- 下一篇： rank() over,dense_ra