题解：P14118 [SCCPC 2021] Hotpot
题意
给定 \(T\) 组测试数据，每组测试数据情景如下：
\(0\) 到 \(n-1\) 共 \(n\) 位游客，\(k\) 种火锅食材，\(m\) 次操作，第 \(i\) 次操作（\(0 \le i < m\)）是由 \(i \mod n\) 号游客执行。每位游客有自己喜欢的食材 \(a_i\)（\(1 \le a_i \le k\)），初始幸福值均为 \(0\)，火锅为空。
操作规则：
执行操作的游客 \(t\) ，若其最喜欢的食材 \(a_t\) 已经在火锅中，则 \(t\) 会吃掉所有 \(a_t\)，自身幸福值 \(+1\)，否则 \(t\) 会向火锅中放入 \(1\) 份 \(a_t\)，自身幸福值不变。
请你输出每位游客的幸福值。
数据规模与约定
\(1 \le T \le 10^3\)；
\(1 \le n \le 10^5,1 \le k \le 10^5,1 \le m \le 10^9\)；
\(1 \le a_i \le k\)；
所有测试数据 \(\sum \limits _{i=1} ^T n_i \le 2 \times 10^5,\sum \limits _{i-1} ^T k_i \le 2 \times 10^5\)。
题解
做法一 直接模拟
用 std::map 维护火锅，可以发现时间复杂度是 \(O(m)\)，但是 \(m\) 可能会到达 \(10^9\) 级别，在 #2 测试点会 TLE。
做法二 数学方法
通过对题目的观察，我们可以发现如下：
\(1.\) 食材之间具有独立性：食材之间不会互相影响。
\(2.\) 单个食材具有独一无二的操作序列：
对于食材 \(x\) ，它的操作序列是 \(O_x=[O_0,O_1,\cdots,O_{k_x-1}]\)（\(k_x\) 为喜欢 \(x\) 的游客数）。所以，所有对 \(x\) 的操作，本质是执行对 \(x\) 的操作序列。
\(3.\) 操作具有奇偶性规律：
关于食材 \(x\) 的操作序列 \(O_x\)，分析在序列下标（\(0\) 开始）上的操作效果：
- 下标为偶数，可以发现在奇数次时已经把食材吃掉了，所以只能向火锅里添加食材，对幸福值没有贡献。
- 下标为奇数，可以发现在偶数次时已经添加了食材，所以需要执行吃掉的操作，幸福值 \(+1\)。
所以，根据我们的发现，可以对算法进行建模：
把食材 \(x\) 的操作拆成完整轮次和不完整轮次，分别进行计算（具体看代码）。
CODE
#include <bits/stdc++.h>
using namespace std;
/*====================*/
using ll=long long;
/*====================*/
#define endl '\n'
/*====================*/
void Solve()
{int n,k,m;cin>>n>>k>>m;vector<int> a(n);for(auto& i:a)cin>>i;unordered_map<int,vector<int>> mp;// 按喜欢的食材分组for(int i=0;i<n;i++){mp[a[i]].push_back(i); } vector<int> h(n,0);// 记录幸福值for(auto it=mp.begin();it!=mp.end();it++){int kx=it->second.size();// 喜欢这个食材的人数 ll cnt_op=0;// 该食材操作的总次数// 计算每个游客在 m 次操作中出现的总次数 for(auto i:it->second){if(i>=m)continue;// 游客 i 的首次操作已经超过 mcnt_op+=(m-1-i)/n+1; } if(cnt_op==0)continue;// 无操作直接跳过// 拆分完成轮次和剩余轮次int full=cnt_op/kx;int rem=cnt_op%kx;// 处理完整轮次的贡献if(kx%2==0)// 食材操作序列长度为偶数：奇数索引操作（吃食材）每轮贡献1次{for(int j=0;j<kx;j++){if(j&1){h[it->second[j]]+=full;}}}else // 食材操作序列长度为奇数：轮次奇偶影响贡献{for(int j=0;j<kx;j++){if(j&1){h[it->second[j]]+=(full+1)/2;}else{h[it->second[j]]+=full/2;}}}// 处理剩余操作的贡献int base=(1LL*full*kx)%2;for(int j=0;j<rem;j++){if((base+j)&1){h[it->second[j]]++;}}}for(int i=0;i<n;i++){cout<<h[i]<<" ";} cout<<endl;
}
/*====================*/
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int T=1;cin>>T;while(T--)Solve();return 0;
}
注：本文已被 luogu 审核通过至P14118 题解区。