算法笔记题目

第三章

3.1

//1 PATB1001
#include <iostream>

int main()
{
    int n;
    std::cin >> n;
    int count = 0;

    while (n!=1)
    {
        if (n%2==0)
        {
            n /= 2;
            count++;
        }
        else
        {
            n = (3 * n + 1) / 2;
            count++;
        }
    }

    std::cout << count << std::endl;

    system("pause");
    return 0;
}
//2 PATB1008
#include <iostream>

int num[100];

int main()
{
    int n, m;
    std::cin >> n >> m;

    for (int i = 0; i < n;i++)
        std::cin >> num[(i + m) % n];

    for (int i = 0; i < n;i++)
    {
        if (i!=n-1)
        {
            std::cout << num[i] << " ";
        }
        else
            std::cout << num[i];
    }

    system("pause");
    return 0;
} 
//3 PATB1011
#include <iostream>

bool Hash[10] = {0};

int main()
{
    using ll = long long;
    int n;
    std::cin >> n;

    ll  a, b, c;
    for (int i = 1; i <= n;i++)
    {
        std::cin >> a >> b >> c;

        if (a+b>c)
        {
            Hash[i] = 1;
        }
    }

    for (int i = 1; i <= n;i++)
    {
        if (Hash[i])
            std::cout << "Case #" << i << ": "
                      << "true" << std::endl;
        else
            std::cout << "Case #" << i << ": "
                      << "false" << std::endl;
    }

    //system("pause");
    return 0;
}
//4 PATB1012
#include<cstdio>

int main() {
	int n;
	int ans[5] = { 0 }, cnt[5] = { 0 }, flag = 1;
	scanf("%d", &n);
	for (int i = 0;i < n;++i) {
		int temp;
		scanf("%d", &temp);
		if (!(temp % 5)){//不可写成逻辑与判断
			if (!(temp % 2)) {
				++cnt[0];
				ans[0] += temp;
			}
		}
		else if (temp % 5 == 1) {
			++cnt[1];
			ans[1] += flag * temp;
			flag *= -1;
		}
		else if (temp % 5 == 2) {
			++cnt[2];
			++ans[2];
		}
		else if (temp % 5 == 3) {
			++cnt[3];
			ans[3] += temp;
		}
		else {
			++cnt[4];
			if (ans[4] < temp) ans[4] = temp;
		}
	}
	if (!cnt[0]) printf("N");
	else printf("%d", ans[0]);
	if (!cnt[1]) printf(" N");
	else printf(" %d", ans[1]);
	if (!cnt[2]) printf(" N");
	else printf(" %d", ans[2]);
	if (!cnt[3]) printf(" N");
	else printf(" %.1f", 1.0 * ans[3] / cnt[3]);
	if (!cnt[4]) printf(" N");
	else printf(" %d", ans[4]);
	return 0;
}
//5 PATB1016
#include <iostream>
#include <string>

int main()
{
    int stra, a, strb, b;
    std::cin >> stra >> a >> strb >> b;
    int counta = 0, countb = 0;

    while (stra)
    {
        int c;
        if ((c=stra%10) == a)
            counta = counta * 10 + a;
        stra /= 10;
    }
    while (strb)
    {
        int c;
        if ((c=strb%10) == b)
            countb = countb * 10 + b;
        strb /= 10;
    }

    std::cout << counta + countb << std::endl;
    system("pause");
    return 0;
}
//6 PATB1018
#include<cstdio>
//B 代表“布” 、C 代表“锤子”、J 代表“剪刀”、，
int main() {
	int n;
	int awin = 0, ab = 0, alose = 0;
	int acnt[3] = { 0 }, bcnt[3] = { 0 };
	scanf("%d", &n);
	while (n--) {
		getchar();
		char a, b;
		scanf("%c %c", &a, &b);
		if (a == 'C') {
			if (b == 'C') ++ab;
			else if (b == 'J') {
				++awin;
				++acnt[1];
			}
			else if (b == 'B') {
				++alose;
				++bcnt[0];
			}
		}
		else if (a == 'J') {
			if (b == 'C') {
				++alose;
				++bcnt[1];
			}
			else if (b == 'J') ++ab;
			else if (b == 'B') {
				++awin;
				++acnt[2];
			}
		}
		else {
			if (b == 'C') {
				++awin;
				++acnt[0];
			}
			else if (b == 'J') {
				++alose;
				++bcnt[2];
			}
			else if (b == 'B') ++ab;
		}
	}

	printf("%d %d %d\n", awin, ab, alose);
	printf("%d %d %d\n", alose, ab, awin);
	int maxa = 0, maxb = 0, a = 0, b = 0;
	for (int i = 0;i < 3;++i) {
		if (acnt[i] > maxa) {
			maxa = acnt[i];
			a = i;
		}
		if (bcnt[i] > maxb) {
			maxb = bcnt[i];
			b = i;
		}
	}
	switch (a) {
	case 0:
		printf("B ");
		break;
	case 1:
		printf("C ");
		break;
	case 2:
		printf("J ");
		break;
	}
	switch (b) {
	case 0:
		printf("B");
		break;
	case 1:
		printf("C");
		break;
	case 2:
		printf("J");
		break;
	}
	return 0;
}
//7 PATB1026
#include <iostream>
#include <cmath>

const int TCK = 100;

int main()
{
    int a, b;
    std::cin >> a >> b;
    
    //注意四舍五入
    int s = (int)round(1.0 * (b - a) / TCK);

    int h = s / 3600;
    int m = (s - h * 3600) / 60;
    int ss = s % 60;

    printf("%02d:%02d:%02d", h, m, ss);
    system("pause");
    return 0;
}
//8 PATB1046
#include <iostream>

int main()
{
    int n;
    std::cin >> n;
    int jia=0, yi=0;
    int a, b, c, d;
    for (int i = 0; i < n;i++)
    {
        std::cin >> a >> b >> c >> d;
        if (a+c==b && a+c == d)
        continue;
        if (a+c==b)
        {
            yi++;
        }
        if (a+c==d)
        {
            jia++;
        }
    }

    std::cout << jia <<" "<< yi << std::endl;

    system("pause");
    return 0;
}

3.2

//1 codeup1934
#include <iostream>

int num[200] = {0};

int main()
{
    int n;
    std::cin >> n;

    for (int i = 1; i <= n;i++)
        std::cin >> num[i];

    //待查询的数
    int k, flag = 1;
    std::cin >> k;

    for (int i = 1; i <= n;i++)
    {
        if (num[i]==k)
        {
            std::cout << i << std::endl;
            flag = 0;
            break;
        }
    }

    if (flag)
        std::cout << "-1" << std::endl;

    system("pause");
    return 0;
}
//2 PATA1011
#include <iostream>

char adr[3] = {'W','T','L'};

int main()
{
    double matrix[3][3];

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
            std::cin >> matrix[i][j];
    }

    //记录倍率
    double a[3] = {0, 0, 0};
    //记录下标
    int b[3];

    for (int i = 0; i < 3;i++)
    {
        for (int j = 0; j < 3;j++)
        {
            if (matrix[i][j]>a[i])
            {
                a[i] = matrix[i][j];
                b[i] = j;
            }
        }
    }

    double sum = (a[0] * a[1] * a[2] * 0.65 - 1) * 2;

    std::cout << adr[b[0]] << " " << adr[b[1]] << " " << adr[b[2]] << " ";
    printf("%.2lf\n", sum);

    //system("pause");
    return 0;
}
//3 PATB1004
#include <iostream>
#include <string>

using std::string;

struct STU
{
    string name;
    string ID;
};

int main()
{
    string nametemp, IDtemp;
    int score;

    int max = 0, min = 110;
    STU mx, mn;

    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++)
    {
        std::cin >> nametemp >> IDtemp >> score;

        if (score>max)
        {
            max = score;
            mx.name = nametemp;
            mx.ID = IDtemp;
        }

        if (score<min)
        {
            min = score;
            mn.name = nametemp;
            mn.ID = IDtemp;
        }
    }

    std::cout << mx.name << " " << mx.ID << std::endl;
    std::cout << mn.name << " " << mn.ID << std::endl;

    //system("pause");
    return 0;
}
//4 PATB1028
#include<cstdio>

struct persons {
	char name[6];
	int year, month, day;
}old, young, temp, tooold, haventburn;

bool LessEqu(persons i, persons j) {
	if (i.year != j.year) return i.year <= j.year;
	else if (i.month != j.month) return i.month <= j.month;
	else return i.day <= j.day;
}

bool MoreEqu(persons i, persons j) {
	if (i.year != j.year) return i.year >= j.year;
	else if (i.month != j.month) return i.month >= j.month;
	else return i.day >= j.day;
}

bool qualify(persons i) {
	if (MoreEqu(i, tooold) && LessEqu(i, haventburn)) return 1;
	else return 0;
}
void init() {
	young.year = tooold.year = 1814;
	old.year = haventburn.year = 2014;
	young.month = old.month = haventburn.month = tooold.month = 9;
	young.day = old.day = haventburn.day = tooold.day = 6;

}
int main() {
	int n, cnt = 0;
	init();
	scanf("%d", &n);
	while (n--) {
		scanf("%s %d/%d/%d", &temp.name, &temp.year, &temp.month, &temp.day);
		if (qualify(temp)) {
			++cnt;
			if (MoreEqu(temp, young)) young = temp;
			if (LessEqu(temp, old)) old = temp;
		}
	}
	if (cnt == 0) printf("0");
	else printf("%d %s %s", cnt, old.name, young.name);
	return 0;
}
//5 PATB1032
#include <iostream>

const int maxn = 100010;
int school[maxn] = {0};

int main()
{
    int n, ID, score;
    std::cin >> n;

    int k = 1, MAX = -1;

    for (int i = 1; i <= n;i++)
    {
        std::cin >> ID >> score;
        school[ID] += score;

        if (school[ID]>MAX)
        {
            MAX = school[ID];
            k = ID;
        }
    }

    std::cout << k << " " << MAX << std::endl;
    return 0;
}
//6 PATB1041
#include <iostream>
#include <string>


struct Student
{
    std::string id;
    int num;
} stu[1000];

int main()
{
    int n;
    std::cin >> n;

    for (int i = 0; i < n; i++)
    {
        int test_num, stu_num;
        std::string temp;
        std::cin >> temp >> test_num >> stu_num;

        stu[test_num].id = temp;
        stu[test_num].num = stu_num;
    }

    int h;
    std::cin >> h;

    for (int i = 0; i < h; i++)
    {
        int x;
        std::cin >> x;
        std::cout << stu[x].id << " " << stu[x].num << std::endl;
    }

    //system("pause");
    return 0;
}

3.3

//1 PATA1031
#include<cstdio>
#include<cstring>
int main() {
	int n1 = 1, n2 = 0, cnt;
	char str[85];
	scanf("%s", str);
	cnt = n2 = strlen(str);
	while (n1 + 1 <= n2 - 2) {
		n2 -= 2;
		++n1;
	}
	for (int i = 0;i < n1-1;++i) {
		printf("%c", str[i]);
		for (int j = 0;j < n2 - 2;++j) printf(" ");
		printf("%c\n", str[cnt - i - 1]);
	}
	for (int i = n1-1;i < n2 + n1-1;++i) {
		printf("%c", str[i]);
	}
	return 0;
}
//2 PATB1027
#include <iostream>

int main()
{
    int n, sum = 1, all = 1,count = 0;
    char c;
    std::cin >> n >> c;

    //计算层数
    while (all<n)
    {
        count++;
        sum += 2;
        all += sum * 2;
    }


    //整体分为三层,上层,中间只有一个符号的那一层,下层
    int col = 1;
    for (int i = 1; i < count;i++)
        col += 2;


    //需要注意的就是不能有多余的空格
    for (int i = 0; i < count-1;i++)
    {
        for (int j = 0; j < col-i;j++)
        {
            if (j>=i && j< col-i)
            {
                std::cout << c;
                n--;
            }
            else
                std::cout << " ";
        }
        std::cout << std::endl;
    }

    for (int i = 0; i < col / 2;i++)
        std::cout << " ";
    std::cout << c << std::endl;

    for (int i = count - 2; i >= 0;i--)
    {
        for (int j = 0; j < col-i;j++)
        {
            if (j>=i && j<col-i)
            {
                std::cout << c;
                n--;
            }
            else
                std::cout << " ";
        }
        std::cout << std::endl;
    }
    std::cout << n-1 << std::endl;

    system("pause");
    return 0;
}
//3 PATB1036
#include <iostream>

int main()
{

    int n, col;
    char s;
    std::cin >> n >> s;
    if (n%2==0)
        col = n / 2;
    else
        col = n / 2 + 1;

    for (int i = 1; i <= col;i++)
    {
        if (i==1 || i==col)
        {
            for (int i = 1; i <= n;i++)
                std::cout << s;
            std::cout << std::endl;
        }
        else
        {
            for (int i = 1; i <= n;i++)
            {
                if (i==1 || i==n)
                    std::cout << s;
                else
                    std::cout << " ";
            }
            std::cout << std::endl;
        }
    }

    return 0;
}

3.4

//1 codeup1928
#include <iostream>

int month[13][2] = {{0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}};
bool isLeap(int year)
{
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

int main()
{
    int time1, y1, m1, d1;
    int time2, y2, m2, d2;
    while (std::cin >> time1 >> time2)
    {
        if (time1 > time2)
        {
            int temp = time1;
            time1 = time2;
            time2 = temp;
        }

        int ans = 1;
        y1 = time1 / 10000, m1 = time1 % 10000 / 100, d1 = time1 % 100;
        y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;

        while (y1<y2 || m1<m2 || d1<d2)
        {
            d1++;
            if (d1==month[m1][isLeap(y1)]+1)
            {
                m1++;
                d1 = 1;
            }
            if (m1==13)
            {
                y1++;
                m1 = 1;
            }
            ans++;
        }
        std::cout << ans << std::endl;
    }
    return 0;
}

3.5

//1 PATB1022
#include <cstdio>

int main()
{
    int a, b, d;
    scanf("%d%d%d", &a, &b, &d);
    int sum = a + b;
    int ans[31], num = 0;
    do{
        ans[num++] = sum % d;
        sum /= d;
    } while (sum != 0);
    for (int i = num - 1; i >= 0;i--)
        printf("%d", ans[i]);
    return 0;
}
//2 PATB1037
#include <iostream>
#include <cstdio>

int main()
{
    int pg, ps, pk;
    int ag, as, ak;

    scanf("%d.%d.%d %d.%d.%d", &pg, &ps, &pk, &ag, &as, &ak);

    int sump = pg * 17 * 29 + ps * 29 + pk;
    int suma = ag * 17 * 29 + as * 29 + ak;

    int sum = suma - sump;

    int a, s, k;
    a = sum / (17 * 29);
    s = (sum - a * 17 * 29) / 29;
    k = (sum - a * 17 * 29 - s * 29) % 29;

    if (suma>sump)
    printf("%d.%d.%d\n", a, s, k);
    else
    printf("-%d.%d.%d\n", -a, -s, -k);

    system("pause");
    return 0;
}

3.6

//1 codeup5901
#include <iostream>
#include <string>

int main()
{
    std::string str;
    
    while (std::cin >> str)
    {
    int len = str.size();
    int flag = 0;

    for (int i = 0, j = len - 1; i < j;i++,j--)
    {
        if (str[i]!=str[j])
            flag = 1;
    }
    if (flag)
        std::cout << "NO" << std::endl;
    else
        std::cout << "YES" << std::endl;
    }
    system("pause");
    return 0;
}
//2 PATB1002
#include <iostream>
#include <string>
#include <stack>
using namespace std;

string order[10] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};

int main()
{

    stack<int> arr;
    string str;
    std::cin >> str;

    int sum = 0;

    for (int i = 0; i <(int)str.size();i++)
    {
        sum += str[i] - '0';
    }

    while (sum)
    {
        arr.push(sum % 10);
        sum /= 10;
    }

    while (!arr.empty())
    {
        cout << order[arr.top()];
        arr.pop();
        if (!arr.empty())
            cout << " ";
    }
    cout << endl;

    system("pause");
    return 0;
}
//3 PATB1006
#include <iostream>

int main()
{
    //测试未过,不明原因
    int n;
    while (std::cin>>n)
    {
        int b, s, g;
        b = n / 100;
        s = (n - b * 100) / 10;
        g = n % 10;

        for (int i = 0; i < b; i++)
            std::cout << 'B';
        for (int i = 0; i < s; i++)
            std::cout << 'S';
        std::cout << 1;
        if (b != 0)
            std::cout << b;
        if (s != 0)
            std::cout << s;
        std::cout << g;
    }

    return 0;
}
//4 PATB1009
#include <iostream>
#include <string>
#include <stack>
#include <sstream>


int main()
{
    std::string str;
    std::getline(std::cin, str);
    std::stack<std::string> array;

    std::stringstream input(str);
    std::string temp;
    while (input >> temp)
        array.push(temp);
    
    while (!array.empty())
    {
        std::cout << array.top();
        array.pop();
        if (!array.empty())
            std::cout << " ";
    }
    std::cout << std::endl;

    system("pause");
    return 0;
}
//5 PATB1021
#include <iostream>
#include <string>

int HashTable[10] = {0};

int main()
{
    std::string n;
    std::cin >> n;

    int len = (int)n.size();

    for (int i = 0; i < len;i++)
    {
        HashTable[n[i] - '0']++;
    }

        for (int i = 0; i < 10; i++)
        {
            if (HashTable[i] != 0)
                std::cout << i << ":" << HashTable[i] << std::endl;
        }

    system("pause");
    return 0;
}
//6 PATB1031
#include<cstdio>
#include<cstring>
const int w[17] = { 7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2 };
const char cp[11] = { '1','0','X','9','8','7','6','5','4','3','2' };
int main() {
	int n;
	scanf("%d", &n);
	bool flag = true;
	char id[20];
	for (int i = 0;i < n;++i) {
		scanf("%s", id);
		int j, sum=0;
		for (j = 0;j < 17;++j) {
			if (!(id[j] >= '0' && id[j] <= '9')) break;
			sum += (w[j] * (id[j] - '0'));
		}
		if (j < 17) {
			flag = false;
			printf("%s\n", id);
		}
		else {
			int z = sum % 11;
			if (cp[z] != id[17]) {
				flag = false;
				printf("%s\n", id);
			}
		}
	}
	if (flag == true) {
		printf("All passed");
	}
	return 0;
}

第四章

4.1

//1 PATA1025
#include <iostream>
#include <algorithm>
#include <string>


struct Student
{
    std::string id;
    int score;
    int location;
    int local_rank;
} stu[30010];

bool cmp(Student a,Student b)
{
    if (a.score != b.score)
        return a.score > b.score;
    else
        return a.id < b.id;
}

int main()
{
    int n,num=0;
    std::cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int k;
        std::cin >> k;
        num += k;

        for (int j = num-k; j < num; j++)
        {
            std::cin >> stu[j].id >> stu[j].score;
            stu[j].location = i;
        }

        std::sort(stu + num - k, stu + num, cmp);

        stu[num - k].local_rank = 1;
        for (int j = num - k + 1,r=2; j < num;j++,r++)
        {
            if (stu[j].score == stu[j-1].score)
                stu[j].local_rank = stu[j - 1].local_rank;
            else
            {
                stu[j].local_rank = r;
            }
        }
    }
    std::cout <<num << std::endl;

    std::sort(stu, stu + num, cmp);

    int r = 1;
    for (int i = 0; i < num;i++)
    {
        if (i>0 && stu[i].score!=stu[i-1].score)
            r=i+1;
        std::cout << stu[i].id << " " << r << " " << stu[i].location << " " << stu[i].local_rank << std::endl;
    }


    return 0;
}

//2 PATA1028
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

struct STUDENT
{
    string id;
    string name;
    int grade;
}stu[100005];

bool cmp1(STUDENT a,STUDENT b)
{
    return a.id < b.id;
}

bool cmp2(STUDENT a,STUDENT b)
{
    if (a.name != b.name)
        return a.name < b.name;
    else
        return a.id < b.id;
}

bool cmp3(STUDENT a,STUDENT b)
{
    if (a.grade != b.grade)
        return a.grade < b.grade;
    else
        return a.id < b.id;
}



int main()
{
    int n, order;
    cin >> n >> order;

    for (int i = 0; i < n; i++)
    {
        cin >> stu[i].id >> stu[i].name >> stu[i].grade;
    }

    switch (order)
    {
        case 1:
            sort(stu, stu + n, cmp1);
            break;
        case 2:
            sort(stu, stu + n, cmp2);
            break;
        case 3:
            sort(stu, stu + n, cmp3);
            break;
    }

    for (int i = 0; i < n; i++)
    {
        cout << stu[i].id << " " << stu[i].name << " " << stu[i].grade << endl;
    }

    system("pause");
    return 0;
}

//3 PATA1062
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

struct People
{
    string id;
    int vg, tg, total;
    int flag;
} people[100005];

bool cmp(People a, People b)
{
    if (a.flag != b.flag)
        return a.flag < b.flag;
    else if (a.total != b.total)
        return a.total > b.total;
    else if (a.vg != b.vg)
        return a.vg > b.vg;
    else
        return a.id < b.id;
}

int main()
{
    int n, m, l, h;
    cin >> n >> l >> h;

    m = n;

    for (int i = 0; i < n; i++)
    {
        cin >> people[i].id >> people[i].vg >> people[i].tg;
        people[i].total = people[i].vg + people[i].tg;

        if (people[i].vg<l || people[i].tg<l)
        {
            people[i].flag = 5;
            --m;
        }
        else if (people[i].vg>=h && people[i].tg>=h)
            people[i].flag = 1;
        else if (people[i].tg<h && people[i].vg>=h)
            people[i].flag = 2;
        else if (people[i].vg<h && people[i].tg<h && people[i].vg>=people[i].tg)
            people[i].flag = 3;
        else
            people[i].flag = 4;
    }

    cout << m << endl;

    sort(people, people + n, cmp);

    for (int i = 0; i < m; i++)
    {
        cout << people[i].id <<" "<< people[i].vg <<" "<< people[i].tg;
        if (i != m-1)
            cout << endl;
    }

    system("pause");
    return 0;
}

//4 PATA1075
#include<cstdio>
#include<cstring>
#include<algorithm> 
using namespace std;
struct User {
	int id, ps[6] = { 0,-1,-1,-1,-1,-1 }, ts = 0, psp = 0, r;
	bool canprint = 0;
}u[10000];
bool cmp(User a, User b) {
	if (a.ts != b.ts) return a.ts > b.ts;
	else if (a.psp != b.psp) return a.psp > b.psp;
	else return a.id < b.id;
}
int main() {
	int n, k, m;
	scanf("%d %d %d", &n, &k, &m);
	int p[6], cnt = 0;
	for (int i = 1;i <= k;++i) scanf("%d", &p[i]);
	for (int i = 0;i < m;++i) {
		bool same = 0;
		int ti, j;
		scanf("%d", &ti);
		for (j = 0;j <= cnt;++j) {
			if (ti == u[j].id) {
				same = 1;
				break;
			}
		}
		int tempps, tempts;
		if (same == 0) {
			u[cnt].id = ti;
			scanf("%d %d", &tempps, &tempts);
			if (tempts != -1) {
				u[cnt].ps[tempps] = tempts;
				if (tempts == p[tempps]) ++u[j].psp;
				u[cnt].ts += tempts;
				u[cnt].canprint = 1;
			}
			else {
				u[cnt].ps[tempps] = 0;
			}
			++cnt;
		}
		else {
			scanf("%d %d", &tempps, &tempts);
			if (tempts == -1 && u[j].ps[tempps] == -1) u[j].ps[tempps] = 0;
			if (u[j].ps[tempps] < tempts) {
				u[j].canprint = 1;
				if (tempts == p[tempps]) ++u[j].psp;
				if (u[j].ps[tempps] == -1) u[j].ts += tempts;
				else u[j].ts += (tempts - u[j].ps[tempps]);
				u[j].ps[tempps] = tempts;
			}
		}
	}
	sort(u, u + cnt, cmp);
	for (int i = 0;i < cnt;++i) {
		if (u[i].canprint == 1) {
			if (i > 0 && u[i].ts == u[i - 1].ts) u[i].r = u[i - 1].r;
			else u[i].r = i + 1;
			printf("%d %05d ", u[i].r, u[i].id);
			printf("%d ", u[i].ts);
			for (int j = 1;j <= k;++j) {
				if (u[i].ps[j] == -1) printf("-");
				else printf("%d", u[i].ps[j]);
				if (j != k) printf(" ");
			}
			printf("\n");
		}
	}
	return 0;
}

4.2

//1 PATA1092
#include <iostream>
#include <string>
using namespace std;


int HashTable[128] = {0};

int main()
{
    string str;
    getline(cin, str);

    int len1 = str.size();
    for (int i = 0; i < len1; i++)
        HashTable[str[i]]++;

    int count = 0;
    getline(cin, str);
    int len2 = str.size();

    for (int i = 0; i < len2;i++)
    {
        if (HashTable[str[i]]!=0)
        {
            HashTable[str[i]]--;
            len1--;
        }
        else
            count++;
    }

    if (count!=0)
        cout << "No" <<" "<< count << endl;
    else
        cout << "Yes" <<" "<< len1 << endl;

    system("pause");
    return 0;
}

//2 PATB1005
#include<cstdio>
#include<algorithm>
using namespace std;
bool cmp(int a, int b) {
	return a > b;
}
int main() {
	bool hashTable[10000] = { false };
	int n;
	scanf("%d", &n);
	int num[110];
	for (int i = 0;i < n;++i) {
		int temp;
		scanf("%d", &num[i]);
		temp = num[i];
		while (temp != 1 && hashTable[num[i]] == false) {//已经被覆盖的数无需再进行计算
			if (temp % 2 == 0) {
				temp /= 2;
				hashTable[temp] = true;
			}
			else {
				temp = (3 * temp + 1) / 2;
				hashTable[temp] = true;
			}
		}
	}
	sort(num, num + n, cmp);
	int f = 0;
	for (int i = 0;i < n;++i) {
		if (hashTable[num[i]] == false) {
			if (f != 0) printf(" ");
			printf("%d", num[i]);
			++f;
		}
	}
	printf("\n");
	return 0;
}

//3 PATB1033
#include<cstdio>
#include<iostream>
#include <stdlib.h>
#include<string>
using namespace std;
int main() {
	string str;
	bool hashTable[128];
    fill(hashTable, hashTable + 128, 1);
    getline(cin, str);
	int len = str.size();
	for (int i = 0;i < len;++i) hashTable[str[i]] = false;
	getline(cin, str);
	len = str.size();
	for (int i = 0;i < len;++i) {
		if (str[i] >= 'A' && str[i] <= 'Z') {
			if (hashTable['+'] == true && hashTable[str[i]] == true)
				printf("%c", str[i]);
		}
		else if (str[i] >= 'a' && str[i] <= 'z') {
			if (hashTable[str[i] - 32] == true)
				printf("%c", str[i]);
		}
		else {
			if (hashTable[str[i]] == true)
				printf("%c", str[i]);
		}

	}
	printf("\n");
	return 0;
}

//4 PATB1038
#include <iostream>

int HashTable[100050] = {0};

int main()
{
    int x;
    int n;
    std::cin >> n;

    for (int i = 0; i < n; i++)
    {
        std::cin >> x;
        HashTable[x]++;
    }

    std::cin >> n;
    int num[n];
    for (int i = 0; i < n;i++)
    {
        std::cin >> num[i];
    }

    for (int i = 0; i < n;i++)
    {
        std::cout << HashTable[num[i]];
        if (i!=n-1)
            std::cout << " ";
    }

    std::cout << std::endl;

    system("pause");
    return 0;
}

//5 PATB1042
#include <iostream>
#include <algorithm>
using namespace std;

int HashTable[26] = {0};

int main()
{
    string str;
    getline(cin, str);

    int len = str.size();

    for (int i = 0; i < len;i++)
    {
        if (str[i]>='a' && str[i]<='z')
            HashTable[str[i] - 'a']++;
        if (str[i]>='A' && str[i]<='Z')
            HashTable[str[i] - 'A']++;
    }
    int k = 0;
    int max = 0;
    for (int i = 0; i < 26;i++)
    {
        if (HashTable[i]>max)
        {
            max = HashTable[i];
            k = i;
        }
    }

    cout << char('a' + k) << " " << max << endl;

    system("pause");
    return 0;
}

//6 PATB1043
#include <iostream>
#include <string>
using namespace std;

char disk[6] = {'P', 'A', 'T', 'e', 's', 't'};
int dir[6] = {0};

int main()
{
    string str;
    getline(cin, str);

    int count = 0;
    int len = str.size();
    for (int i = 0; i < len; i++)
    {
        for (int j = 0; j < 6;j++)
        {
            if (str[i]==disk[j])
            {
                dir[j]++;
                count++;
            }
        }
    }
    int flag = 1;
    while (flag)
    {
        for (int i = 0; i < 6;i++)
        {
            if (count==0)
            {
                flag = 0;
                break;
            }
            if(dir[i])
            {
                dir[i]--;
                cout << disk[i];
                count--;
            }
        }
    }

    cout << endl;
    system("pause");
    return 0;
}

//7 PATB1047
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

int HashTable[10000] = {0};

int main()
{
    int n;
    std::cin >> n;

    int k = 0;

    int team, num, score;
    for (int i = 0; i < n; i++)
    {
        scanf("%d-%d %d", &team, &num, &score);
        HashTable[team] += score;

        if (team > k)
            k = team;
    }

    int max = 0;
    for (int i = 0; i <= k;i++)
    {
        if (HashTable[i]>max)
        {
            max = HashTable[i];
            team = i;
        }
    }

    cout << team << " " << max << endl;

    system("pause");
    return 0;
}

4.3

//1.
//全排列
#include <iostream>
using namespace std;

const int maxn = 11;

int n, P[maxn], hashTable[maxn] = {false};

void get(int index)
{
    if (index == n+1)
    {
        for (int i = 1; i <= n;i++)
        {
            cout << P[i];
        }
        cout << endl;
        return;
    }
    for (int x = 1; x <= n;x++)
    {
        if (hashTable[x]==false)
        {
            P[index] = x;
            hashTable[x] = true;
            get(index + 1);
            hashTable[x] = false;
        }
    }
}

int main()
{
    cin >> n;
    get(1);

    system("pause");
    return 0;
}
//2.
//n皇后,枚举方法
#include <iostream>
#include <cmath>
using namespace std;

int count = 0;
int n;
int p[11];
bool hashTable[11] = {false};

void get(int index)
{
    if (index == n+1)
    {
        //生成一个排列
        bool flag = true;
        //判断排列是否符号条件
        for (int i = 1; i <= n;i++)
        {
            for (int j = i + 1; j <= n;j++)
            {
                if (abs(i-j)==abs(p[i]-p[j]))
                    flag = false;
            }
        }
        if (flag)
            count++;
    }
    for (int x = 1; x <= n;x++)
    {
        if (hashTable[x]==false)
        {
            p[index]=x;
            hashTable[x] = true;
            get(index + 1);
            hashTable[x] = false;
        }
    }
}



int main()
{
    cin >> n;
    get(1);

    cout << count << endl;

    system("pause");
    return 0;
}
//3.
//n皇后 回溯
#include <iostream>
#include <cmath>
using namespace std;

int count = 0;
int n;
bool hashTable[11] = {false};
int p[11];

void get(int index)
{
    if (index == n+1)
    {
        count++;
        return;
    }
    for (int x = 1; x <= n;x++)
    {
        if (hashTable[x]==false)
        {
            bool flag = true;
            //pre 和 index 为列 , x为index的行,还没写入p中,先判断,
            //index列 与 前面列的是否冲突 p[pre]为pre的行
            for (int pre = 1; pre < index;pre++)
            {
                if (abs(index-pre)==abs(x-p[pre]))
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                p[index] = x;
                hashTable[x] = true;
                get(index + 1);
                hashTable[x] = false;
            }
        }
    }
}

int main()
{
    cin >> n;
    get(1);
    cout << count << endl;

    system("pause");
    return 0;
}
//4.
// 题目描述
// 名名的妈妈从外地出差回来，带了一盒好吃又精美的巧克力给名名（盒内共有 N 块巧克力，20 > N >0）。
// 妈妈告诉名名每天可以吃一块或者两块巧克力。
// 假设名名每天都吃巧克力，问名名共有多少种不同的吃完巧克力的方案。
// 例如：
// 如果N=1，则名名第1天就吃掉它，共有1种方案；
// 如果N=2，则名名可以第1天吃1块，第2天吃1块，也可以第1天吃2块，共有2种方案；
// 如果N=3，则名名第1天可以吃1块，剩2块，也可以第1天吃2块剩1块，所以名名共有2+1=3种方案；
// 如果N=4，则名名可以第1天吃1块，剩3块，也可以第1天吃2块，剩2块，共有3+2=5种方案。
// 现在给定N，请你写程序求出名名吃巧克力的方案数目。

// 输入
// 输入只有1行，即整数N。

// 输出
// 可能有多组测试数据，对于每组数据，
// 输出只有1行，即名名吃巧克力的方案数。

// 样例输入
// 1
// 2
// 4

// 样例输出
// 1
// 2
// 5

#include <iostream>
using namespace std;


int eat(int n)
{
    if (n==1)
    {
        return 1;
    }
    else if (n==2)
    {
        return 2;
    }
    return eat(n - 1) + eat(n - 2);
}

int main()
{
    int x;
    while (cin>>x)
    {
        cout << eat(x) << endl;
    }
}
//5.
// 题目描述
// 会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
// 对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2…b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
// 给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

// 输入
// 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92)

// 输出
// 输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。
// 输入
// 3
// 6
// 4
// 25
// 输出
// 25713864
// 17582463
// 36824175

//思路:先递归求解出所有皇后的排列顺序,用一个数组记录,再按数组查找


#include <iostream>
#include <cmath>
using namespace std;


int hashTable[9] = {false};
int p[9];
int n = 8;
int queen[92];
int ans = 0;

void get(int index)
{
    if (index == n+1)
    {
        int sum = 0;
        for (int i = 1; i <= n;i++)
        {
            sum *= 10;
            sum += p[i];
        }
        queen[ans++] = sum;
        return;
    }

    for (int x = 1; x <= n;x++)
    {
        if (hashTable[x]==false)
        {
            bool flag = true;
            for (int pre = 1; pre < index;pre++)
            {
                if (abs(index-pre)==abs(x-p[pre]))
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                p[index] = x;
                hashTable[x] = true;
                get(index + 1);
                hashTable[x] = false;
            }

        }
    }
}

int main()
{
    get(1);

    int n;
    while (cin >> n)
    {
        cout << queen[n-1] << endl;
    }
}
//6.
// 题目描述
// 编写一个求斐波那契数列的递归函数，输入n 值，使用该递归函数，输出如下图形（参见样例）。

// 输入
// 输入第一行为样例数m，接下来有m行每行一个整数n，n不超过10。

// 输出
// 对应每个样例输出要求的图形(参见样例格式)。

// 样例输入
// 1
// 6
//样例输出
//           0
//         0 1 1
//       0 1 1 2 3
//     0 1 1 2 3 5 8
//   0 1 1 2 3 5 8 13 21
// 0 1 1 2 3 5 8 13 21 34 55

//本身与递归有关的只有数列求解部分,很经典的Fibonacci数列,图型输出部分没用递归,就直接抄了


#include <cstdlib>
#include<cstdio>
int a[30] = { 0,1,1 };
int main() {
	for (int i = 3;i < 30;++i) a[i] = a[i - 1] + a[i - 2];
	int n, m, cnt = 1;
	scanf("%d", &n);
	while (n--) {
		scanf("%d", &m);
		cnt = 1;
		while (m--) {
			for (int i = 0;i < 2 * m;++i) printf(" ");
			for (int i = 0;i < cnt;++i) {
				if (i) printf(" ");
				printf("%d", a[i]);
			}
			printf("\n");
			cnt += 2;
		}
	}
    system("pause");
    return 0;
}
//7.
// 题目描述
// 有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，John有多少种不同的选择物品的方式。

// 输入
// 输入的第一行是正整数n (1 <= n <= 20)，表示不同的物品的数目。接下来的n行，每行有一个1到40之间的正整数，分别给出a1，a2……an的值。

// 输出
// 输出不同的选择物品的方式的数目。
// 输入:
// 2
// 12
// 28
// 3
// 21
// 10
// 5
// 输出:
// 1
// 0

//思路:划分为两个子问题 1.用第一个物体 2.不用第一个物体

#include <iostream>
using namespace std;

int count(int target,int n,int* weight)
{
    if(target==0)
        return 1;
    else if (n==0 || target<0)
        return 0;

    return count(target - weight[0], n - 1, weight + 1) + count(target, n - 1, weight + 1);
}

int main()
{
    int n;
    while (cin>>n)
    {

        int weight[n];
        for (int i = 0; i < n; i++)
            cin >> weight[i];
        cout << count(40, n, weight) << endl;
    }

    system("pause");
    return 0;
}

4.4

//1.
#include <iostream>
#include <algorithm>
using namespace std;

struct section
{
    int flag = 0;//判断是否被选中 
    int x;       //左端点
    int y;       //右端点
} sec[20];

//思路: 1.优先选左端点最大的 2.如左端点相等,选右端点小的

//反之,选右端点最小的同行也行,思路类似

bool cmp(section a,section b)
{
    if (a.x != b.x)
        return a.x > b.x;
    else
        return a.y < b.y;
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n;i++)
    {
        cin >> sec[i].x >> sec[i].y;
    }

    sort(sec, sec + n, cmp);

    sec[0].flag = 1;
    int get_x = sec[0].x;      //向下遍历,逐个加入

    for (int i = 1; i < n;i++)
    {
        if (sec[i].y<=get_x)
        {
            get_x = sec[i].x;
            sec[i].flag = 1;
        }
    }

    for (int i = 0; i < n;i++)
    {
        if (sec[i].flag)
        {
            cout << "(" << sec[i].x << "," << sec[i].y << ")"
                 << " ";
        }
    }
    cout << endl;

    system("pause");
    return 0;
}
//2.
// 题目描述
// 小明正在玩游戏，他控制的角色正面临着幽谷的考验——
// 幽谷周围瘴气弥漫，静的可怕，隐约可见地上堆满了骷髅。由于此处长年不见天日，导致空气中布满了毒素，一旦吸入体内，便会全身溃烂而死。
// 幸好小明早有防备，提前备好了解药材料（各种浓度的万能药水）。现在只需按照配置成不同比例的浓度。
// 现已知小明随身携带有n种浓度的万能药水，体积V都相同，浓度则分别为Pi%。并且知道，针对当时幽谷的瘴气情况，只需选择部分或者全部的万能药水，然后配置出浓度不大于 W%的药水即可解毒。
// 现在的问题是：如何配置此药，能得到最大体积的当前可用的解药呢？
// 特别说明：由于幽谷内设备的限制,只允许把一种已有的药全部混入另一种之中（即：不能出现对一种药只取它的一部分这样的操作）。
// -
// 输入
// 输入数据的第一行是一个整数C，表示测试数据的组数；
// 每组测试数据包含2行，首先一行给出三个正整数n,V,W(1<=n,V,W<=100)；
// 接着一行是n个整数，表示n种药水的浓度Pi%(1<=Pi<=100)。
// -
// 输出
// 对于每组测试数据，请输出一个整数和一个浮点数；
// 其中整数表示解药的最大体积，浮点数表示解药的浓度(四舍五入保留2位小数)；
// 如果不能配出满足要求的的解药，则请输出0 0.00。

#include <stdio.h>
#include <stdlib.h>
int cmpInt(const void *ca, const void *cb){
	return *(int*)ca > *(int*)cb; 
} 
int main(){
	int c, n, v, w, i;
	while (scanf("%d", &c) != EOF){
		while (c--){
			scanf("%d %d %d", &n, &v, &w);
			int sum = 0;
			int p[n]; 
			for (i = 0; i < n; ++i)
				scanf("%d", &p[i]);
			qsort(p, n, sizeof(int), cmpInt);
			for (i = 0; i < n; ++i){
				if ((float)(sum+p[i]) / (float)(i+1) <= (float)w){
					sum += p[i];
				} else break;
			}
			if (sum == 0){
				printf("0 0.00\n"); 
			} else {
				printf("%d %.2f\n", i * v, 0.01 * (float)sum / (float)i);
			} 
		} 	
	} 
	return 0;
} 
//3.
// 题目描述
// 小智去超市买东西，买了不超过一百块的东西。收银员想尽量用少的纸币来找钱。
// 纸币面额分为50 20 10 5 1 五种。请在知道要找多少钱n给小明的情况下，输出纸币数量最少的方案。 1<=n<=99;
// -
// 输入
// 有多组数据 1<=n<=99;
// -
// 输出
// 对于每种数量不为0的纸币，输出他们的面值*数量，再加起来输出


#include <iostream>
#include <algorithm>
using namespace std;

int money[5] = {50,20,10,5,1};
int cnt[5];

int main()
{
    int n,i;
    while (cin>>n)
    {
        fill(cnt, cnt + 5, 0);

        for (i = 0; i < 5;i++)
        {
            if (n)
            {
                cnt[i] = n / money[i];
                n %= money[i];
            }
        }
        int flag = 0;
        for (i = 0; i < 5;i++)
        {
            if(cnt[i])
            {
                if (flag)
                    cout << '+';
                flag = 1;
                printf("%d*%d", money[i], cnt[i]);
            }
        }
        cout << endl;
    }
}
//4.PATB1020
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

struct mooncake
{
    double store;
    double sell;
    double price;
} cake[1010];

bool cmp(mooncake a,mooncake b)
{
    return a.price > b.price;
}

int main()
{
    int n;
    double D;
    scanf("%d%lf", &n, &D);

    for (int i = 0; i < n;i++)
    {
        scanf("%lf", &cake[i].store);
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%lf", &cake[i].sell);
        cake[i].price = cake[i].sell / cake[i].store;
    }
    sort(cake, cake + n, cmp);
    double ans = 0;
    for (int i = 0; i < n;i++)
    {
        if (cake[i].store <=D)
        {
            D -= cake[i].store;
            ans += cake[i].sell;
        }else
        {
            ans += cake[i].price * D;
            break;
        }
    }
    printf("%.2f\n", ans);

    system("pause");
    return 0;
}

//5.PATB1023
#include <iostream>

int count[10];

int main()
{
    for (int i = 0; i < 10;i++)
        std::cin >> count[i];

    for (int i = 1; i < 10;i++)
    {
        if (count[i]>0)
        {
            std::cout << i;
            count[i]--;
            break;
        }
    }
    for (int i = 0; i < 10;i++)
    {
        while (count[i]!=0)
        {
            std::cout << i;
            count[i]--;
        }
    }
    std::cout << std::endl;

    system("pause");
    return 0;
}
//6.
// 题目描述
// 某市出租车计价规则如下：起步4公里10元，即使你的行程没超过4公里；接下来的4公里，每公里2元；之后每公里2.4元。行程的最后一段即使不到1公里，也当作1公里计费。
// 一个乘客可以根据行程公里数合理安排坐车方式来使自己的打车费最小。
// 例如，整个行程为16公里，乘客应该将行程分成长度相同的两部分，每部分花费18元，总共花费36元。如果坐出租车一次走完全程要花费37.2元。
// 现在给你整个行程的公里数，请你计算坐出租车的最小花费。
//-
// 输入
// 输入包含多组测试数据。每组输入一个正整数n（n<10000000），表示整个行程的公里数。
// 当n=0时，输入结束。
//-
// 输出
// 对于每组输入，输出最小花费。如果需要的话，保留一位小数。

//八公里以上 剩余部分大于5公里 采用 重新打车，小于五公里直接打完
//2.4 x 6 = 14.4     10 + 2 x 2 = 14

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const double eight_km = 18;

int main()
{
    int n;
    while (cin >> n && n)
    {
        if (n>=8)
        {
            double sum = 0;
            int count1 = n / 8;
            int count2 = n % 8;

            if (count2>=5)
            {
                sum = (10 + (count2 - 4) * eight_km) + count1*eight_km;
            }
            else
                sum = count2 * 2.4 +count1*eight_km;

            cout << sum << endl;
        }
        else
        {
            double sum = 0;
            if (n<=4)
                cout << 10 << endl;
            else
            {
                sum = 10 + (n - 4) * 2;
                cout << sum << endl;
            }
            
        }
    }

    return 0;
}

//7.
// 题目描述
// 暑假到了，小明终于可以开心的看电视了。但是小明喜欢的节目太多了，他希望尽量多的看到完整的节目。
// 现在他把他喜欢的电视节目的转播时间表给你，你能帮他合理安排吗？
//-
// 输入
// 输入包含多组测试数据。每组输入的第一行是一个整数n（n<=100），表示小明喜欢的节目的总数。
// 接下来n行，每行输入两个整数si和ei（1<=i<=n），表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。
// 当n=0时，输入结束。
//-
// 输出
// 对于每组输入，输出能完整看到的电视节目的个数
//-
//输入
// 12
// 1 3
// 3 4
// 0 7
// 3 8
// 15 19
// 15 20
// 10 15
// 8 18
// 6 12
// 5 10
// 4 14
// 2 9
//-
//输出
//5

//一眼丁真,判定为区间



#include <iostream>
#include <algorithm>
using namespace std;

struct time
{
    int flag = 0;
    int start;
    int end;
} watch[20];

bool cmp(time a,time b)
{
    if (a.start!=b.start)
        return a.start > b.start;
    else
        return a.end < b.end;
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0;i<n;i++)
    {
        cin >> watch[i].start >> watch[i].end;
    }

    sort(watch, watch + n, cmp);

    int count = 1;
    watch[0].flag = 1;

    int get_x = watch[0].start;

    for (int i = 1;i<n;i++)
    {
        if (watch[i].end<=get_x)
        {
            watch[i].flag = 1;
            get_x = watch[i].start;
            count++;
        }
    }

    cout << count << endl;

    system("pause");
    return 0;
}

4.5

//1.
#include <iostream>
#include <cmath>

const double PI = std::acos(-1.0);
const double eps = 1e-5;

double f(double R,double h)
{
    double alpha = 2 * std::acos((R - h) / R);
    double L = 2 * std::sqrt(R * R - (R - h) * (R - h));
    double s1 = alpha * R * R / 2 - L * (R - h) / 2;
    double s2 = PI * R * R / 2;
    return s1 / s2;
}

double solve(double R,double r)
{
    double left = 0, right = R, mid;
    while (right - left > eps)
    {
        mid = (left + right) / 2;
        if (f(R,mid)>r)
        {
            right = mid;
        }
        else
        {
            left = mid;
        }
    }
    return mid;
}

int main()
{
    double R, r;
    std::cin >> R >> r;
    std::cout << solve(R, r);
    return 0;
}
//2.
//a b m 求 a ^ b & m
#include <iostream>

using LL = long long;

LL binaryPow(LL a,LL b,LL m)
{
    LL ans = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1;
    }
    return ans;
}

int main()
{
    return 0;
}
//3.
//a b m 求 a ^ b & m
#include <iostream>

using LL = long long;

LL binaryPow(LL a,LL b,LL m)
{
    if (b == 0)
        return 1;
    if (b%2 == 1)
        return a * binaryPow(a, b - 1, m) % m;
    else
    {
        LL mu1 = binaryPow(a, b / 2, m);
        return mu1 * mu1 % m;
    }
}

int main()
{
    return 0;
}
//4.
#include <iostream>
#include <vector>
using namespace std;

std::vector<int> array;

int half_seach(int left, int right, int data)
{
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (array[mid] == data)
        {
            return mid;
        }
        else if (array[mid] > data)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return -1;
}

int main()
{
    int n,data;
    std::cin >> n;
    for (int i = 0; i < n;i++)
    {
        std::cin >> data;
        array.emplace_back(data);
    }

    while (std::cin >> data)
    {
        std::cout << half_seach(0, n-1, data) <<  std::endl;
    }

    system("pause");
    return 0;
}
//5.#include <iostream>
using namespace std;

//不存在重复元素的二分
int A[10] = {1, 3, 4, 6, 7, 8, 10, 11, 12, 15};

int search(int index)
{
    int mid;
    int left = 0;
    int right = 9;

    while (left <= right)
    {
        // mid = left + (right-left)/2;
        mid = (left + right) / 2;
        if (index == A[mid])
            return mid;
        else if (index < A[mid])
        {
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return -1;
}

int main()
{
    int n;
    while (cin >> n)
    {
        cout << "position: " << search(n) << endl;
    }
}
//6.
#include <iostream>
#include <algorithm>
using namespace std;

//存在重复元素的二分

int A[10] = {1, 2, 3, 3, 3, 3, 4, 5, 6, 8};

//对于要查找的x,left=第一个大于等于x的元素下标,right=第一个大于x的元素下标
//即区间为 [left,right) 如 x = 3 ,left = 2 ，right = 6 ，区间 [2,6)

int lower_bound(int x)
{
    int left = 0;
    int right = 9;
    int mid;
    while (left<right)           //left == right 是终止条件,
    {
        mid = (left + right) / 2;

        if (A[mid]>=x)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}

//与找左区间基本一致,区别是判断条件,只有大于
int upper_bound(int x)
{
    int left = 0;
    int right = 9;
    int mid;
    while (left<right)
    {
        mid = (left + right) / 2;
        if (A[mid]>x)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}



int main()
{
    cout << lower_bound(3) << endl;
    cout << upper_bound(3) << endl;

    system("pause");
    return 0;
}
//7.
#include <iostream>
#include <cmath>
using namespace std;

const double eps = 1e-5;

double calSqrt(int p)
{
    double left = 1, right = 2, mid;

    auto f = [p](double x) { return x * x-p; };
    while (right - left > eps)
    {
        mid = (right + left) / 2;
        
        if (f(mid)>0)
            right = mid;
        else
            left = mid;
    }
    return mid;
}

int main()
{
    cout << calSqrt(3) << endl;

    cout << sqrt(3) << endl;

    system("pause");
    return 0;
}
//8.
// 题目
// 题目描述
// 在一个整数数组上，对于下标为i的整数，如果它大于所有它相邻的整数，或者小于所有它相邻的整数，则称为该整数为一个极值点，极值点的下标就是i。
// -
// 输入
// 每-个案例的输入如下：
// -
// 有2×n+1行输入：第一行是要处理的数组的个数n；
// 对其余2×n行，第一行是此数组的元素个数k(4<k<80)，第二行是k个整数，每两个整数之间用空格分隔。
// -
// 输出
// 每个案例输出不多于n行：每行对应于相应数组的所有极值点下标值，下标值之间用空格分隔，如果没有极值点则不输出任何东西。
// -
// 样例输入 Copy
// 2
// 4
// 1 2 1 3
// 5
// 3 4 5 6 7
// 样例输出 Copy
// 0 1 2 3
// 0 4

#include <iostream>
#include <vector>

void print(std::vector<int>& array)
{
    int len = (int)array.size();
    std::vector<int> extrem_num(len);

    if (array[0]!=array[1])
        extrem_num[0] = 1;

    if (array[len-1] != array[len-2])
        extrem_num[len - 1] = 1;

    for (int i = 1; i < len - 1;i++)
    {
        if (array[i] > array[i+1] && array[i] > array[i-1]
        ||  array[i] < array[i+1] && array[i] < array[i-1])
            extrem_num[i] = 1;
    }

    for (int i = 0; i < len;i++)
    {
        if (extrem_num[i])
            std::cout << i << " ";
    }
    std::cout << std::endl;

}

int main()
{
    int n;
    std::cin >> n;
    while (n--)
    {
        int m;
        std::cin >> m;
        std::vector<int> array(m);
        for (int j = 0; j < m;j++)
            std::cin >> array[j];
        print(array);
    }
    system("pause");
    return 0;
}
//9.
#include <iostream>
#include <vector>
#include <string>

std::string search(std::vector<int>& array,int data)
{
    int left = 0;
    int right = array.size() - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (array[mid] == data)
        {
            return "YES";
        }
        else if (array[mid] > data)
        {
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return "NO";
}

int main()
{
    int n;
    std::cin >> n;
    int data;
    std::vector<int> array;
    for (int i = 0; i < n;i++)
    {
        std::cin >> data;
        array.push_back(data);
    }

    int m;
    std::cin >> m;
    for (int i = 0; i < m;i++)
    {
        std::cin >> data;
        std::cout << search(array, data) << std::endl;
    }
    system("pause");
    return 0;
}

4.6

//1.
#include <iostream>
#include <vector>


// void FIND(std::vector<int>&& array,int m)
// {
//     int i = 0, j = array.size() - 1;
//     while (i < j)
//     {
//         if (array[i]+array[j] == m)
//         {
//             std::cout << i << " " << j << std::endl;
//         } else if (array[i] + array[j] > m)
//         {
//             j--;
//         } else
//         {
//             i++;
//         }
//     }
// }

//归并排序 递归版本

std::vector<int> array{66, 12, 33, 57, 64, 27, 18};

void merge(int left1,int right1,int left2,int right2)
{
    std::vector<int> temp;
    int i = left1, j = left2, index = 0;
    while (i<=right1 && j <= right2)
    {
        if (array[i] <= array[j])
        {
            temp.push_back(array[i++]);
            index++;
        }
        else
        {
            temp.push_back(array[j++]);
            index++;
        }
    }
    while (i<=right1)
    {
        temp.push_back(array[i++]);
        index++;
    }
    while (j<=right2)
    {
        temp.push_back(array[j++]);
        index++;
    }

    for (int i = 0; i < index;i++)
    {
        array[left1++] = temp[i];
    }
}

void merge_sort(int left,int right)
{
    if (left<right)
    {
        int mid = (left + right) / 2;
        merge_sort(left, mid);
        merge_sort(mid + 1, right);
        merge(left, mid, mid + 1, right);
    }
}


int main()
{
    merge_sort(0, 6);
    for (int i = 0; i < 7;i++)
        std::cout << array[i] << " ";
    system("pause");
    return 0;
}
//2.
//归并排序 非递归版本
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> array{66, 12, 33, 57, 64, 27, 18};

void merge(int left1, int right1,int left2, int right2)
{
    std::vector<int> temp;
    int i = left1, j = left2, index = 0;

    while (i<=right1 && j<=right2)
    {
        if (array[i] <= array[j])
        {
            temp.push_back(array[i++]);
            index++;
        }
        else
        {
            temp.push_back(array[j++]);
            index++;
        }
    }

    while (i<=right1)
    {
        temp.push_back(array[i++]);
        index++;
    }
    while (j<=right2)
    {
        temp.push_back(array[j++]);
        index++;
    }
    for (int i = 0; i < index;i++)
        array[left1++] = temp[i];
}


// void merge_sort(int n=7)
// {
//     for (int step = 2; step/2 < n;step*=2)
//     {
//         for (int i = 0; i < n;i+=step)
//         {
//             int mid = i + step / 2 - 1;
//             if (mid+1 < n)
//             {
//                 merge(i, mid, mid + 1, std::min(i+step-1,n-1));
//             }
//         }
//     }
// }

void merge_sort(int n=7)
{
    for (int step = 2; step / 2 < n;step*=2)
    {
        for (int i = 0; i < n;i+=step)
        {
            std::sort(array.begin() + i, array.begin() + std::min(i + step , n));
        }
    }
}


int main()
{
     merge_sort();
    for (auto i : array)
    {
        std::cout << i << " ";
    }
    system("pause");
    return 0;
}
//3.
//quick sort
#include <iostream>
#include <vector>
#include <ctime>

std::vector<int> array{35, 18, 16, 72, 24, 65, 12, 88, 46, 28, 55};


int core(int left,int right)
{
    int p = rand() % (right - left + 1) + left;
    std::swap(array[p], array[left]);
    int temp = array[left];

    while (left < right)
    {
        while (left < right && array[right] > temp)
            right--;
        array[left] = array[right];
        while (left<right && array[left] < temp)
            left++;
        array[right] = array[left];
    }
    array[left] = temp;
    return left;
}

void QuickSort(int left,int right)
{
    if (left < right)
    {
        int pos = core(left,right);
        QuickSort(left, pos);
        QuickSort(pos + 1, right);
    }
}

int main()
{
    std::srand(std::time(NULL));
    QuickSort(0, 10);

    for (auto i : array)
        std::cout << i << " ";

    std::cout << std::endl;

     system("pause");
    return 0;
}

//4.
#include <vector>
#include <iostream>

std::vector<int> array;

void merge(int left1,int right1,int left2,int right2)
{
    int i = left1, j = left2, index = 0;
    std::vector<int> temp;
    
    while (i <= right1 && j<=right2)
    {
        if (array[i] <= array[j])
        {
            temp.push_back(array[i++]);
            index++;
        }
        else
        {
            temp.push_back(array[j++]);
            index++;
        }
    }

    while (i<=right1)
    {
        temp.push_back(array[i++]);
        index++;
    }
    while (j<=right2)
    {
        temp.push_back(array[j++]);
        index++;
    }

    for (int i = 0; i < index;i++)
        array[left1++] = temp[i];
}

void merge_sort(int left,int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        merge_sort(left, mid);
        merge_sort(mid + 1, right);
        merge(left, mid, mid + 1, right);
    }
}

int main()
{
    int n,data;
    std::cin >> n;
    for (int i = 0; i < n;i++)
    {
        std::cin >> data;
        array.push_back(data);
    }
    merge_sort(0, n-1);

    for (auto i : array)
        std::cout << i << " ";
    std::cout << std::endl;
    system("pause");
    return 0;
}
//5.
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> array;

void merge_sort(int left,int right)
{
    int n = (int)array.size();
    for (int step = 2; step / 2 < n;step*=2)
    {
        for (int i = 0; i < n;i+=step)
        {
            std::sort(array.begin() + i, array.begin() + std::min(i + step, n));
        }
    }
}

int main()
{
    int n,data;
    std::cin >> n;
    for (int i = 0; i < n;i++)
    {
        std::cin >> data;
        array.push_back(data);
    }
    merge_sort(0, n-1);

    for (auto i : array)
        std::cout << i << " ";
    std::cout << std::endl;
    system("pause");
    return 0;
}

//6.
#include <iostream>
#include <vector>
#include <ctime>

std::vector<int> array;

int core(int left,int right)
{
    int p = rand() % (right - left + 1) + left;
    std::swap(array[p], array[left]);

    int temp = array[left];

    while (left < right)
    {
        while (left < right && array[right] > temp)
            right--;
        array[left] = array[right];
        while (left < right && array[left] < temp)
            left++;
        array[right] = array[left];
    }

    array[left] = temp;
    return left;
}

void quick_sort(int left,int right)
{
    if (left < right)
    {
        int pos = core(left,right);
        quick_sort(left, pos - 1);
        quick_sort(pos + 1, right);
    }
}

int main()
{
    std::srand(std::time(0));
    int n, data;
    std::cin >> n;
    for (int i = 0; i < n;i++)
    {
        std::cin >> data;
        array.push_back(data);
    }
    quick_sort(0, n - 1);

    for (auto i : array)
        std::cout << i << " ";
    std::cout << std::endl;
    system("pause");
    return 0;
}

4.7

//1.
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;

const int MAXN = 100010;
const int MOD = 10000007;
char str[MAXN];
int leftNumP[MAXN] = {0};

int main()
{
    gets(str);
    int len = strlen(str);

    for (int i = 0; i < len;i++)
    {
        if (i>0)
        {
            leftNumP[i] = leftNumP[i - 1];
        }
        if (str[i] == 'P')
        {
            leftNumP[i]++;
        }
    }
    int ans = 0, rightNumT = 0;
    for (int i = len - 1; i >= 0;i--)
    {
        if (str[i] == 'T')
            rightNumT++;
        else if (str[i] == 'A')
            ans = (ans + leftNumP[i] * rightNumT) & MOD;
    }
    printf("%d\n", ans);
    system("pause");
    return 0;
}
//2.
// 题目描述
// 给定一个长度为n（1≤n≤1,000,000）的无序正整数序列，以及另一个数k（1≤k≤1,000,000）（关于第k大的数：例如序列{1,2,3,4,5,6}中第3大的数是4。）

// 输入
// 第一行两个正整数m,n。
// 第二行为n个正整数。

// 输出
// 第k大的数。

// 样例输入

// 6 3
// 1 2 3 4 5 6
// 1
// 2
// 样例输出

// 4

//题目的思路是让用随机选择算法,原理类似于快排,我就直接sort完事了

#include <iostream>
#include <algorithm>
#include <vector>

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

int main()
{
    int n,m;
    std::cin >> n >> m;
    std::vector<int> array;

    int data;
    for (int i = 0; i < n;i++)
    {
        std::cin >> data;
        array.push_back(data);
    }
    std::sort(array.begin(), array.end(), cmp);
    std::cout << array[m - 1] << std::endl;
    system("pause");
    return 0;
}

// #include <stdio.h>
// #include <stdlib.h>
// #include <time.h>
// #include <math.h>

// // 对区间 [left, right] 进行划分 
// int randPartition(int *a, int left, int right) {
// 	int p = (round(1.0 * rand() / RAND_MAX * (right - left) + left));
// 	int temp = a[p];
// 	a[p] = a[left];
// 	a[left] = temp;
	 
// 	temp = a[left];
// 	while (left < right) {
// 		while (left < right && a[right] > temp)
// 			--right;
// 		a[left] = a[right];
// 		while (left < right && a[left] <= temp)
// 			++left;
// 		a[right] = a[left]; 
// 	}
// 	a[left] = temp;
// 	return left; 
// } 

// // 随机选择算法，返回范围中从小到大排，第 K 个数
// int randSelect(int *a, int left, int right, int K) {
// 	if (left == right) return a[left];
// 	int p = randPartition(a, left, right);
// 	int M = p - left + 1;
// 	if (K == M) return a[p];
// 	if (K < M) return randSelect(a, left, p - 1, K);
// 	else return randSelect(a, p + 1, right, K - M);
// } 
 
// int main() {
// 	int n, k, i;
// 	srand((unsigned)time(NULL)); 
// 	while (scanf("%d", &n) != EOF) {
// 		scanf("%d", &k);
// 		int nums[n];
// 		for (i = 0; i < n; ++i)
// 			scanf("%d", &nums[i]);
// 		printf("%d\n", randSelect(nums, 0, n-1, n-k+1));  // 注意第四个参数
// 	} 
// 	return 0;
// }

第五章

5.1

//1.
#include <iostream>
#include <algorithm>

int num[4];

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

void to_array(int n)
{
    for (int i = 0; i < 4;i++)
    {
        num[i] = n % 10;
        n /= 10;
    }
}

int to_num()
{
    int sum = 0;
    for (int i = 0; i < 4;i++)
    {
        sum = sum * 10 + num[i];
    }
    return sum;
}

int main()
{
    int sum;
    std::cin >> sum;

    while (true)
    {
        to_array(sum);
        std::sort(num, num + 4, cmp);
        int left = to_num();
        std::sort(num, num + 4);
        int right = to_num();

        sum = left - right;
        printf("%04d - %04d = %04d\n", left, right, sum);

        if (sum == 0 || sum == 6174)
            break;
    }
    system("pause");
    return 0;
}
//2.
#include <iostream>
#include <algorithm>

bool get(int n)
{
    int num = n * n;
    int sys = 10;
    while (true)
    {
        int count = num % sys;
        if (count == n)
            return true;
        if (sys > num)
            break;
        sys *= 10;
    }

    return false;
}


int main()
{
    int n;
    while (std::cin >> n)
    {
    if (get(n))
    {
        std::cout << "YSE" << std::endl;
    }
    else
    {
        std::cout << "NO" << std::endl;
    }
    }
    system("pause");
    return 0;
}
//3.
#include <stdio.h>
#include <cstdlib>

// 若四位数 a 是 b 的反序数，返回 1，否则返回 0 
//1089
#include <iostream>

bool panduan(int n1)
{
    int sum = 0;
    int n2 = n1;
    while (n2)
    {
        sum = sum * 10 + n2 % 10;
        n2 /= 10;
    }
    return sum == n1*9;
}

int main()
{
    for (int i = 1000; i <= 1111;i++)
    {
        if (panduan(i))
        {
            std::cout << i << std::endl;
        }
    }
    system("pause");
    return 0;
}
//4.
#include <stdio.h>
int main() {
	int n, x, y, z;
	while (scanf("%d", &n) != EOF) {
		// 所有数据都变为 3 倍，避免小数
		n *= 3;
		for (x = 0; x <= 100; ++x) {
			for (y = 0; y <= 100-x; ++y) {
				z = 100 - x - y;
				if (15*x + 9*y + z <= n)
					printf("x=%d,y=%d,z=%d\n", x, y, z); 
			} 
		} 
	} 
} 
//5.
#include <stdio.h>
int main() {
	int a, b, c;
	for (a = 1; a < 10; ++a)
		for (b = 0; b < 10; ++b)
			for (c = 0; c < 10; ++c)
				if (100*a + 110*b + 12*c == 532)
					printf("%d %d %d\n", a, b, c); 
	return 0;
} 
//6.
#include <iostream>
#include <algorithm>

int hashTable[21]={0};

int main()
{
    int n;
    for (int i = 1; i <= 20;i++)
    {
        std::cin >> n;
        hashTable[n]++;
    }
    int count = 0, k;
    for (int i = 1; i <= 20;i++)
    {
        if (hashTable[i]>count)
        {
            count = hashTable[i];
            k = i;
        }
    }
    std::cout << k << std::endl;
    system("pause");
    return 0;
}
//7.
#include <stdio.h>
int main(){
	int i, j, k;
	int a[2][3];
	int b[3][2];
	int c[2][2]; 
	while (scanf("%d %d %d", &a[0][0], &a[0][1], &a[0][2]) != EOF){
		scanf("%d %d %d", &a[1][0], &a[1][1], &a[1][2]);
		for (i = 0; i < 3; ++i) 
			for (j = 0; j < 2; ++j)
				scanf("%d", &b[i][j]);
		for (i = 0; i < 2; ++i) {
			for (j = 0; j < 2; ++j) {
				int sum = 0;
				for (k = 0; k < 3; ++k)
					sum += a[i][k] * b[k][j];
				c[i][j] = sum; 
			}
		}
		printf("%d %d\n", c[0][0], c[0][1]); 
		printf("%d %d\n", c[1][0], c[1][1]);
	} 
} 
//8.
#include <stdio.h>
int main() {
	int n, m;
	while (scanf("%d", &m) != EOF) {
		while (m--) {
			scanf("%d", &n);
			int flag = (n < 0);
			if (flag)
				n *= -1;
			int ans = (n + 2 * n) * (n + 1) / 2;
			printf("%d\n", flag ? -1 * ans : ans); 
		} 
	} 
	return 0;
} 
//9.
#include <iostream>

int main()
{
    double x,ans;
    int n;
    while (std::cin >> x >> n)
    {
        ans = x;
        while (n--)
        ans = ans * 2 / 3 + x / (3 * ans * ans);
		printf("%.6lf\n", ans); 
    }
    system("pause");
    return 0;
}
//10.
#include <stdio.h>
int main() {
	int i, n, p, table[100];
	p = 0;
	for (i = 0; i < 100; ++i)
		if (i % 7 && i % 10 != 7 && i / 10 != 7)
			table[p++] = i;
	
	while (scanf("%d", &n) != EOF) {
		int ans = 0;
		for (i = 0; i < p; ++i){
			if (table[i] > n)
				break;
			else 
				ans += table[i] * table[i];
		}
		printf("%d\n", ans); 
	} 
	return 0;
} 

5.2

//1.
#include <iostream>
// gcd(a,b) = gcd(b,a%b);


int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int main()
{
    int n, m;
    while (std::cin >> n >> m)
    {
        std::cout << gcd(n, m) << std::endl;
    }
    return 0;
}
//2.
#include <iostream>
#include <algorithm>

//找到最大公因数d后, 用a*b/d 考虑到a*b可能超限, 用a/d*b 来实现

int lcm(int a,int b)
{
    int i = a, j = b,r;
    if (a<b)
        std::swap(a, b);
    while (b)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return i/a*j;
}

int main()
{
    int n, m;
    while (std::cin >> n >> m)
    {
        std::cout << lcm(n, m) << std::endl;
    }
}
//3.
// 题目描述
// The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is 
// divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105.
// 输入
// Input will consist of multiple problem instances. The first line of the input will contain a single 
// integer indicating the number of problem instances. Each instance will consist of a single line of 
// the form m n1 n2 n3 … nm where m is the number of integers in the set and n1 … nm are the integers.
//  All integers will be positive and lie within the range of a 32-bit integer.
// 输出
// For each problem instance, output a single line containing the corresponding LCM. 
// All results will lie in the range of a 32-bit integer.
// 样例输入
// 2
// 2 3 5
// 3 4 6 12
// 1
// 2
// 3
// 样例输出
// 15
// 12


#include <stdio.h>

// 返回 a，b 的最大公约数
long gcd(long a, long b){
	return !b ? a : gcd(b, a % b); 
} 

int main() {
	long m, n, i, ans, input;
	while (scanf("%ld", &m) != EOF) {
		while (m--) {
			scanf("%ld", &n);
			scanf("%ld", &ans);
			if (n == 1){
				printf("%ld\n", ans);
				continue; 
			} 
			for (i = 0; i < n-1; ++i) {
				scanf("%ld", &input);
				ans = ans / gcd(ans, input) * input; //ans = LCM(ans,input)
			}
			printf("%ld\n", ans); 
		} 
	} 
	return 0;
} 

5.3

//1.
#include <iostream>
#include <algorithm>
struct Fraction
{
    int up, down;
};

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

Fraction reduction(Fraction result)
{
    if (result.down < 0)
    {
        result.up = -result.up;
        result.down = -result.down;
    }
    if (result.up == 0)
        result.down = 1;
    else
    {
        int d = gcd(std::abs(result.up), std::abs(result.down));
        result.up /= d;
        result.down /= d;
    }
    return result;
}

Fraction add(Fraction f1,Fraction f2)
{
    Fraction result;
    result.up = f1.up * f2.down + f2.up * f1.down;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction minu(Fraction f1,Fraction f2)
{
    Fraction result;
    result.up = f1.up * f2.down - f1.down * f2.up;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction multi(Fraction f1,Fraction f2)
{
    Fraction result;
    result.up = f1.up * f2.up;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction divide(Fraction f1,Fraction f2)
{
    Fraction result;
    result.up = f1.up * f2.down;
    result.down = f1.down * f2.up;
    return reduction(result);
}

void showResult(Fraction r)
{
    r = reduction(r);
    if (r.down == 1)
        printf("%lld", r.up);
    else if (std::abs(r.up) > r.down)
        printf("%d %d/%d", r.up / r.down, std::abs(r.up) % r.down, r.down);
    else
        printf("%d/%d", r.up, r.down);
}

int main()
{
    std::cout << "hello, world" << std::endl;
    return 0;
}
//2.
#include <iostream>

int main()
{
    int n;
    double ans;
    while (std::cin >> n)
    {
        ans = n;
        for (int i = 2; i <= n;i++)
        {
            ans = ans + (n - i + 1) * 2.0 * (1.0 / i);
        }
        std::cout << ans << std::endl;
    }
}

5.4

//1.
#include <iostream>
#include <type_traits>

using MAX = std::integral_constant<int, 100010>::type;

int prime[MAX::value], num = 0;
bool p[MAX::value]{false};

void Find_Prime()
{
    for (int i = 2; i < MAX::value;i++)
    {
        if (p[i] == false)
        {
            prime[num++] = i;
            for (int j = i + i; j < MAX::value;j+=i)
                p[j] = true;
        }
    }
}

int main()
{
    Find_Prime();
    int n, m, count = 0;
    std::cin >> n >> m;
    for (int i = n - 1; i < m;i++)
    {
        std::cout << prime[i];
        if (i==m-1)
        {
            std::cout << std::endl;
            break;
        }
        count++;
        if (count%10 == 0)
            std::cout << std::endl;
        else
            std::cout << " ";
    }
    system("pause");
    return 0;
}
//2.
#include <iostream>
#include <algorithm>

bool IsPrime(int n)
{
    if (n<2)
        return false;
    for (int i = 2; i*i <= n;i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

bool Isprime(int n)
{
    if (n < 2)
        return false;
    for (int i = 2; i < n;i++)
    {
        if(n % i == 0)
            return false;
    }
    return true;
}

int main()
{
    int n = 0;
    for (int i = 1; i <= 100;i++)
    {
        if (IsPrime(i))
            n++;
    }
    std::cout << n << std::endl;
    system("pause");
    return 0;

}
//3.
#include <iostream>
#include <type_traits>

using MAX = std::integral_constant<int, 101>::type;

bool prime[MAX::value] = {0};

bool IsPrime(int n)
{
    if (n<=1)
        return false;

    for (int i = 2; i * i <= n;i++)
    {
        if (n % i == 0)
            return false;
    }
    
    return true;
}

void find_prime_table()
{
    for (int i = 0; i <= 100;i++)
    {
        if (IsPrime(i))
            prime[i] = true;
    }
}

int main()
{
    find_prime_table();
    int n;
    while (std::cin >> n)
    {
        std::cout << (prime[n] ? "YES" : "NO") << std::endl;
    }
    return 0;
}
//4.
#include <iostream>
#include <type_traits>

using MAX = std::integral_constant<int, 101>::type;

int prime[MAX::value], num{0};

bool p[MAX::value]{false};

void Find_Prime()
{
    for (int i = 2; i < MAX::value;i++)
    {
        if (p[i] == false)
        {
            prime[num++] = i;
            for (int j = i + i; j < MAX::value;j+=i)
                p[j] = true;
        }
    }
}

int main()
{
    Find_Prime();
    for (int i = 0; i < num;i++)
        std::cout << prime[i] << " ";
    system("pause");
    return 0;
}
//5.
#include <stdio.h>

#define MAX 10010

int table[MAX/2];
int isPrime[MAX];

// 打素数表，只将个位为 1 的素数放入 table 
int findPrime(void) {
	int i, j, cnt = 0;
	for (i = 2; i < MAX; ++i)
		isPrime[i] = 1; 
	for (i = 2; i < MAX; ++i) {
		if (isPrime[i]) {
			if (i % 10 == 1)
				table[cnt++] = i; 
			for (j = i; j < MAX; j += i)
				isPrime[j] = 0; 
		}
	}
	return cnt;
} 

int main() {
	int n, i, cnt;
	cnt = findPrime();
	while (scanf("%d", &n) != EOF) {
		if (n < 11) {
			printf("-1\n");
			continue; 
		} 
		int flag = 0;
		for (i = 0; i < cnt; ++i) {
			if (table[i] >= n)
				break;
			if (flag)
				putchar(' ');
			flag = 1; 
			printf("%d", table[i]);
		}
		putchar('\n'); 
	}
	return 0;
} 
//6.
#include <iostream>
#include <type_traits>
#include <vector>

using MAX = std::integral_constant<int, 10001>::type;
using GET = std::integral_constant<int, 1500>::type;

std::vector<int> prime;
int num = 0;
bool p[MAX::value]{false};

void Find_Prime()
{
    for (int i = 2; i < MAX::value;i++)
    {
        if (p[i] == false)
        {
            prime.push_back(i);
            for (int j = i + i; j < MAX::value;j+=i)
                p[j] = true;
        }
    }
}

int main()
{
    Find_Prime();
    int n;
    while (std::cin >> n)
    {
        std::cout << prime[n - 1] << std::endl;
    }
    return 0;
}

5.5

//1.
#include <iostream>
#include <cmath>
#include <type_traits>
#include <vector>

using MAX = std::integral_constant<int, 10000>::type;

int prime[MAX::value], num = 0;
bool p[MAX::value]{false};

void Find_Prime()
{
    for (int i = 2; i < MAX::value;i++)
    {
        if (p[i] == false)
        {
            prime[num++] = i;
            for (int j = i + i; j < MAX::value;j+=i)
                p[j] = true;
        }
    }
}

struct factor
{
    int count;
    int cnt;
};

std::vector<factor> Factor;

int main()
{
    int n, pos = 0;
    std::cin >> n;
    Find_Prime();
    int sqr = (int)std::sqrt(1.0 * n);

    for (int i = 0; i < num && i <= sqr;i++)
    {
        if (n % prime[i] == 0)
        {
            Factor.push_back({0, prime[i]});
            while (n%prime[i] == 0)
            {
                Factor[pos].count++;
                n /= prime[i];
            }
            pos++;
        }
        if (n == 1)
            break;
    }
    if (n != 1)
        Factor.push_back({1, n});

    int sum = 0;

    for (auto i : Factor)
    {
        if (sum > 0)
            std::cout << "*";
        std::cout << i.cnt;
        if (i.count > 1)
            std::cout << "^" << i.count;
        sum++;
    }

    system("pause");
    return 0;
}
//2.
#include <iostream>

int main()
{
    int n;
    int sum = 0;
    while (std::cin >> n)
    {
        for (int j = 3; j <= n;j++)
        {
            for (int i = 1; i < j;i++)
            {
                if (j%i == 0)
                    sum += i;
            }
            if (sum == j)
                std::cout << j << " ";
            sum = 0;
        }
    }
    system("pause");
    return 0;
}
//3.
#include <type_traits>
#include <cmath>
#include <iostream>

using MAX = std::integral_constant<int, 1000>::type;

int prime[MAX::value], num = 0;
int p[MAX::value]{false};

void Find_Max()
{
    for (int i = 2; i < MAX::value;i++)
    {
        if (p[i] == false)
        {
            prime[num++] = i;
            for (int j = i + i; j < MAX::value;j+=i)
                p[i] = true;
        }
    }
}

int main()
{
    int n;
    Find_Max();
    while (std::cin >> n)
    {
        int sqr = (int)std::sqrt(1.0 * n);
        int count = 0;
        for (int i = 0; i <= sqr; i++)
        {
            if (n % prime[i] == 0)
            {
                while (n % prime[i] == 0)
                {
                    count++;
                    n /= prime[i];
                }
            }
            if (n == 1)
                break;
        }
        if (n!=1)
            count++;
        std::cout << count << std::endl;
        count = 0;
    }
    return 0;
}
//4.
#include <iostream>

int main()
{
    int n;
    while (std::cin >> n)
    {
        int sum = 0;
        for (int i = 1; i <= n;i++)
        {
            if (n%i == 0)
                sum++;
        }
        std::cout << sum << std::endl;
    }
    return 0;
}
//5.
#include <stdio.h>
#include <cstdlib>
#define MAX 60
int main() {
	int num, i;
	int cntE, cntG;
	cntE = cntG = 0;
	int E[MAX], G[MAX]; 
	for (num >= 2; num <= MAX; ++num) {
		int sum = 0;
		for (i = 1; i < num; ++i)
			if (!(num % i))
				sum += i;
		if (sum == i)
			E[cntE++] = i;
		else if (sum > i)
			G[cntG++] = i;
	}
	printf("E:"); 
	for (i = 0; i < cntE; ++i)
		printf(" %d", E[i]);
	printf("\nG:"); 
	for (i = 0; i < cntG; ++i)
		printf(" %d", G[i]);
    system("pause");
    return 0;
} 

5.6

//1.
#include <iostream>
#include <algorithm>
#include <type_traits>
#include <string>

using MAX = std::integral_constant<int, 100>::type;


//大数四则运算基本算法 除乘法外其他本质都是小学数学
struct Big_Num
{
    int d[MAX::value];
    int length;
    Big_Num()
    {
        length = 0;
        std::fill(d, d + MAX::value, 0);
    }
};

void transform(Big_Num& temp,std::string& str)
{
    int len = (int)str.size();

    for (int i = 0; i < len;i++)
    {
        temp.d[i] = str[len - i - 1]-'0';
    }

    temp.length = len;
}

int compare(Big_Num& a,Big_Num& b)
{
    if (a.length != b.length)
        return a.length > b.length;
    int len = (int)a.length;

    for (int i = len - 1; i >= 0;i--)
    {
        if (a.d[i] > b.d[i])
            return 1;
        else if (a.d[i] < b.d[i])
            return 0;
    }
    return -1;
}

Big_Num add(Big_Num& a, Big_Num& b)
{
    Big_Num c;
    int carry = 0;
    for (int i = 0; i < a.length || i < b.length; i++)
    {
        int temp = a.d[i] + b.d[i] + carry;
        c.d[c.length++] = temp % 10;
        carry = temp / 10;
    }
    if (carry != 0)
        c.d[c.length++] = carry;
    return c;
}

Big_Num sub(Big_Num& a,Big_Num& b)
{
    if (compare(a,b) == 0)
        std::swap(a, b);
    Big_Num c;

    for (int i = 0; i < a.length || i < b.length;i++)
    {
        if (a.d[i] < b.d[i])
        {
            a.d[i + 1] -= 1;
            a.d[i] += 10;
        }
        c.d[c.length++] = a.d[i] - b.d[i];
    }

    while (c.length > 0 && c.d[c.length-1] == 0)
        c.length--;

    return c;
}

Big_Num multi(Big_Num& a, int b)
{
    Big_Num c;
    int carry = 0;
    for (int i = 0; i < a.length;i++)
    {
        int temp = a.d[i] * b + carry;
        c.d[c.length++] = temp % 10;
        carry = temp / 10;
    }
    while (carry != 0)
    {
        c.d[c.length++] = carry % 10;
        carry /= 10;
    }
    return c;
}

Big_Num divide(Big_Num& a, int b, int& r)
{
    Big_Num c;
    c.length = a.length;
    for (int i = a.length - 1; i >= 0;i--)
    {
        r = r * 10 + a.d[i];
        if (r < b)
            c.d[i] = 0;
        else
        {
            c.d[i] = r / b;
            r %= b;
        }
    }

    while (c.length - 1 >= 1 && c.d[c.length-1] == 0)
    {
        c.length--;
    }
    return c;
}

void print(Big_Num& e)
{
    for (int i = e.length-1; i >=0 ;i--)
        std::cout << e.d[i];
    std::cout << std::endl;

}

int main()
{
    int c;
    Big_Num a, b;
    std::string str1;
    std::string str2;
    std::cin >> str1 >> c;
    transform(a, str1);
    //transform(b, str2);

    //Big_Num c = add(a, b);
    //Big_Num c = sub(a, b);
    //Big_Num d = multi(a, c);
    //print(d);
    int r = 0;
    Big_Num d = divide(a, c, r);
    print(d);

    system("pause");
    return 0;
}

// if (compare(a,b) == 1)
//     std::cout << "a>b" << std::endl;
// else if (compare(a,b) == 0)
//     std::cout << "a<b" << std::endl;
// else
//     std::cout << "a=b" << std::endl;

//2.
#include <iostream>
#include <string>
#include <algorithm>

//大数加法
struct Big_Num
{
    int d[1000];
    int length;
    Big_Num()
    {
        std::fill(d, d + 1000, 0);
        length = 0;
    }
};

void transform(Big_Num& e,std::string& str)
{
    int len = (int)str.size();

    for (int i = len - 1; i >= 0;i--)
        e.d[e.length++] = str[i]-'0';
}

Big_Num add(Big_Num& a,Big_Num& b)
{
    Big_Num c;
    int carry = 0;
    for (int i = 0; i < a.length || i < b.length; i++)
    {
        int temp = a.d[i] + b.d[i] + carry;
        c.d[c.length++] = temp % 10;
        carry = temp/ 10;
    }
    if (carry != 0)
        c.d[c.length++] = carry;

    return c;
}

void print(Big_Num& e)
{
    for (int i = e.length-1; i >=0 ;i--)
        std::cout << e.d[i];
    std::cout << std::endl;

}


int main()
{
    Big_Num a, b;
    std::string str1, str2;
    std::cin >> str1 >> str2;
    transform(a, str1);
    transform(b, str2);

    Big_Num c = add(a, b);
    print(c);

    system("pause");
    return 0;
}

//3.
#include <iostream>
#include <algorithm>
#include <string>

//大数阶乘
struct Big_Num
{
    int d[1000];
    int length;
    Big_Num()
    {
        std::fill(d, d + 1000, 0);
        length = 0;
    }
    friend std::ostream &operator<<(std::ostream &os, const Big_Num &e);
};

std::ostream &operator<<(std::ostream &os, const Big_Num &e)
{
    for (int i = e.length - 1; i >= 0;i--)
        os << e.d[i];
    return os;
}

Big_Num multi(Big_Num& a,int b)
{
    Big_Num c;
    int carry = 0;
    for (int i = 0; i < a.length;i++)
    {
        int temp = a.d[i] * b + carry;
        c.d[c.length++] = temp % 10;
        carry = temp / 10;
    }
    while (carry != 0)
    {
        c.d[c.length++] = carry % 10;
        carry /= 10;
    }
    return c;
}

int main()
{
    int n;
    std::cin >> n;

    Big_Num p;
    p.length = 1;
    p.d[0] = 1;

    for (int i = 1; i <= n;i++)
    {
        p = multi(p, i);
    }

    std::cout << p << std::endl;
    
    system("pause");
    return 0;
}

//4.
#include <iostream>
#include <algorithm>
#include <string>

//浮点数加法
struct Big_Num
{
    int before_point[1000], after_point[1000];
    int before_len, after_len;
    Big_Num()
    {
        std::fill(before_point, before_point + 1000, 0);
        std::fill(after_point, after_point + 1000, 0);
        before_len = after_len = 0;
    }
};

void transform(Big_Num& e,std::string& str)
{
    int flag = 0;
    int len = (int)str.size();
    for (int i = len-1; i>=0; i--)
    {
        if (str[i] == '.')
        {
            flag = 1;
            continue;
        }
        if (flag)
            e.before_point[e.before_len++] = str[i] - '0';
    }

    for (int i = 0; i<=len-1; i++)
    {
        if (str[i] == '.')
        {
            flag = 0;
            continue;
        }
        if (!flag)
            e.after_point[e.after_len++] = str[i] - '0';
    }
}

Big_Num add(Big_Num&a, Big_Num& b)
{
    Big_Num c;
    int carry = 0;
    c.after_len = std::max(a.after_len, b.after_len);
    for (int i = c.after_len - 1; i >= 0;i--)
    {
        int temp = a.after_point[i] + b.after_point[i] + carry;
        c.after_point[i] = temp % 10;
        carry = temp / 10;
    }

    for (int i = 0; i < a.before_len || i < b.before_len; i++)
    {
        int temp = a.before_point[i] + b.before_point[i] + carry;
        c.before_point[c.before_len++] = temp % 10;
        carry = temp / 10;
    }
    if (carry != 0)
        c.before_point[c.before_len++] = carry;
    return c;
}

void print(Big_Num& a)
{
    for (int i = a.before_len - 1; i >= 0;i--)
        std::cout << a.before_point[i];
    std::cout << '.';
    for (int i = 0; i <=a.after_len-1;i++)
        std::cout << a.after_point[i];
    std::cout << std::endl;
}

int main()
{
    Big_Num a, b;
    std::string str1,str2;
    std::cin >> str1 >> str2;
    transform(a, str1);
    transform(b, str2);
    Big_Num c = add(a, b);
    print(c);

    system("pause");
    return 0;
}

//5.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

//大数排序
const int maxn = 1010;

struct bign {
	int d[maxn];
	int len;
	bign() {
		memset(d, 0, sizeof(d));
		len = 0;
	}
}b[110];

bign change(char str[]) {
	bign a;
	a.len = strlen(str);
	for (int i = 0;i < a.len;++i) {
		a.d[i] = str[a.len - i - 1] - '0';
	}
	return a;
}

bool cmp(bign a, bign b) {
	if (a.len != b.len) return a.len < b.len;
	for (int i = a.len - 1;i >= 0;--i) {
		if (a.d[i] != b.d[i]) return a.d[i] < b.d[i];
	}
}

void print(bign a) {
	for (int i = a.len - 1;i >= 0;--i) printf("%d", a.d[i]);
	printf("\n");
}

int main() {
	int n;
	while (scanf("%d", &n) != EOF) {
		char str[maxn];
		for (int i = 0;i < n;++i) {
			scanf("%s", str);
			b[i] = change(str);
		}
		sort(b, b + n, cmp);
		for (int i = 0;i < n;++i) print(b[i]);
	}
	return 0;
}

//6.
#include <iostream>
#include <stack>

//方法将n 换为大整数 执行大数的除法,将余数替换n%base 本身替换为商即可

void change(int n,int base,std::stack<char>& get)
{
    char symbol[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
    while (n)
    {
        get.push(symbol[n % base]);
        n /= base;
    }
}

int main()
{
    int n, m;
    std::cin >> n >> m;
    std::stack<char> my;
    change(n, m, my);
    while (!my.empty())
    {
        std::cout << my.top();
        my.pop();
    }
    std::cout << std::endl;
    system("pause");
    return 0;
}

//7.
// 题目描述
// 对于一个十进制数A，将A转换为二进制数，然后按位逆序排列，再转换为十进制数B，我们称B为A的二进制逆序数。
// 例如对于十进制数173，它的二进制形式为10101101，逆序排列得到10110101，其十进制数为181，181即为173的二进制逆序数。
// -
// 输入
// 一个1000位(即10^999)以内的十进制数。
// -
// 输出
// 输入的十进制数的二进制逆序数。
// -
// 样例输入
// 985
// 1
// 样例输出
// 623

//和前一个进制转换 本质差不多 思路 先转换为二进制 在逆序转换回来就行了 ，两步转换就ok了

#include <cstdio>
#include <cstring>

#define MAX 2000

struct bign {
	int d[MAX];
	int len;
	bign() {
		memset(d, 0, sizeof(d));
		len = 0; 
	} 
};

bign change(char *str); 			// 字符串转为 bign			
bign binaryReverse(bign a);			// 把十进制的 a 转为二进制后按位逆序排列再转成十进制
bign add(bign a, bign b);			// 高精度加高精度 
bign multi(bign a, int b);			// 高精度乘低精度
bign divide(bign a, int b, int &r);	// 高精度除以低精度，r为余数
void print(const bign &a);			// 输出 bign，带换行 

int main() {
	char buffer[MAX];
	while (scanf("%s", buffer) != EOF)
		print(binaryReverse(change(buffer)));
	return 0;
}

bign change(char *str) {
	bign a;
	a.len = strlen(str);
	for(int i = 0; i != a.len; ++i)
		a.d[i] = str[a.len - i - 1] - '0';
	return a;
}

bign binaryReverse(bign a) {
	bign b;
	bign binary; 
	b.d[0] = 0; 
	b.len = 1;
	while (a.len != 1 || a.d[0] != 0) {
		a = divide(a, 2, binary.d[binary.len]);
		binary.len++;
	} 
	int i;
	for (i = 0; i != binary.len; ++i) {
		if (binary.d[binary.len - i - 1]) {
			bign power;
			power.d[0] = 1;
			power.len = 1; 
			for (int j = 0; j != i; ++j)
				power = multi(power, 2);
			b = add(b, power); 
		} 
	} 
	return b;
} 

bign add(bign a, bign b) {
	bign c;
	int carry = 0;
	int len = (a.len > b.len) ? a.len : b.len;
	for (int i = 0; i != len; ++i) {
		int temp = a.d[i] + b.d[i] + carry;
		c.d[c.len++] = temp % 10;
		carry = temp / 10; 
	}
	if (carry)
		c.d[c.len++] = carry;
	return c;
}

bign multi(bign a, int b) {
	bign c;
	int carry = 0;
	for (int i = 0; i != a.len; ++i) {
		int temp = b * a.d[i] + carry;
		c.d[c.len++] = temp % 10;
		carry = temp / 10; 
	}
	while (carry) {
		c.d[c.len++] = carry % 10;
		carry /= 10;
	} 
	return c;
} 

bign divide(bign a, int b, int &r) {
	r = 0;
	bign c;
	c.len = a.len;
	for (int i = a.len - 1; i >= 0; --i) {
		r = r * 10 + a.d[i];
		if (r < b)
			c.d[i] = 0;
		else {
			c.d[i] = r / b;
			r %= b;
		}
	} 
	while (c.len - 1 >= 1 && c.d[c.len - 1] == 0)
		--c.len;
	return c;
} 

void print(const bign &a) {
	for (int i = 0; i != a.len; ++i)
		putchar(a.d[a.len - i - 1] + '0'); 
	putchar('\n'); 
} 

5.7

//扩展欧几里得算法
//跳过了,有需要再看,毕竟gcd的证明都没看懂还,这个应该顶不住

#include <iostream>

int main()
{
    std::cout << "hello,world!" << std::endl;
    return 0;
}

5.8

//1.
//关于n!的一个问题 求n!中有多少个质因子p
//寄有点麻烦,后续遇到再来查看,先就用暴力实现吧
#include <iostream>

int cal1(int n,int p)
{
    int ans = 0;
    for (int i = 2; i <= n;i++)
    {
        int temp = i;
        while (temp % p ==0)
        {
            ans++;
            temp /= p;
        }
    }
    return ans;
}


//思路：n/p + n/p^2 + n/p^3 + ···
//非递归实现
int cal2(int n,int p)
{
    int ans = 0;
    while (n)
    {
        ans += n / p;
        n /= p;
    }
    return ans;
}

//递归实现
int cal3(int n,int p)
{
    if (n<p)
        return 0;
    return n / cal3(n / p, p);
}

//计算组合数 通过定义式 Cmn = n! / m!(n-m)!

long long GET_C(long long n, long long m)
{
    long long ans = 1;
    for (long long i = 1; i <= n;i++)
        ans *= i;
    for (long long i = 1; i <= m;i++)
        ans /= i;
    for (long long i = 1; i <= n - m;i++)
        ans /= i;
    return ans;
}
//2.
#include <cstdio>

float fact(float n) {
	if (n == 0)
		return 1;
	else
		return n * fact(n-1); 
} 

int main() {
	float m, n;
	while (scanf("%f %f", &m, &n) != EOF)
		printf("%.0f\n", fact(m)/(fact(n) * fact(m-n))); 
	return 0;
} 
//3.
#include <cstdio>

typedef long long LL;

LL C(LL n, LL m) {
	LL ans = 1;
	for (LL i = 1; i <= m; ++i)
		ans = ans * (n - m + i) / i;
	return ans; 
} 

int main() {
	LL n, m;
	while (scanf("%lld %lld", &n, &m) != EOF)
		printf("%lld\n", C(n, m)); 
} 
s

第六章

6.1

//1.
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <string>

int main()
{
    int n,m;
    std::cin >> n >> m;
    std::vector<std::vector<std::string>> array(n+1);

    std::string temp,data;
    for (int i=0;i<n;i++)
    {
        char str;
        std::getline(std::cin,temp);
        std::stringstream input(temp);
        input >> temp;
        while (input >> str)
        {
            array[str-'0'].push_back(temp);
        }
    }

    for (int i=1;i<=5;i++)
    {
        std::sort(array[i].begin(),array[i].end());
        std::cout << i << " " << array[i].size() << std::endl;
        for (auto j : array[i])
            std::cout << j << std::endl;
    }
    return 0;
}
//2.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int getid(char *name) {
    int id = 0;
    for(int i = 0; i < 3; i++)
        id = 26 * id + (name[i] - 'A');
    id = id * 10 + (name[3] - '0');
    return id;
}
const int maxn = 26 * 26 * 26 * 10 + 10;
vector<int> v[maxn];

int main() {
    int n, k, no, num, id = 0;
    char name[5];
    scanf("%d %d", &n, &k);
    for(int i = 0; i < k; i++) {
        scanf("%d %d", &no, &num);
        for(int j = 0; j < num; j++) {
            scanf("%s", name);
            id = getid(name);
            v[id].push_back(no);
        }
    }
    for(int i = 0; i < n; i++) {
        scanf("%s", name);
        id = getid(name);
        sort(v[id].begin(), v[id].end());
        printf("%s %lu", name, v[id].size());
        for(int j = 0; j < v[id].size(); j++)
            printf(" %d", v[id][j]);
        printf("\n");
    }
    return 0;
}

6.2

//1.
#include <iostream>
#include <set>

std::set<int> temp[50];

int main()
{
    int n,m,t;
    std::cin >> n;

    for (int i=0;i<n;i++)
    {
        int m;
        std::cin >> m;
        for (int j=0;j<m;j++)
        {
            std::cin >> t;
            temp[i].insert(t);
        }
    }

    int k;
    std::cin >> k;
    while (k--)
    {
        int s1, s2, NC =0 , NT = 0;
        std::cin >> s1 >> s2;

        NT = temp[s2-1].size();

        for (auto it : temp[s1-1])
        {
            if (temp[s2-1].find(it) != temp[s2-1].end())
                NC++;
            else
                NT++;
        }
        printf("%.1lf%%\n",100.0*NC/NT);
    }
    return 0;
}

6.3

//1.
#include <iostream>
#include <string>

int n;
std::string deal(std::string s, int & e)
{
    int k = 0;
    while (s.length() > 0 && s[0] == '0')
    {
        s.erase(s.begin());
    }
    if (s[0] == '.')
    {
        s.erase(s.begin());
        while (s.length() > 0 && s[0] == '0')
        {
            s.erase(s.begin());
            e--;
        }
    } else
    {
        while ( k < s.length() && s[k] != '.')
        {
            k++;
        }
        if (k < s.length())
        {
            s.erase(s.begin()+k);
        }
    }
    if (s.length() == 0)
    {
        e = 0;
    }
    int num = 0;
    std::string res;
    while (num < n)
    {
        if (k < s.length())
        {
            res += s[k++];
        }
        else
        {
            res += '0';
        }
        num++;
    }
    return res;
}

int main()
{
    std::string s1,s2,s3,s4;
    std::cin >> n >> s1 >> s2;
    int e1 = 0, e2 = 0;
    s3 = deal(s1,e1);
    s4 = deal(s2,e2);

    if (s3 == s4 && e1 == e2)
    {
        std::cout << "YES 0." << s3 << "*10^" << e1 << std::endl;
    }
    else
        std::cout << "NO 0." << s3 << "*10^" << e1 << " 0." << s4 << "*10^" << e2 <<'\n';

    return 0;
}

6.4

//1.
#include <iostream>
#include <map>
#include <string>

bool check(char e)
{
    if (e>='a' && e<='z' || e>='A' && e<='Z' || e>='0' && e<='9')
        return true;
    else
        return false;
}

int main()
{
    std::map<std::string,int> hash;

    std::string str;
    std::getline(std::cin,str);

    int len = str.length();
    int i = 0;
    while (i < len)
    {
        std::string word;
        while (i < len && check(str[i]))
        {
            if (str[i] >'A' && str[i]<'Z')
                str[i]+=32;
            word+=str[i];
            i++;
        }
        if (word != "")
            hash[word]++;
        while(i<len&&check(str[i])==false)
            ++i;
    }


    std::string k;
    int Max=0;
    for(auto it=hash.begin();it!=hash.end();++it)
    {
        if(it->second>Max)
        {
            k=it->first;
            Max=it->second;
        }
    }
    std::cout<<k<<" "<<Max<<std::endl;
    return 0;
}

6.5

//1.
#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    int min = INT_MAX, max = INT_MIN, min_pos = 0, max_pos = 0;
    int data;
    std::vector<int> array;
    for (int i = 0; i < 10;i++)
    {
        std::cin >> data;
        array.push_back(data);
        if (data < min)
        {
            min = data;
            min_pos = i;
        }
        if (data > max)
        {
            max = data;
            max_pos = i;
        }
    }

    if (min_pos != 0)
        std::swap(array[min_pos], array[0]);
    if (max_pos != 9)
        std::swap(array[max_pos], array[9]);

    for(auto it : array)
    {
        std::cout << it << " ";
    }
    system("pause");
    return 0;
}

6.6

//1.
#include <iostream>
#include <queue>
#include <vector>
#include <string>

struct fruit
{
    std::string name;
    int price;
    friend bool operator <(fruit a, fruit b)
{
    return a.price < b.price;
}
}f1,f2,f3;



int main()
{
    std::priority_queue<int> q1;
    std::priority_queue<int,std::vector<int>, std::greater<int> > q2;
    std::priority_queue<int,std::vector<int>, std::less<int> > q3;
    q1.push(2);
    q1.push(3);
    q1.push(1);

    q2.push(2);
    q2.push(3);
    q2.push(1);

    std::cout << q1.top() << std::endl;
    std::cout << q2.top() << std::endl;

    std::priority_queue<fruit> p;
    f1.name = "apple";
    f1.price = 2;
    f2.name = "orange";
    f2.price = 3;
    f3.name = "banana";
    f3.price = 1;

    p.push(f1);
    p.push(f2);
    p.push(f3);

    std::cout << p.top().name << ":" << p.top().price << std::endl;

    system("pause");
    return 0;
}
//2.
#include <iostream>
#include <string>
#include <cctype>
#include <map>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

map<string, set<string>> priorTask;
bool cmp(const string& a,const string& b)
{
    return priorTask[a].count(b) ? true : a < b;
}

int main() {
	int n, p, q;
	string input, task;
	vector<string> tasks;
	cin >> n;	getchar(); 
	for (int i = 0; i < n; ++i) {
		p = 0;
		getline(cin, input);
		while (isalnum(input[p]))
			++p;
		task = input.substr(0, p);
		tasks.push_back(task);
		do {
			q = ++p;
			while (isalnum(input[q]))
				++q;
			priorTask[task].insert(input.substr(p, q - p));
			p = q;
		} while (input[p] != ')'); 
	} 
	sort(tasks.begin(), tasks.end(), cmp);
	for (auto it = tasks.begin(); it != tasks.end(); ++it)
		cout << *it << " ";
    system("pause");

    return 0;
} 

6.7

//1.
#include <iostream>
#include <vector>
#include <string>
#include <cctype>
using namespace std;
struct Node {
	bool flag;
	double num;
	char op;
};
void doSomething(vector<Node>& ans, char doWhat1, char doWhat2) {
	for (int i = 0; i < ans.size(); ++i) {
		if (!ans[i].flag && (ans[i].op == doWhat1 || ans[i].op == doWhat2)) {
			double a = ans[i - 1].num, b = ans[i + 1].num;
			char op = ans[i].op;
			ans.erase(ans.begin() + i - 1, ans.begin() + i + 2);
			--i;
			Node temp;
			temp.flag = true;
			if 		(op == '+')	temp.num = a + b;
			else if (op == '-')	temp.num = a - b;
			else if (op == '*')	temp.num = a * b;
			else if (op == '/')	temp.num = a / b;
			ans.insert(ans.begin() + i, temp);
		} 
	} 
} 
int main() {
	int p, q;
	string input;
	vector<Node> ans; 
	while (getline(cin, input) && input != "0") {
		ans.clear();
		input += " ";
		p = 0;
		do {
			q = p;
			while (input[q] != ' ')
				++q;
			Node temp;
			if (isdigit((input.substr(p, q - p))[0])) {
				temp.flag = true;
				temp.num = stod(input.substr(p, q - p));
			} else {
				temp.flag = false;
				temp.op = (input.substr(p, q - p))[0];
			}
			ans.push_back(temp); 
			p = ++q;
		} while (q < input.size() - 1);
		doSomething(ans, '*', '/');
		doSomething(ans, '+', '-');
		printf("%.2lf\n", ans[0].num); 
	}
	return 0;
} 
//2.
#include <cstdio>
#include <stack>
#include <string>
using namespace std;
const string CATCHUP = "()[]{}";
int main() {
	int n;
	char input;
	bool flag;
	while (scanf("%d", &n) != EOF) {
		getchar(); 
		while (n--) {
			flag = true;
			stack<char> parentheses;
			while ((input = getchar()) != '\n') {
				if (input == '(' || input == '[' || input == '{')
					parentheses.push(input);
				else if (input == ')' || input == ']' || input == '}') {
					if (parentheses.empty() || CATCHUP.find(input) - CATCHUP.find(parentheses.top()) != 1)
						flag = false;
					else
						parentheses.pop();
				}
			}
			if (!parentheses.empty())
				flag = false;
			puts(flag ? "yes" : "no"); 
		}
	} 
	return 0;
} 

6.8

//1.
#include <map>
#include <iostream>

int main()
{
    int n;
    std::cin >> n;

    while (n--)
    {
        std::pair<double, double> ans(0,0);
        double input;
        for (int i = 0; i < 3;i++)
        {
            std::cin >> input;
            ans.first += input;
            std::cin >> input;
            ans.second += input;
        }
        printf("%.1lf %.1lf\n", (ans.first / 3), (ans.second / 3));
    }
    system("pause");
    return 0;
}
//2.

6.9

//1.
#include <iostream>
#include <algorithm>
#include <string>

int main()
{
    std::string temp;
    std::cin >> temp;

    std::reverse(temp.begin(), temp.end());
    std::cout << temp;

    system("pause");
    return 0;
}
//2.
#include <iostream>
#include <algorithm>
#include <string>

int main()
{
    // int a[3] = {1, 2, 3};
    // do{
    //     printf("%d%d%d\n", a[0], a[1], a[2]);
    // } while (std::next_permutation(a, a + 3));
    std::string input;

    while (std::cin >> input)
    {
        do{
            std::cout << input << std::endl;
        } while (std::next_permutation(input.begin(), input.end()));
    }

    system("pause");
    return 0;
}
//3.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int n, input;
	while (cin >> n) {
		int MAX = -2147483648, MIN = 2147483647;
		while (n--) {
			cin >> input;
			MAX = max(MAX, input);
			MIN = min(MIN, input);
		}
		cout << MAX << " " << MIN << endl;
	} 
	return 0;
} 

第八章

8.1

//1.
#include <iostream>

int max_value = 0;

int n,all_weight;
int price[10], weight[10];

void DFS1(int index,int PSum,int WSum)
{
    if (index == n)
    {
        if (PSum > max_value && WSum <= all_weight)
        {
            max_value = PSum;
        }
        return;
    }
    DFS1(index + 1, PSum, WSum);
    DFS1(index + 1, PSum + price[index], WSum + weight[index]);
}

void DFS2(int index,int PSum,int WSum)
{
    if (index == n)
    {
        return;
    }
    DFS2(index + 1, PSum, WSum);

    if (WSum + weight[index] <= all_weight)
    {
        if (PSum + price[index] > max_value)
        {
            max_value = PSum + price[index];
        }
        DFS2(index + 1, PSum + price[index], WSum + weight[index]);
    }
}

int main()
{
    std::cin >> n >> all_weight;
    for (int i = 0; i < n;i++)
    {
        std::cin >> weight[i];
    }
    for (int i = 0; i < n;i++)
    {
        std::cin >> price[i];
    }
    DFS2(0,0,0);

    std::cout << max_value << std::endl;

    system("pause");
    return 0;
}
//2.
#include <iostream>
#include <vector>

int n, k, x, maxSumSqu = -1;
int A[10];
std::vector<int> temp,ans;

void DFS1(int index,int nowk,int sum, int sumsqrt)
{
    if (nowk == k && sum == x)
    {
        if(sumsqrt > maxSumSqu)
        {
            ans = temp;
            maxSumSqu = sumsqrt;
        }
    }

    if (index == n || nowk > k || sum > x)
        return;

    temp.push_back(A[index]);
    DFS1(index + 1, nowk + 1, sum + A[index], sumsqrt + A[index] * A[index]);
    temp.pop_back();
    DFS1(index + 1, nowk, sum, sumsqrt);
}

int main()
{
    int n;
    std::cin >> n;

    for (int i = 0; i < n;i++)
        std::cin >> A[i];


}
//3.
#include <iostream>

int count = 0;
int n;
int p[10];
bool hash[10]{false};

void DFS(int index)
{
    if (index == n)
    {
        count++;
        for (int i = 0; i < n;i++)
        {
            std::cout << p[i];
        }
        std::cout << std::endl;
        return;
    }

    for (int x = 1; x <= n; x++)
    {
        if (hash[x] == false)
        {
            p[index] = x;
            hash[x] = true;
            DFS(index + 1);
            hash[x] = false;
        }
    }
}

int main()
{
    std::cin >> n;
    DFS(0);
    std::cout << count << std::endl;
    system("pause");
    return 0;
}
//4.
#include <iostream>
#include <vector>

int p[10];
bool hash[10]{false};

int count = 0;
int n,r;

void DFS(int index,std::vector<int> temp)
{
    if (temp.size() == r)
    {
        count++;
        for (int i = 0; i < temp.size();i++)
            std::cout << temp[i] << " ";
        std::cout << std::endl;
        return;
    }
    if (index > n)
        return;
    temp.push_back(index);
    DFS(index + 1,temp);
    temp.pop_back();
    DFS(index + 1,temp);
}

int main()
{
    std::cin >> n >> r;
    std::vector<int> temp;
    DFS(1,temp);
    std::cout << count << std::endl;

    system("pause");
}
//5.
#include <iostream>
#include <vector>

int count = 0;
int n,m;
int A[10];

bool isPrime(int n) {
	if (n < 2)
		return false;
	for (int i = 2; i * i <= n; ++i)
		if (n % i == 0)
			return false; 
	return true;
} 

void dfs(int index,std::vector<int> temp)
{
    if (temp.size() == m)
    {
        int ans = 0;
        for (int i = 0; i < temp.size();i++)
            ans+= temp[i];
        if (isPrime(ans))
            count++;
        return;
    }

    if (index > n-1)
        return;

    temp.push_back(A[index]);
    dfs(index + 1, temp);
    temp.pop_back();
    dfs(index + 1, temp);
}

int main()
{
    std::cin >> n >> m;
    for (int i = 0; i < n;i++)
        std::cin >> A[i];
    std::vector<int> temp;
    dfs(0, temp);
    std::cout << count << std::endl;
    system("pause");
    return 0;
}
//6.
#include <iostream>
#include <algorithm>

int isWrite = false;
int p[10];
int hash[10]{false};
int n;

void dfs(int index)
{
    if (index == n+1)
    {
        isWrite = true;
        for (int i = 1; i <= n;i++)
            std::cout << p[i];
        std::cout << std::endl;
        return;
    }

    for (int x = 1; x <= n;x++)
    {
        if (hash[x] == false)
        {
            int flag = true;
            for (int pre = 1; pre < index;pre++)
            {
                if (std::abs(index-pre) == std::abs(x-p[pre]))
                {
                    flag = false;
                    break;
                }
            }

            if (flag)
            {
                p[index] = x;
                hash[x] = true;
                dfs(index + 1);
                hash[x] = false;
            }
        }
    }
}

int main()
{
    std::cin >> n;
    dfs(1);
    system("pause");
    return 0;
}
//7.
#include <iostream>

//开始一直没看懂题目是什么意思,以为随便入栈出栈就完事了，直接用的全排列
//实际上时固定入栈顺序,但出栈顺序随意

//所以思路就是 wait为还未入栈的元素 stack为栈中元素, 两者都为0时代表一个序列已经生成了

//分叉就是每次处理时,是出栈一个元素还是入栈一个元素

int ant = 0;

void DFS(int wait,int stack)
{
    if (wait == 0 && stack == 0)
    {
        ant++;
        return;
    }
    if (wait > 0)
    {
        DFS(wait-1, stack+1);
    }
    if (stack > 0)
    {
        DFS(wait, stack-1);
    }
}

//卡特兰数 1/n+1  *   (C n/2n)  组合数


// #include <iostream>
// using namespace std;
// int main() {
// 	long long n;
// 	while (scanf("%ld", &n) != EOF) {
// 		long long ans = 1;
// 		for (long long i = 1; i <= n; ++i)
// 			ans = ans * (n + i) / i;
// 		printf("%ld\n", ans / (n + 1)); 
// 	} 
// 	return 0;
// }

int main()
{
    int n;
    std::cin >> n;
    DFS(n, 0);

    std::cout << ant << std::endl;
    system("pause");
    return 0;
}

//8.
#include <iostream>
#include <type_traits>
#include <algorithm>
#include <map>
#include <vector>
using MAX = std::integral_constant<int, 10>::type;


int start_x, start_y;
int end_x, end_y;

int n, m;

int xp[4] = {-1, 0, 1, 0};
int yp[4] = {0, -1, 0, 1};

int matrix[MAX::value][MAX::value];

std::vector<std::pair<int,int>> temp;

void DFS(int x,int y)
{
    if (x == end_y && y == end_x)
    {
        for (auto it : temp)
        {
            std::cout << '(' << it.second << ',' << it.first << ')' << "->";
        }
        std::cout << '(' << 5 << ',' << 6 << ')' << std::endl;
        return;
    }

    for (int i = 0; i < 4;i++)
    {
        if (x + xp[i] >=1 && y + yp[i] >= 1 && x + xp[i]<=m && y + yp[i]<=n && matrix[y][x] == 1)
        {
            temp.push_back({x, y});
            matrix[y][x] = 0;

//            for (auto it : temp)
//            {
//                std::cout << '(' << it.second << ',' << it.first << ')' << "->";
//            }
//            std::cout << std::endl;

            DFS(x + xp[i], y + yp[i]);
            temp.pop_back();
            matrix[y][x] = 1;
        }
    }
}

int main()
{

    std::cin >> n >> m;
    for (int i = 1; i <= n;i++)
    {
        for (int j = 1; j <= m;j++)
        {
            std::cin >> matrix[i][j];
        }
    }

    std::cin >> start_x >> start_y;
    std::cin >> end_x >> end_y;
    DFS(start_x, start_y);

    system("pause");
    return 0;
}

8.2

第九章

9.2

//1.PATA1020
#include <iostream>
#include <queue>

int IN[30];
int POST[30];

class TREE
{
    public:
    struct node {
        int data;
        node *l_child;
        node *r_child;
    };
    using NODE = node *;

    TREE():root(nullptr){}

    void layer_display();

    void Creat(int lin,int rin,int lpost,int rpost)
    {
        root=creat(lin, rin, lpost, rpost);
    }

    NODE creat(int LIN, int RIN, int LPOST, int RPOST);

private:
    NODE root;
};



//IN   中序序列  [LIN,RIN]
//POST 后序序列  [LPOST,RPOST]

TREE::NODE TREE::creat(int LIN, int RIN, int LPOST, int RPOST)
{
    if (LPOST > RPOST)
        return nullptr;

    TREE::NODE root = new TREE::node;

    root->data = POST[RPOST];

    int k;
    for (k = 0; k <= RIN;k++)
    {
        if (IN[k]==POST[RPOST])
            break;
    }

    int num = k - LIN;

    root->l_child = creat(LIN, k - 1, LPOST, LPOST + num - 1);
    root->r_child = creat(k + 1, RIN, LPOST + num, RPOST - 1);
    return root;
}

void TREE::layer_display()
{
    std::queue<TREE::NODE> my_queue;
    my_queue.push(root);

    while (!my_queue.empty())
    {
        TREE::NODE now = my_queue.front();
        my_queue.pop();

        if (now->l_child!= nullptr)
        {
            my_queue.push(now->l_child);
        }
        if (now->r_child!= nullptr)
        {
            my_queue.push(now->r_child);
        }
        if (!my_queue.empty())
            std::cout << now->data <<" ";
        else
            std::cout << now->data;
    }
}

int main()
{
    int n;
    std::cin >> n;

    for (int i = 0; i < n;i++)
        std::cin >> POST[i];
    for (int i = 0; i < n;i++)
        std::cin >> IN[i];

    TREE my_tree;
    my_tree.Creat(0, n - 1, 0, n - 1);
    my_tree.layer_display();

    return 0;
}
//2.
// 题目描述
// 编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
// 例如如下的先序遍历字符串：
// ABC##DE#G##F###
// 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
// -
// 输入
// 输入包括1行字符串，长度不超过100。
// -
// 输出
// 可能有多组测试数据，对于每组数据，
// 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
// 每个输出结果占一行。
// 样例输入
// -
// a#b#cdef#####
// a##
// 样例输出
// -
// a b f e d c 
// a 

#include <iostream>

struct node
{
    char data;
    node *l_child;
    node *r_child;
};

void creat(node* & root)
{
    char c;
    std::cin >> c;
    
    if (c=='#')
        return;
    else
    {
        root = new node;
        root->data = c;
        root->l_child = nullptr;
        root->r_child = nullptr;
        creat(root->l_child);
        creat(root->r_child);
    }
}

void display(node* & root)
{
    if (root == nullptr)
        return;
    else
    {
        display(root->l_child);
        std::cout << root->data << " ";
        display(root->r_child);
    }
}

int main()
{
    node *root = nullptr;
    while (true)
    {
        creat(root);
        display(root);
        std::cout << std::endl;
    }

    system("pause");
    return 0;
}
//3.
// 题目描述
// 小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。
// -
// 输入
// 输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。
// -
// 输出
// 对于每组输入，输出对应的二叉树的后续遍历结果。
// 样例输入
// -
// DBACEGF ABCDEFG
// BCAD CBAD
// 样例输出
// -
// ACBFGED
// CDAB
#include <iostream>
#include <string>
using std::string;

string PRE;
string IN;

struct node
{
    char data;
    node *l_child;
    node *r_child;
};

//前序 pre 
//中序 in 

//n  [0,n-1]

node * creat(int Lpre,int Rpre,int Lin,int Rin)
{
    if (Lpre > Rpre)
        return nullptr;

    node *root = new node;
    root->data = PRE[Lpre];

    int k;
    for (k = Lin; k <= Rin;k++)
    {
        if (IN[k]==PRE[Lpre])
            break;
    }

    int num = k - Lin;

    root->l_child = creat(Lpre+1,Lpre+num,Lin,k-1);
    root->r_child = creat(Lpre+num+1,Rpre,k+1,Rin);
    return root;
}

void display(node* & root)
{
    if (root == nullptr)
        return;
    else
    {
        display(root->l_child);
        display(root->r_child);
        std::cout << root->data;
    }
}

int main()
{
    while (std::cin >> PRE >> IN)
    {
        int n = (int)PRE.size();
        node *root = creat(0, n - 1, 0, n - 1);
        display(root);
        std::cout << std::endl;
    }
    system("pause");
    return 0;
}
//4.
// 题目描述
// -
// 如上所示，由正整数1，2，3……组成了一颗特殊二叉树。我们已知这个二叉树的最后一个结点是n。现在的问题是，结点m所在的子树中一共包括多少个结点。
// -
// 比如，n = 12，m = 3那么上图中的结点13，14，15以及后面的结点都是不存在的，结点m所在子树中包括的结点有3，6，7，12，因此结点m的所在子树中共有4个结点。
// -
// 输入
// 输入数据包括多行，每行给出一组测试数据，包括两个整数m，n (1 <= m <= n <= 1000000000)。最后一组测试数据中包括两个0，表示输入的结束，这组数据不用处理。
// -
// 输出
// 对于每一组测试数据，输出一行，该行包含一个整数，给出结点m所在子树中包括的结点的数目。
// 样例输入
// -
// 3 7
// 142 6574
// 2 754
// 0 0
// 样例输出
// -
// 3
// 63
// 498

//递归写法 易懂
#include <iostream>

int n, m;

int get_value(int now)
{
    //每次判断当前节点是否在最大节点范围内
    if (now > n)
        return 0;
    //如果不在,直接返回,如果在 value + 1 , 在去判断当前节点的左右结点是否也在   2i 和 2i+1
    else
        return get_value(2 * now) + get_value(2 * now + 1) + 1;
}

int main()
{
    while (std::cin >> m >> n)
    {
        std::cout <<get_value(m) <<  std::endl;
    }

    system("pause");
    return 0;
}

9.3

//1.PATA1053
#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 200;

//对于一般树的解决,用容器容纳

struct node
{
    int weight;
    std::vector<int> child;
}NODE[MAXN];

bool cmp(int a,int b)
{
    return NODE[a].weight > NODE[b].weight;
}

// n = 节点数  m = 非叶节点数  s = 权值和
int n,m,s;

//path 记录路径 保存child
int path[MAXN];

//index 当前访问节点  numNode 当前path中的节点数  sum 权值和
void DFS(int index, int numNode, int sum)
{
    if (sum > s)
        return ;
    if (sum == s)
    {
        if (NODE[index].child.size() != 0)
            return ;

        for (int i=0; i<numNode; i++)
        {
            std::cout << NODE[path[i]].weight;

            if (i < numNode-1)
                std::cout << " ";
            else
                std::cout << std::endl;
        }
        return ;
    }

    for (int i=0;i<NODE[index].child.size();i++)
    {
        int child = NODE[index].child[i];
        path[numNode] = child;
        DFS(child,numNode+1,sum+NODE[child].weight);
    }
}

int main()
{
    int id,num,child;

    std::cin >> n >> m >> s;

    for (int i=0; i<n; i++)
        std::cin >> NODE[i].weight;

    for (int i=0; i<m; i++)
    {
        std::cin >> id >> num;

        for (int j=0;j<num;j++)
        {
            std::cin >> child;
            NODE[id].child.push_back(child);
        }
        //由于后面路径是按权值高低输出,在此处先对子节点按高到低排序
        std::sort(NODE[id].child.begin(),NODE[id].child.end(),cmp);
    }
    //第一个路径总是root
    path[0] = 0;
    DFS(0,1,NODE[0].weight);

    return 0;
}
//2.
// 一棵树有n个节点，其中1号节点为根节点。
// -
// 输入：
// 第一行是整数n，表示节点数
// 后面若干行，每行两个整数a b，表示b是a的子节点
// 输出：
// 求这棵树的高度（根节点为第1层）
// 样例输入：
// 5
// 1 2
// 1 3
// 3 4
// 3 5
// 样例输出：
// 3

#include <vector>
#include <iostream>
#include <queue>
using namespace std;

int BFS(vector<vector<int>>& tree)
{
    int level = 0;
    queue<int> my_queue;
    my_queue.push(1);

    while (!my_queue.empty())
    {
        int now = my_queue.front();
        my_queue.pop();

        for (int i = 1; i < tree[now].size();i++)
        {
            //计算子节点层数
            tree[tree[now][i]][0] = tree[now][0] + 1;
            //子节点入队
            my_queue.push(tree[now][i]);
            //将节点赋给level  因为BFS是逐层遍历下来的 所以最终保存的一定是最大层数
            level = tree[tree[now][i]][0];
        }
    }
    //第一层 储存的层数为0 所以后序的层数都比实际层数少一
    return level + 1;
}

int main()
{
    int n,id,child;
    cin >> n;

    // 这里{0} 的作用,预备一个元素 用来储存层数 ,实际孩子的节点从1开始存储
    // 这也是我一直觉得麻烦的,怎么储存层数最简单,我的想法是结构体储存,但比起这种方法麻烦了点
    vector<vector<int>> tree(n + 1,{0});

    while (cin >> id >> child && id != -1)
    {
        tree[id].push_back(child);
    }

    cout << BFS(tree) << endl;
    system("pause");
    return 0;
}
//3.
// 题目描述
// 有一棵树，输出某一深度的所有节点，有则输出这些节点，无则输出EMPTY。该树是完全二叉树。
// -
// 输入
// 输入有多组数据。
// 每组输入一个n(1<=n<=1000)，然后将树中的这n个节点依次输入，再输入一个d代表深度。
// -
// 输出
// 输出该树中第d层得所有节点，节点间用空格隔开，最后一个节点后没有空格。
// 样例输入
// 5
// 1 2 3 4 5 
// 7
// 7
// 1 2 3 4 5 6 7 
// 2
// 0
// 样例输出
// EMPTY
// 2 3
#include <iostream>
#include <cmath>

int main()
{
    //完全二叉树,直接用性质就行了
    int n,depth;
    while (std::cin >> n && n!=0)
    {
        int tree[n];
        for (int i = 1; i <= n;i++)
            std::cin >> tree[i];

        std::cin >> depth;

        int left = std::pow(2, depth-1) - 1;
        int right = std::pow(2, depth) - 1;

        if (left > n)
        {
            std::cout << "EMPTY" << std::endl;
            continue;
        }

        if (n < right)
            right = n;

        for (int i = left + 1; i <= right;i++)
            std::cout << tree[i] << " ";
        std::cout << std::endl;
    }

}

9.4

//1.PATA1043
#include <cstdio>
#include <vector>
using namespace std;

struct node
{
    int data;
    node *left, *right;
};

void insert(node*& root,int data)
{
    if (root == nullptr)
    {
        root = new node;
        root->data = data;
        root->left = root->right = nullptr;
        return;
    }
    if (data < root->data)
        insert(root->left, data);
    else
        insert(root->right, data);
}

void preOrder(node* root,vector<int>& vi)
{
    if (root == nullptr)
        return;
    vi.push_back(root->data);
    preOrder(root->left, vi);
    preOrder(root->right, vi);
}

void preOrderMirror(node* root,vector<int>& vi)
{
    if (root == nullptr)
        return;
    vi.push_back(root->data);
    preOrderMirror(root->right, vi);
    preOrderMirror(root->left, vi);
}

void postOrder(node* root,vector<int>& vi)
{
    if (root == nullptr)
        return;
    postOrder(root->left, vi);
    postOrder(root->right, vi);
    vi.push_back(root->data);
}

void postOrderMirror(node* root,vector<int>& vi)
{
    if (root == nullptr)
        return;
    postOrderMirror(root->right, vi);
    postOrderMirror(root->left, vi);
    vi.push_back(root->data);
}

vector<int> origin, pre, preM, post, postM;

int main()
{
    int n, data;
    node *root = nullptr;
    scanf("%d", &n);

    for (int i = 0; i < n;i++)
    {
        scanf("%d", &data);
        origin.push_back(data);
        insert(root, data);
    }

    preOrder(root, pre);
    preOrderMirror(root, preM);
    postOrder(root, post);
    postOrderMirror(root, postM);

    if (origin == pre)
    {
        printf("YES\n");
        for (int i = 0; i < post.size();i++)
        {
            printf("%d", post[i]);
            if (i<post.size()-1)
                printf(" ");
        }
    }else if (origin == preM)
    {
        printf("YES\n");
        for (int i = 0; i < postM.size();i++)
        {
            printf("%d", postM[i]);
            if (i<postM.size()-1)
                printf(" ");
        }
    }else
    {
        printf("NO\n");
    }
    return 0;
}
//2.
// 题目描述
// 输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
// -
// 输入
// 输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。
// -
// 输出
// 可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。
// 样例输入
// 1
// 2 
// 2
// 8 15 
// 4
// 21 10 5 39
// 样例输出
// 2 
// 2 
// 2 
// 8 15 
// 8 15 
// 15 8 
// 21 10 5 39 
// 5 10 21 39 
// 5 10 39 21 
#include <iostream>
#define ENDL std::cout << std::endl;

struct node
{
    int data;
    node *l_child;
    node *r_child;
};

using NODE = node *;

void insert(NODE& root,int data)
{
    if (root == nullptr)
    {
        root = new node;
        root->data = data;
        root->l_child = nullptr;
        root->r_child = nullptr;
        return;
    }
    else if (root->data > data)
    {
        insert(root->l_child, data);
    }
    else
        insert(root->r_child, data);
}

NODE creat(int n)
{
    int data;
    NODE root = nullptr;
    for (int i = 0; i < n;i++)
    {
        std::cin >> data;
        insert(root, data);
    }
    return root;
}

void pre_display(NODE root)
{
    if(root)
    {
        std::cout << root->data << " ";
        pre_display(root->l_child);
        pre_display(root->r_child);
    }
}
void in_display(NODE root)
{
    if (root)
    {
        in_display(root->l_child);
        std::cout << root->data << " ";
        in_display(root->r_child);
    }
}

void post_display(NODE root)
{
    if (root)
    {
        post_display(root->l_child);
        post_display(root->r_child);
        std::cout << root->data << " ";
    }
}

int main()
{
    int n;
    while (std::cin >> n)
    {
        NODE root = creat(n);
        std::cout << n << ":" << std::endl;
        pre_display(root);
        ENDL;
        in_display(root);
        ENDL;
        post_display(root);
        ENDL;
    }

    return 0;
}
//3.
// 判断两序列是否为同一二叉搜索树序列
// -
// 输入
// 开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
// 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
// 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
// -
// 输出
// 如果序列相同则输出YES，否则输出NO
// 样例输入
// 6
// 45021
// 12045
// 54120
// 45021
// 45012
// 21054
// 50412
// 0
// 样例输出
// NO
// NO
// YES
// NO
// NO
// NO
#include <iostream>
#include <string>
using namespace std;

struct Node {
	char data;
	Node *lchild, *rchild;
};

Node* newNode(char x) {
	Node *p = new Node;
	p->data = x;
	p->lchild = p->rchild = nullptr;
	return p;
} 
void insert(Node* &root, char x) {
	if (!root) { 
		root = newNode(x);
		return;
	}
	if (x <= root->data)
		insert(root->lchild, x);
	else if (x > root->data) 
		insert(root->rchild, x);
}
void preOrder(Node *root, string &pre) {
	pre += root->data;
	if (root->lchild)
		preOrder(root->lchild, pre);
	if (root->rchild)
		preOrder(root->rchild, pre);
}
void inOrder(Node *root, string &in) {
	if (root->lchild)
		inOrder(root->lchild, in);
	in += root->data;
	if (root->rchild)
		inOrder(root->rchild, in);
}
void deleteTree(Node* &root) {
	if (root == nullptr)
		return; 
	deleteTree(root->lchild);
	deleteTree(root->rchild);
	delete root;
} 

int main() {
	int n;
	string input, pre1, in1, pre2, in2;
	while (scanf("%d", &n) != EOF && n) { 
		getchar(); 
		string pre1, in1, pre2, in2;
		getline(cin, input);
		Node *root1 = newNode(input[0]);
		for (int i = 1; i < input.size(); ++i)
			insert(root1, input[i]);
		preOrder(root1, pre1);
		inOrder(root1, in1);
		for (int i = 0; i < n; ++i) {
			getline(cin, input);
			Node *root2 = newNode(input[0]);
			for (int j = 1; j < input.size(); ++j)
				insert(root2, input[j]);
			pre2.clear();
			in2.clear();
			preOrder(root2, pre2);
			inOrder(root2, in2);
			puts(pre1 == pre2 && in1 == in2 ? "YES" : "NO");
			deleteTree(root2);
		}
		deleteTree(root1);
	}
	return 0;
} 

9.5

// 题目描述
// 平衡二叉树又称AVL树，它是一种具有平衡因子的特殊二叉排序树。平衡二叉树或者是一棵空树，或者是具有以下几条性质的二叉树：
// -
// 若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；
// 若它的右子树不空，则右子树上所有结点的值均大于它的根节点的值；
// 它的左右子树也分别为平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。
// 若将二叉树上结点的平衡因子定义为该结点的左子树深度减去它的右子树的深度，则平衡二叉树上的所有结点的平衡因子只可能为-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则这棵二叉树就是不平衡的。
// 通过平衡二叉树的性质不难得知，其插入、删除、查询都操作的时间复杂度均为O(log2n)。
// 维持平衡二叉树性质的操作可以被称为旋转。其中平衡二叉树的右旋处理可以描述如下：
// -
// 而其左旋处理与右旋正好相反，可以描述如下：
// -
// 在本题中，读入一串整数，首先利用这些整数构造一棵平衡二叉树。另外给定多次查询，利用构造出的平衡二叉树，判断每一次查询是否成功。
// -
// 输入-
// 输入的第一行包含2个正整数n和k，分别表示共有n个整数和k次查询。其中n不超过500，k同样不超过500。
// 第二行包含n个用空格隔开的正整数，表示n个整数。
// 第三行包含k个用空格隔开的正整数，表示k次查询的目标。
// -
// 输出
// 只有1行，包含k个整数，分别表示每一次的查询结果。如果在查询中找到了对应的整数，则输出1，否则输出0。
// 请在每个整数后输出一个空格，并请注意行尾输出换行。
// -
// 样例输入
// 8 3
// 1 3 5 7 8 9 10 15
// 9 2 5
// 样例输出
// 1 0 1 

#include <iostream>
#include <algorithm>

struct node
{
    int data;
    int height;
    node *l_child;
    node *r_child;
};
using NODE = node *;

//获取树高
int get_height(NODE root)
{
    if (root == nullptr)
        return 0;
    return root->height;
}
//更新树高
void Update_height(NODE root)
{
    root->height = std::max(get_height(root->l_child), get_height(root->r_child)) + 1;
}
//计算平衡因子
int get_BF(NODE root)
{
    return get_height(root->l_child) - get_height(root->r_child);
}
//建立新节点
NODE newNode(int data)
{
    NODE root = new node;
    root->data = data;
    root->height = 1;
    root->l_child = nullptr;
    root->r_child = nullptr;
    return root;
}
//左旋
void L(NODE& root)
{
    NODE temp = root->r_child;
    root->r_child = temp->l_child;
    temp->l_child = root;
    Update_height(root);
    Update_height(temp);
    root = temp;
}
void R(NODE& root)
{
    NODE temp = root->l_child;
    root->l_child = temp->r_child;
    temp->r_child = root;
    Update_height(root);
    Update_height(temp);
    root = temp;
}

void insert(NODE& root, int data)
{
    if (root == nullptr)
    {
        root = newNode(data);
    }
    else if (root->data > data)
    {
        insert(root->l_child, data);
        Update_height(root);

        if (get_BF(root) == 2)
        {
            if (get_BF(root->l_child) == 1)
            {
                R(root);
            }
            else
            {
                L(root->l_child);
                R(root);
            }
        }
    }
    else
    {
        insert(root->r_child, data);
        Update_height(root);

        if (get_BF(root) == -2)
        {
            if (get_BF(root->r_child) == -1)
            {
                L(root);
            }
            else
            {
                R(root->r_child);
                L(root);
            }
        }
    }
}

NODE creat(int n)
{
    int data;             
    NODE root = nullptr;

    for (int i = 0; i < n;i++)
    {
        std::cin >> data;
        insert(root, data);
    }
    return root;
}

bool search(NODE root,int data)
{
    if (root == nullptr)
        return false;
    else if (root->data == data)
        return true;
    else if (root->data > data)
        search(root->l_child, data);
    else
        search(root->r_child, data);
}

int main()
{
    //n为节点数 m为待查节点数
    int n, m;
    std::cin >> n >> m;
    NODE tree;

    tree = creat(n);

    int data[m];
    for (int i = 0; i < m;i++)
        std::cin >> data[i];

    for (int i = 0; i < m;i++)
    {
        if (search(tree,data[i]))
            std::cout << "1 ";
        else
            std::cout << "0 ";
        if (i == m-1)
        std::cout << std::endl;
    }
    

    system("pause");
    return 0;
}

9.6

//1.
#include <iostream>

const int N = 10;
int father[N];
bool isRoot[N];

int find_father(int n)
{
    int a = n;
    while (n!=father[n])
        n = father[n];

        //路径压缩 n 为找到的根节点
        //在根据a节点 将路径上的所有节点全部指向根节点
    while (a!=father[a])
    {
        int z = a;
        a = father[a];
        father[z] = n;
    }
    return n;
}

void init(int n)
{
    for (int i = 1; i <= n;i++)
    {
        father[i] = i;
        isRoot[i] = false;
    }
}

void Union(int a,int b)
{
    int fa = find_father(a);
    int fb = find_father(b);

    if (fa!=fb)
        father[fa] = fb;
}

int main()
{
    int n, m;
    std::cin >> n >> m;
    int a, b;

    init(n);
    for (int i = 0; i < m;i++)
    {
        std::cin >> a >> b;
        Union(a, b);
    }

    int ans = 0;
    for (int i = 1; i <= n;i++)
        isRoot[find_father(i)] = true;

    for (int i = 1; i <= n;i++)
    {
        if (isRoot[i]==true)
            ans++;
    }
    std::cout << ans << std::endl;

    system("pause");
    return 0;
}
//2.
// 题目描述
// 某市计划建设一个通信系统。按照规划，这个系统包含若干端点，这些端点由通信线缆链接。消息可以在任何一个端点产生，并且只能通过线缆传送。每个端点接收消息后会将消息传送到与其相连的端点，除了那个消息发送过来的端点。如果某个端点是产生消息的端点，那么消息将被传送到与其相连的每一个端点。
// 为了提高传送效率和节约资源，要求当消息在某个端点生成后，其余各个端点均能接收到消息，并且每个端点均不会重复收到消息。
// 现给你通信系统的描述，你能判断此系统是否符合以上要求吗？
// -
// 输入
// 输入包含多组测试数据。每两组输入数据之间由空行分隔。
// 每组输入首先包含2个整数N和M，N（1<=N<=1000）表示端点个数，M（0<=M<=N*(N-1)/2）表示通信线路个数。
// 接下来M行每行输入2个整数A和B（1<=A，B<=N），表示端点A和B由一条通信线缆相连。两个端点之间至多由一条线缆直接相连，并且没有将某个端点与其自己相连的线缆。
// 当N和M都为0时，输入结束。
// -
// 输出
// 对于每组输入，如果所给的系统描述符合题目要求，则输出Yes，否则输出No。
// 样例输入
// -
// 4 3
// 1 2
// 2 3
// 3 4
// -
// 3 1
// 2 3
// -
// 0 0
// 样例输出
// -
// Yes
// No

#include <iostream>
const int N = 10;

int father[N];
int isRoot[N];

int find_Father(int n)
{
    int z = n;
    while (n!=father[n])
        n = father[n];

    while (z!=father[z])
    {
        int a = z;
        z = father[z];
        father[a] = n;
    }
    return n;
}

bool Union(int a,int b)
{
    int fa = find_Father(a);
    int fb = find_Father(b);

    if (fa == fb)
        return false;
    else
    {
        father[fa] = fb;
        return true;
    }
}

void init(int n)
{
    for (int i = 1; i <= n;i++)
    {
        father[i] = i;
        isRoot[i] = false;
    }
}

int main()
{
    int n, m;
    while (std::cin >> n >> m && n!=0)
    {
        int flag = true;
        init(n);
        int a, b;
        for (int i = 0; i < m;i++)
        {
            std::cin >> a >> b;
            if (Union(a,b) == false)
                flag = false;
        }
        if (!flag)
        {
            std::cout << "NO" << std::endl;
            continue;
        }
        for (int i=1;i<=n;i++)
            isRoot[find_Father(i)] = true;
        int ans = 0;
        for (int i=1;i<=n;i++)
        {
            ans += isRoot[i];
        }
        if (ans == 1)
            std::cout << "YES" << std::endl;
        else
            std::cout << "NO" << std::endl;
    }
}
//3.
// 题目描述
// 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

// 输入
// 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。
// 注意:两个城市之间可以有多条道路相通,也就是说
// 3 3
// 1 2
// 1 2
// 2 1
// 这种输入也是合法的
// 当N为0时，输入结束，该用例不被处理。
// 输出
// 对每个测试用例，在1行里输出最少还需要建设的道路数目。
// 样例输入
// 5 3
// 1 2
// 3 2
// 4 5
// 0
// 样例输出
// 1
#include <iostream>
const int MAX = 10;

int father[MAX];
bool isRoot[MAX];

void init(int n)
{
    for (int i = 1; i <= n;i++)
    {
        father[i] = i;
        isRoot[i] = false;
    }
}

int find_Father(int n)
{
    int z = n;
    while (n!=father[n])
        n = father[n];
    
    while (z!=father[z])
    {
        int a = z;
        z = father[z];
        father[a] = n;
    }
    return n;
}

void Union(int a,int b)
{
    int fa = find_Father(a);
    int fb = find_Father(b);
    if (fa!=fb)
        father[fa] = fb;
}

int main()
{
    int N, M;
    while (std::cin >> N >> M && N!=0)
    {
        init(N);
        int a, b;
        for (int i = 0; i < M;i++)
        {
            std::cin >> a >> b;
            Union(a, b);
        }
        for (int i = 1; i <= N;i++)
            isRoot[find_Father(i)] = true;
        int ans = 0;
        for (int i = 1; i <= N;i++)
            ans += isRoot[i];

        std::cout << ans - 1 << std::endl;
    }
}
//4.
#include <iostream>
const int MAX = 10;

int father[MAX];
bool isRoot[MAX];

void init(int n)
{
    for (int i = 1; i <= n;i++)
    {
        father[i] = i;
        isRoot[i] = false;
    }
}

int find_Father(int n)
{
    int z = n;
    while (n!=father[n])
        n = father[n];
    
    while (z!=father[z])
    {
        int a = z;
        z = father[z];
        father[a] = n;
    }
    return n;
}

void Union(int a,int b)
{
    int fa = find_Father(a);
    int fb = find_Father(b);
    if (fa!=fb)
        father[fa] = fb;
}

int main()
{
    int N, M;
    while (std::cin >> N >> M && N!=0)
    {
        init(N);
        int a, b;
        for (int i = 0; i < M;i++)
        {
            std::cin >> a >> b;
            Union(a, b);
        }
        for (int i = 1; i <= N;i++)
            isRoot[find_Father(i)] = true;
        int ans = 0;
        for (int i = 1; i <= N;i++)
            ans += isRoot[i];

        std::cout << ans  << std::endl;
    }
}
//5.
// 题目描述
// Mr Wang wants some boys to help him with a project. Because the project is rather complex, the more boys come, the better it will be. 
// Of course there are certain requirements.Mr Wang selected a room big enough to hold the boys. 
// The boy who are not been chosen has to leave the room immediately. There are 10000000 boys in the room numbered from 1 to 10000000 at 
// the very beginning. After Mr Wang’s selection any two of them who are still in this room should be friends (direct or indirect), 
// or there is only one boy left. Given all the direct friend-pairs, you should decide the best way.
// -
// 输入
// The first line of the input contains an integer n (0 ≤ n ≤ 100 000) - the number of direct friend-pairs. 
// The following n lines each contains a pair of numbers A and B separated by a single space that suggests A and B are direct friends. 
// (A ≠ B, 1 ≤ A, B ≤ 10000000)
// -
// 输出
// The output in one line contains exactly one integer equals to the maximum number of boys Mr Wang may keep.
// -
// 样例输入
// 样例输入
// 3
// 1 3
// 1 5
// 2 5
// 4
// 3 2
// 3 4
// 1 6
// 2 6
// 样例输出
// 4
// 5
#include <iostream>
#include <vector>
#include <utility>
#define MAX 10000001
using std::vector;
using std::pair;

int father[MAX], manCnt[MAX], max;

int findFather(int x) {
	int f = x, temp;
	while (f != father[f])
		f = father[f];
	while (x != father[x]) {
		temp = x;
		x = father[x];
		father[temp] = f; 
	} 
	return f;
} 
void Union(int a, int b) {
	int fa = findFather(a), fb = findFather(b);
	if (fa != fb) {
		father[fa] = fb;
		manCnt[fb] += manCnt[fa];
		if (manCnt[fb] > max)
			max = manCnt[fb];
	}
}
inline void init(int a) {
	father[a] = a;
	manCnt[a] = 1; 
} 

int main() {
	int n, a, b;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			printf("1\n");
			continue; 
		} 
		max = 0;
		vector<pair<int, int> > input;
		for (int i = 0; i < n; ++i) {
			scanf("%d%d", &a, &b);
			input.push_back( {a, b} ); 
			init(a);
			init(b);
		}
		for (int i = 0; i < input.size(); ++i)
			Union(input[i].first, input[i].second); 
		printf("%d\n", max); 
	} 
	return 0;
} 

9.7

//1.
// 题目描述
// 堆排序是一种利用堆结构进行排序的方法，它只需要一个记录大小的辅助空间，每个待排序的记录仅需要占用一个存储空间。
// 首先建立小根堆或大根堆，然后通过利用堆的性质即堆顶的元素是最小或最大值，从而依次得出每一个元素的位置。
// 堆排序的算法可以描述如下：

// 在本题中，读入一串整数，将其使用以上描述的堆排序的方法从小到大排序，并输出。

// 输入
// 输入的第一行包含1个正整数n，表示共有n个整数需要参与排序。其中n不超过100000。
// 第二行包含n个用空格隔开的正整数，表示n个需要排序的整数。

// 输出
// 只有1行，包含n个整数，表示从小到大排序完毕的所有整数。
// 请在每个整数后输出一个空格，并请注意行尾输出换行
// 样例输入
// 10
// 2 8 4 6 1 10 7 3 5 9
// 样例输出
// 1 2 3 4 5 6 7 8 9 10 
#include <iostream>
#include <algorithm>
const int MAX = 100;
int heap[MAX];

void downAdjust(int low, int high)
{
    int i = low, j = 2 * i;

    while (j<=high)
    {
        if (j+1 <= high && heap[j+1] > heap[j])
            j = j + 1;
        if (heap[i] < heap[j])
        {
            std::swap(heap[i], heap[j]);
            i = j;
            j = 2 * i;
        }
        else
            break;
    }
}

void creat(int n)
{
    for (int i = n / 2; i >= 1;i--)
    {
        downAdjust(i, n);
    }
}

void heap_sort(int n)
{
    creat(n);
    for (int i = n; i > 1;i--)
    {
        std::swap(heap[i], heap[1]);
        downAdjust(1, i - 1);
    }
}

int main()
{
    int n;
    std::cin >> n;

    for (int i = 1; i <= n;i++)
        std::cin >> heap[i];

    heap_sort(n);

    for (int i = 1; i <= n;i++)
        std::cout << heap[i] << " ";

    std::cout << std::endl;
    system("pause");
    return 0;
}
//2.
// 题目描述
// 有两个长度都为N的序列A和B，在A和B中各取一个数相加可以得到N2个和，求这N2个和中最小的N个。
// -
// 输入
// 第一行一个正整数N（1 <= N <= 100000）。
// 第二行N个整数Ai，满足Ai <= Ai+1且Ai <= 109
// 第三行N个整数Bi，满足Bi <= Bi+1且Bi <= 109
// -
// 输出
// 输出仅有一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
// 样例输入
// 3
// 2 6 6
// 1 4 8
// 样例输出
// 3 6 7
// #include <vector>
// #include <iostream>
// #include <algorithm>

// int main()
// {
//     int n;
//     std::cin >> n;
//     int a[n];
//     int b[n];
//     for (int i = 0; i < n;i++)
//         std::cin >> a[i];
//     for (int j = 0; j < n;j++)
//         std::cin >> b[j];
//     std::vector<int> array;

//     for (int i = 0; i < n;i++)
//     {
//         for (int j = 0; j < n;j++)
//             array.push_back(a[i] + b[j]);
//     }

//     std::sort(array.begin(), array.end());

//     std::cout << array[0] <<" " <<array[1] << " " << array[2] <<  std::endl;

//     system("pause");
//     return 0;
// }

#include <cstdio>
#include <algorithm>
#define MAX 100010

int a[MAX], heap[MAX];

void downAdjust(int low, int high) {
	int i = low, j = i * 2;
	while (j <= high) {
		if (j + 1 <= high && heap[j + 1] > heap[j])
			++j;
		if (heap[j] > heap[i]) {
			std::swap(heap[j], heap[i]);
			i = j;
			j = 2 * i;
		} else
			break; 
	} 
} 
void createHeap(int n) {
	for (int i = n / 2; i >= 1; --i)
		downAdjust(i, n);
}
void heapSort(int n) {
	for (int i = n; i > 1; --i) {
		std::swap(heap[1], heap[i]);
		downAdjust(1, i - 1); 
	} 
} 

int main() {
	int n, input;
	while (scanf("%d", &n) != EOF) {
		for (int i = 1; i <= n; ++i) { 
			scanf("%d", &a[i]);
			heap[i] = a[i];
		}
		scanf("%d", &input);
		for (int i = 1; i <= n; ++i)
			heap[i] += input; 
		createHeap(n);
		for (int i = 2; i <= n; ++i) {
			scanf("%d", &input);
			for (int j = 1; j <= n; ++j) {
				if (input + a[j] < heap[1]) { 
					heap[1] = input + a[j];
					downAdjust(1, n);
				} else
					break;
			} 
		}
		heapSort(n);
		for (int i = 1; i <= n; ++i)
			printf("%s%d", i == 1 ? "" : " ", heap[i]);
		putchar('\n'); 
	} 
	return 0;
} 
//3.
// 题目
// 题目描述
// 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
// 每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
// 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
// 例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
// -
// 输入
// 输入文件fruit.in包括两行，第一行是一个整数n（1 <= n <= 30000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 20000）是第i种果子的数目。
// -
// 输出
// 输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
// 样例输入
// 10
// 3 5 1 7 6 4 2 5 4 1
// 1
// 2
// 样例输出
// 12

#include <iostream>
#include <algorithm>

int heap[100];
int n;

void downAdjust(int low,int high)
{
     int i=low,j=2*i;
     while (j<=high)
     {
         if (j+1 <= high && heap[j+1] < heap[j])
             j++;
         if (heap[j]<heap[i])
         {
             std::swap(heap[i],heap[j]);
             i = j;
             j = 2*i;
         }
         else
             break;
     }
}

void creat()
{
    for (int i=n/2;i>=1;i--)
    {
        downAdjust(i,n);
    }
}

void heap_sort()
{
    creat();
    for (int i=n;i>1;i--)
    {
        std::swap(heap[i],heap[1]);
        downAdjust(1,i-1);
    }
}

int main()
{
    int temp_n,temp,sum=0;
    std::cin >> n ;
    for (int i=1;i<=n;i++)
        std::cin >> heap[i];
    creat();
    temp_n = n;
    for (int i=1;i<=n-1;i++)
    {
        temp = heap[1];
        heap[1]=heap[temp_n--];
        downAdjust(1,temp_n);
        heap[1]+=temp;
        sum+=heap[1];
        downAdjust(1,temp_n);
    }
    std::cout << sum << std::endl;
    system("pause");
    return 0;
}   

9.8

//1.
// 在通讯领域，经常需要将需要传送的文字转换成由二进制字符组成的字符串。在实际应用中，由于总是希望被传送的内容总长尽可能的短，如果对每个字符设计长度不等的编码，且让内容中出现次数较多的字符采用尽可能短的编码，则整个内容的总长便可以减少。另外，需要保证任何一个字符的编码都不是另一个字符的编码前缀，这种编码成为前缀编码。
// 而赫夫曼编码就是一种二进制前缀编码，其从叶子到根（自底向上）逆向求出每个字符的算法可以表示如下：
// -
// 在本题中，读入n个字符所对应的权值，生成赫夫曼编码，并依次输出计算出的每一个赫夫曼编码。
// -
// 输入
// 输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。
// 第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。
// -
// 输出
// 共n行，每行一个字符串，表示对应字符的赫夫曼编码。
// 样例输入
// 8
// 5 29 7 8 14 23 3 11
// 1
// 2
// 样例输出
// 0110
// 10
// 1110
// 1111
// 110
// 00
// 0111
// 010

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

struct node
{
    int w;
    int parent;
    int l_child;
    int r_child;
};
std::vector<node> tree;

void findMinTwo(int& min,int &max)
{
    int data = INT_MAX;
    int len = tree.size();
    for (int i=0;i<len;i++)
    {
        if (tree[i].parent == -1 && tree[i].w < data)
        {
            data = tree[i].w;
            min = i;
        }
    }
    data = INT_MAX;
    tree[min].parent = -2;
    for (int i=0;i<len;i++)
    {
        if (tree[i].parent == -1 && tree[i].w < data)
        {
            data = tree[i].w;
            max = i;
        }
    }
}


int main()
{
    int n,data;
    std::cin >> n;
    for (int i=1; i<=n; i++)
    {
        std::cin >> data;
        tree.push_back({data,-1,-1,-1});
    }

    int z = n;
    for (int i=0;i<z-1;i++)
    {
        int max,min;
        findMinTwo(min,max);
        tree[min].parent = tree[max].parent = n+i;
        tree.push_back({tree[min].w+tree[max].w,-1,min,max});
    }
    
    std::vector<std::string> huffman_code(n);
    for (int i=0;i<n;i++)
    {
        node temp = tree[i];
        int pos = i;
        while (temp.parent != -1)
        {
            node parent = tree[temp.parent];
            if (pos == parent.l_child)
                huffman_code[i] += '0';
            else
                huffman_code[i] += '1';
            pos = temp.parent;
            temp = parent;
        }
    }
    for (int i=0;i<n;i++)
    {
        for (auto it = huffman_code[i].rbegin();it!=huffman_code[i].rend(); it++)
            std::cout << *it;
        std::cout << std::endl;
    }
    return 0;
}
//2.
// 题目描述
// 在本题中，我们将要讨论的是自顶向下的赫夫曼编码算法。从根出发，遍历整棵赫夫曼树从而求得各个叶子结点所表示的字符串。算法的关键部分可以表示如下：
// -
// 在本题中，读入n个字符所对应的权值，生成赫夫曼编码，并依次输出计算出的每一个赫夫曼编码。
// -
// 输入
// 输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。
// 第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。
// -
// 输出
// 共n行，每行一个字符串，表示对应字符的赫夫曼编码。
// 样例输入
// 8
// 5 29 7 8 14 23 3 11
// 1
// 2
// 样例输出
// 0110
// 10
// 1110
// 1111
// 110
// 00
// 0111
// 010
#include <iostream>
#include <vector>
#include <string>

struct node
{
    char data;
    int weight;
    int parent;
    int l_child,r_child;
};

std::vector<node> tree;
std::vector<std::string> huffman_code(15);

void find_two_min(int& min1, int& min2)
{
    int weight = INT_MAX;
    int len = tree.size();
    for (int i=0;i<len;i++)
    {
        if (tree[i].parent == -1 && tree[i].weight < weight)
        {
            weight = tree[i].weight;
            min1 = i;
        }
    }
    weight = INT_MAX;
    tree[min1].parent = -2;
    for (int i=0;i<len;i++)
    {
        if (tree[i].parent == -1 && tree[i].weight < weight)
        {
            weight = tree[i].weight;
            min2 = i;
        }
    }
}

void DFS(int root, std::string temp)
{
    if (tree[root].l_child == -1 && tree[root].r_child == -1)
    {
        huffman_code[root] = temp;
        return ;
    }
    DFS(tree[root].l_child,temp+'0');
    DFS(tree[root].r_child,temp+'1');
}

int main()
{
    int n;
    while (std::cin >> n)
    {
        int weight;
        char data;
        for (int i=0;i<n;i++)
        {
            std::cin >> data >> weight;
            tree.push_back({data,weight,-1,-1,-1});
        }
        int z = n;
        for (int i=0;i<z-1;i++)
        {
            int min1,min2;
            find_two_min(min1,min2);
            tree[min1].parent = tree[min2].parent = n+i;
            tree.push_back({' ',tree[min1].weight+tree[min2].weight,-1,min1,min2});
        }
        DFS(2*n-2,"");
        for (int i=0;i<n;i++)
        {
            std::cout << tree[i].data << " " << huffman_code[i] << std::endl;
        }

        tree.clear();
        huffman_code.clear();
    }
    return 0;
}
//3.// 题目描述
// 哈弗曼编码大家一定很熟悉吧（不熟悉也没关系，自己查去。。。）。现在给你一串字符以及它们所对应的权值，让你构造哈弗曼树，从而确定每个字符的哈弗曼编码。当然，这里有一些小规定：
// -
// 1.规定哈弗曼树的左子树编码为0，右子树编码为1；
// -
// 2.若两个字符权值相同，则ASCII码值小的字符为左孩子，大的为右孩子；
// -
// 3.创建的新节点所代表的字符与它的做孩子的字符相同；
// -
// 4.所有字符为ASCII码表上32-96之间的字符（即“ ”到“`”之间的字符）。
// -
// 输入
// 输入包含多组数据（不超过100组）
// 每组数据第一行一个整数n，表示字符个数。接下来n行，每行有一个字符ch和一个整数weight，表示字符ch所对应的权值，中间用空格隔开。
// 输入数据保证每组测试数据的字符不会重复。
// -
// 输出
// 对于每组测试数据，按照输入顺序输出相应的字符以及它们的哈弗曼编码结果，具体格式见样例。
// 样例输入
// 3
// a 10
// b 5
// c 8
// 4
// a 1
// b 1
// c 1
// d 1
// 样例输出
// a:0
// b:10
// c:11
// a:00
// b:01
// c:10
// d:11

#include <iostream>
#include <vector>
#include <string>

struct node
{
    char data;
    int weight;
    int parent;
    int l_child,r_child;
};

std::vector<node> tree;
std::vector<std::string> huffman_code(15);

void find_two_min(int& min1, int& min2)
{
    int weight = INT_MAX;
    int len = tree.size();
    for (int i=0;i<len;i++)
    {
        if (tree[i].parent == -1 && tree[i].weight < weight)
        {
            weight = tree[i].weight;
            min1 = i;
        }
    }
    weight = INT_MAX;
    tree[min1].parent = -2;
    for (int i=0;i<len;i++)
    {
        if (tree[i].parent == -1 && tree[i].weight < weight)
        {
            weight = tree[i].weight;
            min2 = i;
        }
    }
}

void DFS(int root, std::string temp)
{
    if (tree[root].l_child == -1 && tree[root].r_child == -1)
    {
        huffman_code[root] = temp;
        return ;
    }
    DFS(tree[root].l_child,temp+'0');
    DFS(tree[root].r_child,temp+'1');
}

int main()
{
    int n;
    while (std::cin >> n)
    {
        int weight;
        char data;
        for (int i=0;i<n;i++)
        {
            std::cin >> data >> weight;
            tree.push_back({data,weight,-1,-1,-1});
        }
        int z = n;
        for (int i=0;i<z-1;i++)
        {
            int min1,min2;
            find_two_min(min1,min2);
            tree[min1].parent = tree[min2].parent = n+i;
            tree.push_back({' ',tree[min1].weight+tree[min2].weight,-1,min1,min2});
        }
        DFS(2*n-2,"");
        for (int i=0;i<n;i++)
        {
            std::cout << tree[i].data << " " << huffman_code[i] << std::endl;
        }

        tree.clear();
        huffman_code.clear();
    }
    return 0;
}
//4.
// 题目
// 题目描述
// 哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
// -
// 输入
// 输入有多组数据。
// 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
// -
// 输出
// 输出权值。

// 样例输入
// 2
// 2 8 
// 3
// 5 11 30 
// 1
// 2
// 3
// 4
// 样例输出
// 10
// 62

#include <iostream>
#include <vector>
#include <algorithm>

struct Node {
	int w, parent, lchild, rchild, path, depth;
};

void findMinTwo(std::vector<Node>& huffman, int& min1, int& min2) {
	int i = 1, w1, w2;
	while (huffman[i++].parent != 0)
		continue;
	min1 = i - 1;
	while (huffman[i++].parent != 0)
		continue;
	min2 = i - 1;
	for ( ; i < huffman.size(); ++i) { 
		if (huffman[i].parent == 0 && huffman[i].w < std::max(huffman[min1].w, huffman[min2].w)) { 
			if (huffman[min1].w != huffman[min2].w)
				(huffman[min1].w > huffman[min2].w ? min1 : min2) = i;
			else
				(min1 > min2 ? min1 : min2) = i; 
		}
	}
	if (min1 > min2)
		std::swap(min1, min2);
} 

int main() {
	int n, input, min1, min2;
	std::vector<Node> huffmanTree;
	while (scanf("%d", &n) != EOF) {
		if (n == 1) {
			scanf("%d", &input);
			printf("1\n");
			continue;
		} 
		huffmanTree.clear();
		huffmanTree.resize(n + 1);
		huffmanTree[0] = {0, 0, 0, 0, 0, 0};
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &input);
			huffmanTree[i] = {input, 0, 0, 0, 0, 0};
		}
		for (int i = n + 1; i <= 2 * n - 1; ++i) {
			findMinTwo(huffmanTree, min1, min2);
			huffmanTree[min1].parent = huffmanTree[min2].parent = i;
			huffmanTree.push_back( {huffmanTree[min1].w + huffmanTree[min2].w, 0, min1, min2, 0, 0} );
		}
		int c = 2 * n - 1, sum = 0;
		while (c) {
			if (huffmanTree[c].path == 0) {
				huffmanTree[c].path = 1;
				if (huffmanTree[c].lchild != 0) {
					huffmanTree[huffmanTree[c].lchild].depth = huffmanTree[c].depth + 1;
					c = huffmanTree[c].lchild;
				} else if (huffmanTree[c].rchild == 0) {
					sum += huffmanTree[c].depth * huffmanTree[c].w;
				} 
			} else if (huffmanTree[c].path == 1) {
				huffmanTree[c].path = 2;
				if (huffmanTree[c].rchild != 0) {
					huffmanTree[huffmanTree[c].rchild].depth = huffmanTree[c].depth + 1;
					c = huffmanTree[c].rchild;
				} 
			} else {
				huffmanTree[c].path = 0;
				c = huffmanTree[c].parent;
			} 
		}
		printf("%d\n", sum); 
	} 
	return 0;
} 
//5.
// 题目描述
// 　　在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
// -
// 因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
// 　　例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。
// 所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
// -
// 输入
// 　　输入包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。
// 　　第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。
// -
// 输出
// 　　输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2^31

// #include <iostream>
// #include <algorithm>

// const int MAX = 15;
// int heap[MAX];

// void downAdjust(int low,int high)
// {
//     int i = low, j = 2 * i;

//     while (j<=high)
//     {
//         if (j+1 <=high && heap[j+1] < heap[j])
//             j++;
//         if (heap[i]>heap[j])
//         {
//             std::swap(heap[i], heap[j]);
//             i = j;
//             j = 2 * i;
//         }
//         else
//             break;
//     }
// }

// void creat(int n)
// {
//     for (int i = n / 2; i >= 1;i--)
//         downAdjust(i, n);
// }

// int main()
// {
//     int n;
//     std::cin >> n;
//     for (int i = 1; i <= n;i++)
//         std::cin >> heap[i];

//     int sum = 0;
//     int temp_n = n;
//     for (int i = 1; i <= n - 1;i++)
//     {
//         int temp = heap[1];
//         std::swap(heap[1], heap[temp_n--]);
//         downAdjust(1, temp_n);
//         heap[1] += temp;
//         sum += heap[1];
//         downAdjust(1, temp_n);
//     }
//     std::cout << sum << std::endl;
//     system("pause");
//     return 0;
// }

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    int n, input, a, b, sum;
    
    while (cin >> n)
    {
        sum = 0;
        priority_queue<int, vector<int>, greater<int>> Q;

        for (int i = 0; i < n;i++)
        {
            cin >> input;
            Q.push(input);
        }
        while (Q.size() > 1)
        {
            a = Q.top();l
            Q.pop();
            b = Q.top();
            Q.pop();
            Q.push(a + b);
            sum += a + b;
        }
        std::cout << sum << std::endl;
    }
    return 0;
}

第十章

10.1

//1.
#include <iostream>
#include <vector>

int main()
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> matrix(n,std::vector<int>(n,0));

    int a, b;
    for (int i = 0; i < m;i++)
    {
        std::cin >> a >> b;
        matrix[a][b] = matrix[b][a] = 1;
    }


    for (int i = 0; i < n;i++)
    {
        int ans = 0;
        for (int j = 0; j < n;j++)
        {
            if (matrix[i][j])
                ans++;
        }
        std::cout << ans << " ";
    }

    system("pause");
    return 0;
}
//2.
#include <vector>
#include <iostream>
#include <map>

int main()
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));
    std::vector<std::pair<int, int>> degree(m, {0, 0});
    //first 出度 second 入度

    int a, b;
    for (int i = 0; i < m;i++)
    {
        std::cin >> a >> b;
        matrix[a][b] = 1;
    }

    for (int i = 0; i < n;i++)
    {
        for (int j = 0; j < n;j++)
        {
            if (matrix[i][j])
            {
                degree[i].first++;
                degree[j].second++;
            }
        }
    }

    for (int i = 0; i < n;i++)
    {
        std::cout << degree[i].second << " " << degree[i].first << std::endl;
    }

    system("pause");
    return 0;
}

10.2

//1.
#include <iostream>
#include <vector>

int main()
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> matrix(n,std::vector<int>(n,0));

    int a, b;
    for (int i = 0; i < m;i++)
    {
        std::cin >> a >> b;
        matrix[a][b] = matrix[b][a] = 1;
    }
    for (auto it : matrix)
    {
        for (auto x : it)
        {
            std::cout << x  << " ";
        }
        std::cout << std::endl;
    }

    system("pause");
    return 0;
}
//2.
#include <iostream>
#include <vector>

int main()
{
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> matrix(n,std::vector<int>(n,0));

    int a, b;
    for (int i = 0; i < m;i++)
    {
        std::cin >> a >> b;
        matrix[a][b] = 1;
    }
    for (auto it : matrix)
    {
        for (auto x : it)
        {
            std::cout << x  << " ";
        }
        std::cout << std::endl;
    }

    system("pause");
    return 0;
}
//3.
#include <iostream>
#include <vector>

int main()
{
    int n , m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> matrixt(n);
    int a, b;
    for (int i = 0; i < m;i++)
    {
        std::cin >> a >> b;
        matrixt[a].push_back(b);
        matrixt[b].push_back(a);
    }

    int i = 0;
    for (auto it : matrixt)
    {
        std::cout << i << '(' << it.size() << ')' << ' ';
        for (auto x : it)
        {
            std::cout << x << " ";
        }
        i++;
        std::cout << std::endl;
    }

    system("pause");
    return 0;
}
//4.
#include <iostream>
#include <vector>

int main()
{
    int n , m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> matrixt(n);
    int a, b;
    for (int i = 0; i < m;i++)
    {
        std::cin >> a >> b;
        matrixt[a].push_back(b);
    }

    int i = 0;
    for (auto it : matrixt)
    {
        std::cout << i << '(' << it.size() << ')' << ' ';
        for (auto x : it)
        {
            std::cout << x << " ";
        }
        i++;
        std::cout << std::endl;
    }

    system("pause");
    return 0;
}

10.3

//1.
#include <iostream>
#include <vector>
#include <map>
#include <string>

const int maxn = 2010;
const int INF = 100000000;
int n,k,numPerson = 0;
std::map<std::string, int> string_to_int;
std::map<int, std::string> int_to_string;
std::map<std::string, int> Gang;
int G[maxn][maxn]{0}, weight[maxn]{0};
bool vis[maxn]{false};

void DFS(int nowVisit, int& head,int& numMember,int& totalValue)
{
    numMember++;
    vis[nowVisit] = true;
    if (weight[nowVisit] > weight[head])
    {
        head = nowVisit;
    }

    for (int i = 0; i < numPerson;i++)
    {
        if (G[nowVisit][i]>0)
        {
            totalValue += G[nowVisit][i];
            G[nowVisit][i] = G[i][nowVisit] = 0;
            if (vis[i] == false)
            {
                DFS(i, head, numMember, totalValue);
            }
        }
    }
}

void DFSTrave()
{
    for (int i = 0; i < numPerson;i++)
    {
        if (vis[i] == false)
        {
            int head = i, numMember = 0, totalValue = 0;
            DFS(i, head, numMember, totalValue);
            if (numMember > 2 && totalValue > k)
            {
                Gang[int_to_string[head]] = numMember;
            }
        }
    }
}




int check(std::string str)
{
    if (string_to_int.find(str) != string_to_int.end())
    {
        return string_to_int[str];
    } 
    else 
    {
        string_to_int[str] = numPerson;
        int_to_string[numPerson] = str;
        return numPerson++;
    }
}

int main()
{
    int w;
    std::string str1, str2;
    int n;
    std::cin >> n >> k;

    for (int i = 0; i < n;i++)
    {
        std::cin >> str1 >> str2 >> w;
        int id1 = check(str1);
        int id2 = check(str2);
        weight[id1] += w;
        weight[id2] += w;
        G[id1][id2] += w;
        G[id2][id1] += w;
    }

    std::cout << Gang.size() << std::endl;
    for (auto it = Gang.begin(); it != Gang.end();it++)
    {
        std::cout << it->first << " " << it->second << std::endl;
    }
    system("pause");
    return 0;
}
//2.
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <type_traits>

using MAX = std::integral_constant<int, 2010>::type;


int limit;                //阈值
int Person_Num = 0;       //图中顶点数量

bool vis[MAX::value] = {false};
std::map<std::string, int> StringToInt;//string 到 int 的映射
std::map<int, std::string> IntToString;//int 到 string 的映射
std::map<std::string,int> gang;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, 0));   //邻接矩阵
std::vector<int> weight(MAX::value,0);                                               //点权

void DFS(int now_visit, int& head, int& weight_total, int& area_member)
{
    vis[now_visit] = true;
    area_member++;

    if (weight[now_visit] > weight[head])
    {
        head = now_visit;
    }

    for (int i = 0; i < Person_Num;i++)
    {
        if (matrix[now_visit][i] > 0 )
        {
            weight_total += matrix[now_visit][i];
            matrix[now_visit][i] = matrix[i][now_visit] = 0;
            if (vis[i] == false)
            DFS(i, head, weight_total, area_member);
        }
    }
}

void DFS_Display()
{
    for (int i = 0; i < Person_Num;i++)
    {
        if (vis[i] == false)
        {
            int head = i, weight_total = 0, area_member = 0;
            DFS(i, head, weight_total, area_member);

            if (weight_total > limit && area_member > 2)
            {
                gang[IntToString[head]] = area_member;
            }
        }
    }
}

int change(std::string str)
{
    if (StringToInt.find(str) != StringToInt.end())
    {
        return StringToInt[str];
    }
    else
    {
        StringToInt[str] = Person_Num;
        IntToString[Person_Num] = str;
        return Person_Num++;
    }
}

int main()
{
    int n, w;
    std::string str1, str2;
    std::cin >> n >> limit;

    for (int i = 0; i < n;i++)
    {
        std::cin >> str1 >> str2 >> w;
        int id1 = change(str1);
        int id2 = change(str2);

        weight[id1] += w;
        weight[id2] += w;

        matrix[id1][id2] += w;
        matrix[id2][id1] += w;
    }

    DFS_Display();

    std::cout << gang.size() << std::endl;
    for (auto &it : gang)
    {
        std::cout << it.first << " " << it.second << std::endl;
    }

    return 0;
}
//3.
#include <iostream>
#include <vector>
#include <type_traits>
#include <queue>

using MAX = std::integral_constant<int, 10>::type;

int total, limit;

struct node
{
    int vertex;
    int layer;
    node (int v,int l):vertex(v),layer(l){}
};

std::vector<std::vector<node>> matrix(MAX::value);
bool IsEnqueue[MAX::value] = {false};

int BFS(int now_visit)
{
    int Num_Forward = 0;
    std::queue<node> q;
    node start(now_visit, 0);
    q.push(start);
    IsEnqueue[start.vertex] = true;

    while (!q.empty())
    {
        node now = q.front();
        q.pop();

        int vertex = now.vertex;

        for (int i = 0; i < matrix[vertex].size();i++)
        {
            node next = matrix[vertex][i];
            next.layer = now.layer + 1;

            //遍历要求 层数不大于上限 且未被访问 
            if (IsEnqueue[next.vertex] == false && next.layer <= limit)
            {
                //入队人数即是转发人数
                q.push(next);
                IsEnqueue[next.vertex] = true;
                Num_Forward++;
            }
        }
    }
    return Num_Forward;
}

int main()
{
    std::cin >> total >> limit;

    for (int i = 1; i <= total;i++)
    {
        int count;
        std::cin >> count;
        for (int j = 0; j < count;j++)
        {
            int data;
            std::cin >> data;
            matrix[data].push_back({i, 0});
        }
    }

    int count;
    std::cin >> count;
    for (int i = 0; i < count;i++)
    {
        int start;
        std::cin >> start;
        std::fill(IsEnqueue, IsEnqueue + MAX::value, false);
        std::cout << BFS(start) << std::endl;
    }

    system("pause");
    return 0;
}
//4.
#include <iostream>
#include <vector>
#include <type_traits>

//PATA1013
//思路 对于非关注(也就是没被占领的城市) 从该城市出发,遍历整个图,将遍历的城市设置为已遍历
//类似于并查集吧 DFS 遍历过后 , 以没有遍历的城市为起点出发 , 继续遍历整个图 , 相当于查询连通快的数量

using MAX = std::integral_constant<int, 10>::type;

int city_num, edge_num, concern, k;

bool vis[MAX::value]{false};

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, 0));

void DFS(int start)
{
    if (start != concern)
    {
        vis[start] = true;
        for (int i = 1; i <= city_num;i++)
        {
            if (vis[i] == false && matrix[start][i] == 1)
            {
                DFS(i);
            }
        }
    }
    else
        return;
}

int main()
{
    std::cin >> city_num >> edge_num >> k;

    for (int i = 0; i < edge_num;i++)
    {
        int a, b;
        std::cin >> a >> b;
        matrix[a][b] = matrix[b][a] = 1;
    }



    for (int i = 0; i < k;i++)
    {
        int ans = 0;
        std::cin >> concern;
        std::fill(vis, vis + MAX::value, false);

        for (int j = 1; j <= city_num;j++)
        {
            if (vis[j] == false && j != concern)
            {
                DFS(j);
                ans++;
            }
        }
        std::cout << ans-1 << std::endl;
    }
    system("pause");
    return 0;
}
//5.
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <type_traits>
int ans=0,n,num = 0;

using MAX = std::integral_constant<int, 10010>::type;

std::set<int> result;
std::set<int> temp;

std::vector<std::vector<int>> matrix(MAX::value);
// std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, 0));
bool isVisit[MAX::value]{false};

int father[10010];
bool IsRoot[10010]{false};

void init()
{
    for (int i = 1; i <= n;i++)
    {
        father[i] = i;
    }
}

int Find_Father(int a)
{
    int z = a;
    while (a!=father[a])
        a = father[a];
    
    while (z!=father[z])
    {
        int x = z;
        z = father[z];
        father[x] = a;
    }
    return a;
}

void Union(int a, int b)
{
    int fa = Find_Father(a);
    int fb = Find_Father(b);

    if (fa!=fb)
    {
        father[fa] = fb;
    }
}

void Find_Root()
{
    for (int i = 1; i <= n;i++)
        IsRoot[Find_Father(i)] = true;

    for (int i = 1; i <= n; i++)
        ans += IsRoot[i];
}
int MAX_H = 0;
void DFS(int now_visit,int height)
{
    isVisit[now_visit] = true;
    if (height > MAX_H)
    {
        result.clear();
        result.insert(now_visit);
        MAX_H = height;
    }
    else if (height == MAX_H)
    {
        result.insert(now_visit);
    }
    for (int i = 0; i < (int)matrix[now_visit].size();i++)
    {
        if (isVisit[matrix[now_visit][i]] == false)
            DFS(matrix[now_visit][i], height + 1);
    }
}


int main()
{

    std::cin >> n;
    init();
    int a, b;
    for (int i = 0; i < n-1;i++)
    {
        std::cin >> a >> b;
        Union(a, b);
        //matrix[a][b] = matrix[b][a] = 1;
        matrix[a].push_back(b);
        matrix[b].push_back(a);
    }

    Find_Root();

    if (ans == 1)
    {
        DFS(1, 1);
        temp = result;
        std::fill(isVisit, isVisit+MAX::value, false);
        DFS(*temp.begin(), 1);
        
        for (auto it : result)
        {
            temp.insert(it);
        }

        for (auto it : temp)
        {
            std::cout << it << std::endl;
        }
    }
    else
        std::cout << "Error: " << ans << " components" << std::endl;

    system("pause");
    return 0;
}
//6.
//test5 的完美版本

#include <cstdlib>
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
const int maxn = 10010;
vector<int> G[maxn];

int father[maxn];
int n;
bool hashTable[maxn] = { false };
int findFather(int x) {
	int a = x;
	while (x != father[x]) x = father[x];
	while (a != father[a]) {
		int z = a;
		a = father[a];
		father[z] = x;
	}
	return x;
}

void Union(int a, int b) {
	int faA = findFather(a);
	int faB = findFather(b);
	if (faA != faB) {
		father[faA] = faB;
	}
}

void init() {
	for (int i = 1;i <= n;++i) {
		father[i] = i;
	}
}

int calBlock() {
	int Block = 0;
	for (int i = 1;i <= n;++i) {
		hashTable[findFather(i)] = true;
	}
	for (int i = 1;i <= n;++i) {
		Block += hashTable[i];
	}
	return Block;
}

int maxH = 0;
set<int> ans, temp;
void DFS(int u, int Height, int pre) {
	if (Height > maxH) {
		temp.clear();
		temp.insert(u);
		maxH = Height;
	}
	else if (Height == maxH) {
		temp.insert(u);
	}
	for (int i = 0;i < G[u].size();++i) {
		if (G[u][i] != pre) {
			DFS(G[u][i], Height + 1, u);
		}
	}
}

int main() {
	scanf("%d", &n);
	init();
	for (int i = 0;i < n - 1;++i) {
		int a, b;
		scanf("%d %d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
		Union(a, b);
	}
	int Block = calBlock();
	if (Block == 1) {
		DFS(1, 1, -1);
		ans = temp;
		set<int>::iterator it = temp.begin();
		DFS(*it, 1, -1);
		for (it = temp.begin();it != temp.end();++it) {
			ans.insert(*it);
		}
		for (it = ans.begin();it != ans.end();++it) {
			printf("%d\n", *it);
		}
	}
	else {
		printf("Error: %d components", Block);
	}
	system("pause");
	return 0;
}

10.4

//1.
#include <iostream>
#include <vector>
#include <type_traits>
#include <string>
#include <map>


int n = 6;

using LIMIT = std::integral_constant<int, 10000>::type;
using MAX = std::integral_constant<int, 6>::type;
std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, 0));
std::map<int, std::string> path;
bool IsVisit[6]{false};
int depth[6];

void MakeGraph()
{
    matrix[0][1] = 1;
    matrix[0][3] = 4;
    matrix[0][4] = 4;

    matrix[1][3] = 2;

    matrix[2][5] = 1;

    matrix[3][2] = 2;
    matrix[3][4] = 3;

    matrix[4][5] = 3;
    
}

void Dijkstra(int start)
{
    path[0] = '0';
    std::fill(depth, depth + 6, LIMIT::value);
    depth[start] = 0;
    for (int i = 0; i < 6;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < n;j++)
        {
            if (depth[j] < min && IsVisit[j]==false)
            {
                u = j;
                min = depth[j];
            }
        }

        if (u == -1)
            return;
        IsVisit[u] = true;

        for (int v = 0; v < n;v++)
        {
            if (IsVisit[v]==false && depth[u]+matrix[u][v]<depth[v] && matrix[u][v]>0)
            {
                depth[v] = depth[u] + matrix[u][v];
                path[v] = path[u] + (char)(v + '0');
            }
        }
    }
}

int main()
{
    MakeGraph();
    Dijkstra(0);

    system("pause");
    return 0;
}
//2.
#include <iostream>
#include <vector>
#include <type_traits>


//PATA1003 Dijkstra
using LIMIT = std::integral_constant<int, 10000>::type;
using MAX = std::integral_constant<int, 5>::type;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, LIMIT::value));
std::vector<int> weight(MAX::value,0);
std::vector<bool> IsVisit(MAX::value,false);
std::vector<int> depth(MAX::value, LIMIT::value);
std::vector<int> w(MAX::value,0), num(MAX::value,0);
int start, end, vertex, edge;

void Dijkstra(int start)
{
    depth[start] = 0;
    w[start] = weight[start];
    num[start] = 1;

    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex;j++)
        {
            if (IsVisit[j] == false && depth[j] < min)
            {
                min = depth[j];
                u = j;
            }
        }

        if (u == -1)
            return;

        IsVisit[u] = true;

        for (int v = 0; v < vertex;v++)
        {
            //有点疑问的就是为什么第一个if 里 num 直接覆盖 第二个是累加
            //思考 因为是贪心思想 逐步最优解 第一步的情况是最早发生的，此时depth[V]不确定,自然不能来到第二步
            //且最开始找到一条最短路径时,num也是不确定,第一个num[v]的值就是num[u]的值,后续再次找到的时候就累加上去
            //另外就是小于 为最优情况, 如果后续找到更短的路径, 直接将其覆盖
            if (IsVisit[v] == false && matrix[u][v] != LIMIT::value)
            {
                if (matrix[u][v] + depth[u] < depth[v])
                {
                    depth[v] = depth[u] + matrix[u][v];
                    w[v] = w[u] + weight[v];
                    num[v] = num[u];
                }
                else if (matrix[u][v]+depth[u] == depth[v])
                {
                    if (w[u]+weight[v] > w[v])
                    {
                        w[v] = w[u] + weight[v];
                    }
                    num[v] += num[u];
                }
            }
        }
    }
}

int main()
{
    std::cin >> vertex >> edge >> start >> end;
    for (int i = 0; i < vertex;i++)
    {
        std::cin >> weight[i];
    }

    for (int i = 0; i < edge;i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a][b] = matrix[b][a] = c;
    }
    Dijkstra(start);
    std::cout << num[end] << " " <<  w[end] << std::endl;

    system("pause");
    return 0;
}
//3.
#include <iostream>
#include <type_traits>
#include <vector>

//PATA1030 Dijkstra + DFS

using LIMIT = std::integral_constant<int, 10000>::type;
using MAX = std::integral_constant<int,4>::type; 

int vertex, edge, start, end;

std::vector<std::vector<int>> edge_weight(MAX::value,std::vector<int>(MAX::value,0));
std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, LIMIT::value));
std::vector<std::vector<int>> pre(MAX::value);
std::vector<bool> IsVisit(MAX::value,false);
std::vector<int> depth(MAX::value, LIMIT::value);



void Dijkstra(int start)
{
    depth[start] = 0;

    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex;j++)
        {
            if (IsVisit[j] == false && depth[j] < min)
            {
                min = depth[j];
                u = j;
            }
        }

        if (u == -1)
            return;

        IsVisit[u] = true;

        for (int v = 0; v < vertex;v++)
        {
            if (matrix[u][v] != LIMIT::value && IsVisit[v] == false)
            {
                if (matrix[u][v]+depth[u] < depth[v])
                {
                    depth[v] = matrix[u][v] + depth[u];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if (matrix[u][v] + depth[u] == depth[v])
                {
                    pre[v].push_back(u);
                }
            }
        }
    }
}

std::vector<int> path, temp;
int weight = LIMIT::value;

void DFS(int v)
{
    if (v == start)
    {
        int ans = 0;
        temp.push_back(start);
        for (int i = temp.size() - 1; i > 0;i--)
        {
            int id = temp[i], next = temp[i - 1];
            ans += edge_weight[id][next];
        }
        if (ans < weight)
        {
            path = temp;
            weight = ans;
        }
        temp.pop_back();
        return;
    }
    //为什么放在外面,减少push_back 和pop_back的操作,提升效率
    //若放在里面,每次递归都要push pop 一次
    temp.push_back(v);  
    for (int i = 0; i < pre[v].size();i++)
    {
        DFS(pre[v][i]);
    }
    temp.pop_back();
    
}

int main()
{
    std::cin >> vertex >> edge >> start >> end;

    for (int i = 0; i < edge;i++)
    {
        int a, b, c, d;
        std::cin >> a >> b >> c >> d;
        matrix[a][b] = matrix[b][a] = c;
        edge_weight[a][b] = edge_weight[b][a] = d;
    }
    Dijkstra(start);
    DFS(end);

    for (auto it = path.rbegin(); it != path.rend();it++)
    {
        std::cout << *it << " ";
    }

    std::cout << depth[end] << " " << weight << std::endl;
    
    system("pause");
    return 0;
}
//4.
#include <iostream>
#include <type_traits>
#include <vector>
#include <string>
#include <map>

//PATA1030 Dijkstra

using LIMIT = std::integral_constant<int, 10000>::type;
using MAX = std::integral_constant<int, 4>::type;

std::map<int, std::string> path;
std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, LIMIT::value));
std::vector<std::vector<int>> edge_weight(MAX::value, std::vector<int>(MAX::value, 0));
std::vector<bool> IsVisit(MAX::value, false);
std::vector<int> depth(MAX::value, LIMIT::value);
std::vector<int> cost(MAX::value, LIMIT::value);

//直接Dijkstra 有点小问题 思路差不多

int vertex, edge, start, end;

void Dijkstra(int start)
{
    path[start] = '0';
    depth[start] = 0;
    cost[start] = 0;

    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex;j++)
        {
            if (IsVisit[j] == false && depth[j] < min)
            {
                min = depth[j];
                u = j;
            }
        }

        if (u == -1)
            return;
        IsVisit[u] = true;

        for (int v = 0; v < vertex;v++)
        {
            if (IsVisit[v] == false && matrix[u][v]!=LIMIT::value)
            {
                if (depth[u]+matrix[u][v] < depth[v])
                {
                    depth[v] = depth[u] + matrix[u][v];
                    cost[v] = cost[u] + edge_weight[u][v];
                    path[v] = path[u] + (char)(v + '0');
                }
                else if (depth[u]+matrix[u][v] == depth[v])
                {
                    if (cost[u]+edge_weight[u][v] < cost[v])
                    {
                        cost[v] = cost[u] + edge_weight[u][v];
                        path[v] = path[u] + (char)(v + '0');
                    }
                }
            }
        }
    }
}

int main()
{
    std::cin >> vertex >> edge >> start >> end;

    for (int i = 0; i < edge;i++)
    {
        int a, b, c, d;
        std::cin >> a >> b >> c >> d;
        matrix[a][b] = matrix[b][a] = c;
        edge_weight[a][b] = edge_weight[b][a] = d;
    }
    Dijkstra(start);

    for (auto it : path[end]) std::cout << it << " "; std::cout << depth[end] << " " << cost[end] << std::endl;

    system("pause");
    return 0;
}
//5.
#include <iostream>
#include <vector>
#include <type_traits>
#include <map>
#include <set>

//PATA1003 BellmanFord

using MAX = std::integral_constant<int, 5>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

//first : vertxt , second : edge_weight
std::vector<std::vector<std::pair<int,int>>> matrix(MAX::value);
std::vector<int> weight(MAX::value);
std::vector<int> depth(MAX::value,LIMIT::value);
std::vector<int> num(MAX::value, 0);
std::vector<int> w(MAX::value, 0);
std::vector<std::set<int>> pre(MAX::value);  //存储当前节点的前缀

int vertex, edge, start, end;

bool BellmanFord(int start)
{
    depth[start] = 0;
    w[start] = weight[start];
    num[start] = 1;

    for (int i = 0; i < vertex - 1;i++)
    {
        int flag = 1;
        for (int j = 0; j < vertex;j++)
        {
            for (int v = 0; v < matrix[j].size();v++)
            {
                int id = matrix[j][v].first;
                int w1 = matrix[j][v].second;

                if (depth[j] + w1 < depth[id])
                {
                    depth[id] = depth[j] + w1;
                    w[id] = w[j] + weight[id];
                    flag = 0;
                    num[id] = num[j];
                    pre[id].clear();
                    pre[id].insert(j);
                }
                else if (depth[j]+w1 == depth[id])
                {
                    if (w[j] + weight[id] > w[id])
                    {
                        w[id] = w[j] + weight[id];
                    }
                    //处理重复的情况
                    num[id] = 0;
                    pre[id].insert(j);
                    for (auto it : pre[id])
                    {
                        num[id] += num[it];
                    }
                }
            }
        }
        if (flag)
            break;
    }

    for (int j = 0; j < vertex;j++)
    {
        for (int v = 0; v < matrix[j].size();v++)
        {
            int id = matrix[j][v].first;
            int w1 = matrix[j][v].second;

            if (depth[j] + w1 < depth[id])
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    std::cin >> vertex >> edge >> start >> end;

    for (int i = 0; i < vertex; i++)
    {
        std::cin >> weight[i];
    }

    for (int i = 0; i < edge; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a].push_back({b, c});
        matrix[b].push_back({a, c});
    }

    BellmanFord(start);

    std::cout << num[end] << " " << w[end] << std::endl;

    system("pause");
    return 0;
}
//6.
#include <iostream>
#include <vector>
#include <queue>
#include <type_traits>
#include <map>
#include <set>

//PATA 1003 SPFA
using MAX = std::integral_constant<int, 5>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

//first : vertex , second : edge_weight
std::vector<std::vector<std::pair<int, int>>> matrix(MAX::value);
std::vector<int> weight(MAX::value);
std::vector<int> depth(MAX::value, LIMIT::value);
std::vector<bool> IsEnqueue(MAX::value, false);
std::vector<int> w(MAX::value, 0);
std::vector<int> num(MAX::value,0);

int vertex, edge, start, end;

bool SPFA(int start)
{
    std::queue<int> q;
    depth[start] = 0;
    w[start] = weight[start];
    num[start] = 1;
    q.push(start);
    IsEnqueue[start] = true;

    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        IsEnqueue[now] = false;

        for (int v = 0; v < matrix[now].size();v++)
        {
            int id = matrix[now][v].first;
            int w1 = matrix[now][v].second;
            if (depth[now] + w1 < depth[id])
            {
                num[id] = num[now];
                w[id] = w[now] + weight[id];
                depth[id] = depth[now] + w1;
                q.push(id);
            }
            else if (depth[now] + w1 == depth[id])
            {
                if (w[now] + weight[id] > w[id])
                {
                    w[id] = w[now] + weight[id];
                }
                num[id] += num[now];
            }
        }
    }

    return true;
}

int main()
{
    std::cin >> vertex >> edge >> start >> end;

    for (int i = 0; i < vertex; i++)
    {
        std::cin >> weight[i];
    }

    for (int i = 0; i < edge; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a].push_back({b, c});
        matrix[b].push_back({a, c});
    }

    SPFA(start);
    std::cout << num[end] << " " << w[end] << std::endl;
    system("pause");
    return 0;
}
//7.
#include <iostream>
#include <vector>
#include <type_traits>


//floyd
using MAX = std::integral_constant<int, 200>::type;
using LIMIT = std::integral_constant<int, 100000000>::type;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, LIMIT::value));

int n, m;

void Floyd()
{
    for (int k = 0; k < n;k++)
    {
        for (int i = 0; i < n;i++)
        {
            for (int j = 0; j < n;j++)
            {
                if (matrix[i][k] != LIMIT::value && matrix[k][j] != LIMIT::value
                 && matrix[i][k] + matrix[k][j] < matrix[i][j])
                 {
                     matrix[i][j] = matrix[i][k] + matrix[k][j];
                 }
            }
        }
    }
}

int main()
{
    int u, v, w;
    std::cin >> n >> m;
    for (int i = 0; i < n;i++)
    {
        matrix[i][i] = 0;
    }
    for (int i = 0; i < m;i++)
    {
        std::cin >> u >> v >> w;
        matrix[u][v] = w;
    }

    Floyd();

    for (int i = 0; i < n;i++)
    {
        for (int j= 0; j < n;j++)
        {
            if (matrix[i][j]!=LIMIT::value)
                std::cout << matrix[i][j] << "  ";
            else
            std::cout << "-1 ";
        }
        std::cout << std::endl;
    }
    system("pause");
    return 0;
}
//8.
#include <iostream>
#include <vector>
#include <type_traits>
#include <map>
#include <set>

//PATA 1003 Dijkstra + DFS

using MAX = std::integral_constant<int, 5>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value,LIMIT::value));
std::vector<int> weight(MAX::value, 0);
std::vector<int> depth(MAX::value,LIMIT::value);
std::vector<bool> IsVisit(MAX::value, false);

std::vector<std::vector<int>> pre(MAX::value);

int vertex, edge, start, end;

void Dijkstra(int start)
{
    depth[start] = 0;
    pre[start].push_back(0);

    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex;j++)
        {
            if (IsVisit[j]==false && depth[j]<min)
            {
                min = depth[j];
                u = j;
            }
        }
        if (u == -1)
            return;
        IsVisit[u] = true;

        for (int v = 0; v < vertex; v++)
        {
            if (IsVisit[v] == false &&matrix[u][v]!=LIMIT::value)
            {
                if (depth[u] + matrix[u][v] < depth[v])
                {
                    depth[v] = depth[u] + matrix[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if (depth[u] + matrix[u][v] == depth[v])
                {
                    pre[v].push_back(u);
                }
            }
        }
    }
}

//最短路径数量
int member = 0;
//最大点权和
int cost = 0;
//路径
std::vector<int> temp, path;

void DFS(int v)
{
    if (v == start)
    {
        int ans = 0;
        temp.push_back(start);
        for (int i = 0; i < temp.size();i++)
        {
            ans += weight[temp[i]];
        }
        if (ans > cost)
        {
            path = temp;
            cost = ans;
        }
        temp.pop_back();
        member++;
        return;
    }
    temp.push_back(v);
    for (int j = 0; j < pre[v].size();j++)
    {
        DFS(pre[v][j]);
    }
    temp.pop_back();
}

int main()
{
    std::cin >> vertex >> edge >> start >> end;

    for (int i = 0; i < vertex; i++)
    {
        std::cin >> weight[i];
    }

    for (int i = 0; i < edge; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[b][a] = matrix[a][b] = c;
    }
    Dijkstra(start);
    DFS(end);
    std::cout << member << " " << cost << std::endl;
    system("pause");
    return 0;
}
//9.
#include <iostream>
#include <vector>
#include <string>
#include <type_traits>
#include <queue>
#include <map>
 
//PATA1030 SPFA

using MAX = std::integral_constant<int, 4>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

std::vector<std::vector<int>> matrix(MAX::value,std::vector<int>(MAX::value,LIMIT::value));
std::vector<std::vector<int>> weight(MAX::value,std::vector<int>(MAX::value,LIMIT::value));
std::map<int, std::string> path;
std::vector<int> depth(MAX::value, LIMIT::value);
std::vector<bool> IsEnqueue(MAX::value, false);
std::vector<int> TotalEdge(MAX::value);
int vertex, edge, start, end;

void SPFA(int start)
{
    path[start] = '0';
    std::queue<int> q;
    TotalEdge[start] = 0;
    q.push(start);
    depth[start] = 0;
    IsEnqueue[start] = true;

    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        IsEnqueue[now] = false;

        for (int i = 0; i < vertex;i++)
        {
            if (matrix[now][i]!=LIMIT::value && depth[now]+matrix[now][i] < depth[i])
            {
                TotalEdge[i] = TotalEdge[now] + weight[now][i];
                depth[i] = depth[now] + matrix[now][i];
                path[i] = path[now] + char(i + '0');
                q.push(i);
                IsEnqueue[i] = true;
            }
            else if (matrix[now][i]!=LIMIT::value && depth[now]+matrix[now][i] == depth[i])
            {
                if (TotalEdge[now] + weight[now][i] < TotalEdge[i])
                {
                    TotalEdge[i] = TotalEdge[now] + weight[now][i];
                    path[i] = path[now] + char(i + '0');
                }
            }
        }
    }
}

int main()
{
    std::cin >> vertex >> edge >> start >> end;

    for (int i = 0; i < edge; i++)
    {
        int a, b, c, d;
        std::cin >> a >> b >> c >> d;
        matrix[a][b] = matrix[b][a] = c;
        weight[a][b] = weight[b][a] = d;
    }
    SPFA(start);
    std::cout << path[end] << std::endl;
    std::cout << depth[end] << " " << TotalEdge[end] << std::endl;
    system("pause");
    return 0;
}
//10.
#include <iostream>
#include <vector>
#include <type_traits>
#include <algorithm>

//PATA1018
//对一半

//capacity : 站点最大容量 vertex : 除PBMC以外的站点量 end : 问题结点 edge : 边数
int capacity, vertex, end, edge;

using MAX = std::integral_constant<int, 4>::type;
using LIMIT = std::integral_constant<int, 10000>::type;
const int PBMC = 0;

std::vector<std::vector<int>> matrix(MAX::value,std::vector<int>(MAX::value,LIMIT::value));
std::vector<int> weight(MAX::value,0);
std::vector<std::vector<int>> pre(MAX::value);
std::vector<int> depth(MAX::value, LIMIT::value);
std::vector<bool> IsVisit(MAX::value, false);

void Dijkstra(int start)
{
    pre[start].push_back(0);
    depth[start] = 0;

    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex;j++)
        {
            if (IsVisit[j]==false && depth[j] < min)
            {
                min = depth[j];
                u = j;
            }
        }
        if (u == -1)
            return;
        IsVisit[u] = true;

        for (int v = 0; v < vertex;v++)
        {
            if (matrix[u][v] !=LIMIT::value && IsVisit[v] == false)
            {
                if (depth[u]+matrix[u][v] < depth[v])
                {
                    depth[v] = depth[u] + matrix[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if (depth[u]+matrix[u][v] == depth[v])
                {
                    pre[v].push_back(u);
                }
            }
        }
    }
}

std::vector<int> temp, path;
int need_to_get = LIMIT::value;
int need_to_back;

void DFS(int v)
{
    if (v == PBMC)
    {
        int total = 0;
        temp.push_back(PBMC);
        int len = (int)temp.size();
        for (int j = len-1; j >0;j--)
        {
            if (weight[temp[j]] > 5)
            {
                total -= (weight[temp[j]] - 5);
            }
            else
            {
                total += (5 - weight[temp[j]]);
            }
        }

        if (total<need_to_get)
        {
            if (total>=0)
            {
                need_to_back = 0;
                path = temp;
                need_to_get = total;
            }
            else
            {
                need_to_get = 0;
                path = temp;
                need_to_back = -total;
            }
        }

        temp.pop_back();
        return;
    }
    temp.push_back(v);
    for (int i = 0; i < pre[v].size();i++)
    {
        DFS(pre[v][i]);
    }
    temp.pop_back();
}

int main()
{
    std::cin >> capacity >> vertex >> end >> edge;
    vertex++;
    for (int i = 1; i < vertex;i++)
    {
        std::cin >> weight[i];
    }
    for (int i = 0; i < edge;i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a][b] = matrix[b][a] = c;
    }
    Dijkstra(0);
    DFS(end);
    std::cout << need_to_get << " ";
    for (auto it = path.rbegin(); it != path.rend();++it)
    {
        if ((it+1) != path.rend())
        {
            std::cout << *it << "->";
        }
        else
            std::cout << *it << " ";
    }
    std::cout << need_to_back << std::endl;
    system("pause");
    return 0;
}



// #include<cstdio>
// #include<vector>
// #include<algorithm>
// using namespace std;
// const int maxn = 510;
// const int INF = 1 << 30 - 1;
// int G[maxn][maxn], d[maxn];
// int weight[maxn];
// int cmax, n, sp, m;//每个结点最大容量，结点总量，问题结点编号，路数；
// bool vis[maxn] = { false };
// vector<int> pre[maxn];
// vector<int> path, tempPath;

// void Dijkstra(int s) {
// 	fill(d, d + maxn, INF);
// 	d[s] = 0;
// 	for (int i = 0;i <= n;++i) {
// 		int u = -1, MIN = INF;
// 		for (int j = 0;j <= n;++j) {
// 			if (vis[j] == false && d[j] < MIN) {
// 				u = j;
// 				MIN = d[j];
// 			}
// 		}
// 		if (u == -1) return;
// 		vis[u] = true;
// 		for (int v = 0;v <= n;++v) {
// 			if (vis[v] == false && G[u][v] != INF) {
// 				if (d[u] + G[u][v] < d[v]) {
// 					d[v] = d[u] + G[u][v];
// 					pre[v].clear();
// 					pre[v].push_back(u);
// 				}
// 				else if (d[u] + G[u][v] == d[v]) {
// 					pre[v].push_back(u);
// 				}
// 			}
// 		}
// 	}
// }

// int minNeed = INF, minRemain = INF;
// void DFS(int v) {
// 	if (v == 0) {
// 		tempPath.push_back(v);
// 		//需要携带和带回的数目 
// 		int need = 0, remain = 0;
// 		for (int i = tempPath.size() - 2;i >= 0;--i) {//此处必须倒着枚举， 
// 			int id = tempPath[i];
// 			if (weight[id] > cmax / 2) {//需要带走一部分车 
// 				remain += (weight[id] - cmax / 2);
// 			}
// 			else {
// 				if (remain > cmax / 2 - weight[id]) {//足够补给 
// 					remain -= cmax / 2 - weight[id];
// 				}
// 				else {//不够补给 
// 					need += cmax / 2 - weight[id] - remain;
// 					remain = 0;
// 				}
// 			}
// 		}
// 		if (need < minNeed) {//需要从PBMC携带的自行车数目更少 
// 			minNeed = need;
// 			minRemain = remain;
// 			path = tempPath;
// 		}
// 		else if (need == minNeed && remain < minRemain) {//需要带回的更少 
// 			minRemain = remain;
// 			path = tempPath;
// 		}
// 		tempPath.pop_back();
// 		return;//别忘了 
// 	}
// 	tempPath.push_back(v);
// 	for (int i = 0;i < pre[v].size();++i) {
// 		DFS(pre[v][i]);
// 	}
// 	tempPath.pop_back();
// }

// int main() {
// 	scanf("%d %d %d %d", &cmax, &n, &sp, &m);
// 	fill(G[0], G[0] + maxn * maxn, INF);
// 	for (int i = 1;i <= n;++i) {
// 		scanf("%d", &weight[i]);//点权 
// 	}
// 	for (int i = 0;i < m;++i) {
// 		int u, v, l;
// 		scanf("%d %d %d", &u, &v, &l);
// 		G[u][v] = G[v][u] = l;//边权 
// 	}
// 	Dijkstra(0);
// 	DFS(sp);
// 	printf("%d ", minNeed);
// 	for (int i = path.size() - 1;i >= 0;--i) {
// 		if (i < path.size() - 1) printf("->");
// 		printf("%d", path[i]);
// 	}
// 	printf(" %d", minRemain);
// 	return 0;
// }

//11.
#include <iostream>
#include <vector>
#include <queue>
#include <type_traits>

//PATA1072 
//写完了主框架,细节还没处理

using MAX = std::integral_constant<int, 8>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

//first : vertex  second : edge_Weight
std::vector<std::vector<std::pair<int, int>>> matrix(MAX::value);
std::vector<int> depth(MAX::value, LIMIT::value);
std::vector<bool> IsEnqueue(MAX::value, false);

void SPFA(int start)
{
    depth[start] = 0;
    std::queue<int> q;
    q.push(start);

    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        IsEnqueue[now] = true;

        for (int i = 0; i < matrix[now].size();i++)
        {
            int id = matrix[now][i].first;
            int w = matrix[now][i].second;
            if (depth[now] + w < depth[id])
            {
                depth[id] = depth[now] + w;
                IsEnqueue[id] = true;
                q.push(id);
            }
        }
    }
}

int vertex, house, gas, edge, range;

int main()
{
    std::cin >> house >> gas >> edge >> range;
    for (int i = 0; i < edge;i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a].push_back({b, c});
        matrix[b].push_back({a, c});
    }
    SPFA(5);

    system("pause");
    return 0;
}

//12.
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <type_traits>

//PATA1087 思路简单 就是限制条件比较多 处理起来很麻烦
//限制条件: 1.最短路径 2.最大点权 3.最大点权相等情况下选择最大平均点权 4.最短路径数量 5.边权和

using MAX = std::integral_constant<int, 6>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

int member = 0;
std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, LIMIT::value));
std::vector<int> weight(MAX::value, 0);
std::map<std::string, int> StringToInt;
std::map<int, std::string> IntToString;
std::vector<bool> IsVisit(MAX::value, false);
std::vector<int> depth(MAX::value, LIMIT::value);
std::map<int, std::string> path;
std::vector<int> cost(MAX::value);
std::vector<int> num(MAX::value, 0);
std::vector<double> average_cost(MAX::value, 0);

int vertex, edge, start_num;
std::string start_str;

int change(std::string str)
{
    if (StringToInt.find(str) != StringToInt.end())
    {
        return StringToInt[str];
    }
    else
    {
        StringToInt[str] = member;
        IntToString[member] = str;
        return member++;
    }

}

void Dijkstra(int start)
{
    depth[start] = 0;
    path[start] =(char)(start+'0');
    cost[start] = weight[start];
    num[start] = 1;
    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex; j++)
        {
            if (IsVisit[j]==false && depth[j] < min)
            {
                min = depth[j];
                u = j;
            }
        }
        
        if (u == -1)
            return;
        IsVisit[u] = true;

        for (int v = 0; v < vertex;v++)
        {
            if (matrix[u][v] != LIMIT::value && IsVisit[v] == false)
            {
                if (depth[u]+matrix[u][v] < depth[v])
                {
                    depth[v] = depth[u] + matrix[u][v];
                    path[v] = path[u] + (char)(v + '0');
                    cost[v] = cost[u] + weight[v];
                    num[v] = num[u];
                }
                else if (depth[u]+matrix[u][v] == depth[v])
                {
                    if (cost[u] + weight[v] > cost[v])
                    {
                        path[v] = path[u] + (char)(v + '0');
                        cost[v] = cost[u] + weight[v];
                    }
                    num[v] += num[u];
                }
            }
        }
    }
}

int main()
{
    std::cin >> vertex >> edge >> start_str;
    start_num = change(start_str);
    for (int i = 0; i < vertex-1; i++)
    {
        std::string str;
        std::cin >> str;
        int id = change(str);
        std::cin >> weight[id];
    }
    for (int i = 0; i < edge;i++)
    {
        std::string str1, str2;
        int u, v, l;
        std::cin >> str1 >> str2 >> l;
        u = StringToInt[str1];
        v = StringToInt[str2];
        matrix[u][v] = matrix[v][u] = l;
    }

    Dijkstra(start_num);
    
    int id = StringToInt["ROM"];
    int len = path[id].size();
    for (int i = 0; i <len ;i++)
    {
        if (i != len -1)
        {
            std::cout << IntToString[path[id][i] - '0'] << "->";
        }
        else 
        {
            std::cout << IntToString[path[id][i] - '0'] << std::endl;
        }
    }
        system("pause");
    return 0;
}

10.5

//1.
#include <iostream>
#include <vector>
#include <type_traits>


//prim
using MAX = std::integral_constant<int, 6>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, LIMIT::value));
std::vector<bool> IsVisit(MAX::value, false);
std::vector<int> depth(MAX::value, LIMIT::value);

int vertex, edge;

int prim(int start)
{
    depth[start] = 0;
    int sum = 0;

    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex; j++)
        {
            if (IsVisit[j]==false && depth[j] < min)
            {
                min = depth[j];
                u = j;
            }
        }
        if (u == -1)
            return sum;
        IsVisit[u] = true;
        sum += depth[u];

        for (int v = 0; v < vertex;v++)
        {
            if (matrix[u][v]!=LIMIT::value && IsVisit[v]==false && matrix[u][v] < depth[v])
            {
                depth[v] = matrix[u][v];
            }
        }
    }
    return sum;
}



int main()
{
    std::cin >> vertex >> edge;
    for (int i = 0; i < edge; i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a][b] = matrix[b][a] = c;
    }
    std::cout << prim(0) << std::endl;
    system("pause");
    return 0;
}
//2.
#include <iostream>
#include <vector>
#include <algorithm>
#include <type_traits>

//Kruskal
using MAX = std::integral_constant<int, 10>::type;
std::vector<int> father(MAX::value);

int Find_Father(int n)
{
    int a = n;
    while (n!=father[n])
    {
        n = father[n];
    }
    while (a!=father[a])
    {
        int z = a;
        a = father[a];
        father[z] = n;
    }
    return n;
}

struct node
{
    int u, v;
    int cost;
} edge[MAX::value];

bool cmp(node a,node b)
{
    return a.cost < b.cost;
}

int vertex, edge_num;

int Kruskal()
{
    int ans = 0, count = 0;
    for (int i = 0; i < father.size();i++)
    {
        father[i] = i;
    }
    std::sort(edge, edge + edge_num, cmp);

    for (int i = 0; i < edge_num;i++)
    {
        int fa = Find_Father(edge[i].u);
        int fb = Find_Father(edge[i].v);

        if (fa != fb)
        {
            father[fa] = fb;
            ans += edge[i].cost;
            count++;
        }
        if (count == vertex-1)
            break;
    }
    if (count != vertex-1)
    {
        return -1;
    }
    else
        return ans;
}

int main()
{
    std::cin >> vertex >> edge_num;
    for (int i = 0; i < edge_num;i++)
    {
        std::cin >> edge[i].u >> edge[i].v >> edge[i].cost;
    }
    std::cout << Kruskal() << std::endl;
    system("pause");
    return 0;
}
//3.
#include <iostream>
#include <vector>
#include <type_traits>

using MAX = std::integral_constant<int, 4>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, LIMIT::value));
std::vector<bool> IsVisit(MAX::value, false);
std::vector<int> depth(MAX::value,LIMIT::value);

int vertex, edge;

int prim(int start)
{
    int ans = 0;
    depth[start] = 0;

    for (int i = 0; i < vertex; i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex; j++)
        {
            if (IsVisit[j]==false && depth[j]<min)
            {
                min = depth[j];
                u = j;
            }
        }
        if (u == -1)
            return -1;
        IsVisit[u] = true;
        ans += depth[u];

        for (int v = 0; v < vertex; v++)
        {
            if (matrix[u][v] != LIMIT::value && IsVisit[v] == false && matrix[u][v] < depth[v])
            {
                depth[v] = matrix[u][v];
            }
        }
    }
    return ans;
}

int main()
{
    std::cin >> vertex >> edge;
    for (int i = 0; i < edge;i++)
    {
        int a, b, c;
        std::cin >> a >> b >> c;
        matrix[a][b] = matrix[b][a] = c;
    }
    std::cout << prim(0) << std::endl;
    system("pause");
    return 0;
}
//4.
#include <iostream>
#include <type_traits>
#include <algorithm>
#include <vector>
#include <map>


using MAX = std::integral_constant<int, 5>::type;

std::vector<int> father(MAX::value);

int Find_Father(int n)
{
    int a = n;
    while (n!=father[n])
    {
        n = father[n];
    }
    while (a!=father[a])
    {
        int z = a;
        a = father[a];
        father[z] = n;
    }
    return n;
}

struct node 
{
    int u, v, cost;
} edge[MAX::value];

bool cmp(node a,node b)
{
    return a.cost < b.cost;
}

int vertex, edge_num;

int Kruskal()
{
    int ans = 0, count = 0;
    for (int i = 0; i < vertex;i++)
    {
        father[i] = i;
    }
    std::sort(edge, edge + MAX::value, cmp);

    for (int i = 0; i < edge_num;i++)
    {
        int fa = Find_Father(edge[i].u);
        int fb = Find_Father(edge[i].v);
        if (fa != fb)
        {
            father[fa] = fb;
            ans += edge[i].cost;
            count++;
        }
        if (count == vertex-1)
            break;
    }
    if (count != vertex-1)
        return -1;
    else
        return ans;
}

int main()
{
    std::cin >> vertex >> edge_num;
    for (int i = 0; i < edge_num; i++)
    {
        std::cin >> edge[i].u >> edge[i].v >> edge[i].cost;
    }
    std::cout << Kruskal() << std::endl;
    system("pause");
    return 0;
}
//5.
#include <iostream>
#include <type_traits>
#include <vector>

using MAX = std::integral_constant<int, 4>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, 0));
std::vector<int> depth(MAX::value, LIMIT::value);
std::vector<bool> IsVisit(MAX::value, false);


int vertex;

int Prim(int start)
{
    int ans = 0;
    depth[start] = 0;

    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex; j++)
        {
            if (IsVisit[j] == false && depth[j] < min)
            {
                min = depth[j];
                u = j;
            }
        }

        if (u == -1)
            return -1;
        IsVisit[u] = true;
        ans += depth[u];

        for (int v = 0; v < vertex; v++)
        {
            if (matrix[u][v] > 0 && IsVisit[v] == false && matrix[u][v] <depth[v])
            {
                depth[v] = matrix[u][v];
            }
        }
    }
    return ans;
}

int main()
{
    std::cin >> vertex;
    for (int i = 0; i < vertex; i++)
    {
        for (int j = 0; j < vertex;j++)
        {
            std::cin >> matrix[i][j];
        }
    }

    std::cout << Prim(0) << std::endl;

    system("pause");
    return 0;
}
//6.
#include <type_traits>
#include <algorithm>
#include <iostream>
#include <vector>

using MAX = std::integral_constant<int, 5>::type;
std::vector<int> father(MAX::value);

int Find_Father(int n)
{
    int a = n;
    while (n!=father[n])
    {
        n = father[n];
    }
    while (a!=father[a])
    {
        int z = a;
        a = father[a];
        father[z] = n;
    }
    return n;
}

struct node
{
    int flag;
    int u, v, cost;
} edge[MAX::value];

bool cmp(node a,node b)
{
    return a.cost < b.cost;
}

int vertex, edge_num;

int Kruskal()
{
    int ans = 0, count = 0;
    for (int i = 0; i < vertex;i++)
    {
        father[i] = i;
    }
    std::sort(edge, edge + MAX::value, cmp);

    for (int i = 0; i < edge_num; i++)
    {
        int fa = Find_Father(edge[i].u);
        int fb = Find_Father(edge[i].v);
        if (fa != fb)
        {
            father[fa] = fb;
            //ans += edge[i].cost;
            edge[i].flag = 0;
            count++;
        }
        if (count == vertex-1)
            break;
    }
    if (count != vertex-1)
        return -1;
    else
    {
        for (int i = 0; i < edge_num;i++)
        {
            if (edge[i].flag)
                ans += edge[i].cost;
        }
        return ans;
    }
}

int main()
{
    std::cin >> vertex >> edge_num;
    for (int i = 0; i < edge_num; i++)
    {
        std::cin >> edge[i].u >> edge[i].v >> edge[i].cost;
        edge[i].flag = 1;
    }
    std::cout << Kruskal() << std::endl;
    system("pause");
    return 0;
}

//7.
#include <iostream>
#include <type_traits>
#include <vector>

using MAX = std::integral_constant<int, 4>::type;
using LIMIT = std::integral_constant<int, 10000>::type;

std::vector<std::vector<int>> matrix(MAX::value, std::vector<int>(MAX::value, 0));
std::vector<int> depth(MAX::value, LIMIT::value);
std::vector<bool> IsVisit(MAX::value, false);


int vertex, already;

int Prim()
{
    int ans = 0;
    for (int i = 0; i < vertex;i++)
    {
        int u = -1, min = LIMIT::value;
        for (int j = 0; j < vertex; j++)
        {
            if (IsVisit[j] == false && depth[j] < min)
            {
                min = depth[j];
                u = j;
            }
        }

        if (u == -1)
            return -1;
        IsVisit[u] = true;
        ans += depth[u];

        for (int v = 0; v < vertex; v++)
        {
            if (matrix[u][v] > 0 && IsVisit[v] == false && matrix[u][v] <depth[v])
            {
                depth[v] = matrix[u][v];
            }
        }
    }
    return ans;
}

int main()
{
    std::cin >> vertex >> already;
    for (int i = 0; i < vertex; i++)
    {
        for (int j = 0; j < vertex;j++)
        {
            std::cin >> matrix[i][j];
        }
    }

    for (int i = 0; i < already;i++)
    {
        int h;
        std::cin >> h;
        depth[h] = 0;
        IsVisit[h] = false;
    }

    std::cout << Prim() << std::endl;

    system("pause");
    return 0;
}

10.6

//1.
#include <iostream>
#include <type_traits>
#include <vector>
#include <queue>

using MAX = std::integral_constant<int, 4>::type;

std::vector<std::vector<int>> matrix(MAX::value);
std::vector<int> InDegree(MAX::value, 0);

int vertex, edge;

bool topologicalSort()
{
    int num = 0;
    std::queue<int> q;
    for (int i = 0; i < vertex;i++)
    {
        if (InDegree[i] == 0)
        {
            q.push(i);
        }
    }

    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        std::cout << now << " ";

        for (int i = 0; i < matrix[now].size();i++)
        {
            int id = matrix[now][i];
            InDegree[id]--;

            if (InDegree[id] == 0)
            {
                q.push(id);
            }
        }
        num++;
    }
    std::cout << std::endl;
    if (num == vertex)
        return true;
    else
        return false;
}

int main()
{
    std::cin >> vertex >> edge;

    for (int i = 0; i < edge; i++)
    {
        int a, b;
        std::cin >> a >> b;
        matrix[a].push_back(b);
        InDegree[b]++;
    }
    topologicalSort();
    system("pause");
    return 0;
}
//2.
#include <iostream>
#include <type_traits>
#include <vector>
#include <queue>

using MAX = std::integral_constant<int, 4>::type;

std::vector<std::vector<int>> matrix(MAX::value);
std::vector<int> InDegree(MAX::value, 0);

int vertex, edge;

bool topologicalSort()
{
    int num = 0;
    std::queue<int> q;
    for (int i = 0; i < vertex;i++)
    {
        if (InDegree[i] == 0)
            q.push(i);
    }

    while (!q.empty())
    {
        int now = q.front();
        q.pop();

        for (int i = 0; i < (int)(matrix[now].size()); i++)
        {
            int id = matrix[now][i];
            InDegree[id]--;
            if (InDegree[id] == 0)
            {
                q.push(id);
            }
        }
        num++;
    }
    if (num==vertex)
        return true;
    else
        return false;
}

int main()
{
    std::cin >> vertex >> edge;

    for (int i = 0; i < edge; i++)
    {
        int a, b;
        std::cin >> a >> b;
        matrix[a].push_back(b);
        InDegree[b]++;
    }
    if (topologicalSort())
        std::cout << "YES" << std::endl;
    else
        std::cout << "NO" << std::endl;
    system("pause");
    return 0;
}
//3.
#include <iostream>
#include <type_traits>
#include <vector>
#include <queue>

using MAX = std::integral_constant<int, 4>::type;

std::vector<std::vector<int>> matrix(MAX::value);
std::vector<int> InDegree(MAX::value, 0);
std::vector<int> study;

int vertex, edge;

bool topologicalSort()
{
    int num = 0;
    std::queue<int> q;
    for (int i = 0; i < vertex;i++)
    {
        if (InDegree[i] == 0)
            q.push(i);
    }

    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        study.push_back(now);

        for (int i = 0; i < (int)(matrix[now].size()); i++)
        {
            int id = matrix[now][i];
            InDegree[id]--;
            if (InDegree[id] == 0)
            {
                q.push(id);
            }
        }
        num++;
    }
    if (num==vertex)
        return true;
    else
        return false;
}

int main()
{
    std::cin >> vertex >> edge;

    for (int i = 0; i < edge; i++)
    {
        int a, b;
        std::cin >> a >> b;
        matrix[a].push_back(b);
        InDegree[b]++;
    }
    if (topologicalSort())
    {
        std::cout << "YES" << std::endl;
        for (int i = 0; i < study.size(); i++)
            std::cout << study[i] << " ";
        std::cout << std::endl;
    }
    else
    {
        std::cout << "NO" << std::endl;
        std::cout << vertex - (int)(study.size()) << std::endl;
    }
    system("pause");
    return 0;
}