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

内容纲要

题意略

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";
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇