SRM 706 div 2

发表于 | 更新于

p1

Bear Limak has three boxes arranged in a row. The first box currently contains a candies, the second one contains b candies, and the third one contains c candies. Limak thinks that the three boxes would look nice if they had the following two properties: Each box should contain at least one candy. The numbers of candies should form a strictly increasing sequence. In other words, the first box should contain fewer candies than the second box, and the second box should contain fewer candies than the third one. Limak can only modify the current content of the boxes in one way: he can eat some of the candies. You are given the ints a, b, and c. Compute and return the smallest possible number of candies Limak should eat in order to make his three boxes look nice. If he has no way to make his boxes look nice, return -1 instead.

Code

1
2
3
4
5
6
7
8
9
10
11
12
struct ThreeIncreasing
{
public:
	int minEaten(int a,int b,int c)
	{
		int res=0;
		if(b>=c) res+=b-c+1,b-=b-c+1;
		if(a>=b) res+=a-b+1,a-=a-b+1;
		if(a<1 || b<1) res=-1;
		return res;
	}
};

p2

Little Limak wants to show his parents that he's responsible and independent. He decided to move out and live on his own, at least for some time. While living alone, he has to eat every day. Living alone comes with some other expenses as well. More precisely, Limak will eat 1 fruit and spend x dollars each day he lives on his own. Currently Limak has f fruits and d dollars. Limak can buy more pieces of fruit in the local store. The store sells 1 fruit for p dollars, and Limak can purchase arbitrarily many pieces of fruit there. You are given the ints x, f, d, and p. Compute and return the largest possible number of days Limak can live on his own.

Code

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll;
class SellingFruits
{
public:
	int maxDays(ll x,ll f,ll d,ll p)
	{
		int res;
		if(x!=0 && d/x<=f) res=d/x;
		else res=(d+p*f)/(x+p);
		return res;
	}
};

p3

The lotteries you know are probably quite boring. You just buy a lottery ticket with some numbers and then you hope that the organizers announce the same set of numbers. As you will discover below, the lottery in Bearland is way more fun! In the Bearland lottery, you win if you have a ticket that matches the goal string. The goal string is a string of length N chosen by the organizers. Each character of the string will be 'A', 'B', or 'C'. Additionally, it is guaranteed that the goal string will contain "ABC" as a subsequence. For example, "AABAC" and "BBABC" are two possible goal strings of length 5, but "CBAAA" is not a goal string. However, the lottery tickets do not contain any strings at all. Instead, each Bearland lottery ticket contains some sequence of N (not necessarily distinct) integers. You win the lottery if you can transform your sequence into the goal string. Transformation rules: Each element of the sequence should be replaced by a single character: 'A', 'B', or 'C'. All occurrences of the same number must be replaced by the same letter. For example, the sequence {5, 8, 5, 2} can be transformed into "ABAC" or "BABB" but not into "ABBB". Limak got a lottery ticket for his birthday. You are given the vector t: the sequence of the N numbers on the the ticket. Count the number of different goal strings for which Limak can win the lottery. Return that count modulo 10^9+7.

Solution

好吧这就不会做了，，太弱了，一开始还把题都看错了。。 对一个数字序列，相同的数字替换成A,B,C中相同的字母，问有多少种方案可以让产生的字符串中含有子序列A...B...C。 首先枚举三个不相同的a[i],a[j],a[k]，考虑钦定这三个分别为A,B,C对答案能产生的贡献。 对于x..x..x..y.y...z...zz这种情况好说，只要确保当前枚举的x1,y1,z1是同类数字中的第一个，即x1之前没有x，x1与y1之间没有y，依次类推。

那对于ijkxyz ixjkyz之类的情况，可能换出ABCABC AABCBC，只能算一次。这样就限定当前枚举的ABC左边不存在ABC，就可以了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using std::vector;
using std::sort;
using std::unique;
using std::lower_bound;
using std::set;

const int P=1e9+7;
const int MAXN=100;
#define iter(x) typeof((x).begin())
typedef long long ll;
class MappingABC2
{
public:
	int countStrings(vector <int> t)
	{
		static int a[MAXN],b[MAXN];
		int n=t.size();
		if(n<3) return 0;
		ll res=0;
		for(int i=0;i<n;++i)
			a[i+1]=b[i+1]=t[i];
		sort(b+1,b+1+n);int cc=unique(b+1,b+1+n)-b-1;
		for(int i=1;i<=n;i++)
			a[i]=lower_bound(b+1,b+1+cc,a[i])-b;
		#define differ(x,y,z) (x!=y && x!=z && y!=z)
		set<int> kcnt[MAXN];
		for(int i=1;i<=n-2;i++)
		{
			for(int j=i+1;j<=n-1;j++)
			{
				for(int k=j+1;k<=n;k++)
				{
					if(!differ(a[i],a[j],a[k])) continue;
					for(int c=1;c<=cc;++c) kcnt[c].clear();
					ll temp=1;
					for(int p=1;p<=n;p++)
					{
						if(p<i) kcnt[a[p]].insert(1);
						if(i<p && p<j) kcnt[a[p]].insert(2);
						if(j<p && p<k) kcnt[a[p]].insert(3);
					}
					if(kcnt[a[i]].count(1) || kcnt[a[j]].count(2) || kcnt[a[k]].count(3))
						continue;
					for(int c=1;c<=cc;++c)
					{
						if(a[i]==c || a[j]==c || a[k]==c) continue;
						(temp*=(3-kcnt[c].size()))%=P;
					}
					(res+=temp)%=P;
				}
			}
		}
		((res%=P)+=P)%=P;
		return (int)res;
	}
};