🍻 正在加载今日诗词....

1004 Counting Leaves (30分)

1. 题目

A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.

Input Specification:
Each input file contains one test case. Each case starts with a line containing 0<N<100, the number of nodes in a tree, and M (<N), the number of non-leaf nodes. Then M lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]
where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.

The input ends with N being 0. That case must NOT be processed.

Output Specification:
For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.

The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output 0 1 in a line.

2. 样例输入

2 1 01 1 02

3. 样例输出

0 1

4. 思路

这题的话使用dfs把整棵树遍历一遍,统计一下叶子节点就行啦
还是非常简单的

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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define maxn 10000
vector<int> G[maxn];
int level[maxn],maxdepth=-1;
void dfs(int node,int depth){
    if(G[node].size()==0){
        level[depth]++;
        maxdepth=max(depth,maxdepth);
        return;
    }
    for(int i=0;i<G[node].size();i++){
        dfs(G[node][i],depth+1);
    }
}

int main() {
	int n,m;scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++){
        int node,k;
        scanf("%d %d",&node,&k);
        for(int j=0;j<k;j++){
            int temp;scanf("%d",&temp);
            G[node].push_back(temp);
        }
    }
    dfs(1,0);
    printf("%d",level[0]);
    for(int i=1;i<=maxdepth;i++){
        printf(" %d",level[i]);
    }
    system("pause");
	return 0;
}

展开全文 >>

1003 Emergency (25分)

1. 题目

2. 样例输入

5 6 0 2 1 2 1 5 3 0 1 1 0 2 2 0 3 1 1 2 1 2 4 1 3 4 1

3. 样例输出

2 4

4. 思路

第一次做的时候还图样图森破
第一次遇见图的时候是完全懵逼的
不过现在回过头来看图的题还是非常简单的…
说起图想起一个技巧就是#define maxn 1000000www
这题需要用迪杰斯特拉算法将题目中的最短路径算出,然后在路径长度的情况下比较他们能获得的人力资源,最多的就是最优解

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
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <algorithm>
using namespace std;
#define Maxn 505
#define inf 99999
int City[Maxn][Maxn];
int manpower[Maxn];
int dist[Maxn];
bool vis[Maxn]{ false };
int W[Maxn];
int num[Maxn];
int N, M, start, result;

int main() {
	cin >> N >> M >> start >> result;
	for (int n = 0; n < N; n++) {
		cin >> manpower[n];
	}
	fill(City[0],City[0] + Maxn*Maxn, inf);
	fill(dist, dist + Maxn, inf);
	for (int n = 0; n < M; n++) {
		int a, b; cin >> a >> b;
		cin >> City[a][b];
		City[b][a] = City[a][b];
	}
	dist[start] = 0;
	W[start] = manpower[start];
	num[start] = 1;
	for (int n = 0; n < N; n++) {
		int min = inf, u = -1;
		for (int m = 0; m < N; m++) {
			if (vis[m] == false && dist[m] < min) {
				min = dist[m];
				u = m;
			}
		}
		if (u == -1)break;
		vis[u] = true;
		for (int i = 0; i < N; i++) {
			if (vis[i] == false && City[u][i] != inf) {
				if (dist[u] + City[u][i] < dist[i]) {
					dist[i] = dist[u] + City[u][i];
					num[i] = num[u];
					W[i] = W[u]+manpower[i];
				}
				else if (dist[u] + City[u][i] == dist[i]) {
					num[i] = num[i] + num[u];
					if (W[u] + manpower[i] > W[i]) {
						W[i] = W[u] + manpower[i];
					}
				}
			}
		}
	}
	cout << num[result] << " " << W[result];
	return 0;
}

展开全文 >>

1002 A+B for Polynomials (25分)

1. 题目

2. 样例输入

2 1 2.4 0 3.2
2 2 1.5 1 0.5

3. 样例输出

3 2 1.5 1 2.9 0 3.2

4. 思路

我记得这是何老师讲过的一道题
非常的经典，但是我没用何老师的解法
主要是map太好用辣！！！

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
#include <iostream>
#include <iomanip>
#include <map>
using namespace std;

int main() {
	int a, b;
	map<int, double>mp;
	cin >> a;
	for (int n = 0; n < a; n++) {
		int e;
		double c;
		cin >> e >> c;
		mp[e] = c;
	}
	cin >> b;
	for (int n = 0; n < b; n++) {
		int e;
		double c;
		cin >> e >> c;
		mp[e] += c;
		if (mp[e] == 0) {
			mp.erase(e);
		}
	}
	cout << mp.size();
	for (auto it = mp.rbegin(); it != mp.rend(); it++) {
		printf(" %d %.1f", it->first, it->second);
	}
	return 0;
}

展开全文 >>

1001 A+B Format (20分)

梦开始的地方

1. 题目

2. 样例输入

-1000000 9

3. 样例输出

-999,991

4. 思路

看起来挺简单
注意一点就是要判断是不是最后一位的情况，要不然会造成输出-，999，991

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
# include <cstdio>
# include <iostream>
using namespace std;
 
int main(){
    int a,b;
    cin >> a >> b;
    int ans = a+b;
    if (ans==0)
        printf("0");
    else{
        if (ans<0){
            printf("-");
            ans = - ans;
        }
        int s[10000],e=0;
        while (ans){
            s[e++] = ans%1000;
            ans  = ans/1000;
        }
        printf("%d",s[--e]);
        while (e--){
            printf(",%03d",s[e]);
        }
    }
    cout << endl;
    return 0;
}

展开全文 >>

许久不更新

好久不写博客了，主要是因为懒，搭建的博客并没有那些网上的那么容易维护，只能定期把博客给更上
写一次博客就得花挺多时间的，而且最近也很忙，没空更新，PAT到时候会一起把题解放上来的~~

不说了，该学数学了

展开全文 >>

PAT-A-1068

1. A1068

1.1. 题目

1.2. 样例输入&&样例输出

1.3. 思路

0 1背包问题，是你最爱的动态规划
XD动态规划看了就有点害怕，不过学了还是能理解一些的
关于动态规划1还有2能帮助你理解一些动态规划背包问题

1.4. 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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int w[10004], dp[103] = { 0 };
bool flag[10004] = { false };
bool choice[10004][103] = { false };
bool cmp(int a, int b) {
    return a > b;
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
    }
    sort(w + 1, w + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        for (int v = m; v >= w[i]; v--) {
            if (dp[v] <= dp[v - w[i]] + w[i]) { //如果放入i 
                dp[v] = dp[v - w[i]] + w[i];
                choice[i][v] = true;
            }
        }
    }
    if (dp[m] != m)
        puts("No Solution");
    else {
        int k = n, num = 0, v = m;
        while (k > 0) {
            if (choice[k][v] == true) {
                flag[k] = true;
                v -= w[k];
                num++;
            }
            k--;
        }
        for (int i = n; i >= 1; i--) {
            if (flag[i]) {
                printf("%d", w[i]);
                num--;
                if (num > 0) putchar(' ');
            }
        }
    }
    return 0;
}

展开全文 >>

PAT-A-1064

1. A 1060

1.1. 题目

1.2. 样例输入&&样例输出

1.3. 思路

因为搜索树他的中序遍历是有序的，所以我们可以利用这一点来建树
可以使用数组建树使得代码更加的简洁

1.4. 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
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#define maxn 10000
int N,index=0;
int number[maxn]; int BST[maxn];
void inorder(int root) {
	if (root > N)return;
	inorder(root * 2);
	BST[root] = number[index++];
	inorder(root * 2 + 1);
}

bool cmp(int a, int b) {
	return a < b;
}

int main() {
	cin >> N;
	for (int n = 0; n < N; n++) {
		cin >> number[n];
	}
	sort(number, number + N, cmp);
	inorder(1);
	for (int n = 1; n <= N; n++) {
		cout << BST[n];
		if (n != N)cout << " ";
	}
	return 0;
}

展开全文 >>

PAT-A-1060

1. A1060

1.1. 题目：

1.2. 样例输入&输出：

1.3. 思路：

就是按着题目走，不过有坑点就是前导零的问题，
例如他输入3 0.000 0你得输出 YES 0.00010^0
输入5 000010.013 10.012 你得输出 NO 0.1001310^2 0.10012*10^2
真是成也零 败也零啊

1.4. AC代码：

这里参考的算法笔记上面的代码，我自己的代码没过前导零o(´^｀)o

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
48
49
50
51
52
53
#include <iostream>
#include <string>
using namespace std;
int N;
string deal(string s, int& e) {
	int k = 0;
	while (s.size() > 0 && s[0] == '0') {
		s.erase(s.begin());
	}
	if (s[0] == '.') {
		s.erase(s.begin());
		while (s.size() > 0 && s[0] == '0') {
			s.erase(s.begin());
			e--;
		}
	}
	else {
		while (k<s.size() && s[k] != '.') {
			k++;
			e++;
		}
		if (k < s.size()) {
			s.erase(s.begin() + k);
		}
	}
	if (s.size() == 0) {
		e = 0;
	}
	int num = 0;
	k = 0;
	string res;
	while (num < N) {
		if (k < s.size())res += s[k++];
		else res += '0';
		num++;
	}
	return res;
}

int main() {
	string s1, s2, s3, s4;
	cin >> N >> s1 >> s2;
	int e1 = 0, e2 = 0;
	s3 = deal(s1, e1);
	s4 = deal(s2, e2);
	if (s3 == s4 && e1 == e2) {
		cout << "YES 0." << s3 << "*10^" << e1;
	}
	else {
		cout << "NO 0." << s3 << "*10^" << e1 << " 0." << s4 << "*10^" << e2;
	}
	return 0;
}

展开全文 >>

PAT A 1057

A1057

题目：

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop

样例输出：

1
2
3
4
5
6
7
8
9
10
11
12
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

思路：

这题讲的是线段树！！或者分块法（分桶法），比较难，先看看树状数组的做法吧。

PS：emmm关于树状数组：1

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
# include <cstdio>
# include <stack>
using namespace std;
class BIT
{
private:
	int* Elem;
	int Size;
	int lowbit(int n)
	{
		return n & (-n);
	}
public:
	BIT(int size) :Size(size + 1)  /*想想看还是+1好了，要不申请了100的空间只能用到99感觉太奇怪了*/
	{
		Elem = new int[Size];
		for (int i = 0; i < Size; i++)/*还没试过用memset初始化，下次试试*/
			Elem[i] = 0;
	}
	int GetSum(int right)/*[0,right]*/
	{
		int sum = 0;
		while (right)
		{
			sum += Elem[right];
			right -= lowbit(right);
		}
		return sum;
	}
	int GetSum(int left, int right)/*[left,right]*/
	{
		return GetSum(left - 1) - GetSum(right);
	}
	void Add(int value, int index)
	{
		while (index < Size)
		{
			Elem[index] += value;
			index += lowbit(index);
		}
	}
	~BIT()
	{
		delete[] Elem;
	}
};
BIT bit(100000);
int getmid(int size)
{
	int index = (size + 1) / 2;
	int left = 1, right = 100000, mid;
	while (left < right)
	{
		mid = (left + right) / 2;
		if (bit.GetSum(mid) < index)
			left = mid + 1;
		else
			right = mid;
	}
	return left;
}
int main()
{
	int n, tmp;
	scanf("%d", &n);
	stack<int> s;
	char str[10];
	while (n--)
	{
		scanf("%s", str);
		switch (str[1])
		{
		case 'e':
		{
			if (s.empty())
				printf("Invalid\n");
			else
				printf("%d\n", getmid(s.size()));
			break;
		}
		case 'o':
		{
			if (s.empty())
				printf("Invalid\n");
			else
			{
				tmp = s.top(); s.pop();
				printf("%d\n", tmp);
				bit.Add(-1, tmp);
			}
			break;
		}
		case 'u':
		{
			scanf("%d", &tmp); s.push(tmp);
			bit.Add(1, tmp);
		}
		break;
		}
	}
	return 0;
}

这个是一位大佬的代码，其实也可以用zkw线段树来做

zkw线段树

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
# include <cstdio>
# include <stack>
using namespace std;
 
typedef int Node;
class zkw_segtree
{
private:
    Node *T;
	int size;
public:
    zkw_segtree(int range)
	{
	    for (size = 1;size < range+2;size<<=1);
	    T = new Node[2*size];
	    for (int i=1;i<size+size;i++)
		    T[i] = 0;    
	} 
	void Add(int value,int i)
    {
	    for (i+=size;i;i>>=1)
	        T[i] += value;
	}
	int Query(int s,int t)
	{
	    int ret = 0;
	    for (s+=size-1,t+=size+1;s^t^1;s>>=1,t>>=1)
	        {
			  if (~s^1) ret += T[s^1];
			  if (t^1)  ret += T[t^1]; 
			}
	    return ret;
	}
	int Find_Kth(int k,int root = 1)
	{
	    while (root<<1 < size<<1)
		{
		  if (T[root<<1]>=k)  root = root<<1;
          else 
		    {
			  k -= T[root<<1];
			  root = (root<<1) + 1;
		    }
		}		    
	    return root - size;
	}
	~zkw_segtree()
	{
	    delete[] T;
	}
};
zkw_segtree segtree(100000);
int main()
{
  int n,tmp;
  scanf("%d",&n);
  stack<int> s;
  char str[10];
  while (n--)
  {
      scanf("%s",str);
      switch(str[1])
      {
	      case 'e':
		      {
			  if (s.empty()) 
			      printf("Invalid\n");
			  else 
			      printf("%d\n",segtree.Find_Kth((s.size()+1)/2));
			  break;
			  }
	      case 'o':
		      {
    	      if (s.empty())
    	          printf("Invalid\n");
	          else 
                  {
          	      tmp = s.top();s.pop();
          	      printf("%d\n",tmp);
                  segtree.Add(-1,tmp);
				  }
			  break;
			  }
	      case 'u':
		  	  {
	              scanf("%d",&tmp);s.push(tmp);
                  segtree.Add(1,tmp);
			  }
			  break;
	  }
  }
  return 0;
}

时间效率是最快的，不愧是大佬(^▽^)

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

计算机菜狗<br><br>什么都会一点<br>什么都不擅长