Vjudge刷题记录

发表于 | 分类于 |
字数统计: 2.5k | 阅读时长 ≈ 12

Vjudge刷题记录

以后从新开始每天在vjudge上每天刷一题，最开始会做些简单的找找感觉。
这里记录做题的思路以及学习到的东西。

热血格斗场

蒜头君新开了一家热血格斗场。格斗场实行会员制，但是新来的会员不需要交入会费，而只要同一名老会员打一场表演赛，证明自己的实力。

我们假设格斗的实力可以用一个正整数表示，成为实力值。另外，每个人都有一个唯一的
id
，也是一个正整数。为了使得比赛更好看，每一个新队员都会选择与他实力最为接近的人比赛，即比赛双方的实力值之差的绝对值越小越好，如果有两个人的实力值与他差别相同，则他会选择比他弱的那个（显然，虐人必被虐好）。

不幸的是，蒜头君一不小心把比赛记录弄丢了，但是他还保留着会员的注册记录。现在请你帮蒜头君恢复比赛纪录，按照时间顺序依次输出每场比赛双方的
id
。

输入格式第一行一个数 n(0<n≤100000)，表示格斗场新来的会员数（不包括蒜头君）。以后 n 行每一行两个数，
按照入会的时间给出会员的 id(2≤id≤106) 和实力值(≤109)。一开始，蒜头君就算是会员，id 为 1，
实力值 1000000000。输入保证两人的实力值不同。输出格式N 行，每行两个数，为每场比赛双方的 id，新手的 id 写在前面。

思路

map的使用

代码

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
#include<iostream>
#include<map>
using namespace std;
int main(){
	int n,a,b,ans;
	map<int,int>mp;
	map<int,int>::iterator itr;
	cin>>n;
	mp[1e9]=1;
	while(n--){
		cin>>a>>b;
		itr = mp.upper_bound(b);
		if (itr==mp.end()) {
			itr--;
			ans = itr->second;
		}else if(itr==mp.begin()){
			ans = itr->second;
		}else{
			int diff = itr->first - b;
			ans = itr->second;
			itr--;
			if((b-itr->first)<=diff){
				ans = itr->second;
			}
		}
		mp[b]=a;
		cout<<a<<' '<<ans<<endl;
	}
	return 0;
}

知识点

std::map 的底层是红黑树，是按照key有序的

std::unordered_map 的底层是哈希表，是无序的

map.lower_bound(key) 返回第一个不小于key的迭代器索引。

map.upper_bound(key) 返回第一个大于key的迭代器索引。

Neighbor House

The people of Mohammadpur have decided to paint each of their houses red, green, or blue. They have also decided that no two neighboring houses will be painted the same color. The neighbors of house i are houses i-1 and i+1. The first and last houses are not neighbors.

You will be given the information of houses. Each house will contain three integers “R G B” (quotes for clarity only), where R, G and B are the costs of painting the corresponding house red, green, and blue, respectively. Return the minimal total cost required to perform the work.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int main(){
	int n,t;
	cin>>n;
	for(int j=1;j<=n;j++){
		cin>>t;
		int dp[t][3];
		int data[t][3];
		for(int i=0; i<t ;i++){
			cin>>data[i][0]>>data[i][1]>>data[i][2];
		}
		dp[0][0]=data[0][0],dp[0][1]=data[0][1],dp[0][2]=data[0][2];
		for(int i=1;i<t;i++){
			dp[i][0]=min(dp[i-1][1],dp[i-1][2])+data[i][0];
			dp[i][1]=min(dp[i-1][2],dp[i-1][0])+data[i][1];
			dp[i][2]=min(dp[i-1][1],dp[i-1][0])+data[i][2];
		}
		cout<<"Case "<<j<<": "<<min(dp[t-1][2],min(dp[t-1][0],dp[t-1][1]))<<endl;
			
	}
	return 0;
}

Staircases

One curious child has a set of N little bricks (5 ≤ N ≤ 500). From these bricks he builds different staircases. Staircase consists of steps of different sizes in a strictly descending order. It is not allowed for staircase to have steps equal sizes. Every staircase consists of at least two steps and each step contains at least one brick.

Your task is to write a program that reads the number N and writes the only number Q — amount of different staircases that can be built from exactly N bricks.

思路

dp[i][j]表示当前使用第i块砖头时，最后一列的砖块数为j的组合数量。
dp[i][j] = sum(dp[i-j][k]) (0<=k<j)

这里为什么要用i-j而不是直接使用j呢？？
因为j是从1到i变化的，而i-j是从i-1到0变化的。 这样可以保证这一轮的dp是完全由上一轮产生的。

代码

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
#include<iostream>
#define maxn 510
using namespace std;
int main(){
	int dp[maxn][maxn],n;
	dp[0][0]=1;
	for(int i=1; i<maxn; i++){
		for(int j=1; j<=i; j++){
			for(int k=0; k<j; k++){
				dp[i][j]+=dp[i-j][k];
			}
			
		}
		
	}
	
	while( cin>>n ){
		long long ans=0;
		for(int i=1; i<n; i++){
			ans+=dp[n][i];
		}
		cout<<ans<<endl;
		
	}
	
	return 0;
}

优化版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<vector>
using namespace std;
int main(){
	int N;
	cin>>N;
	vector<long long> dp(N+1);
	dp[0]=1;
	for(int i=1;i<=N;i++){
		for(int j=N;j>=i;j--){
			dp[j]+=dp[j-i];
		}
	}
	cout<<dp[N]-1<<endl;
	return 0;
}

解释

这里我也没搞懂为什么可以这样写。

感觉像是通过和背包问题中相似的优化减少了一维。

Basketball Exercise

Finally, a basketball court has been opened in SIS, so Demid has decided to hold a basketball exercise session. 2⋅n students have come to Demids exercise session, and he lined up them into two rows of the same size (there are exactly n people in each row). Students are numbered from 1 to n in each row in order from left to right.

Now Demid wants to choose a team to play basketball. He will choose players from left to right, and the index of each chosen player (excluding the first one taken) will be strictly greater than the index of the previously chosen player. To avoid giving preference to one of the rows, Demid chooses students in such a way that no consecutive chosen students belong to the same row. The first student can be chosen among all 2n students (there are no additional constraints), and a team can consist of any number of students.

Demid thinks, that in order to compose a perfect team, he should choose students in such a way, that the total height of all chosen students is maximum possible. Help Demid to find the maximum possible total height of players in a team he can choose.

2*n的数组从左往右选不能选择相邻的两个数，求最终能选择的最大和。

思路

dp[i][0]表示这一列选择第一个的最大值。

dp[i][1]表示这一列选择第二个的最大值。

dp[i][2]表示这一列都不选的最大值。

有状态转移方程

dp[i][0]=max(dp[i-1][1],dp[i-1][2])+data[i][0];

dp[i][1]=max(dp[i-1][0],dp[i-1][2])+data[i][1];

dp[i][2]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));

代码

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
#include<iostream>
#define maxn 100008
using namespace std;

int main(){
	int n;
	int data[maxn][2];
	long long dp[maxn][3];
	while(cin>>n){
		for(int i=0; i<n; i++){
			cin>>data[i][0];
		}
		for(int i=0; i<n; i++){
			cin>>data[i][1];
		}
		dp[0][0]=data[0][0];
		dp[0][1]=data[0][1];
		dp[0][2]=0;

		for(int i=1; i<n; i++){
			dp[i][0]=max(dp[i-1][1],dp[i-1][2])+data[i][0];
			dp[i][1]=max(dp[i-1][0],dp[i-1][2])+data[i][1];
			dp[i][2]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));

		}

		cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;

		
		
	}
	return 0;
}

Gargari and Permutations

Gargari got bored to play with the bishops and now, after solving the problem about them, he is trying to do math homework. In a math book he have found k permutations. Each of them consists of numbers 1, 2, …, n in some order. Now he should find the length of the longest common subsequence of these permutations. Can you help Gargari?

思路

dp[i]表示到data[0][i]为止所能达到的最长公共子序列。

那么训练j 0->i 如果data[0][j]在其余序列中的位置都在data[0][i]之前，那是不是说明dp[i]能在dp[j]上扩展一位。

代码

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
#include<iostream>
#include<cstring>
#define maxn 1004
#define maxk 5
using namespace std;
int main(){
	int n,k;
	int data[maxk][maxn];
	int pos[maxk][maxn];
	int dp[maxn];
	cin>>n>>k;
	memset(dp, 0, sizeof(dp));
	for(int i=0; i<k; i++){
		for(int j=0; j<n; j++){
			cin>>data[i][j];
			pos[i][data[i][j]]=j;
		}
	}
	dp[0]=1;	
	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++){
			bool Flag=false;
			for(int p=1; p<k; p++){
				if (pos[p][data[0][j]]>pos[p][data[0][i]]) {
					Flag=true;
				}	
			}
			if (!Flag) {
				dp[i]=max(dp[i],dp[j]+1);
			}
		}
		if(!dp[i]) dp[i]=1;
		
	}
	int ans=dp[0];
	for(int i=1; i<n; i++){
		ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	
	return 0;
}

Checkout Assistant

Bob came to a cash & carry store, put n items into his trolley, and went to the checkout counter to pay. Each item is described by its price ci and time ti in seconds that a checkout assistant spends on this item. While the checkout assistant is occupied with some item, Bob can steal some other items from his trolley. To steal one item Bob needs exactly 1 second. What is the minimum amount of money that Bob will have to pay to the checkout assistant? Remember, please, that it is Bob, who determines the order of items for the checkout assistant.

思路

这里不需要考虑我结了那些，逃了那些，只要保证我结账的物品能够逃掉所有物品就行了。

转化为01背包问题也就是，我每件物品的花费为pi,然后我能清算掉ti+1件物品

这里要注意的是这里我们需要的是最终的价值大于等于背包容量，而不是小于等于所以当剩余背包容量不足的时候，也就是j<data[i][0]的时候也需要将话费加入进来。 也就是dp[j]=data[i][1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#define maxn 2005
using namespace std;
int main() {
  int n;
  int data[maxn][2];
  long long dp[maxn];
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> data[i][0] >> data[i][1];
    data[i][0]++;
    dp[i] = 1e18;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = n; j >= 1; j--) {
      dp[j] = min(dp[j], dp[max(j - data[i][0],0)] + data[i][1]);
    }
  }
  cout << dp[n] << endl;
  return 0;
}

0%