[做题记录-乱做] [AGC003E] Sequential operations on Sequence
2021/10/1 23:14:16
本文主要是介绍[做题记录-乱做] [AGC003E] Sequential operations on Sequence,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意
一串数,初始为 \(1\sim n\),现在给 \(Q\) 个操作,每次操作把数组长度变为 \(q_i\),新增的数为上一个操作后的数组的重复。问 \(Q\) 次操作后 \(1\sim n\) 每个数出现了多少次。
\[1 \leq n \leq 10^5 \]题解
为什么题解都说这个很简单啊, 为啥我感觉根本不会啊
首先可以忽略无效操作让操作序列单增。
让\(A_i\)表示第\(i\)次操作以后的数组, 那么\(A_i\)会是若干倍的\(A_{i - 1}\)加上\(A_{i -1}\)的前面一部分组成。也就是说实际上可以递归地表示\(A_i\)这个数组。由于最后考虑总答案, 可以倒着做, 设\(f_i\)表示数组\(i\)的贡献次数, 倒过来模拟即可。
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long int read() { int x = 0, f = 1; char a = getchar(); for(; ! isdigit(a); a = getchar()) if(a == '-') f = -1; for(; isdigit(a); a = getchar()) x = x * 10 + a - '0'; return x * f; } const int N = 1e5 + 10; int n, q, top; int stk[N]; int f[N], g[N]; void calc(int x, int tf) { if(x == 0) return ; int y = upper_bound(stk + 1, stk + 1 + top, x) - stk - 1; if(y == 0) g[1] += tf, g[x + 1] -= tf; else f[y] += x / stk[y] * tf, calc(x % stk[y], tf); } signed main() { n = read(); q = read(); stk[++ top] = n; for(int i = 1; i <= q; i ++) { int x = read(); while(x <= stk[top]) top --; stk[++ top] = x; } f[top] = 1; for(int i = top; i >= 2; i --) f[i - 1] += stk[i] / stk[i - 1] * f[i], calc(stk[i] % stk[i - 1], f[i]); g[1] += f[1]; g[stk[1] + 1] -= f[1]; for(int i = 1; i <= n; i ++) g[i] += g[i - 1]; for(int i = 1; i <= n; i ++) printf("%lld%c", g[i], '\n'); return 0; }
这篇关于[做题记录-乱做] [AGC003E] Sequential operations on Sequence的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding