第一题：
添加一个头部字符串和一个尾部字符串。头部字符串满足至少包含一个“MT”子序列，
且以T结尾。尾部字符串需要满足至少包含一个“MT”子序列，且以M开头。求S是满
足头尾字符串合法的情况下的最长的字符串。
思路：AC 直接模拟
代码：
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("a.txt", "r", stdin);
#endif
int n;
string s;
while(cin >> n) {
cin >> s;
int size = s.size();
int l = 0;
int mcnt = 0;
for(int i = 0; i < size; ++i) {
if(s[i] == 'M') {
++mcnt;
} else if(s[i] == 'T' && mcnt > 0) {
l = i;
break;
}
}
int r = size-1;
int tcnt = 0;
for(int i = size-1; i >= l; i--) {
if(s[i] == 'T') {
++tcnt;
} else if(s[i] == 'M' && tcnt > 0) {
r = i;
break;
}
}
cout << s.substr(l+1, r - l - 1);
}
return 0;
} 第二题：
本着能者优先的原则，公司将这n个人按照业务能力从高到底编号为1~n。编号靠前的人
具有优先选择的权力，每一个人都会填写一个意向，这个意向是一个1~n的排列，表示
一个人希望的去的业务区域顺序，如果有两个人同时希望去某一个业务区域则优先满足编号小的人，
思路：AC 直接模拟
代码：
const int maxn = 305;
int a[maxn][maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("b.txt", "r", stdin);
#endif
int n;
while(cin >> n) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
cin >> a[i][j];
}
}
vector<int> ans(n+1, 0);
vector<bool> visit(n+1, false);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
if(visit[ a[i][j] ]) continue;
ans[i] = a[i][j];
visit[a[i][j]] = true;
break;
}
}
for(int i = 1; i <= n; ++i) {
if(i < n) cout << ans[i] << " ";
else cout << ans[i] << endl;
}
}
return 0;
} 第三题：
小美要去找小团“讲道理”。小团望风而逃，他们住的地方可以抽象成一棵有n个结点的树，小美位于x位置，
小团位于y位置。小团和小美每个单位时间内都可以选择不动或者向相邻的位置转移，假设小美足够聪明，
很显然最终小团会无路可逃，只能延缓一下被“讲道理”的时间，请问最多经过多少个单位时间后，小团会被追上。
思路：AC 分别以 x y 为起点搜索到所有其他点的路径长度，然后取dx > dy得最大的dx就是答案
代码：
const int maxn = 50005;
void dfs(vector<vector<int>>& tree, vector<int>& dis, int u, int fa, int step) {
for(int v : tree[u]) {
if(v == fa) continue;
dis[v] = step+1;
dfs(tree, dis, v, u, step+1);
}
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("c.txt", "r", stdin);
#endif
int n, x, y;
while(cin >> n >> x >> y) {
vector<vector<int>> tree(n+1);
for(int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}
vector<int> disx(n+1, 0);
vector<int> disy(n+1, 0);
dfs(tree, disx, x, -1, 0);
dfs(tree, disy, y, -1, 0);
int ans = 0;
for(int i = 1; i <= n; ++i) {
if(disx[i] > disy[i]) ans = max(ans, disx[i]);
}
cout << ans << endl;
}
return 0;
} 第四题：
小团和小美各自选择一个[1,m]之间的整数，设小美选择的是l，小团选择的是r，
我们认为两个人是默契的需要满足以下条件:
1. l 小于等于r。
2. 对于序列中的元素x，如果0<x<l,或r<x<m+1,则x按其顺序保留下来，要求保留下来的子序列单调不下降。
小团为了表现出与小美最大的默契，因此事先做了功课，他想知道能够使得两人默契的二元组<l,r>一共有
多少种。我们称一个序列A为单调不下降的，当且仅当对于任意的i>j,满足A_i>=A_j。输入第一行包含
两个正整数m和n，表示序列元素的最大值和序列的长度。(1<=n,m<=100000)
思路：AC 18%(我用的求逆序的算法，然后总数-逆序数), 题目真的没有读懂，好吧，不是不懂，
是完全没有一点思路（卡了30min 无果）希望路过的大佬们可以提供点思路。非常感谢！
代码：
const int maxn = 100005;
int a[maxn];
int t[maxn];
int quikSort(int left, int right) {
if(left >= right) return 0;
int m = (left + right) / 2;
int l = quikSort(left, m);
int r = quikSort(m+1, right);
int i = left;
int j = m+1;
int k = left;
int cnt = 0;
while(i <= m && j <= right) {
if(a[i] > a[j]) {
cnt += (j - m);
t[k++] = a[j++];
} else {
t[k++] = a[i++];
}
}
while(i <= m) t[k++] = a[i++];
while(j <= right) {
if(a[m] > a[j]) cnt += (j-m);
t[k++] = a[j++];
}
for(int k = left; k <= right; ++k) a[k] = t[k];
return l + cnt + r;
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("d.txt", "r", stdin);
#endif
int n, m;
while(cin >> m >> n) {
for(int i = 1; i <= n; ++i) cin >> a[i];
cout << n*(n+1)/2 - quikSort(1, n) << endl;
}
return 0;
} 附加题：
我们用如下的方式表示他的粘贴操作和查询操作：
粘贴操作：1 k x y，表示把A序列中从下标x位置开始的连续k个元素粘贴到B序列中从下标y开始的连续k个位置上，
原始序列中对应的元素被覆盖。（数据保证不会出现粘贴后k个元素超出B序列原有长度的情况）
查询操作：2 x，表示询问当前B序列下标x处的值是多少。
输入第一行包含一个正整数n，表示序列A和序列B的长度。(1<=n<=2000)
输入第二行包含n个正整数，表示序列A中的n个元素，第 i 个数字表示下标为 i 的位置上的元素，
每一个元素保证在10^9以内。
输入第三行是一个操作数m，表示进行的操作数量。(1<=m<=2000)
思路：AC 数据量比较小，直接模拟做就行了！n <= 2000, 所以直接n^2暴力即可。直觉告诉我一定会有
比n^2更优的复杂度，希望路过的大佬可以指点一下，非常感谢！
代码：
const int maxn = 2005;
int a[maxn];
int b[maxn];
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("e.txt", "r", stdin);
#endif
int n, m;
int op, k, x, y;
while(cin >> n) {
memset(b, -1, sizeof(b));
for(int i = 1; i <= n; ++i) cin >> a[i];
cin >> m;
while(m--) {
cin >> op;
if(op == 2) {
cin >> x;
cout << b[x] << endl;
continue;
}
cin >> k >> x >> y;
int t = 0;
for(int i = x; i < k + x; ++i, ++t) {
b[y+t] = a[i];
}
}
}
return 0;
} 
全部评论
(8) 回帖