浅谈桶排思想及[USACO08DEC]Patting Heads 题解
一、桶排思想
1.通过构建n个空桶再将待排各个元素分配到每个桶。而此时有可能每个桶的元素数量不一样,可能会出现这样的情况:有的桶没有放任何元素,有的桶只有一个元素,有的桶不止一个元素可能会是2+;
2.按照下标对内容非0的桶按个数输出下标;
二、[USACO08DEC]Patting Heads题解
Description
-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.
inout:
-Line 1: A single integer: N
-Lines 2..N+1: Line i+1 contains a single integer: A_i
output:
-Lines 1..N: On line i, print a single integer that is the number of other cows patted by cow i.
Solution
1.题目意为输出所有当前手上纸条数为当前牛手上纸条数因子的牛的序号。
2.因为数据规模到了1e6所以有很大概率有重复标记,使用桶排思路,a数组记地址,num数组用桶排计数,ans数组记录因子个数;
3.从较小的数开始对其倍数进行ans数组中因数的累加;
4.因为自己作为自己的因子也会被累加记得最后对结果-1,用a数组记地址作下标输出ans[a[i]]-1;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
inline int rd()
{
int x=0;
char c;
c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0') //邢神的读入优化
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x;
}
int n,Max,a[100005],num[1000005],ans[1000005];
int main()
{
n=rd();
for (int i=1;i<=n;i++) a[i]=rd(),num[a[i]]++,Max=max(Max,a[i]);
for (int i=1;i<=Max;i++)
{
if (num[i]==0) continue;
for (int j=i;j<=Max;j+=i) ans[j]+=num[i]; //桶排思想对Max内i的倍数进行因数的累加
}
for (int i=1;i<=n;i++) printf("%d\n",ans[a[i]]-1); //(因为自己作为自己的因子也会被累加记得最后对结果-1)用a数组记地址作下标输出ans[a[i]]-1
return 0;
}
最新文章
- C语言中字符串结束符&#39;\0&#39;
- Python几种主流框架
- CSU 1337 搞笑版费马大定理(2013湖南省程序设计竞赛J题)
- 解析私有IP地址和公网IP地址
- 第三百三十三天 how can I 坚持
- Android问题-打开DelphiXE8与DelphiXE10编译空工程提示“[Exec Error] The command exited with code 1.”
- Linux下卸载ORACLE的多种方法(转)
- Binary Tree Preorder Traversal and Binary Tree Postorder Traversal
- netty 入门二 (传输bytebuf 或者pojo)
- BZOJ 4031: [HEOI2015]小Z的房间 [矩阵树定理 行列式取模]
- UVA - 12186 Another Crisis (树形DP)
- javascript之reduce()方法的使用
- 举例分析 Makefile 中的 patsubst、wildcard、notdir 函数
- tomcat整体架构
- 关于javascript三目
- nginx 获取自定义header头部信息
- CentOS6.3升级Python到2.7.3版本
- Android开发-- 简单对话框
- VM VirtualBox虚拟机与物理主机之间的复制
- 获取分组后统计数量最多的纪录;limit用法;sql执行顺序
热门文章
- ElasticSearch API 简要介绍
- ansible的介绍和一些基本模块介绍
- [LeetCode] [LeetCode] Populating Next Right Pointers in Each Node II
- bzoj1318[spoj 744] Longest Permutation
- URAL1519:Formula 1——题解
- Linux网络接口配置文件解析
- redis的数据持久化存储
- django 自己编写admin
- 《JavaScript高级程序设计(第三版)》-2
- poj3254 Corn Fields