hdu 6058 Kanade's sum (计算贡献,思维)
2024-08-30 11:16:35
题意: 给你一个全排列,要你求这个序列的所有区间的第k大的和
思路:比赛的时候一看就知道肯定是算贡献,也知道是枚举每个数,然后看他在多少个区间是第K大,然后计算他的贡献就可以了,但是没有找到如何在o(k)的时间内找到这k个区间,然后就一直挂机,惨惨惨
感觉官方题解的思路就很棒啊:
我们只要求出对于一个数x左边最近的k个比他大的和右边最近k个比他大的,扫一下就可以知道有几个区间的k大值是x.=
我们考虑从小到大枚举x,每次维护一个链表,链表里只有>=x的数,那么往左往右找只要暴力跳k次,删除也是O(1)的。
时间复杂度:O(nk)
代码:
/** @xigua */
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <climits>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = 5e5 + 5;
const int mod = 1e9 + 9;
const int mod2 = 1e9 + 7;
const int INF = 1e8 + 5;
const ll inf = 1e15 + 5;
const db eps = 1e-5;
const ll hp = 233333;
int a[maxn], pos[maxn], pre[maxn], nex[maxn];
ll pp[105], np[105]; void solve() {
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
pos[a[i]] = i;
pre[i] = i - 1;
nex[i] = i + 1;
}
pre[0] = -1, nex[n+1] = n + 2;
ll ans = 0;
for (int i = 1; i <= n; i++) {
int t1 = 0, t2 = 0;
int curp = pos[i];
for (int j = curp; j >= 0 && t1 <= k; j = pre[j]) {
pp[++t1] = j;
}
for (int j = curp; j <= n + 1 && t2 <= k; j = nex[j]) {
np[++t2] = j;
}
for (int j = 1; j <= t1 - 1; j++) {
if (k - j + 2 > t2) continue;
ll tmp = (pp[j] - pp[j+1]) * (np[k - j + 2] - np[k - j + 1]);
ans += tmp * i;
}
//删除当前节点 相当于链表
int tp = pre[curp], tn = nex[curp];
nex[tp] = tn, pre[tn] = tp;
}
cout << ans << endl;
} int main() {
int t = 1, cas = 1;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// init();
scanf("%d", &t);
while(t--) {
// printf("Case %d: ", cas++);
solve();
}
return 0;
}
最新文章
- excel复制+粘贴,怎样让公式里的参数不自动变化?
- div 两列布局,左侧固定宽度px,右侧自适应宽度,满屏
- js贪吃蛇
- iOS 网络请求NSURLSession
- java-基础练习题1
- 【转载】Powershell获取世纪互联Office365所有用户最后一次登录时间
- HDU4893--Wow! Such Sequence! (线段树 延迟标记)
- zoj2314(有上下界的网络流)
- OC语言的特性(二)-Block
- Web渗透测试(sql注入 access,mssql,mysql,oracle,)
- Django基础四(model和数据库)
- [C#] .NET4.0中使用4.5中的 async/await 功能实现异步
- C# 数字字符串前面不足位补零方法
- echo和重定向
- JavaEE 之 Spring(一)
- C++调用IDL程序的做法(三)
- CentOS 7 下安装 Nginx(转)
- 12月13日 什么是help_method,session的简单理解, find_by等finder method
- struts2 的特征
- [学习笔记]平衡树(Splay)——旋转的灵魂舞蹈家
热门文章
- STL树
- 一个github搞定微信小程序支付系列
- Lightoj1037【状压DP】
- CodeForces 41A+43A【课上无聊刷水题系列】
- Metabolic and gut microbial characterization of obesity-prone mice under high-fat diet (文献分享一组-赵容丽)
- 生产者消费者 java.util.concurrent.lock包
- sql索引的作用
- IP服务-7-系统日志
- django (三) admin后台系统
- ajax中get和post区别