题目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 = 100000 + 5; const ll INF = 1<<30; 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=0; i<len; i++) { if( i%2 ) a = a + s[i]; else b = b + s[i]; } int len_a = 0, len_b = 0; for(int i=0; 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 0; }
题目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 = 1024 + 5; const ll INF = 1<<30; ll T, n, sum, num, m, t, len, ans, k; int a[maxn]; void input() { while( cin >> n >> t ) { len = (ll)pow(2, n); for(int i=0; i<len; i++) cin >> a[i]; if( t%2 ) for(int i=len-1; i>=0; i--) cout << a[i] << endl; else for(int i=0; i<len; i++) cout << a[i] << endl; } //sysp; } int main() { input(); return 0; }
题目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 = 1024 + 5; const ll INF = 1<<30; ll T, n, sum, num, m, t, len, k; char s[15]; int a[19], b[20], l; ll ten; ll check() { ll tnum=0; for(int i=0;i<l;i++) tnum=tnum*10+a[i]; return min(abs(tnum-num),ten-abs(tnum-num)); } void input() { scanf("%s",s); num=0; ten=1; l=strlen(s); for(int i=0;i<l;i++) { num=num*10+(s[i]-'0'); ten=ten*10; } for(int i=0;i<10;i++) a[i]=b[i]=i; long long ans=check(); while(next_permutation(a,a+10)) { long long tans = check(); if(tans>ans){ ans=tans; for(int i=0;i<l;i++) b[i]=a[i]; } } for(int i=0;i<l;i++) printf("%c",b[i]+'0'); printf(" "); //sysp; } int main() { input(); return 0; }
题目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 = 200005; int h[maxn],mem; int belong[maxn]; long long dp[maxn][3]; struct { int v,w,next; }e[maxn<<1]; 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=0;i<3;i++) dp[u][i]=INF; dp[u][belong[u]]=0; } for(int i=h[u];i+1;i=e[i].next) { int v=e[i].v; if(v==fa) continue; dfs(v,u); dp[u][1] = min(min(min(dp[v][0],dp[v][1]),dp[v][2]+e[i].w) + dp[u][1],dp[u][0]+dp[v][1]); dp[u][2] = min(min(min(dp[v][0],dp[v][2]),dp[v][1]+e[i].w) + dp[u][2],dp[u][0]+dp[v][2]); dp[u][0] = min(dp[v][0],min(dp[v][1],dp[v][2])+e[i].w) + dp[u][0]; } } int main() { int n; scanf("%d",&n); memset(belong,0,sizeof(belong)); int x,y; scanf("%d",&x); mem=0;memset(h,-1,sizeof(h)); for(int i=0;i<x;i++) { int val; scanf("%d",&val); belong[val]=1; } scanf("%d",&y); for(int i=0;i<y;i++) { int val; scanf("%d",&val); belong[val]=2; } for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs(1,1); printf("%lld ",min(dp[1][0],min(dp[1][1],dp[1][2]))); return 0; }