Codeforces 980D
2024-10-07 09:55:30
这题其实挺水的,但我比较vegetable,交了好多次才过。
题意:
给定一个序列,把这个序列的所有连续子序列分组,每组中任意两个数相乘是个完全平方数,输出每个子序列最少分的组数;
思路:
先把每个数都除去自身的完全平方因子,为什么呢?这样处理了之后,只有相同的数相乘才能变成完全平方数,而且原来相乘能变成完全平方数的数对也不会有影响,举个例子:$ 1 \times 4 = 4 $,$4$是完全平方数,除去平方因子后,变成 $1 \times 1 = 1$,$1$还是完全平方数(感性地理解YY一下就好了)
把处理完的数列从小到大排序,再离散化(防止数字太大,爆MLE)
由于题目给定n的范围是$5000$,所以不能$ O(n^3) $爆扫,QXZ大佬介绍了一种非常gin的方法,我用了离散化+桶的方法;
开个桶bo[i][j]表示1到i中数值为j的个数;然后dp,f[i][j]表示i到j的数列需要分成几个区间,f[i][j]=f[i][j-1],当第j个数在i到j中唯一时,f[i][j]++;
需要注意的点:
1、除去平方因子时要用while或者倒着扫i,防止有多个平方数;
2、排序时,要记录原来的位置,离散化完要排列回原来的序列(要按原来给定序列的子序列,而且子序列在原序列中是连续的)
3、0要特判,当0为一个单独的子序列时自成一组,否则与其他任何数都能变成完全平方数(和任何数都能一组)
附上蒟蒻的代码:
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=;
struct rec
{
int place,num;
}a[MAXN],now;
bool comp1(const rec &x,const rec &y)
{
return x.num<y.num;
}
bool comp2(const rec &x,const rec &y)
{
return x.place<y.place;
}
int n,bo[MAXN][MAXN],f[MAXN][MAXN],ans[MAXN],special0;
bool special[MAXN];
main()
{
scanf("%d",&n);
for(int i=;i<=n;++i)
{
scanf("%d",&a[i].num);
a[i].place=i;
}
for(int i=;i<=n;++i)
{
if(a[i].num!=)
{
int k=sqrt(abs(a[i].num));
for(int j=k;j>=;--j)
while(a[i].num%(j*j)==)
{
a[i].num/=j*j;
}
} else
{
special[i]=true;
special0=i;
}
}
sort(a+,a+n+,comp1);
now.place=;
now.num=a[now.place].num;
a[now.place].num=;
for(int i=;i<=n;++i)
{
if(a[i].num==now.num)
{
a[i].num=a[now.place].num;
} else
{
now.place=i;
now.num=a[i].num;
a[i].num=a[i-].num+;
}
}
sort(a+,a+n+,comp2);
for(int i=;i<=n;++i)
for(int j=i;j<=n;++j)
bo[j][a[i].num]++;
special0=a[special0].num;
for(int i=;i<=n;++i)
{
f[i][i]=;
++ans[f[i][i]];
}
for(int i=;i<=n;++i)
for(int j=i+;j<=n;++j)
{
f[i][j]=f[i][j-];
if(bo[j][a[j].num]-bo[i-][a[j].num]==&&(!special[j])&&(((bo[j][special0]-bo[i-][special0]!=j-i)||special0==)))
++f[i][j];
++ans[f[i][j]];
}
for(int i=;i<=n;++i)
printf("%d ",ans[i]);
return ;
}
最新文章
- Struts2入门(七)——Struts2的文件上传和下载
- 用c#开发的一款webservice调用小工具,方便测试
- SharePoint 2013 &ndash; Workflow Manager 1.0 offline download
- iOS及Mac开源项目和学习资料【超级全面】
- python 逐行读取文件的三种方法
- css行内样式
- RouterOS 软路由开启SSH服务器
- Oracle varchar2 4000
- 1060: [ZJOI2007]时态同步 - BZOJ
- nyoj 891 找点
- FatMouse&#39; Trade(hdoj1009)
- SQL Convert XML to Table
- Dijkstra、Dij + heap、Floyd、SPFA、 SPFA + SLF Template
- poj 3370 鸽笼原理知识小结
- Codeforces Round #554 (Div. 2) B. Neko Performs Cat Furrier Transform(思维题+log2求解二进制位数的小技巧)
- ASP.NET MVC系列:web.config中ConnectionString aspnet_iis加密与AppSettings独立文件
- 4. SpringBoot —— 单元测试
- 6. 深度克隆_ES7**_arr.includes(&#39;孙悟空&#39;)
- Python复习笔记(三)函数进阶
- 『TensorFlow Internals』笔记_系统架构
热门文章
- jmeter遍历时间戳
- 【ABAP系列】SAP ABAP DYNP_VALUES_UPDATE 更新屏幕字段的函数及用法
- 【MM系列】SAP 关于物料间的替代问题
- lnmp一键安装包卸载mysql,重新安装报错mysql57-community-release conflicts with mysql-community-release-el6-5.noarch
- xmake新增对WDK驱动编译环境支持
- 图解 SQL 里的各种 JOIN
- python面试题--初级(二)
- 【C语言--数据结构】线性表链式存储结构
- Windows netcat 的工具的简单使用
- shell学习笔记3---shell变量