题目1 : 命名
描述
有两个公司想要合并，第一个公司的名字是一个字符串S，第二个公司的名字是一个字符串T.
合并后的新公司是这样取名的：
1.先选一个S的子序列A，T的一个子序列B，要求-1 ≤ |A|-|B| ≤ 1
2.如果|A|=|B|，那么可以选择取名为A1B1A2B2..A|A|B|B|或者B1A1B2A2..B|B|A|A|，例如A=abc, B=def，则可以取名为adbecf或者daebfc.
3.如果|A|=|B|+1，那么只能取名为A1B1A2B2..A|B|B|B|A|B|+1
4.如果|B|=|A|+1，那么只能取名为B1A1B2A2..B|A|A|A|B|A|+1
现在第一个公司的老总想知道，是否存在一种取名方式，使得新的名字为S
定义字符串X是字符串Y的子序列，当且仅当X可以由Y删掉若干个位置得到。
输入
输入包含多组数据。第一行包含一个整数N，代表测试数据组数。
对于每组测试数据：
第一行一个小写字母字符串S
第二行一个小写字母字符串T
1 ≤ N ≤ 5, 1 ≤ |S|, |T| ≤ 103
输出
对于每组数据，如果存在一种取名方式使得新的名字为S的话，输出Yes，否则输出No
- 样例输入
-
3
hoge
moen
abcdefg
xacxegx
abcdef
ghijkl - 样例输出
-
Yes
Yes
No
没看清题目意思wa了两发~，题目意思其实就是从S中取一段子序列A，再从T中取一段子序列B，将AB依次各取一个字母合并成S，问存不存在这样的AB。
我们从题目中可以看出A与B的长度不会相差1，如果想要合成S，根据题目意思AB是间隔合并，也就是说如果AB想要合并成S，那么AB两个序列一定要是A的奇数下标序列和偶数下标序列，也就是说题目只需要考虑T中是不是含有A中所有奇数（或者所有偶数）下标的串。
// Asimple
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<" = "<<a<<endl
#define sysp system("pause")
using namespace std;
typedef long long ll;
const int maxn = + ;
const ll INF = <<;
ll T, n, sum, num, m, t, len, ans, k;
string s, str; void input() {
cin >> T;
while( T --) {
cin >> s >> str;
len = s.length();
string a = "", b = "";
for(int i=; i<len; i++) {
if( i% ) a = a + s[i];
else b = b + s[i];
}
int len_a = , len_b = ;
for(int i=; i<str.length(); i++) {
if( str[i] == a[len_a] && len_a < a.length() ) len_a ++;
if( str[i] == b[len_b] && len_b < b.length() ) len_b ++;
}
if( len_a==a.length() || len_b==b.length() ) cout << "Yes" << endl;
else cout << "No" << endl;
}
//sysp;
} int main() {
input();
return ;
}
题目2 : 洗牌
描述
你有一副扑克牌，里面一共有2n张牌，从上往下第 i 张牌上的数为ai.
现在定义对一副牌堆洗牌是这样的过程：
1.如果这副牌只有2张牌，交换这两张牌的顺序。
2.否则，假设这副牌有2k张牌，把牌分成上下两部分，每部分的牌的数量都是2k-1，然后分别对这两部分洗一次牌。之后把本来在下面的那部分放到本来在上面那部分的上面。
现在小 C 想知道，对一副牌洗t次后，这副牌会变成什么样。
输入
第一行两个正整数n,t
第二行2n个整数，第i个整数表示ai
2 ≤ n ≤ 10, 1 ≤ t ≤ 109, 1 ≤ ai ≤ 109
输出
输出2n行，第i行一个整数，表示洗了t次牌后从上往下第 i 张牌上的数。
- 样例输入
-
2 1
2 4 1 5 - 样例输出
-
5
1
4
2
原来这才是真的签到题，仔细看了下题目，因为题目没说牌会减少，所以每反转2次就会回到原来的样子，也就是说如果翻转的次数的奇数就反过来输出数组，偶数就直接输出数组。
// Asimple
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<" = "<<a<<endl
#define sysp system("pause")
using namespace std;
typedef long long ll;
const int maxn = + ;
const ll INF = <<;
ll T, n, sum, num, m, t, len, ans, k;
int a[maxn]; void input() {
while( cin >> n >> t ) {
len = (ll)pow(, n);
for(int i=; i<len; i++) cin >> a[i];
if( t% ) for(int i=len-; i>=; i--) cout << a[i] << endl;
else for(int i=; i<len; i++) cout << a[i] << endl;
}
//sysp;
} int main() {
input();
return ;
}
题目3 : 密码更改
描述
小 C 有一个由数字构成的密码 S，例如："123" , "3211" ,"111111"，"0123"
定义数字密码的大小为：这个数字密码代表的十进制数字的大小。
现在小 C 想改成一个更强的密码，新密码需要满足以下条件：
1.为了保证强度，每个数字在新密码中必须最多只出现一次。
2.旧密码和新密码的长度一样。
3.新密码和旧密码的距离尽量大。
4.如果有多个距离相同的，则取大小比较小的密码。
定义两个长度相同的数字密码 a , b的距离为min(|a-b|,10N-|a-b|)
其中 N 是数字密码 a,b 的长度。
例如 "012" 和 "987" 的距离为 25。
现在给定S，小 C 想知道满足条件的新密码是啥。
输入
第一行读入一个由数字构成的字符串 S
保证 1 ≤ |S| ≤ 10，其中|S|表示 S 的串长。
输出
输出一个长度和 S 相同的由数字构成的字符串，表示新密码。
额外样例
| 样例输入 | 样例输出 |
| 512 | 012 |
| 99999 | 49876 |
| 765876346 | 265874931 |
- 样例输入
-
201
- 样例输出
-
701
这个题目竟然可以用STL做，比赛的时候感觉可能会时间超限没做~~
代码：
// Asimple
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<" = "<<a<<endl
#define sysp system("pause")
using namespace std;
typedef long long ll;
const int maxn = + ;
const ll INF = <<;
ll T, n, sum, num, m, t, len, k;
char s[];
int a[], b[], l;
ll ten; ll check() {
ll tnum=;
for(int i=;i<l;i++) tnum=tnum*+a[i];
return min(abs(tnum-num),ten-abs(tnum-num));
} void input() {
scanf("%s",s);
num=;
ten=;
l=strlen(s);
for(int i=;i<l;i++) {
num=num*+(s[i]-'');
ten=ten*;
}
for(int i=;i<;i++) a[i]=b[i]=i;
long long ans=check();
while(next_permutation(a,a+)) {
long long tans = check();
if(tans>ans){
ans=tans;
for(int i=;i<l;i++)
b[i]=a[i];
}
}
for(int i=;i<l;i++) printf("%c",b[i]+'');
printf("\n");
//sysp;
} int main() {
input();
return ;
}
题目4 : 道路摧毁
描述
A国一共有 n 个城市且有n-1条双向道路，且任意两个城市都可以通过道路互相到达。
现在 B 国给出了两个城市的集合X,Y，你需要摧毁若干条A国的道路，使得任意一个在X中的城市无法到达任何一个Y中的城市。
现在给定每条道路摧毁需要付出的代价，求一个代价之和最小的方案。
输入
第一行一个正整数n
第二行一个整数mX，表示|X|
第三行给出mX个互不相同的正整数，描述集合X
第四行一个整数mY，表示|Y|
第五行给出mY个互不相同的正整数，描述集合Y
接下来n-1行，每行三个正整数(u,v,w)，描述一条代价为w的双向道路(u,v)
1 ≤ n ≤ 2 × 105，1 ≤ w ≤ 109，保证集合X和集合Y的交集为空。
输出
输出一个整数，表示代价之和最小的方案的代价之和。
样例解释
摧毁道路(2,5),(1,3)
- 样例输入
-
6
1
4
2
5 6
1 2 5
2 4 4
2 5 1
1 3 2
3 6 7 - 样例输出
-
3
排名第一的AC代码：
#include <bits/stdc++.h> using namespace std;
const long long INF = 1000000000000000LL;
const int maxn = ;
int h[maxn],mem;
int belong[maxn];
long long dp[maxn][];
struct
{
int v,w,next;
}e[maxn<<];
void add(int u,int v,int w)
{
e[mem].v=v;
e[mem].w=w;
e[mem].next=h[u];
h[u]=mem++;
}
void dfs(int u,int fa)
{
if(belong[u]){
for(int i=;i<;i++)
dp[u][i]=INF;
dp[u][belong[u]]=;
}
for(int i=h[u];i+;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,u);
dp[u][] = min(min(min(dp[v][],dp[v][]),dp[v][]+e[i].w) + dp[u][],dp[u][]+dp[v][]);
dp[u][] = min(min(min(dp[v][],dp[v][]),dp[v][]+e[i].w) + dp[u][],dp[u][]+dp[v][]);
dp[u][] = min(dp[v][],min(dp[v][],dp[v][])+e[i].w) + dp[u][];
}
}
int main()
{
int n;
scanf("%d",&n);
memset(belong,,sizeof(belong));
int x,y;
scanf("%d",&x);
mem=;memset(h,-,sizeof(h));
for(int i=;i<x;i++)
{
int val;
scanf("%d",&val);
belong[val]=;
}
scanf("%d",&y);
for(int i=;i<y;i++)
{
int val;
scanf("%d",&val);
belong[val]=;
}
for(int i=;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
dfs(,);
printf("%lld\n",min(dp[][],min(dp[][],dp[][])));
return ;
}