hihocoder编程练习赛52
A
描述
一般我们在对字符串排序时，都会按照字典序排序。当字符串只包含小写字母时，相当于按字母表”abcdefghijklmnopqrstuvwxyz”的顺序排序。
现在我们打乱字母表的顺序，得到一个26个字母的新顺序。例如”bdceafghijklmnopqrstuvwxyz”代表’b’排在’d’前，’d’在’c’前，’c’在’e’前……
给定N个字符串，请你按照新的字母顺序对它们排序。
输入
第一行包含一个整数N。(1 <= N <= 1000)
第二行包含26个字母，代表新的顺序。
以下N行每行一个字符串S。 (|S| <= 100)
输出
按新的顺序输出N个字符串，每个字符串一行。
样例输入
5
bdceafghijklmnopqrstuvwxyz
abcde
adc
cda
cad
ddc
样例输出
ddc
cda
cad
abcde
adc
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| using namespace std; int n; string s1,s2[maxn]; map<char,char>mp1,mp2; int main(){ // freopen("input.txt","r",stdin); cin>>n; cin>>s1; mp1.clear(),mp2.clear(); for(int i=0;i<26;i++){ mp1[s1[i]]=i+'a'; mp2[i+'a']=s1[i]; } for(int i=1;i<=n;i++){ cin>>s2[i]; int len=s2[i].length(); for(int j=0;j<len;j++) s2[i][j]=mp1[s2[i][j]]; } sort(s2+1,s2+1+n); for(int i=1;i<=n;i++){ int len=s2[i].length(); for(int j=0;j<len;j++) s2[i][j]=mp2[s2[i][j]]; cout<<s2[i]<<endl; } return 0; }
|
思路
两个map双向映射
把原来的字母映射成abcd··· 然后用sring直接sort 再映射回去
B
C
描述
小Hi在Hihoole公司的实习期结束了。在回学校前，他决定请部门所有同事来住所聚会。
已知小Hi一共有N名同事，编号1~N，其中第i名同事的酒量是Ai。
这N名同事的上下级关系恰好组成一棵树型结构。对于第i名同事来说，如果他的直接上级没有出席聚会，他会喝掉Ai单位的酒；如果他的直接上级出席了聚会，他会有所收敛，只喝掉Ai/2单位的酒。
小Hi想知道，自己至少要准备多少单位的酒，才能保证无论哪些人出席聚会，酒都够喝。
输入
第一行包含一个整数N。(1 <= N <= 100000)
第二行包含N个整数，A1, A2, … AN。(0 <= Ai <= 100000)
以下N-1行每行包含两个整数u和v，代表u是v的直接上级。
输出
小Hi至少需要准备的酒量，保留1位小数。
样例输入
5
5 2 4 1 4
2 4
2 1
1 5
1 3
样例输出
10.5
参考AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| using namespace std; vector<int>e[maxn]; int n,root; int a[maxn],in[maxn],out[maxn]; double dp[maxn][2]; void dfs(int x){ if(out[x]==0){ dp[x][0]=0.0; dp[x][1]=(double)a[x]; return; } double sum1=0.0,sum2=0.0; for(int i=0;i<e[x].size();i++){ int nextx=e[x][i]; dfs(nextx); sum1+=max(dp[nextx][0],dp[nextx][1]); //根不参加 sum2+=max(dp[nextx][0],dp[nextx][1]-a[nextx]/2.0); //根参加 } dp[x][0]=sum1; dp[x][1]=(double)a[x]+sum2; } int main(){ // freopen("input.txt","r",stdin); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; memset(in,0,sizeof in); memset(out,0,sizeof out); memset(dp,0,sizeof dp); for(int i=1;i<n;i++){ int x,y; cin>>x>>y; e[x].push_back(y); in[y]++,out[x]++; } root=0; for(int i=1;i<=n;i++){ if(in[i]==0){ root=i; break; } } dfs(root); printf("%.1lf\n",max(dp[root][0],dp[root][1])); return 0; }
|
思路
树形dp
dp[x][0]表示x号结点不参加获得的最大价值
dp[x][1]表示x号结点参加获得的最大价值
无根树换有根树
转移方程：
dp[x][0]=子树max(dp[next][0],dp[next][1])求和
dp[x][1]=子树max(dp[nextx][0],dp[nextx][1]-a[nextx]/2.0) 根参加 所有子树参加的价值要减去自身的一半
