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

洛谷[USACO08DEC] Patting Heads S

题目传送门
题目难度:普及/提高一

题面翻译

今天是贝茜的生日,为了庆祝自己的生日,贝茜邀你来玩一个游戏。

贝茜让 N N N ( 1 ≤ N ≤ 1 0 5 1\leq N\leq 10^5 1N105) 头奶牛坐成一个圈。除了 1 1 1 号与 N N N 号奶牛外, i i i 号奶牛与 i − 1 i-1 i1 号和 i + 1 i+1 i+1 号奶牛相邻。 N N N 号奶牛与 1 1 1 号奶牛相邻。农夫约翰用很多纸条装满了一个桶,每一张包含了一个不一定是独一无二的 1 1 1 1 0 6 10^6 106 的数字。

接着每一头奶牛 i i i 从桶中取出一张纸条 A i A_i Ai。每头奶牛轮流走上一圈,同时拍打所有手上数字能整除在自己纸条上的数字的牛的头,然后坐回到原来的位置。牛们希望你帮助他们确定,每一头奶牛需要拍打的牛的数量。

题目描述

It’s Bessie’s birthday and time for party games! Bessie has instructed the N (1 <= N <= 100,000) cows conveniently numbered 1…N to sit in a circle (so that cow i [except at the ends] sits next to cows i-1 and i+1; cow N sits next to cow 1). Meanwhile, Farmer John fills a barrel with one billion slips of paper, each containing some integer in the range 1…1,000,000.

Each cow i then draws a number A_i (1 <= A_i <= 1,000,000) (which is not necessarily unique, of course) from the giant barrel. Taking turns, each cow i then takes a walk around the circle and pats the heads of all other cows j such that her number A_i is exactly

divisible by cow j’s number A_j; she then sits again back in her original position.

The cows would like you to help them determine, for each cow, the number of other cows she should pat.

输入格式

* Line 1: A single integer: N

* Lines 2…N+1: Line i+1 contains a single integer: A_i

输出格式

* Lines 1…N: On line i, print a single integer that is the number of other cows patted by cow i.

样例 #1

样例输入 #1

5 
2 
1 
2 
3 
4

样例输出 #1

2 
0 
2 
1 
3

提示

The 5 cows are given the numbers 2, 1, 2, 3, and 4, respectively.

The first cow pats the second and third cows; the second cows pats no cows; etc.

题目分析:由于本题纯暴力枚举会炸的,优化解法:统计每个数字 Ai 出现的次数。对于每头奶牛 i枚举 Ai 的所有因数 并统计出现的次数。时间复杂度:O(NM)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;int ans[N],cnt[N],a[N]; 
int n;ll read()
{ll s=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}return s*f;
}int main() {n = read();for(int i = 1; i <= n; i++) {a[i] = read();cnt[a[i]]++;}int t = 0;for(int i = 1; i <= n; i++){t = 0;for(int j = 1; j <= a[i] / j; j++){if(a[i] % j == 0) {t += cnt[j];if(j != a[i] / j) t += cnt[a[i] /  j];}} ans[i] = t - 1;}for(int i = 1; i <= n; i++) cout<<ans[i]<<endl;return 0;
}

http://www.lryc.cn/news/531016.html

相关文章:

  • CSS 溢出内容处理:从基础到实战
  • Spring Boot项目如何使用MyBatis实现分页查询
  • 飞行汽车中的无刷外转子电机、人形机器人中的无框力矩电机技术解析与应用
  • FreeRTOS学习 --- 队列集
  • 【R语言】R语言安装包的相关操作
  • 15.[前端开发]Day15-HTML+CSS阶段练习(网易云音乐四)
  • 【基于SprintBoot+Mybatis+Mysql】电脑商城项目之用户登录
  • 测试方案和测试计划相同点和不同点
  • c++提取矩形区域图像的梯度并拟合直线
  • Unity Shader Graph 2D - 角色身体电流覆盖效果
  • 【LLM-agent】(task4)搜索引擎Agent
  • 携程Java开发面试题及参考答案 (200道-下)
  • GWO优化SVM回归预测matlab
  • QMK启用摇杆和鼠标按键功能
  • Unity实现按键设置功能代码
  • 基于物联网技术的实时数据流可视化研究(论文+源码)
  • list容器(详解)
  • Elasticsearch基本使用详解
  • 17.3.4 颜色矩阵
  • FPGA 时钟多路复用
  • 机器学习10
  • 【Block总结】CoT,上下文Transformer注意力|即插即用
  • linux库函数 gettimeofday() localtime的概念和使用案例
  • 编程题-电话号码的字母组合(中等)
  • EasyExcel使用详解
  • 基于“蘑菇书”的强化学习知识点(二):强化学习中基于策略(Policy-Based)和基于价值(Value-Based)方法的区别
  • 民法学学习笔记(个人向) Part.2
  • 物业管理系统源码驱动社区管理革新提升用户满意度与服务效率
  • 租房管理系统助力数字化转型提升租赁服务质量与用户体验
  • Ollama教程:轻松上手本地大语言模型部署