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

钉耙编程(3)

1001深度自同构

Problem Description

对于无向图中的点,定义一个点的度为与其相连的边的条数。

对于一棵有根树,定义一个点的深度为该点到根的距离。

对于由若干有根树构成的森林,定义该森林是深度自同构的,当且仅当森林中任意两个深度相同的节点都有相同的度。

请计数有多少个深度自同构的无编号有根树森林,使得其恰好由 nn 个节点构成,答案对 998244353998244353 取模。

Input

一个整数 N (1≤N≤106)N (1≤N≤106),代表计数的范围。

Output

输出一行 NN 个整数,第 ii 个数代表 n=in=i 时的答案,对 998244353998244353 取模。

标准代码:

#include<bits/stdc++.h>
using namespace std;
#define N 1000007
#define mod 998244353
int f[N] = {0, 1}, ans[N];
int main() {cin.tie(0);ios::sync_with_stdio(false);int n; cin >> n; 
//   也可以这样写 
//	for (int i = 1; i <= n; ++i) 
//		for (int j = i; j <= n; j += i)  (f[j+1]+=f[i])%=mod;for (int i = 1; i <= n; i++)for (int j = 1; i * j <= n; j++) (f[j * i + 1] += f[i]) %= mod;for (int i = 1; i <= n; ++i) for (int j = i; j <= n; j += i) (ans[j] += f[i]) %= mod;for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);return 0;
}

1007 单峰数列

Problem Description

对于一个整数数列,如果其先严格递增,然后在某一点后严格递减,我们称这个数列为单峰数列(严格递增和严格递减的部分均要是非空)。

给定长度为 𝑛n 的整数数列 𝑎1,𝑎2,…,𝑎𝑛a1​,a2​,…,an​ ,请你支持 𝑞q 次操作:

  1. 1 l r x:将 𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟al​,al+1​,…,ar​ 的每个数加 𝑥x。

  2. 2 l r:判断 𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟al​,al+1​,…,ar​ 的元素是否全都相同。

  3. 3 l r:判断 𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟al​,al+1​,…,ar​ 是否严格升序排序。当 𝑙=𝑟l=r 时,认为符合严格升序排序。

  4. 4 l r:判断 𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟al​,al+1​,…,ar​ 是否严格降序排序。当 𝑙=𝑟l=r 时,认为符合严格降序排序。

  5. 5 l r:判断 𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟al​,al+1​,…,ar​ 是否为单峰数列。保证 𝑟−𝑙+1≥3r−l+1≥3。

Input

第一行输入包含一个整数 𝑛 (3≤𝑛≤105)n (3≤n≤105)。

第二行输入包含 𝑛n 个整数 𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤109)a1​,a2​,…,an​ (0≤ai​≤109)。

第三行输入包含一个整数 𝑞 (1≤𝑞≤2×105)q (1≤q≤2×105)。

接下来的 𝑞q 行,每行描述一个操作,格式见题目描述。对于第一类操作,保证 −109≤𝑥≤109−109≤x≤109。

Output

对于每个询问输出一行一个整数,如果查询符合要求输出 1,否则输出 0

 

解析:

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<int, 4> state;
const int MAXN = 200000+5;
ll a[MAXN], b[MAXN];
state tr[MAXN<<2]; //线段树开4倍 
int n, q;
state unite(state a, state b){state tmp;tmp[0] = a[0] & b[0];tmp[1] = a[1] & b[1];tmp[2] = a[2] & b[2];tmp[3] = (a[1] & b[2]) | (a[1] & b[3]) | (a[3] & b[2]);return tmp;
}
void up(int x){tr[x] = unite(tr[x<<1], tr[x<<1|1]);
}
void build(int p,int l,int r){if(l==r){if (b[l] == 0) tr[p][0] = 1;else if (b[l] > 0) tr[p][1] = 1;else tr[p][2] = 1;return;}int mid=r+l>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);up(p);
}
void update(int p,int l,int r,int x,int v){if(l==r&l==x){b[l]+=v;if (b[l] == 0) tr[p][0] = 1;else if (b[l] > 0) tr[p][1] = 1;else tr[p][2] = 1;return;}int mid=l+r>>1;if(x<=mid) update(p<<1,l,mid,x,v);else update(p<<1|1,mid+1,r,x,v);up(p);
}
state query(int p,int l,int r,int L,int R){ //现在:l,r 要查:L,R;if(l>=L&&r<=R){return {tr[p][0], tr[p][1], tr[p][2], tr[p][3]};}int mid=l+r>>1;if(R<=mid) return query(p<<1,l,mid,L,R);else if(L>mid) return query(p<<1|1,mid+1,r,L,R);else{state left=query(p<<1,l,mid,L,R);state rigth=query(p<<1,l,mid,L,R);return unite(left,rigth);}
}
int main(){cin >> n;for(int i = 1; i <= n; i++){cin >> a[i];b[i] = a[i] - a[i-1];}build(1, 2, n);cin >> q;while(q--){int op, l, r, x;cin >> op >> l >> r;if(op == 1){cin >> x;if(l > 1) update(1, 2, n, l, x);if(r < n) update(1, 2, n, r+1, -x);} else if(op == 2){if(l == r){cout << "1\n";continue;}cout <<query(1,2,n,l+1,r)[0]<<endl;}else if(op==3){if(l == r){cout << "1\n";continue;}cout <<query(1,2,n,l+1,r)[1]<<endl;}else if(op==4){if(l == r){cout << "1\n";continue;}cout <<query(1,2,n,l+1,r)[2]<<endl;}else{cout <<query(1,2,n,l+1,r)[3]<<endl;}}return 0;
}

1008比特跳跃

Problem Description

比特国由 nn 个城市组成,编号为 1,2,⋯,n1,2,⋯,n。

有 mm 条双向道路连接这些城市,第 ii 条连通城市 uiui​ 和城市 vivi​,通过这条道路需要花费 titi​ 的时间。

此外,比特国的人们还可以使用“比特跳跃“来通行于任意两个城市之间。

从城市 xx 通过比特跳跃移动到城市 yy 需要花费 k×(x∣y)k×(x∣y) 的时间,其中 ∣∣ 表示按位或。比特跳跃可以使用任意多次。

现在请你计算出,从 11 号城市移动到每个城市所需的最短时间。

Input

第一行一个整数 t (1≤t≤15)t (1≤t≤15),代表数据组数。

对于每组数据:

第一行三个整数 n,m,k (2≤n≤105,0≤m≤105,0≤k≤106)n,m,k (2≤n≤105,0≤m≤105,0≤k≤106),代表城市个数,道路条数,比特跳跃的系数。

接下来 mm 行,每行三个整数 ui,vi,ti (1≤ui,vi≤n,0≤ti≤109)ui​,vi​,ti​ (1≤ui​,vi​≤n,0≤ti​≤109) ,代表一条道路的信息。

保证所有测试数据的 ∑n≤106,∑m≤106∑n≤106,∑m≤106 。

Output

对于每组数据,输出一行 n−1n−1 个整数,代表从 11 号城市移动到编号为 2,3,…,n2,3,…,n 的城市所需的最短时间。

解析:

代码:

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+5;
struct point{int id,val;  //起始点到该点当前的距离 bool operator <(const point &n1)const{return val>n1.val;   //从小到大     } 
};
priority_queue<point>q;
int h[N],v[2*N],ne[2*N],w[2*N];
int vist[N],ans[N]; //是否收录进最优路线,起始点到该点当前的距离;
int idx; //从1开始 
int mind[N];
void add(int a,int b,int c){ne[++idx]=h[a];	h[a]=idx; v[idx]=b; w[idx]=c;
}
int lowbit(int i){return i&(-i);
}
int main(){
//	freopen("D:\\1008(4).txt","w",stdout);int t; cin>>t;while(t--){memset(ans,0x3f,sizeof(ans));memset(vist,0,sizeof(vist));int n,m,k; scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c);add(b,a,c);}for(int j=2;j<=n;++j) add(1,j,1ll*k*(1|j));q.push({1,0});while(q.size()){point tp=q.top(); q.pop();if(vist[tp.id]) continue;vist[tp.id]=1;ans[tp.id]=tp.val;for(int i=h[tp.id];i;i=ne[i])if(ans[tp.id]+w[i]<ans[v[i]]){ans[v[i]]=ans[tp.id]+w[i];q.push({v[i],ans[v[i]]});}}printf("%d ",ans[2]);for(int i=3;i<=n;i++)printf("%d ",ans[i]);printf("\n");for(int i=1;i<=n;i++) mind[i]=ans[i];for(int i=2;i<=n;i++){if(i==lowbit(i)) continue;for(int j=1;j<=n;j<<=1)if (i&j) mind[i]=min(mind[i],mind[i^j]);if(mind[i]+1ll*k*i<ans[i]) ans[i]=mind[i]+1ll*k*i;}for (int i=1;i<=n;++i) vist[i]=0, q.push({i,ans[i]});while(q.size()){point tp=q.top(); q.pop();if(vist[tp.id]) continue;vist[tp.id]=1;ans[tp.id]=tp.val;for(int i=h[tp.id];i;i=ne[i])if(ans[tp.id]+w[i]<ans[v[i]]){ans[v[i]]=ans[tp.id]+w[i];q.push({v[i],ans[v[i]]});}}printf("%d ",ans[2]);for(int i=3;i<=n;i++)printf("%d ",ans[i]);printf("\n");}
}

1011 抓拍

Problem Description

学校里有 𝑛n 名同学,初始时第 𝑖i 位同学从 (𝑥𝑖,𝑦𝑖)(xi​,yi​) 出发,以每秒 11 米的速度散步。

同学们散步的方向有东南西北四种可能。假设有一位同学正在位于 (0,0)(0,0),则下一秒︰

  • 如果向东走,到达 (1,0)(1,0)
  • 如果向西走,到达 (−1,0)(−1,0)
  • 如果向南走,到达 (0,−1)(0,−1)
  • 如果向北走,到达 (0,1)(0,1)

假设散步过程会进行无限长的时间,同学们散步的方向不会改变,并且忽略碰撞的情况(允许某个时刻多人在同一个点,互不影响)。

现在你可以选择某个非负整数秒时刻抓拍照片。

一张照片可以用长方形 ((𝑒,𝑛),(𝑤,𝑠))((e,n),(w,s)) 表示,东北角为 (𝑒,𝑛)(e,n),西南角为 (𝑤,𝑠)(w,s)。

只有抓拍的照片包含了所有同学时,我们才称这张照片是完美的。

请选择某个时刻抓拍一张完美的照片,使得照片的周长最小。

Input

第一行一个整数 𝑛 (1≤𝑛≤2×105)n (1≤n≤2×105),代表人数。

接下来 𝑛n 行,第 𝑖i 行包含两个整数 𝑥𝑖,𝑦𝑖 (−109≤𝑥𝑖,𝑦𝑖≤109)xi​,yi​ (−109≤xi​,yi​≤109) 和一个字符 𝑑𝑖di​ ,由空格分隔,描述第 𝑖i 位同学。

𝑑𝑖di​ 是 'E', 'W', 'S', 'N' 之一,分别代表第 𝑖i 位同学散步的方向是东、西、南、北。

Output

输出一行一个整数,代表最短的完美照片的周长。

解析:

三分法:时间复杂度是log(1.5)^(n);求单峰函数的最值。

当n=1e9时log(1.5)^(n)=50;log(2)^(n)=30;

核心代码:

代码:

#include<iostream>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int x[N],y[N],fid[N];
int fx[4]={1,-1,0,0};
int fy[4]={0,0,-1,1};
int n;
ll check(ll t){ll mxx,mxy,mnx,mny;mxx=mxy=-0x3f3f3f,mnx=mny=0x3f3f3f;for(int i=1;i<=n;i++){ll tpx=x[i]+t*fx[fid[i]],tpy=y[i]+t*fy[fid[i]];mxx=max(mxx,tpx);mxy=max(mxy,tpy);mnx=min(mnx,tpx);mny=min(mny,tpy);}return (mxx-mnx)+(mxy-mny);
}
int main(){cin>>n;for(int i=1;i<=n;i++){char op;scanf("%d%d %c",&x[i],&y[i],&op);if(op=='E') fid[i]=0;else if(op=='W') fid[i]=1;else if(op=='S') fid[i]=2;else fid[i]=3;}ll l=0,r=2e9;ll tpl,tpr;while(l<=r){tpl=l+(r-l)/3,tpr=r-(r-l)/3;if(check(tpl)<=check(tpr)) r=tpr-1;else l=tpl+1;} printf("%lld",2*check(l));return 0;
}

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

相关文章:

  • python 线程池处理文件
  • AI技术和大模型对人才市场的影响
  • 解释“location”和“position”
  • Netty 必知必会(三)—— ByteBuf
  • 芋道以开源之名行下作之事 恬不知耻 标榜自己开源 公开源码+sql 不用再加入知识星球
  • wordpress中,wp_posts 文章的状态 有哪些,分别对应什么数值
  • 输入成绩问题(c语言)
  • 基于域名+基于ip+基于端口的虚拟主机+上线商务系统
  • vue每次路由跳转前将页面滚动到顶部
  • 【Qt】QDateTimeEdit
  • Redis和Mysql如何保持数据一致性
  • Java中Optional相关
  • AI在HR候选人关系管理中的革新应用
  • HTML+CSS+JavaScript制作七夕表白网页(含音乐+自定义文字+烟花特效)
  • 【Python机器学习系列】一文教你实现决策树模型可视化(案例+源码)
  • 如何在Python中使用网页抓取API获得Google搜索结果
  • Postman高频面试题及答案汇总(接口测试必备)
  • JavaEE 初阶(13)——多线程11之“定时器”
  • 2024最新全开源付费进群系统源码二开修复版 支持易支付
  • 【奥顺苹果CMS二开泛目录4.X版】PHP站群程序新增首页堆砌关键词新增四套seo模板
  • day06 项目实践:router,axios
  • ⌈ 传知代码 ⌋ 基于矩阵乘积态的生成模型
  • 软件测试必备技能
  • TL3568编译uboot报错
  • qiankun 微前端 隔离子应用样式,解决 ant-design-vue 子应用样式污染问题(已落地)
  • 一个前后端分离架构的低代码开发平台,支持微服务架构,支持开发SAAS项目(附源码)
  • whisper+whisperx ASR加对齐
  • 【已解决】YOLOv8加载模型报错:super().__init__(torch._C.PyTorchFileReader(name_or_buffer))
  • 中国象棋 纯网页前端 演示与下载
  • 学习大数据DAY29 python基础语法2