hihoCoder编程练习赛52

题目1 : 字符串排序

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

一般我们在对字符串排序时，都会按照字典序排序。当字符串只包含小写字母时，相当于按字母表"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
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 int ord[26];
 9 
10 struct Node{
11     string str;
12     bool operator<(Node x) const{
13         int len1 = str.length();
14         int len2 = x.str.length();
15         for(int i = 0; i < len1 && i < len2; i++){
16             if(str[i] == x.str[i])continue;
17             return ord[str[i]-'a'] < ord[x.str[i]-'a'];
18         }
19         if(len1 < len2)return true;
20         else return false;
21     }
22 }node[1010];
23 
24 int main()
25 {
26     int n;
27     string str;
28     while(cin>>n){
29         cin>>str;
30         for(int i = 0; i < 26; i++){
31             ord[str[i]-'a'] = i;
32         }
33         for(int i = 0; i < n; i++){
34             cin>>node[i].str;
35         }
36         sort(node, node+n);
37         for(int i = 0; i < n; i++)
38               cout<<node[i].str<<endl;
39     }
40 
41     return 0;
42 }
View Code
 1 import java.util.Arrays;
 2 import java.util.Scanner;
 3 
 4 public class Main {
 5     
 6     public static void main(String[] args) {
 7         Scanner cin = new Scanner(System.in);
 8         int n;
 9         String str;
10         while(cin.hasNext()) {
11             n = cin.nextInt();
12             str = cin.next();
13             Node.calOrd(str);
14             Node[] nodes = new Node[n];
15             for(int i = 0; i < n; i++) {
16                 String ss = cin.next();
17                 nodes[i] = new Node(ss);
18             }
19             Arrays.sort(nodes);
20             for(Node node: nodes) {
21                 System.out.println(node.sb.toString());
22             }
23         }
24     }
25 }
26 
27 class Node implements Comparable<Node>{
28     static int[] ord = new int[26];
29     public String sb;
30     
31     Node(String _str) {
32         this.sb = _str;
33     }
34     
35     static public void calOrd(String str) {
36         for(int i = 0; i < 26; i++) {
37             ord[str.charAt(i)-'a'] = i;
38         }
39     }
40     
41     public void setSb(String _sb) {
42         this.sb = _sb;
43     }
44     
45     public int compareTo(Node x) {
46         int len1 = sb.length();
47         int len2 = x.sb.length();
48         for(int i = 0; i < len1 && i < len2; i++) {
49             if(sb.charAt(i) == x.sb.charAt(i))continue;
50             return ord[sb.charAt(i)-'a'] < ord[x.sb.charAt(i)-'a'] ? -1 : 1;
51         }
52         if(len1 < len2)return -1;
53         else return 1;
54     }
55 }
Java

题目2 : 亮灯方案

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

NxM盏灯组成了一个N行M列的矩阵，其中有些(至少一盏)灯是亮的，有些(至少一盏)是灭的。

现在小Hi希望点亮全部的灯。他每次可以选择一盏熄灭的灯点亮，前提是这盏灯与至少一盏亮的灯相邻(上下左右四个方向）。

请你计算小Hi一共有多少种不同的点亮顺序。

输入

第一行包含两个整数N和M。(1 <= N * M <= 20)  

以下N行M列是一个01矩阵，0代表灭，1代表亮。

输出

一个整数代表答案

样例输入
2 2
10
00
样例输出
4
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <map>
 6 
 7 using namespace std;
 8 
 9 const int dx[4] = {0, 1, 0, -1};
10 const int dy[4] = {1, 0, -1, 0};
11 map<string, long long> dp;
12 string M[25];
13 int n, m;
14 
15 bool isOK(int x, int y){
16     for(int i = 0; i < 4; i++){
17         int nx = x + dx[i];
18         int ny = y + dy[i];
19         if(nx < 0 || nx >= n || ny < 0 || ny >= m)
20           continue;
21         if(M[nx][ny] == '1')return true;
22     }
23     return false;
24 }
25 
26 string toString(){
27     string str(n*m, '0');
28     for(int i = 0; i < n; i++)
29       for(int j = 0; j < m; j++)
30         str[i*m+j] = M[i][j];
31     return str;
32 }
33 
34 long long dfs(int mie){
35     if(mie == 1)return 1;
36     if(dp[toString()] != 0)return dp[toString()];
37     dp[toString()] = 0;
38     long long sum = 0;
39     for(int i = 0; i < n; i++){
40         for(int j = 0; j < m; j++){
41             if(M[i][j] == '0' && isOK(i, j)){
42                 M[i][j] = '1';
43                 sum += dfs(mie-1);
44                 M[i][j] = '0';
45             }
46         }
47     }
48     return dp[toString()] = sum;
49 }
50 
51 int main()
52 {
53     while(cin>>n>>m){
54         int mie = 0;
55         dp.clear();
56         for(int i = 0; i < n; i++){
57             cin>>M[i];
58             for(int j = 0; j < m; j++){
59                 if(M[i][j] == '0')mie++;
60             }
61         }
62         cout<<dfs(mie)<<endl;
63     }
64 
65     return 0;
66 }
View Code
 1 import java.util.Arrays;
 2 import java.util.HashMap;
 3 import java.util.Map;
 4 import java.util.Scanner;
 5 
 6 public class Main {
 7     static int[] dx = {0, 1, 0, -1};
 8     static int[] dy = {1, 0, -1, 0};
 9     static StringBuilder[] M = new StringBuilder[20];
10     static int n, m;
11     static Map<String, Long> dp = new HashMap<String, Long>();
12     
13     static String MtoString() {
14         StringBuilder sb = new StringBuilder("");
15         for(int i = 0; i < n; i++) {
16             sb.append(M[i]);
17         }
18         return sb.toString();
19     }
20     
21     static boolean isOK(int x, int y) {
22         for(int i = 0; i < 4; i++){
23             int nx = x + dx[i];
24             int ny = y + dy[i];
25             if(nx < 0 || nx >= n || ny < 0 || ny >= m)
26               continue;
27             if(M[nx].charAt(ny) == '1')return true;
28         }
29         return false;
30     }
31     
32     static long dfs(int mie) {
33         if(mie == 1)return 1;
34         if(dp.get(MtoString()) != null)return dp.get(MtoString());
35         long sum = 0;
36         for(int i = 0; i < n; i++){
37             for(int j = 0; j < m; j++){
38                 if(M[i].charAt(j) == '0' && isOK(i, j)){
39                     M[i].setCharAt(j, '1');
40                     sum += dfs(mie-1);
41                     M[i].setCharAt(j, '0');
42                 }
43             }
44         }
45         dp.put(MtoString(), sum);
46         return sum;
47     }
48     
49     public static void main(String[] args) {
50         Scanner cin = new Scanner(System.in);
51         
52         int mie;
53         while(cin.hasNext()) {
54             dp.clear();
55             n = cin.nextInt();
56             m = cin.nextInt();
57             mie = 0;
58             for(int i = 0; i < n; i++) {
59                 M[i] = new StringBuilder(cin.next());
60                 for(int j = 0; j < m; j++)
61                     if(M[i].charAt(j) == '0')
62                         mie++;
63             }
64             System.out.println(dfs(mie));
65         }
66     }
67 }
Java

题目3 : 部门聚会

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小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
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 
 7 using namespace std;
 8 
 9 const int N = 100005;
10 
11 double dp[N][2];
12 int arr[N], fa[N];
13 vector<int> vec[N];
14 
15 void dfs(int rt){
16     int len = vec[rt].size();
17     dp[rt][1] = arr[rt]*1.0;
18     for(int i = 0; i < len; i++)
19           dfs(vec[rt][i]);
20     for(int i = 0; i < len; i++){
21         dp[rt][0] += max(dp[vec[rt][i]][0], dp[vec[rt][i]][1]);
22         dp[rt][1] += max(dp[vec[rt][i]][1] - 0.5*arr[vec[rt][i]], dp[vec[rt][i]][0]);
23     }
24 }
25 
26 int main()
27 {
28     int n;
29     while(cin>>n){
30         memset(dp, 0, sizeof(dp));
31         for(int i = 1; i <= n; i++){
32             cin>>arr[i];
33             fa[i] = -1;
34             vec[i].clear();
35         }
36         int u, v;
37         for(int i = 0; i < n-1; i++){
38             cin>>u>>v;
39             fa[v] = u;
40             vec[u].push_back(v);
41         }
42         int root = 1;
43         while(fa[root] != -1)root = fa[root];
44         dfs(root);
45         printf("%.1f
", max(dp[root][0],dp[root][1]));
46     }
47 
48     return 0;
49 }
View Code
 1 import java.util.*;
 2 
 3 public class Main {
 4     static final int N = 100005;
 5     static double[][] dp = new double[N][2];
 6     static int [] arr = new int[N];
 7     static int [] fa = new int[N];
 8     static Vector<Integer> [] vec = new Vector[N];
 9     
10     static void dfs(int rt) {
11         int len = vec[rt].size();
12         dp[rt][1] = arr[rt];
13         for(int v: vec[rt]) {
14             dfs(v);
15         }
16         for(int v: vec[rt]) {
17             dp[rt][0] += Math.max(dp[v][0], dp[v][1]);
18             dp[rt][1] += Math.max(dp[v][1]-0.5*arr[v], dp[v][0]);
19         }
20     }
21     
22     public static void main(String[] args) {
23         Scanner cin = new Scanner(System.in);
24         
25         int n;
26         while(cin.hasNext()) {
27             n = cin.nextInt();
28             for(int i = 1; i <= n; i++) {
29                 dp[i][0] = dp[i][1] = 0;
30                 arr[i] = cin.nextInt();
31                 fa[i] = -1;
32                 vec[i] = new Vector<Integer>();
33             }
34             int u, v;
35             for(int i = 0; i < n-1; i++) {
36                 u = cin.nextInt();
37                 v = cin.nextInt();
38                 fa[v] = u;
39                 vec[u].add(v);
40             }
41             int root = 1;
42             while(fa[root] != -1)root = fa[root];
43             dfs(root);
44             System.out.printf("%.1f
", Math.max(dp[root][0], dp[root][1]));
45         }
46     }
47 }
Java
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Penn000/p/8647096.html