1036. Boys vs Girls (25)

1.求出男生中成绩最低的,女生中成绩最高的,并且输出两者的差。没有的话输出Absent和NA。

2.简单的重写比较函数。

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

This time you are asked to tell the difference between the lowest grade of all the male students and the highest grade of all the female students.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N, followed by N lines of student information. Each line contains a student’s name, gender, ID and grade, separated by a space, where name and ID are strings of no more than 10 characters with no space, gender is either F (female) or M (male), and grade is an integer between 0 and 100. It is guaranteed that all the grades are distinct.

Output Specification:

For each test case, output in 3 lines. The first line gives the name and ID of the female student with the highest grade, and the second line gives that of the male student with the lowest grade. The third line gives the difference gradeF-gradeM. If one such kind of student is missing, output “Absent” in the corresponding line, and output “NA” in the third line instead.

Sample Input 1:

3
Joe M Math990112 89
Mike M CS991301 100
Mary F EE990830 95

Sample Output 1:

Mary EE990830
Joe Math990112
6

Sample Input 2:

1
Jean M AA980920 60

Sample Output 2:

Absent
Jean AA980920
NA
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
struct studentNode{
	string name;
	string id;
	int grade;
	studentNode(string n, string i, int g) :name(n), id(i), grade(g){};
	studentNode() :name(""), id(""), grade(0){};
};
bool cmpM(const studentNode&a, const studentNode&b)
{
	return a.grade < b.grade;
}
bool cmpF(const studentNode&a, const studentNode&b)
{
	return a.grade > b.grade;
}
int main(void)
{
	int n;
	cin >> n;
	vector<studentNode> m(0);
	vector<studentNode> f(0);
	for (int i = 0; i < n; i++)
	{
		string name, id, gender;
		int grade;
		cin >> name >> gender >> id >> grade;
		if (gender == "F")
			f.push_back(studentNode(name, id, grade));
		else
			m.push_back(studentNode(name, id, grade));
	}
	sort(f.begin(), f.end(), cmpF);
	sort(m.begin(), m.end(), cmpM);

	if (f.size()>0)
		cout << f[0].name << " " << f[0].id << endl;
	else
		cout << "Absent" << endl;
	if (m.size()>0)
		cout << m[0].name << " " << m[0].id << endl;
	else
		cout << "Absent" << endl;
	if (f.size() > 0 && m.size() > 0)
		cout << f[0].grade - m[0].grade << endl;
	else
		cout << "NA" << endl;



	return 0;
}

1035. Password (20)

1.把1替换成@,把0替换成%,把l替换成L,把O替换成o。replace 1 (one) by @, 0 (zero) by %, l by L, and O by o。

2.简单的字符串处理。

3.注意0,1个没有修改,输出的句子是is,大于1个没有修改的,输出的句子是are。

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

To prepare for PAT, the judge sometimes has to generate random passwords for the users. The problem is that there are always some confusing passwords since it is hard to distinguish 1 (one) from l (L in lowercase), or 0 (zero) from O (o in uppercase). One solution is to replace 1 (one) by @, 0 (zero) by %, l by L, and O by o. Now it is your job to write a program to check the accounts generated by the judge, and to help the juge modify the confusing passwords.

Input Specification:

Each input file contains one test case. Each case contains a positive integer N (<= 1000), followed by N lines of accounts. Each account consists of a user name and a password, both are strings of no more than 10 characters with no space.

Output Specification:

For each test case, first print the number M of accounts that have been modified, then print in the following M lines the modified accounts info, that is, the user names and the corresponding modified passwords. The accounts must be printed in the same order as they are read in. If no account is modified, print in one line “There are N accounts and no account is modified” where N is the total number of accounts. However, if N is one, you must print “There is 1 account and no account is modified” instead.

Sample Input 1:

3
Team000002 Rlsp0dfa
Team000003 perfectpwd
Team000001 R1spOdfa

Sample Output 1:

2
Team000002 RLsp%dfa
Team000001 R@spodfa

Sample Input 2:

1
team110 abcdefg332

Sample Output 2:

There is 1 account and no account is modified

Sample Input 3:

2
team110 abcdefg222
team220 abcdefg333

Sample Output 3:

There are 2 accounts and no account is modified

 
AC代码:

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;

char replace(char a)
{
	switch (a)
	{
	case'1':return '@';
	case'0':return '%';
	case'l':return 'L';
	case'O':return 'o';
	default:return a;
	}
}

int main(void)
{
	int n;
	cin >> n;
	vector<pair<string, string>> ans(0);
	for (int i = 0; i < n; i++)
	{
		string name, pw;
		cin >> name >> pw;
		bool re = false;
		for (int i = 0; i < pw.size(); i++)
		{
			if (pw[i] == '1' || pw[i] == '0' || pw[i] == 'l' || pw[i] == 'O')
			{
				pw[i] = replace(pw[i]);
				re = true;
			}
		}
		if (re)
		{
			ans.push_back({ name, pw });
		}
	}
	if (ans.size() == 0)
	{
		if (n<=1)
			printf("There is %d account and no account is modified\n", n);
		else
			printf("There are %d accounts and no account is modified\n", n);

	}
	else
	{
		cout << ans.size() << endl;
		for (int i = 0; i < ans.size(); i++)
			cout << ans[i].first << " " << ans[i].second << endl;
	}
	return 0;
}

1034. Head of a Gang (30)

1.该题目主要求团伙中通话的时间总和,有多个潜在的团伙,涉及到了并查集和一些统计。

2.算法过程

1)收集根据记录,存储每个人的总通话时间和他的联系人,同时进行并查集的合并。

2)根据并查集中分好的集合,进行集合的分类,并且分别统计各集合的名单和总通话时间

3)遍历上面的集合,找出符合条件的gang和gang的头目

注:A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K

有联系即可,不是gang里面每个人都相互联系。

代码利用了大量的map,set之类,可能会有点难懂。

时间限制
100 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

One way that the police finds the head of a gang is to check people’s phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls made between the two persons. A “Gang” is a cluster of more than 2 persons who are related to each other with total relation weight being greater than a given threshold K. In each gang, the one with maximum total weight is the head. Now given a list of phone calls, you are supposed to find the gangs and the heads.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive numbers N and K (both less than or equal to 1000), the number of phone calls and the weight threthold, respectively. Then N lines follow, each in the following format:

Name1 Name2 Time

where Name1 and Name2 are the names of people at the two ends of the call, and Time is the length of the call. A name is a string of three capital letters chosen from A-Z. A time length is a positive integer which is no more than 1000 minutes.

Output Specification:

For each test case, first print in a line the total number of gangs. Then for each gang, print in a line the name of the head and the total number of the members. It is guaranteed that the head is unique for each gang. The output must be sorted according to the alphabetical order of the names of the heads.

Sample Input 1:

8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10

Sample Output 1:

2
AAA 3
GGG 3

Sample Input 2:

8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10

Sample Output 2:

0
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;

struct guyNode{
	set<string> contact;
	int time;
	string r;
	guyNode() : time(0), r(""){ contact.clear(); };
};
string find(string a,map<string, guyNode>&m)
{
	if (m[a].r == a)
		return a;
	else
	{
		m[a].r = find(m[a].r, m);
		return m[a].r;
	}
}

int main(void)
{
	int recordNum, threshold;
	cin >> recordNum >> threshold;
	map<string, guyNode> m;//存储每个人的总通话时间和联系人
	for (int i = 0; i < recordNum; i++)
	{//输入联系记录
		string a, b;
		int time;
		cin >> a >> b >> time;
		if (m[a].r == "") m[a].r = a;//如果是第一次输入,则把代表设为自己
		if (m[b].r == "") m[b].r = b;
		m[a].contact.insert(b);//增加联系人b
		m[a].time += time;//累加通话时间
		m[b].contact.insert(a);//增加联系人a
		m[b].time += time;//累加通话时间
		if (find(a,m)!=find(b,m))
			m[find(a, m)].r = find(b, m);//合并
	}

	map<string, set<string>> gang;//存储gang的代表和成员,注意,代表还不是头目
	map<string, int> contactTime;//计算各个gang的总通话时间,注意,a和b通话,a累加了一次时间,b又累加了一次时间,所以是实际时间的两倍
	for (map<string, guyNode>::iterator ite = m.begin(); ite != m.end(); ite++)
	{//遍历所有的集合
		gang[find(ite->first, m)].insert(ite->first);//利用并查集,分为不同的集合gang
		contactTime[find(ite->first, m)] += ite->second.time;//统计各个gang的时间
	}
	map<string, int> ans;
	for (map<string, set<string>>::iterator ite = gang.begin(); ite != gang.end(); ite++)
	{
		if (contactTime[ite->first] <= threshold * 2 || ite->second.size()<=2) 
			continue;//通话时间不满足要求,人数少于两人

		bool isGang = true;//标志位
		string head = "";//设置头目信息
		int maxTime = 0;//通话时间为0
		int sum = ite->second.size();//gang的总人数
		for (set<string>::iterator ite2 = ite->second.begin(); ite2 != ite->second.end(); ite2++)
		{
			string name = *ite2;
			if (m[name].time > maxTime)
			{//查找通话时间最长的人,即head of gang
				head = name;
				maxTime = m[name].time;
			}
		}
		if (isGang)
		{
			ans[head] = sum;
		}
	}
	cout << ans.size() << endl;
	for (map<string, int>::iterator ite = ans.begin(); ite != ans.end(); ite++)
	{//输出gang的head和成员数
		cout << ite->first << " " << ite->second << endl;
	}





	return 0;
}

1033. To Fill or Not to Fill (25)

1.这道题目比较有趣,给出了加油站的位置和每个站的油价,求最小耗费,如果不能到达终点,则求能走的最远距离。

2.思路:

1)采用一个油箱数组的概念,实则是一个vector,当成队列使用,这个vector记录了加了的油的价格,油的容量,通过这些油走过的长度和耗费;

2)每到一个站,计算从上一站达到这个站所需要的油needGas

3)从油箱数组容量不为0的油中开始遍历,直接完全满足needGas的要求,同时计算油箱数组中被使用到的油的耗费和走的距离。

4)遍历完油箱数组后,如果needGas不为0,那么油箱数组的总油量不够用,直接计算油箱数组走的总距离并输出答案

5)如果needGas为0,那么对比油箱数组剩余油(油的容量不为0)的价格,如果比当前站高,则更新为当前站的价格,

其实际意义是:到了当前的加油站,油箱里面还有油(这些油可加也可不加,都能使车到达当前站点),这些油的价格比当前加油站要高(那么之前就没必要加油,直接在当前站点加满),那么在之前就不加油了,在这个站点家满cMax的油量,记录价格,进入下一次循环即可。

6)把终点作为最后一个站,油的价格为0.

时间限制
10 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
ZHANG, Guochuan

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,…N. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print “The maximum travel distance = X” where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

Sample Input 1:

50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300

Sample Output 1:

749.17

Sample Input 2:

50 1300 12 2
7.10 0
7.00 600

Sample Output 2:

The maximum travel distance = 1200.00

 
AC代码:

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
/*
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
  
50 1300 12 2
7.10 0
7.00 600
  
50 0 12 2
7.10 0
7.00 600
  
50 0 12 0
  
50 13000 12 2
7.10 0
7.00 600
*/
struct stationNode{
    double price;
    int position;
    stationNode() :price(0), position(0){};
};
struct gasNode{
    double price;//价格
    double cap;//容量
    double cost;//总价格
    double dist;
    gasNode() :price(0), cap(0), cost(0),dist(0){};
    gasNode(double p,double c) :price(p), cap(c), cost(0),dist(0){};
};
bool cmp(const stationNode&a, const stationNode&b)
{
    return a.position < b.position;
}
int main(void)
{
    int cMax, target, dAvg, n;
    cin >> cMax >> target >> dAvg >> n;
    n++;//把终点也作为一个站
    vector<stationNode> sta(n);
    for (int i = 0; i < n - 1; i++)
    {//初始化
        cin >> sta[i].price >> sta[i].position;
    }
    sta.back().position = target;//设置终点的距离
    sort(sta.begin(), sta.end(), cmp);//按照站的位置进行排序
    vector<gasNode> gas(0);//油箱数组
    int gasIndex = 0;//记录当前用到哪个油箱数组的油
    double totalGas = 0;
    if (0 >= sta[0].position)
    {//把第一个站加进去,包含价格信息和加了多少油
        gas.push_back(gasNode(sta[0].price, cMax));
        totalGas = cMax;
        //now += cMax*dAvg;
    }
    for (int now = 1; now < n; now++)
    {
        //needGas表示从i-1站到i站需要多少油
        double needGas = (sta[now].position - sta[now - 1].position) *1.0 / dAvg;
  
        //把油箱里的油减去需要用的油,计算得到油箱还剩多少油
        totalGas -= needGas;
        //在这里可以直接判断totalGas是否小于0,小于0表示油箱不够油跑下去,但是由于题目还需要求最长距离,所以这里不作处理,统计完邮箱所有的油再进行处理
  
  
        //遍历邮箱数组,利用gasIndex做开始位,减少时间复杂度
        for (int j = gasIndex; j < gas.size(); j++)
        {
            if (gas[j].cap > needGas)
            {//当前vector的油能够满足需求
                gas[j].cap -= needGas;//减去需要用的油,得到剩余的油
                gas[j].cost += needGas*gas[j].price;//计算这个vector的油已经耗费了多少钱
                gas[j].dist += needGas*dAvg;//计算这个vector的油走了多长的路
                gasIndex = j;//下次直接从这个vector计算油量
                needGas = 0;
                break;
            }
            else if (gas[j].cap < needGas)
            {//如果当前vector的油量不足
                gas[j].cost += gas[j].cap*gas[j].price;//计算这个vector的油耗费了多少钱
                gas[j].dist += gas[j].cap*dAvg;//计算这个vector的油走了多长的路
                needGas -= gas[j].cap;//除去这个vector的油,还需要多少油
                gasIndex = j;
            }
            else
            {//刚好等于需要的油,由于使用了double,基本不会出现这种needGas等于0的情况
                gas[j].cost += gas[j].cap*gas[j].price;//计算这个vector的油耗费了多少钱
                gas[j].dist += gas[j].cap*dAvg;//计算这个vector的油走了多长的路
                needGas -= gas[j].cap;//needGas为0
                gasIndex = j + 1;//直接指向下个vector
                break;
            }
        }
  
        if (needGas > 0)
        {//当前油箱的总油量不能走到当前地点
            double totalDist = 0;
            //统计走了多少路
            for (int j = 0; j < gas.size(); j++)
                totalDist += gas[j].dist;
  
            printf("The maximum travel distance = %.2f", totalDist);
            return 0;
        }
  
        //能够到当前地点
        for (int j = gasIndex; j < gas.size(); j++)
        {//遍历邮箱里面存在的油,如果价格比当前油站要高,那么就更新价格
        //实际的意义相当于:到了当前的站还有油剩(这些油可加可不加),且之前加的油价格比当前油站要高(这些油没必要在之前加),那么在之前就不加油了,全换成到这个站才加油
            if (gas[j].price>sta[now].price)
                gas[j].price = sta[now].price;
        }
        //把油补充满
        gas.push_back(gasNode(sta[now].price, cMax - totalGas));
        totalGas = cMax;
    }
  
    //计算总价格
    double totalCost = 0;
    for (int i = 0; i < gas.size(); i++)
    {
        totalCost += gas[i].cost;
    }
    printf("%.2lf", totalCost);
    return 0;
}

1032. Sharing (25)

1.题目求两个链表的公共节点。

2.直接建立两个100001长度的数组,一个用来当作链表使用,一个用来当作后面的哈希查询使用。

2.遍历第一个链表,把第一个链表中存在的节点记录在哈希表中。

3.遍历第二个链表,如果哈希中存在某个节点的值,就break,最终输出该节点值。

4.把地址改为int存储,最后输出注意-1和其他的补0的情况。

时间限制
100 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, “loading” and “being” are stored as showed in Figure 1.

1032sharingFigure 1
You are supposed to find the starting position of the common suffix (e.g. the position of “i” in Figure 1).

Input Specification:

Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (<= 105), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is the letter contained by this node which is an English letter chosen from {a-z, A-Z}, andNext is the position of the next node.

Output Specification:

For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output “-1” instead.

Sample Input 1:

11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010

Sample Output 1:

67890

Sample Input 2:

00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1

Sample Output 2:

-1

AC代码:

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;

/*
11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010

11111 22222 9
00012 i 00002
00010 a 12345
00003 g -1
12345 D 00012
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 00012
00001 o 00010
*/
int main(void)
{
	int *m = new int[100001];
	int *exist = new int[100001];
	memset(m, -1, sizeof(m));
	memset(exist, -1, sizeof(exist));
	int sum;
	int a, b;
	scanf("%d %d %d", &a, &b, &sum);
	m[a] = -1;
	m[b] = -1;

	for (int i = 0; i < sum; i++)
	{
		char tmp[10];
		int pre, next;
		scanf("%d %s %d", &pre, tmp, &next);
		m[pre] = next;
	}
	int head = a;
	while (head != -1)
	{//把第一个链表存进哈希表 exist中
		exist[head] = 1;
		head = m[head];
	}
	head = b;
	while (head != -1)
	{
		if (exist[head] == 1)
		{
			break;
		}
		head = m[head];
	}
	if (head != -1)
		printf("%05d\n", head);
	else
		printf("%d\n", head);

	return 0;
}

1031. Hello World for U (20)

1.题目要求把一个字符串按照U型输出。

2..通过 n1 = n3 = max { k| k <= n2 for all 3 <= n2 <= N } with n1 + n2 + n3 – 2 = N的条件,通过for循环求出最大的n1。

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

Given any string of N (>=5) characters, you are asked to form the characters into the shape of U. For example, “helloworld” can be printed as:

h  d
e  l
l  r
lowo

That is, the characters must be printed in the original order, starting top-down from the left vertical line with n1characters, then left to right along the bottom line with n2 characters, and finally bottom-up along the vertical line with n3 characters. And more, we would like U to be as squared as possible — that is, it must be satisfied that n1 = n3 = max { k| k <= n2 for all 3 <= n2 <= N } with n1 + n2 + n3 – 2 = N.Input Specification:

Each input file contains one test case. Each case contains one string with no less than 5 and no more than 80 characters in a line. The string contains no white space.

Output Specification:

For each test case, print the input string in the shape of U as specified in the description.

Sample Input:

helloworld!

Sample Output:

h   !
e   d
l   l
lowor

AC代码:

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;

int main(void)
{
	string s;
	cin >> s;
	int n = s.size();
	int n1 = 0, n2 = 0;
	for (int i = 0; i < n; i++)
	{//求出n1的最大值
		n1 = i;
		n2 = n + 2 - 2 * n1;
		if (n2 < n1) break;
	}
	if (n2 < n1)
		n1--;
	n2 = n + 2 - 2 * n1;
	string mid = "";
	for (int i = 0; i < n2 - 2; i++)
		mid += " ";

	for (int i = 0; i < n1 - 1; i++)
	{
		cout << s[i] << mid << s[s.size() - 1 - i] << endl;
	}
	for (int i = n1 - 1; i < n1 - 1 + n2; i++)
	{
		cout << s[i];
	}
	cout << endl;
	return 0;
}

1030. Travel Plan (30)

1.题目要求最短路径,最短路径不唯一时,求花费最小的路径。

2.仍然是先使用Dijkstra求出最短距离,然后使用深度搜索遍历,以最短距离作为条件进行剪枝,最后求出最短距离的基础上耗费最小的路径。

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

A traveler’s map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If such a shortest path is not unique, you are supposed to output the one with the minimum cost, which is guaranteed to be unique.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers N, M, S, and D, where N (<=500) is the number of cities (and hence the cities are numbered from 0 to N-1); M is the number of highways; S and D are the starting and the destination cities, respectively. Then M lines follow, each provides the information of a highway, in the format:

City1 City2 Distance Cost

where the numbers are all integers no more than 500, and are separated by a space.

Output Specification:

For each test case, print in one line the cities along the shortest path from the starting point to the destination, followed by the total distance and the total cost of the path. The numbers must be separated by a space and there must be no extra space at the end of output.

Sample Input

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

Sample Output

0 2 3 3 40

 
AC代码:

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
/*
4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

4 5 0 0
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20
*/
struct neighbor
{
	int idx;
	int w;
	long long dist;
	neighbor() :idx(-1), w(-1), dist(-1){};
	neighbor(int a, int b, int c) :idx(a), w(b), dist(c){};
};
struct vertexNode{
	vector<neighbor> nb;
	bool visited;
	bool sured;
	long long dist;
	vertexNode(): nb(0), visited(false), sured(false), dist(INT_MAX){};
};

void dfs(int now,int t,int dist,int minDist,int cost,vector<int>& path,vector<pair<int,vector<int>>>& ans,vector<vertexNode>& v,vector<bool>&used)
{
	if (dist > minDist) return;
	if (now == t && dist == minDist)
	{
		ans.push_back({ cost, path });
	}
	else
	{
		for (int i = 0; i < v[now].nb.size(); i++)
		{
			int q = v[now].nb[i].idx;
			if (!used[q])
			{
				used[q] = true;
				path.push_back(q);
				dfs(q, t, dist + v[now].nb[i].dist, minDist, cost + v[now].nb[i].w, path, ans, v, used);
				path.pop_back();
				used[q] = false;
			}
		}
	}
}
bool cmp(const pair<int, vector<int>>&a, const pair<int, vector<int>>&b)
{
	return a.first < b.first;
}
int main(void)
{
	int cityNum, edgeNum, s, t;
	cin >> cityNum >> edgeNum >> s >> t;
	vector<vertexNode> v(cityNum);
	for (int i = 0; i < edgeNum; i++)
	{
		int a, b, d, w;
		scanf("%d %d %d %d", &a, &b, &d, &w);
		v[a].nb.push_back(neighbor(b, w, d));
		v[b].nb.push_back(neighbor(a, w, d));
	}

	v[s].visited = true;
	v[s].dist = 0;

	while (1)
	{
		int p = -1;
		for (int i = 0; i < v.size(); i++)
		{
			if (p == -1 && v[i].visited && !v[i].sured)
				p = i;
			else if (p != -1 && v[i].visited && !v[i].sured && v[p].dist > v[i].dist)
				p = i;
		}
		if (p == -1) break;
		v[p].sured = true;
		if (v[t].sured) break;
		for (int i = 0; i < v[p].nb.size(); i++)
		{
			int q = v[p].nb[i].idx;//获取邻居的编号
			if (!v[q].sured && v[q].dist > v[p].dist + v[p].nb[i].dist)
			{
				v[q].visited = true;
				v[q].dist = v[p].dist + v[p].nb[i].dist;
			}
		}
	}
	int minDist = v[t].dist;
	vector<int> path(0);
	path.push_back(s);
	vector < pair<int, vector<int>>> ans(0);
	vector<bool> used(cityNum, false);
	dfs(s, t, 0, minDist, 0, path, ans, v, used);
	sort(ans.begin(), ans.end(), cmp);
	for (int i = 0; i < ans[0].second.size(); i++)
	{
		cout << ans[0].second[i] << " ";
	}
	cout << minDist << " " << ans[0].first;
	return 0;
}

1029. Median (25)

1.求两个已经排好序的数组的中位数

2.这道题目与leetcode中的Median of Two Sorted Arrays相似,只是偶数情况取前一个,不用求平均

3.采用二分法进行查找。

数组分为如下部分:

{a[0],a[1],a[2],….a[i-1]  |   a[i],a[i+1],…a[m-1]}
{b[0],b[1],b[2],….b[j-1]  |   b[j],b[j+1],…b[n-1]}

然后根据a[i-1]与b[j]、a[i]与b[j-1]的大小,进行二分查找。

4.注意边界条件,可以看代码的注释。

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

Input

Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (<=1000000) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output

For each test case you should output the median of the two given sequences in a line.

Sample Input

4 11 12 13 14
5 9 10 15 16 17

Sample Output

13

AC代码:

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
/*
0
0

1 100
0

0
1 100

1 10
1 100

1 10
2 20 30

2 10 20
2 30 40

3 10 20 30
3 40 50 60

4 10 20 30 70
4 40 50 60 80

3 10 20 30
4 40 50 60 80

2 3 4
0

*/

/*
{a[0],a[1],a[2],....a[i-1]  |   a[i],a[i+1],...a[m-1]}
{b[0],b[1],b[2],....b[j-1]  |   b[j],b[j+1],...b[n-1]}

*/
int findMedianSortedArrays(int *nums1, int*nums2,int m,int n) {

	if (m>n) return findMedianSortedArrays(nums2, nums1,n,m);
	int minIdx = 0, maxIdx = m;//第一个数组的范围
	int i, j;//两个数组的下标
	int num1, num2;
	int mid = (m + n + 1) >> 1;//为什么+1
	while (minIdx <= maxIdx)
	{
		i = (minIdx + maxIdx) >> 1;//取中间值
		j = mid - i;
		if (i<m && j>0 && nums2[j - 1] > nums1[i]) 
			minIdx = i + 1;
		else if (i>0 && j<n && nums2[j] < nums1[i - 1]) 
			maxIdx = i - 1;
		else
		{
			if (i == 0) num1 = nums2[j - 1];
			else if (j == 0) num1 = nums1[i - 1];
			else num1 = max(nums1[i - 1], nums2[j - 1]);
			break;
		}
	}
	return num1;
}

int main(void)
{
	int m, n;
	scanf("%d", &m);
	int *nums1 = new int[m];
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &nums1[i]);
	}
	scanf("%d", &n);
	int *nums2 = new int[n];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &nums2[i]);
	}
	//cout << findMedianSortedArrays(nums1, nums2, m, n) << endl;

	int *a, *b;

	if (m > n)
	{
		a = nums2;
		b = nums1;
		swap(m, n);
	}
	else
	{
		a = nums1;
		b = nums2;
	}
	/*
	{a[0],a[1],a[2],....a[i-1]  |   a[i],a[i+1],...a[m-1]}
	{b[0],b[1],b[2],....b[j-1]  |   b[j],b[j+1],...b[n-1]}
	*/
	int ans = INT_MIN;
	bool getAns = false;
	int l = 0, r = m;//必须是r=m,数组a是长度较小的一个,假如长度为0,那么m-1=-1,下面会直接出错
	int i = (l + r) / 2;
	int j = (m + n + 1) / 2 - i;
	while (l <= r)//同理,假如m==0,至少确保循环执行了一次
	{
		i = (l + r) / 2;//假如m为0,i为0
		j = (m + n + 1) / 2 - i;//+1很重要
		if (i > 0 && j<n && a[i - 1]>b[j])
			r = i - 1;
		else if (j > 0 && i<m && b[j - 1]>a[i])
			l = i + 1;
		else
		{
			if (i == 0)
				ans = b[j - 1];
			else if (j == 0)
				ans = a[i - 1];
			else
				ans = max(a[i - 1], b[j - 1]);
			break;
		}
	}
	cout << ans << endl;

	return 0;
}

1028. List Sorting (25)

1.根据要求,分别按照ID,姓名,分数排名。

2.这道题目使用C++的cin和cout均会超时;

3.需要使用scanf输入,printf输出;

4.使用char[]存储ID和name,使用strcmp进行比较,strcmp(a,b),当a<b,strcmp(a,b)<0;当a==b,strcmp(a,b)==0;当a>b,strcmp(a,b)>0

下面截图为部分实验结果:

1)程序仅执行cin输入数据,可以看出使用cin仅输入就耗费了137ms

2)程序仅执行cin和cout,最后一个测试点已经出现超时

3)最后使用scanf,printf,能够AC

时间限制
200 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

Excel can sort records according to any column. Now you are supposed to imitate this function.

Input

Each input file contains one test case. For each case, the first line contains two integers N (<=100000) and C, where N is the number of records and C is the column that you are supposed to sort the records with. Then N lines follow, each contains a record of a student. A student’s record consists of his or her distinct ID (a 6-digit number), name (a string with no more than 8 characters without space), and grade (an integer between 0 and 100, inclusive).

Output

For each test case, output the sorting result in N lines. That is, if C = 1 then the records must be sorted in increasing order according to ID’s; if C = 2 then the records must be sorted in non-decreasing order according to names; and if C = 3 then the records must be sorted in non-decreasing order according to grades. If there are several students who have the same name or grade, they must be sorted according to their ID’s in increasing order.

Sample Input 1

3 1
000007 James 85
000010 Amy 90
000001 Zoe 60

Sample Output 1

000001 Zoe 60
000007 James 85
000010 Amy 90

Sample Input 2

4 2
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 98

Sample Output 2

000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60

Sample Input 3

4 3
000007 James 85
000010 Amy 90
000001 Zoe 60
000002 James 90

Sample Output 3

000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90

 
AC代码:

//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
int check;
struct studentNode{
	char id[7], name[8];
	int grade;
};
bool cmpID(const studentNode&a, const studentNode&b)
{
	return strcmp(a.id,b.id)<0;
}
bool cmpName(const studentNode&a, const studentNode&b)
{
	if (strcmp(a.name, b.name)<0) return true;
	else if (strcmp(a.name, b.name) == 0 && strcmp(a.id, b.id)<0) return true;
	else return false;
}
bool cmpGrade(const studentNode&a, const studentNode&b)
{
	if (a.grade < b.grade) return true;
	else if (a.grade == b.grade && strcmp(a.id, b.id)<0) return true;
	else return false;
}
bool cmp(const studentNode&a, const studentNode&b)
{
	if (check == 1)
		return cmpID(a, b);
	else if (check == 2)
		return cmpName(a, b);
	else return cmpGrade(a, b);
}

int main(void)
{
	int studentSum;
	cin >> studentSum >> check;
	studentNode *student=new studentNode[studentSum];
	for (int i = 0; i < studentSum; i++)
	{//scanf 输入char
		scanf("%s %s %d", &student[i].id, student[i].name, &student[i].grade);
	}
	sort(student, student + studentSum, cmp);
	for (int i = 0; i < studentSum;i++)
	{
		printf("%s %s %d\n", student[i].id, student[i].name, student[i].grade);
	}
	return 0;
}

1027. Colors in Mars (20)

1.给出RGB十进制颜色,求出其13进制颜色,主要涉及到进制的转换,10进制到13进制。

2.处理0和个位数,前面需要补0。

3.可以自行输出0~168检测函数的鲁棒性。

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

People in Mars represent the colors in their computers in a similar way as the Earth people. That is, a color is represented by a 6-digit number, where the first 2 digits are for Red, the middle 2 digits for Green, and the last 2 digits for Blue. The only difference is that they use radix 13 (0-9 and A-C) instead of 16. Now given a color in three decimal numbers (each between 0 and 168), you are supposed to output their Mars RGB values.

Input

Each input file contains one test case which occupies a line containing the three decimal color values.

Output

For each test case you should output the Mars RGB value in the following format: first output “#”, then followed by a 6-digit number where all the English characters must be upper-cased. If a single color is only 1-digit long, you must print a “0” to the left.

Sample Input

15 43 71

Sample Output

#123456
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
string int2str(int a)
{
	char c;
	if (a >= 0 && a <= 9)
		c = a + '0';
	else
		c = a - 10 + 'A';
	string ans = "";
	ans += c;
	return ans;
}
string dec213(int a)
{
	if (a == 0) return "00";
	string ans = "";
	while (a != 0)
	{
		ans += int2str(a % 13);
		a /= 13;
	}
	for (int i = 0; i < ans.size() / 2; i++)
		swap(ans[i], ans[ans.size() - 1 - i]);
	if (ans.size() == 1) ans = '0' + ans;
	return ans;
}
int main(void)
{
	int r, g, b;
	cin >> r >> g >> b;
	cout << "#" << dec213(r) << dec213(g) << dec213(b) << endl;
	return 0;
}