当前位置: 首页 > news >正文

CSP-J历届真题总结

P2671 [NOIP 2015 普及组] 求和

题目描述

一条狭长的纸带被均匀划分出了 \(n\) 个格子,格子编号从 \(1\)\(n\)。每个格子上都染了一种颜色 \(color_i\)\([1,m]\) 当中的一个整数表示),并且写了一个数字 \(number_i\)

编号 1 2 3 4 5 6
颜色和数字 \(\color{blue}{5}\) \(\color{blue}{5}\) \(\color{red}{3}\) \(\color{red}{2}\) \(\color{blue}{2}\) \(\color{red}{2}\)

定义一种特殊的三元组:\((x,y,z)\),其中 \(x,y,z\) 都代表纸带上格子的编号,这里的三元组要求满足以下两个条件:

  1. \(x,y,z\) 都是整数,\(x<y<z,y-x=z-y\)

  2. \(color_x=color_z\)

满足上述条件的三元组的分数规定为 \((x+z) \times (number_x+number_z)\)。整个纸带的分数规定为所有满足条件的三元组的分数的和。这个分数可能会很大,你只要输出整个纸带的分数除以 \(10007\) 所得的余数即可。

输入格式

第一行是用一个空格隔开的两个正整数 \(n\)\(m,n\) 表纸带上格子的个数,\(m\) 表纸带上颜色的种类数。

第二行有 \(n\) 用空格隔开的正整数,第 \(i\) 个数字表示纸带上编号为 \(i\) 格子上面写的数字 \(number_i\)

第三行有 \(n\) 用空格隔开的正整数,第 \(i\) 数字表示纸带上编号为 \(i\) 格子染的颜色 \(color_i\)

输出格式

一个整数,表示所求的纸带分数除以 \(10007\) 所得的余数。

输入输出样例 #1

输入 #1

6 2
5 5 3 2 2 2
2 2 1 1 2 1

输出 #1

82

输入输出样例 #2

输入 #2

15 4
5 10 8 2 2 2 9 9 7 7 5 6 4 2 4
2 2 3 3 4 3 3 2 4 4 4 4 1 1 1

输出 #2

1388

说明/提示

样例 1 解释

纸带如题目描述中的图所示。

所有满足条件的三元组为:\((1, 3, 5), (4, 5, 6)\)

所以纸带的分数为 \((1 + 5) \times (5 + 2) + (4 + 6) \times (2 + 2) = 42 + 40 = 82\)

对于第 \(1\) 组至第 \(2\) 组数据, \(1 ≤ n ≤ 100, 1 ≤ m ≤ 5\)

对于第 \(3\) 组至第 \(4\) 组数据,\(1 ≤ n ≤ 3000, 1 ≤ m ≤ 100\)

对于第 \(5\) 组至第 $ 6 $ 组数据,\(1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000\),且不存在出现次数超过 $ 20 $ 的颜色;

对于全部 \(10\) 组数据,\(1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000, 1 ≤ color_i ≤ m,1≤number_i≤100000\)

题解

首先,我们可以观察到分数是只与\(x\)\(z\)有关。
那么我们便可以忽略掉\(y\)
那么要求就从枚举三元组变为了枚举二元组且\(z-x\)不能被\(2\)整除
那就可以发现\(x,z\)的奇偶性相同
那么朴素的方法就是枚举\(x,z\)
时间复杂度为\(O(n^2)\)
无法通过这道题的所有数据。
那让我们再把目光看回到答案式子,
\((x+z)\times(number_x+number_z)\)
可以用乘法分配律将其拆开,
\(x\times(number_x+number_z)+z\times(number_x+number_z)\)
那么显然可以维护颜色为\(i\),奇偶性为\(j\)\(number\)\(sum_{i,j}\),格子个数\(size_{i,j}\)
则那么对于每个格子\(x\),对答案的贡献就是\(i \times (sum_{i,j}-number_i) + i \times number_i \times (size_{i,j}-1)\)
化简式子,得\(i \times sum_{i,j}+i \times (size_{i, j} - 2) \times number_i\)

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7, mod = 10007;
int n, m;
int color[N], number[N];
long long sum[N][2], sz[N][2], ans;
inline int read(){int sum = 0, f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();}while(c >= '0' && c <= '9'){sum = (sum << 3) + (sum << 1) + (c - 48);c = getchar_unlocked();}return sum * f;
}
int main(){n = read();m = read();for(int i = 1; i <= n; i++){number[i] = read() % mod;}for(int i = 1; i <= n; i++){color[i] = read();sum[color[i]][i & 1] = (sum[color[i]][i & 1] + number[i]) % mod;sz[color[i]][i & 1]++;}for(int i = 1; i <= n; i++){int c = color[i], op = i & 1;ans = (ans + i * sum[c][op] % mod + (sz[c][op] - 2) * i * number[i] % mod ) % mod;}printf("%lld\n", ans);return 0;
}
//最优解前10ヾ(≧▽≦*)o
http://www.hskmm.com/?act=detail&tid=34818

相关文章:

  • MATLAB中海洋要素计算工具箱解析
  • Python 中的绘图功能 matplotlib - stone-stone
  • 回文字符串(p2010)
  • 妈咪斜特!罗小黑战记2啥时候上线流媒体啊!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  • 你们的SpringBoot项目使用Mybatis还是Spring Data JPA?
  • 2025年10月豆包排名优化服务推荐排行榜单:十家服务商综合对比与评测分析
  • ICPC2023沈阳 游记(VP)
  • 2025年10月豆包排名优化服务排行榜评测:十家优质服务商综合对比分析报告
  • 2025?CTF(部分wp) -- week1
  • 2025年10月豆包排名优化服务推荐排行榜:十大服务商对比评测与选择指南
  • 为WPF应用增加项目图标
  • 基于STM32单片机的ECG心电滤波算法
  • 《掰开揉碎讲编程-长篇》一文读懂 哈希表
  • 【URP】Unity中Mipmap Streaming原理与实现
  • 如何设计PAD ring?
  • 如何把研究性学习糊弄过去
  • C#实现连续语音转文字
  • 2025 年钢结构源头厂家最新推荐排行榜:聚焦美标欧标 / 环保设备 / 厂房别墅等多领域优质供应商,精选优质厂家助力企业精准选材
  • PostgreSQL 18 中国贡献者经验分享:开源参与的四点建议
  • 2025 年碳晶板厂家最新推荐榜:涵盖木纹 / 白色 / 全屋整装等品类,西南及全国优质品牌甄选指南
  • 2025 年干细胞服务机构最新推荐排行榜:聚焦三体系认证与专利技术,精选优质机构供选择
  • 2025 最新隔音棉生产厂家口碑推荐榜:甄选家装公装专用材质,含西南 / 昆明阻尼片 / 吊顶 / 止震板品牌最新推荐
  • 2025 灭老鼠公司最新推荐榜:欧盟认证技术加持,环保服务双优品牌权威甄选指南
  • Collections集合工具类和可变参数
  • 2025 最新推荐!全国除甲醛公司权威榜单发布,解析蓉皓等标杆企业技术服务优势,覆盖新房 / 办公 / 学校多场景
  • 上周热点回顾(10.13
  • 一文读懂零知识证明Plonk 协议
  • P14259 兄妹(siblings)题解
  • 2025 年国内连接器厂家经销商最新推荐榜:聚焦优质品牌,助力企业精准采购,实力企业深度解析住友/日端/HRS连接器经销商推荐
  • P6076 [JSOI2015] 染色问题 分析