Problem Statement
A string S is a subsequence of a string T if we can obtain S from T by erasing some (possibly all or none) of its characters. For example, “000” is a subsequence of “01010”. The longest common subsequence (LCS) of two strings A and B is a string C that is a subsequence of each of them and has the largest length among all strings with this property. Let f(A,B) be the length of the LCS of strings A and B. For example, we have f(“101”, “111000”) = 2, f(“101”, “110011”) = 3, and f(“00”, “1111”) = 0. You are given three small positive integers ab, bc, and ca. Please find three strings A, B, C such that:
Each of the strings contains only the characters ‘0’ and ‘1’.
The length of each string is between 1 and 1,000, inclusive.
f(A, B) = ab
f(B, C) = bc
f(C, A) = ca
Return a string formed as follows: A + ” ” + B + ” ” + C. (I.e., the returned string should contain the three strings A, B, C, separated by single spaces.) You may assume that a solution always exist. If there are multiple solutions you may return any of them.
Definition
Class:
ConstructLCS
Method:
construct
Parameters:
int, int, int
Returns:
string
Method signature:
string construct(int ab, int bc, int ca)
(be sure your method is public)
Limits
Time limit (s):
2.000
Memory limit (MB):
256
Stack limit (MB):
256
Constraints
ab will be between 1 and 50, inclusive.
bc will be between 1 and 50, inclusive.
ca will be between 1 and 50, inclusive.
Examples
0)
3
4
2
Returns: “101 1010101 1111”
The returned string corresponds to the following solution:
A = “1111”
B = “101”
C = “1010101”
We can easily verify that the only LCS of A and B is “11”, the only LCS of B and C is “101”, and the only LCS of C and A is “1111”.
1)
7
4
4
Returns: “10101010 1010101 1011”
There are other solutions like: A = “1110000”, B = “1110000”, C = “0000”.
2)
8
7
8
Returns: “110101001011 010101101 10101010”
3)
8
6
7
Returns: “110101010 10101010 1111010”
4)
15
17
19
Returns: “000100101101111011000 11110111010011101010 100100001010101001010101000011111”
5)
50
50
50
Returns:
“11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111111”
【题目链接】:
【题意】
让你构造出3个只包含数字0和1的字符串a,b,c;
给你3个数字ab,bc,ca
表示所要求的a和b的LCS长度为ab,b和C的LCS长度为….
【题解】
找出最大的两个数字;
它所代表的两条边,必然有同时连向同一个点x;
“a、b、c分别代表3个点”
设两条边的边权从大到小分别为a1,a2
则令x+=a1个’1’;
x+=a2个’0’;
然后令a1的另一端的点所代表的字符串为a1个’1’
同时a2的另一端的点所代表的字符串为a2个’0’
然后a3的话,可以不断的在只含‘0’的那个字符串的开头一直把‘0’换成1;直到满足a3为止.
【Number Of WA】
0
【反思】
想得太慢了,没来得及交上去QAQ;
狂跌100+rating;
下次要打div2了:(
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 110;
//head
struct abc{
int idx1,idx2,num;
};
abc a[4];
int b[4];
vector <pii> g[4];
string s[4];
class ConstructLCS
{
public:
string construct(int ab, int bc, int ca)
{
rep1(i,1,3) s[i]="";
a[1].idx1 = 1,a[1].idx2 = 2,a[1].num = ab;
a[2].idx1 = 2,a[2].idx2 = 3,a[2].num = bc;
a[3].idx1 = 1,a[3].idx2 = 3,a[3].num = ca;
sort(a+1,a+1+3,[&] ( abc a ,abc b) {return a.num > b.num;});
int ma = 0;
rep1(i,1,2){
int x = a[i].idx1,y = a[i].idx2;
b[a[i].idx1]++,b[a[i].idx2]++;
ma = max(ma,a[i].num);
g[x].pb(mp(y,a[i].num)),g[y].pb(mp(x,a[i].num));
}
int mid = 1;
rep1(i,1,3){
if (b[i]>1){
mid = i;
rep1(j,1,max(g[i][0].se,g[i][1].se))
s[i]+='1';
rep1(j,1,min(g[i][0].se,g[i][1].se))
s[i]+='0';
break;
}
}
int bigger = 0,smaller = 0;
rep1(i,1,3){
if (mid==i) continue;
if (bigger==0 && ma==g[i][0].se){
rep1(j,1,ma)
s[i]+='1';
bigger = i;
}
else{
rep1(j,1,g[i][0].se)
s[i]+='0';
smaller = i;
}
}
int t = a[3].num;
int now = 0;
while (t--){
s[smaller][now++] = '1';
}
return s[1] + ' ' + s[2] + ' ' + s[3];
}
};