2 找角色
输入：
1
3 6
33 66 99
3 6 9 30 60 90
输出：
5 6 -1
输入：
1
3 6
66 33 99
3 6 9 30 60 90
输出：
6 5 -1
输入：
1
3 6
66 33 99
90 6 9 30 60 3
输出：
1 5 -1
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std
;
struct MyStruct
{
int mark
;
int num
;
};
bool cmp(MyStruct
& t1
, MyStruct
& t2
)
{
return t1
.num
< t2
.num
;
}
int main()
{
int T
; cin
>> T
;
vector
<MyStruct
> vec1
;
vector
<MyStruct
> vec2
;
vector
<MyStruct
> res
;
int n
, m
;
int tmp
;
MyStruct t
;
while (T
--)
{
vec1
.clear(); vec2
.clear(); res
.clear();
cin
>> n
>> m
;
for (int i
= 0; i
< n
; i
++)
{
cin
>> tmp
;
t
.mark
= i
;
t
.num
= tmp
;
vec1
.push_back(t
);
}
sort(vec1
.begin(), vec1
.end(),cmp
);
for (int i
= 0; i
< m
; i
++)
{
cin
>> tmp
;
t
.mark
= i
;
t
.num
= tmp
;
vec2
.push_back(t
);
}
sort(vec2
.begin(), vec2
.end(),cmp
);
for (int i
= 0, j
= 0; i
< n
; i
++)
{
if (j
>=m
)
{
t
.mark
= -1;
t
.num
= vec1
[i
].mark
;
res
.push_back(t
); continue;
}
while(vec1
[i
].num
>vec2
[j
].num
)
{
j
++;
}
t
.mark
= vec2
[j
++].mark
+1;
t
.num
= vec1
[i
].mark
;
res
.push_back(t
);
}
sort(res
.begin(), res
.end(), cmp
);
for (int i
= 0; i
< n
; i
++)
{
cout
<< res
[i
].mark
<< " ";
}
cout
<< endl
;
}
}
3 爬台阶
任意一步不能与前两步上升的台阶数相同。
输入：
7 3
输出：
2
输入：
7 4
输出：
10
"[]"内为下一步可选的台阶数，"[]"外为当前所选的台阶数
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std
;
void full_step(vector
<int>& vec
,int N
)
{
for (int i
= 0; i
< N
; i
++)
{
vec
.push_back(i
+ 1);
}
}
void backtrace(int&sum
,int pre
,int next
, vector
<int>& vec
,int &N
, int& M
, int &res
)
{
for (int i
= 0; i
< N
; i
++)
{
if (pre
== vec
[i
] || next
== vec
[i
])
{
continue;
}
sum
+= vec
[i
];
if (sum
>= M
)
{
if (sum
== M
)
{
res
++;
}
sum
-= vec
[i
];
return;
}
backtrace(sum
, next
, vec
[i
], vec
, N
, M
, res
);
sum
-= vec
[i
];
}
}
int main()
{
int M
, N
; cin
>> M
>> N
;
vector
<int> vec
;
full_step(vec
,N
);
int sum
= 0;
int res
= 0;
int pre
= N
+1, next
= N
+ 1;
backtrace(sum
, pre
, next
, vec
, N
, M
, res
);
cout
<< res
<< endl
;
return 0;
}
