12-11 哈理工团体新生赛

自用笔记算法

哈理工团体新生赛

Time

Problem Description
Kim是一个掌控时间的大师。不同于一般人，他习惯使用秒来计算时间。如果你问他现在是几点，他会告诉你现在是今天的xxxx秒。Mik想要考考Kim。他想知道从某一天的
00:00:00开始，经过s秒后是哪一天。但是Mik不会计算答案，他需要你的帮助。
注意：我们认为一天从00:00:00开始，到23:59:59结束。00:00:00经过1秒后是00:00:01；从00:00:00开始，加86400（606024）秒后就是下一天的00:00:00.

Input

第一行一个整数T表示数据组数。
接下来T行，每行一个日期yyyy-MM-dd，接下来一个整数s表示s秒。

Output
对于每个输入，输出一行yyyy-MM-dd 表示答案。对于不足两位的数要补齐前导0。

Sample Input
3
2016-12-10 1000
2016-02-28 86400
2016-01-01 1000000

Sample Output
2016-12-10
2016-02-29
2016-01-12

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<string>
using namespace std;
int Month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int check(int year)
{
	if(year%4==0&&(year%400==0||year%100!=0))
		return 1;
	return 0;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string s;
		long long int year,month,day,second,se;
		cin>>s>>second;
		year=(s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+s[3]-'0';
		month=(s[5]-'0')*10+s[6]-'0';
		day=(s[8]-'0')*10+s[9]-'0';
		se=second/86400;
		day+=se;
		if(check(year))
			Month[2]=29;
		if(day>Month[month])
		{
			day-=Month[month];
			month++;
			if(month>=13)
			{
				year++;
				month=1;
				if(check(year))
					Month[2]=29;
			}
		}
		printf("%lld-%02lld-%02lld\n",year,month,day);
	}
}

思路

简单模拟。
注意闰年的处理以及输出补0。

ID

Problem Description
It is very cold in Harbin in the winter, but it is pretty warm in the Zhengxin Building. Today is Saturday, Teacher ABG want to play a trick on the only
one student called NWL because he didn’t finish the MOOC.
At the beginning, every student is in the building. The teacher calls some students to sweep the snow on the playground out of the building, and
sometimes he also call some students who are on the playground back to the building. At last, teacher ABG wants to leave only one student, NWL, on the
playground out of the building. It means that the teacher ABG calls NWL’s ID ODD times, but called other students’ ID EVEN times, maybe more than twice.
Now give you the list describing the students’ ID which the teacher called in order, please tell us NWL’s ID.

Input
The first line is an integer T, describes the number of tests. Then T tests.
In each test, the first line is an integer N, describes the number of IDs on the list.
Then followed N lines, each line contains an integer M, describes one ID on the list.

Output
T lines. Each line, an integer, the NWL’s ID.

Sample Input
3
3
1140310000
1140310000
1140310000
1
1140310002
5
1
2
2
2
2

Sample Output
1140310000
1140310002
1

题目要求

求出数组中出现次数为奇数次（一次）的数字，其余数字出现偶数次。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
int main()
{
	int T;
	cin>>T;
	long long temp,ans;
	while(T--)
	{
		int N;
		cin>>N;
		N--;
		cin>>temp;
		ans=temp;
		while(N--)
		{
			cin>>temp;
			ans^=temp;
		}
		cout<<ans<<endl;
	}
	return 0;
}

思路

经典算法，考察异或运算。
求数组中出现奇数次（一次），或数组中唯一两个出现1次的数字，均可用异或操作。

Game

Problem Description
Kim is a college student who love computer games, but unfortunately his school just published a rule that Games should disappear in the campus
, that means nobody can play computer games in school, including the students dormitory. However, the student don’t take it seriously, that’s
why the manager of the school gets so angry that he decided to go to the dormitory to punish the students. You should know the manager will
punish those students who is playing games at the moment he enter the room, and leave immediately if nobody is playing game in this room.
Kim is a talented game player , in fact, he is the Carry of a famous Gaming club, so he needs time to practice he’s skills . And luckily ,
Kim’s roommate Mik is a Geek(also a Kim fan), he hacked the manager’s computer and get the timetable of the manager, and tell Kim when will
the manager come to their room tomorrow. A big E-sport Event is around the corner, so Kim list m skills he should practice, each skill takes
some time to practice and improve Kim’s skill by some points. You should calculate the max total improvement points Kim can get. Note any
skills can be practiced any times , including 0.

Input
The first line contains a integer T ( T <= 10 ), then T cases follows.
In each case, there are 3 parts of input.
The first part contains 3 integers L, n, m in a single line.Range[0, L] is the time Kim decide to practice , n is the times manager would enter his room,
m indicate the total number of the skills.
The second part contains n integers ti(0 <= ti <= L) in a single line, means the manager would enter his room at ti. Note that ti is giving in the
increasing order.
The third part has m lines , each line contains two integers ci, vi, means this skill needs ci minutes to practice and can make vi points improvement.
L<=500, n<=10, m<=100.

Output
For each case, you should output the max points Kim can improve.

Sample Input
2
6 1 3
3
2 3
2 4
2 5
6 2 3
2 4
2 3
2 4
2 5

Sample Output
10
15

题目要求

分段背包问题。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<cstring>
using namespace std;
int cost[555],value[555];
int num[555];
int f[555];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int l,m,n;
		cin>>l>>m>>n;
		for(int i=1;i<=m;i++)
			cin>>num[i];
		for(int i=1;i<=n;i++)
			cin>>cost[i]>>value[i];
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)
			for(int j=0;j<=l;j++)
				if(j-cost[i]>=0)
					f[j]=max(f[j],f[j-cost[i]]+value[i]);
		int ans=0;
		for(int i=1;i<=m;i++)
			ans+=f[num[i]-num[i-1]];
		if(num[m]<l)
			ans+=f[l-num[m]];
		cout<<ans<<endl;
	}
	return 0;
}

思路

完全背包的变形。
分段后把每一段的最大值求和即可。

Mod

Problem Description
Kim刚刚学会C语言中的取模运算（mod）。他想要研究一下一个数字A模上一系列数后的结果是多少。帮他写个程序验证一下。

Input
第一行一个整数T代表数据组数。
接下来T组数据，第一行一个整数n，接下来n个数字ai
接下来一行一个整数m，接下来m个数字bi

Output
对于每个bi，输出bi%a1%a2%…%an 。

Sample Input
1
4
10 9 5 7
5
14 8 27 11 25

Sample Output
4
3
2
1
0

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
using namespace std;
struct node
{
	int data,jump;
}no[100050];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&no[i].data);
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
			{
				if(no[j].data<=no[i].data)
				{
					no[i].jump=j;
					break;
				}
			}
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			int qu;
			scanf("%d",&qu);
			for(int j=1;j<=n;j=no[j].jump)
			{
				if(j==0)
					break;
				qu%=no[j].data;
			}
			printf("%d\n",qu);
		}
	}
	return 0;
}

思路

连续求余问题。
求出每个数字后边第一个比它小的数的位置。跳着取余即可。

Number Game

Problem Description
There are n items and two players, Kim and you. For each player and for each item, the value of the item for this player is known. Denote values of the
i-th item for the first and the second player as ai and bi correspondingly.
Players take the items in turns. Kim starts the game. Kim is greedy: each turn, he chooses the item which has the maximal ai among the remaining items.
If there are several such items, he can take any one of them. What is the maximal possible sum of values bi of items taken by the second player that he
can guarantee regardless of the first player’s moves?

Input
The first line is an integer T, describes the number of tests. Then T tests.
Each case contains a single integer n, the number of items.
The second line contains n numbers, i-th is equal to ai, the value of the i-th item for Kim.
The third line contains n numbers, i-th is equal to bi, the value of the i-th item for the second player.

Output
Output a single number: the maximal sum of values bi of items taken by the second player that he can guarantee.

Sample Input
1
5
1 2 3 4 5
2 3 4 5 6

Sample Output
8

题目要求

a跟b玩游戏，每个物品对a,b分别有价值。a每次会去对价值最高 且 对b价值较高的(第二关键字)。求b能取到最大价值。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;
struct node
{
	int x,y;
}data[1050];
struct cmp
{
	bool operator() (const int a,const int b)
	{
		return a>b;
	}
};
bool cmp2(node a,node b)
{
	if(a.x==b.x)
		return a.y>b.y;
	return a.x>b.x;
}
priority_queue<int,vector<int>,cmp>q;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>data[i].x;
		for(int i=1;i<=n;i++)
			cin>>data[i].y;
		while(!q.empty())
			q.pop();
		sort(data+1,data+1+n,cmp2);
		LL ans=0;
		for(int i=2;i<=n;i++)
		{
			if(!(i&1))
				q.push(data[i].y);
			else if(data[i].y>q.top())
			{
				q.pop();
				q.push(data[i].y);
			}
		}
		while(!q.empty())
		{
			ans+=q.top();
			q.pop();
		}
		cout<<ans<<endl;
	}
	return 0;
}

思路

优先队列。
先进行一次多关键字排序。
往后每次，如果可以用当前的bi换下下一个被拿走的bi使和变大，那就交换。否则取最大的。

Permutation

Problem Description
n个人排成一队，队头的人编号为1，后面的人编号分别为2,3,…,n. 1号人前面没有人，i号人的前面是i-1。 现在Kim想让这n个人重新排队，要求重新排队后编号为i的人前面不能
是i-1。问有多少种排队的方法。方案数可能很大，输出答案模1e9+7。

Input
第一行一个整数T，表示有T组数据。
接下来T行，每行一个整数n。表示有n个人排成一队。

Output
对于每个n，输出答案 mod 1000000007。

Sample Input
2
1
4

Sample Output
1
11

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#define LL long long
using namespace std;
LL f[2222222];
const LL base = 1000000007;
int main(){
	f[1]=1;f[2]=1;f[3]=3;
	for(LL i=4;i<=2000000;i++){
		f[i]=(i * (f[i-1]%base) % base - (i-3) * (f[i-3]%base) %base + base )%base; 
	}
	int T,n;
	cin>>T;
	while(T--){
		scanf("%d",&n);
		cout<<f[n]<<endl;
	}
	return 0;
}

思路

容斥原理，推出f[i] = if[i-1] - (i-3)f[i-3]

Team

Problem Description
Kim 正在玩一款手游，在这款游戏中，Kim可以选择若干个角色编成一队作战。为了挑战不同的关卡，Kim需要不断的调整编队阵容。然而随着游戏不断更新，队伍成员变得越
来越多，Kim已经记不清哪些角色在队伍中，哪些角色不在队伍中了。请你写一个程序来帮助他。
具体来说，Kim有三种可以执行的操作。
1 x ：把 x 号角色加入队伍。如果x号角色已经在队伍中，什么都不会发生。
2 x ：把 x 号角色从队伍中移除。如果x号角色不在队伍中，什么都不会发生。
3 x ：撤销第x次操作。如果第x次操作已经被撤销，什么都不会发生。
每次操作有一个编号，从1开始。对于3 x操作，第x次操作会被撤销。被撤销的操作相当于没有进行这次操作。
Kim可能撤销一次插入，撤销一次删除，或撤销另一次撤销操作。
现在请你告诉Kim所有操作都结束后，队伍中有几个角色，都是谁。

Input
第一行一个整数T，表示有T组数据。
每组数据第一行两个整数n,m表示一共有n个角色（编号1-n）,m个操作。
初始队伍中没有角色。
接下来m行，每行一个操作，格式为
1 x 或 2 x 或 3 x,含义见题目描述。
操作的编号等价于给出操作的顺序。第一个给出的操作是1号，第二个给出的操作是2号，以此类推。
对于3 x 操作，保证 x 小于 这条操作的编号。

Output
对于每组数据，输出两行。
第一行一个整数n,表示最后队伍中有n个人。
接下来一行n个整数，表示队伍中角色的编号，角色编号按照从小到大的顺序输出。
（每个编号后面有一个空格，包括最后一个编号。如果第一行n为0，则第二行为一个空行，即没有编号，只有一个换行符）

Sample Input
1
5 8
1 1
1 2
3 2
1 4
3 3
3 5
1 5
2 5

Sample Output
2
1 4

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstring>
using namespace std;
#define max 50050
int succ[max],info[max][3];
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		memset(succ,0,sizeof(succ));
		for(int i=1;i<=m;i++)
		{
			cin>>info[i][0]>>info[i][1];
			info[i][2]=1;
		}
		for(int i=m;i>0;i--)
		{
			if(info[i][2]==0)
				continue;
			if(info[i][0]==3)
				info[info[i][1]][2]=0;
		}
		for(int i=1;i<=m;i++)
		{
			if(info[i][2]==0)
				continue;
			if(info[i][0]==1)
				succ[info[i][1]]=1;
			if(info[i][0]==2)
				succ[info[i][1]]=0;
		}
		int sum=0;
		for(int i=1;i<=n;i++)
			if(succ[i]==1)
				sum++;
		cout<<sum<<endl;
		for(int i=1;i<=n;i++)
			if(succ[i]==1)
				cout<<i<<" ";
		cout<<endl;
	}
	return 0;
}

思路

模拟
注意info和succ数组的用途。

Emirp

Problem Description
An emirp (prime spelled backwards) is a prime number that results in a different prime when its decimal digits are reversed.
The first five emirps are 13, 17, 31, 37, 71
Now Kim want to know the kth emirp. Help him.

Input
The first line is an integer T, describes the number of tests. Then T tests.
In each test, one line an integer k.

Output
For each test, output the kth emirp.

Sample Input
3
1
2
3

Sample Output
13
17
31

题目要求

求出第n个反素数。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
LL re[1005];
int isprime(LL num)
{
	if(num==0||num==1)
		return 0;
	for(int i=2;i*i<=num;i++)
		if(num%i==0)
			return 0;
	return 1;
}
LL transform(LL num)
{
	LL res=0;
	while(num>0)
	{
		res=res*10+num%10;
		num/=10;
	}
	return res;
}
void excell()
{
	int i=1;
	LL x=13;
	while(i<=1005)
	{
		if(isprime(x)&&isprime(transform(x))&&x!=transform(x))
			re[i++]=x;
		x++;
	}
}
int main()
{
	excell();
	int t;
	cin>>t;
	while(t--)
	{
		int k;
		cin>>k;
		cout<<re[k]<<endl;
	}
	return 0;
}

思路

反素数：原本是质数，取反后仍是质数，且不是回文。
暴力打表即可。

本文标题:12-11 哈理工团体新生赛

文章作者:Hippopmonkey

发布时间:2016-12-11, 21:06:52

最后更新:2016-12-11, 21:35:58

原始链接:http://xuboming8.github.io/2016/12/11/12-11-哈理工团体新生赛/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 哈理工团体新生赛
    1. 1.1. Time
      1. 1.1.1. 参考AC代码
      2. 1.1.2. 思路
    2. 1.2. ID
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. Game
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. Mod
      1. 1.4.1. 参考AC代码
      2. 1.4.2. 思路
    5. 1.5. Number Game
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. Permutation
      1. 1.6.1. 参考AC代码
      2. 1.6.2. 思路
    7. 1.7. Team
      1. 1.7.1. 参考AC代码
      2. 1.7.2. 思路
    8. 1.8. Emirp
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
|