第一题判断字符串是否合法没啥好说的。
第二题是说每个物品的总价值是v[i]+2*w[i]，问n个物品中价值最大的m个物品，对n个物品排序，排序的时候价值相同的物品取编号小的排在前面，价值不同的则价值大的排在前面，然后把前m个物品的编号放在set里面排序以后再输出。
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <utility>
using namespace std;
bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
if (a.first == b.first)
return a.second < b.second;
return a.first > b.first;
}
int main()
{
vector<pair<int, int>> vp;
int n, m;
cin >> n >> m;
int v, w;
for (int i = 1; i <= n; ++i){
cin >> v >> w;
vp.push_back(make_pair(v+2*w, i));
}
sort(vp.begin(), vp.end(), cmp);
set<int> ans;
for (int i = 0; i < m; ++i) ans.insert(vp[i].second);
int flag = 0;
for (int num : ans){
if (flag) cout<< " ";
cout << num;
flag = 1;
}
cout << endl;
return 0;
} 第三题是说在一个序列中按某个顺序取出数据，取完一个以后序列变成两个子序列，取完第二个变成三个子序列，每次取完数输出一下当前存在的子序列中和最大的值，但是样例给的太cao了，我误以为是每次取完数就只看左边和右边谁更大。 然而还是不会做，是线段树吗？我用树状数组+set暴力搞了一下，就是用set存放已经查询过的位置，然后暴力遍历区间，用树状数组求区间的和，更新ans，过了64%，应该不需要用long long，写的比较保险。
#include <iostream>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
int n;
long long fro[50010];
long long w[50010];
int lowbit(int x)
{
return x&(-x);
}
void update(int pos, long long num)
{
while (pos <= n)
{
fro[pos] += num;
pos += lowbit(pos);
}
}
long long get_sum(int pos)
{
long long sum = 0;
while (pos > 0)
{
sum += fro[pos];
pos -= lowbit(pos);
}
return sum;
}
int main()
{
cin >> n;
memset(fro, 0, sizeof fro);
for (int i = 1; i <= n; ++i){
cin >> w[i];
update(i, w[i]);
}
set<int> s;
s.insert(0);
s.insert(n);
int index;
for (int i = 1; i <= n; ++i){
cin >> index;
update(index, -w[index]);
s.insert(index);
set<int>::iterator p = s.begin();
set<int>::iterator q = s.begin();
++q;
long long ans = 0;
while (q != s.end()){
long long x = get_sum(*q) - get_sum(*p);
ans = max(ans, x);
++p;
++q;
}
cout << ans << endl;
}
return 0;
} 第四题啥玩意。。。完全不会，题目很难读懂，读懂了也不会。刚在讨论区找到了AC了第三题的大佬，把他的代码理解了一下。https://www.nowcoder.com/discuss/485678?type=0&order=0&pos=24&page=1&channel=666&source_id=discuss_center_0
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
#define MAXN 50005
int a[MAXN];
int b[MAXN];
int sum[MAXN];
int ans[MAXN];
class UnionFind{//并查集模板
public:
int n, count;
vector<int> father;
UnionFind(int num){
n = count = num;
father.resize(n);
for(int i = 0 ; i < n ; i++)
father[i] = i;
}
int find(int x){
if(father[x] == x)
return x;
return find(father[x]);
}
};
int main()
{
int n;
scanf("%d", &n);
for(int i = 0 ; i < n ; i++)
scanf("%d", &a[i]);
for(int i = 0 ; i < n ; i++)
scanf("%d", &b[i]);
ans[n-1] = 0;
int mmax = 0;
UnionFind u(n);
for(int i = n-1 ; i >= 0 ; i--){//倒着搞，把去除数字变成了插入数字，每插入一个位置，这个位置会变成所属堆的祖先，sum[id]是这个堆的和
int id = b[i] - 1;
sum[id]+= a[id];
if(id > 0 && sum[id-1] > 0){//当插入的位置左边还没有被插入过数字时，说明当前数字不会跟左边的堆合并，否则去找左边位置的祖先，这个祖先是最近处理过的一个位置
int x = id;
int y = u.find(id - 1);
if(x != y){//其实x一定是不等于y的，因为x是第一次出现，y会等于x的左边最近计算过的一个位置，那个位置存放了x的左边的堆的和
sum[x] += sum[y];
u.father[y] = x;//左边的堆现在加到x上了，之后插入数字的时候如果x在数字旁边的堆，那就会find到x，sum[x]表示包含了x的堆的和，也就是说x现在变成了这个堆的祖先
}
}
if(id < n-1 && sum[id+1] > 0){//同理，当插入的位置右边还没有被插入过数字时，说明当前数字不会跟右边的堆合并，否则可以把当前数字跟右边的堆合并成一个更大的堆
int x = id;
int y = u.find(id + 1);
if(x != y){
sum[x] += sum[y];
u.father[y] = x;//当前堆的祖先变成了x，且sum[x]表示这个堆的和
}
}
mmax = max(mmax, sum[id]);//更新目前为止最大的堆，由于是插入，所以堆的最大值要么不变要么变成sum[x]了
if(i > 0)
ans[i-1] = mmax;//记录一下
}
for(int i = 0 ; i < n ; i++)//正向输出
printf("%d\n", ans[i]);
return 0;
} 真的太厉害了！这个反向操作实在高明！！！
全部评论
(17) 回帖