Ryan's WorkSpace
  • 首页
  • 关于我
  1. 首页
  2. C++
  3. 正文

HDU6319 2018HDU多校第三场 1001 Problem A. Ascending Rating

2018年07月30日 1177点热度 0人点赞 0条评论

内容纲要

题意略

coding出来其实很简单,按照题目要求填写数组,然后倒着搜维护一个单调队列就可以了,维护单调队列的时候要注意单调队列中元素数量等价于目标区间$$count_i$$的值,即$$count_i = q.size()$$
AC代码:

#include <iostream>
#include <queue>
#include <algorithm>
#include <array>

using namespace std;
using ll = long long;
const int maxn = 1e7 + 1e2;
array<int, maxn> a;
int n, m, k, P, Q, R, mod;
ll A, B;
deque<int> q;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        q.clear();
        cin >> n >> m >> k >> P >> Q >> R >> mod;
        for (int i = 1; i <= k; ++i)cin >> a[i];
        for (int i = k + 1; i <= n; ++i) {
            a[i] = (1ll * P * a[i - 1] + 1ll * Q * i + R) % mod;
        }
        A = B = 0;
        for (int i = n; i; --i) {
            while (!q.empty() && a[q.back()] <= a[i])q.pop_back();//维护单调队列
            q.push_back(i);//注意,这个队列是保证队尾元素最小的 所以要插入的值若比队尾元素大
                           //一定要去除对答案没有贡献的元素 这个是关键
            if (i + m - 1 <= n) {//当区间大小满足题意要求
                while (q.front() >= i + m) q.pop_front();//这里清除的是不满足当前所取区间范围的值
                A += i ^ a[q.front()];
                B += i ^ q.size();
            }
        }
        cout << A << " " << B << "\n";
    }
}

相关

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2018年07月30日

Ryan Lee

如果帮助到你,请点击广告,谢谢!

点赞
< 上一篇
下一篇 >

文章评论

您需要 登录 之后才可以评论

如果帮助到你,请点击广告,谢谢!

用户您好!请先登录!
登录 注册
Social Media
Github: ryanlee2014
标签聚合
hustoj Java Apache C++ C php GitHub JavaScript
友链
Pacolyon
Lucien's blog
Slian's DreamWork
卡拉搜索
  • 0
  • 15,313
  • 5,553
  • 0
广告

COPYRIGHT © 2020 Ryan's WorkSpace. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

登录
注册|忘记密码?