2019.9.28 csp-s模拟测试54 反思总结
2024-10-07 23:21:18
咕咕咕的冲动如此强烈x
T1x:
看完题目想了想,感觉把gcd不为1的强行放在一组,看作一个连通块,最后考虑连通块之间的组合方式就可以了。
然后维护这个连通块可以写并查集可以连边跑dfs怎么着都行…
然而我在处理数字分解质因数这里T掉了,原因是一个很显然的优化写法我基本没怎么写过。线性筛的时候记录每个数是被哪个质数标记过的,分解一个数的时候直接处理记录下来的质数就可以。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,t;
long long mod=1e9+,ans,sum;
int num[],pri[],cnt,vis[],pre[];
int fa[];
void work(){
for(int i=;i<=;i++){
if(!vis[i]){
pri[++cnt]=i;
pre[i]=i;
}
for(int j=;j<=cnt&&i*pri[j]<=;j++){
vis[i*pri[j]]=;
pre[i*pri[j]]=pri[j];
if(i%pri[j]==)break;
}
}
}
long long ks(long long x,long long k){
long long num=;
while(k){
if(k&)num=num*x%mod;
x=x*x%mod;
k>>=;
}
return num;
}
int get(int x){
if(fa[x]==x)return x;
else return fa[x]=get(fa[x]);
}
int main()
{
scanf("%d",&t);
work();
while(t--){
scanf("%d",&n);
sum=n;
for(int i=;i<=cnt;i++)num[pri[i]]=;
for(int i=;i<=n;i++)fa[i]=i;
for(int i=,x;i<=n;i++){
scanf("%d",&x); while(x>){
int y=pre[x];
while(x%y==)x/=y;
if(!num[y])num[y]=i;
else{
int x1=get(num[y]),x2=get(i);
if(x1!=x2){
fa[x2]=x1;
sum--;
}
num[y]=i;
}
} }
ans=((ks(2ll,sum)%mod-)%mod+mod)%mod;
printf("%lld\n",ans);
}
return ;
}
T2y:
如果直接做的话,显然是从1开始,枚举路径状态,看看这个状态能达到的节点有哪些,并根据这些节点所连的边能达到的点的集合拓展下一位的状态。最后看长度为d的状态有多少个所能到达的点的集合不为空,统计答案。
但是这样要枚举的状态太多了。
于是考虑把路径拆成两部分,对每个点都求一次能达到的路径的答案,存下每个长度为d的一半的路径状态能达到哪些点。可以倒序从n开始求,最后一次求的就正好是1能达到的一半路径的状态。枚举前后两半的路径状态,若两者存在交集,即两半路径存在可以相连的中间点,那么答案+1。
#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;
int n,m,d,x1,x2,ans;
bitset<>sum0[],sum1[],f[<<],g[<<];
//void add(int x,int y,int z){
// ver[++tot]=y;
// Next[tot]=head[x];
// head[x]=tot;
// edge[tot]=z;
//}
int main()
{
scanf("%d%d%d",&n,&m,&d);
x1=d/,x2=d-x1;
for(int i=,x,y,z;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
if(z){
sum1[x][y]=;
sum1[y][x]=;
}
else{
sum0[x][y]=;
sum0[y][x]=;
}
}
for(int i=n;i>=;i--){
for(int j=;j<(<<);j++)f[j].reset();
f[][i]=;
for(int j=;j<(<<x2);j++){
for(int k=;k<=n;k++){
if(f[j][k]){
f[j<<]|=sum0[k];
f[j<<|]|=sum1[k];
}
}
}
for(int j=;j<(<<x2);j++){
g[j][i]=f[(<<x2)|j].any();
}
}
for(int i=;i<(<<x2);i++){
for(int j=;j<(<<x1);j++){
if((g[i]&f[(<<x1)|j]).any())ans++;
}
}
printf("%d\n",ans);
return ;
}
T3z:
强行模拟这个过程是可以骗到分的,虽然我没骗到多少…
然而正解好像是个更难写的模拟…
首先观察n个任务,发现如果有任务与上一个相同,或者处在上一个任务到下一个任务的路径上,那么这个任务可以忽略不计。简化以后的任务序列就成为了一左一右的过程,每一次线段平移都与上一次走相反方向。
然后可以用链表串起这些有效任务,在询问线段长度小于最小的两个任务间距的时候,答案是一个一次函数。如果有两个任务之间的距离小于询问线段的长度,就合并相连的三个位移,答案还是一个一次函数。
然而并不会写,虽然刚刚重新下载题解的时候好像看到发标程了…
垃圾选手什么都菜,被赶了出来【大雾】
最新文章
- Find cmd
- 相对路径获取项目文件 及报错 No mapping found for HTTP request with URI XXX in DispatcherServlet with name ‘springmvc’解决方法
- 关于app的清除缓存的功能
- DataTable排序的一般方法
- poj 1704
- iOS中引用计数内存管理机制分析
- NDK(16)Jni中GetStaticFieldID和GetMethodID 中的类型标识串
- JAVA-5-关于for循环的几个例子
- nginx: [emerg] socket() [::]:80 failed (97: Address family not supported by protocol)
- Centos 7系统启动修复
- python_code list_3
- 读《图解HTTP》有感-(了解web及网络基础)
- X级联动
- redis加固
- snopy 数据库简介
- Reportviewer中的函数使用——打印当前日期并格式化
- Jenkins构建.net项目
- insserv: Script <;name>; is broken: incomplete LSB comment.
- jenkins 调用 k8s api
- 【划水闲谈】Terraria 1.3.5更新
热门文章
- MFC 使程序不在任务栏显示
- pandas的使用方法
- 莫烦PyTorch学习笔记(四)——回归
- Codeforces Round #599 (Div. 2)的简单题题解
- Object.keys()应用
- win7+64位笔记本 python3.6安装opencv3
- 使用python和tableau对数据进行抓取及可视化
- Linux 启动、关闭、重启服务的两种方式
- 转载https://www.luogu.org/problemnew/solution/P1665,http://bailian.openjudge.cn/practice/2002/的新解法
- Free- Linux必学的60个命令