山东省交通厅建设网站首页,网站建设策划书的心得,网站ui设计怎么做,恒佳企划网站建设1001深度自同构
Problem Description
对于无向图中的点#xff0c;定义一个点的度为与其相连的边的条数。
对于一棵有根树#xff0c;定义一个点的深度为该点到根的距离。
对于由若干有根树构成的森林#xff0c;定义该森林是深度自同构的#xff0c;当且仅当森林中任意…1001深度自同构
Problem Description
对于无向图中的点定义一个点的度为与其相连的边的条数。
对于一棵有根树定义一个点的深度为该点到根的距离。
对于由若干有根树构成的森林定义该森林是深度自同构的当且仅当森林中任意两个深度相同的节点都有相同的度。
请计数有多少个深度自同构的无编号有根树森林使得其恰好由 nn 个节点构成答案对 998244353998244353 取模。
Input
一个整数 N (1≤N≤106)N (1≤N≤106)代表计数的范围。
Output
输出一行 NN 个整数第 ii 个数代表 nini 时的答案对 998244353998244353 取模。 标准代码
#includebits/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[j1]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 l r x将 ,1,…,al,al1,…,ar 的每个数加 x。 2 l r判断 ,1,…,al,al1,…,ar 的元素是否全都相同。 3 l r判断 ,1,…,al,al1,…,ar 是否严格升序排序。当 lr 时认为符合严格升序排序。 4 l r判断 ,1,…,al,al1,…,ar 是否严格降序排序。当 lr 时认为符合严格降序排序。 5 l r判断 ,1,…,al,al1,…,ar 是否为单峰数列。保证 −1≥3r−l1≥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 arrayint, 4 state;
const int MAXN 2000005;
ll a[MAXN], b[MAXN];
state tr[MAXN2]; //线段树开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[x1], tr[x1|1]);
}
void build(int p,int l,int r){if(lr){if (b[l] 0) tr[p][0] 1;else if (b[l] 0) tr[p][1] 1;else tr[p][2] 1;return;}int midrl1;build(p1,l,mid);build(p1|1,mid1,r);up(p);
}
void update(int p,int l,int r,int x,int v){if(lrlx){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 midlr1;if(xmid) update(p1,l,mid,x,v);else update(p1|1,mid1,r,x,v);up(p);
}
state query(int p,int l,int r,int L,int R){ //现在l,r 要查L,Rif(lLrR){return {tr[p][0], tr[p][1], tr[p][2], tr[p][3]};}int midlr1;if(Rmid) return query(p1,l,mid,L,R);else if(Lmid) return query(p1|1,mid1,r,L,R);else{state leftquery(p1,l,mid,L,R);state rigthquery(p1,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, r1, -x);} else if(op 2){if(l r){cout 1\n;continue;}cout query(1,2,n,l1,r)[0]endl;}else if(op3){if(l r){cout 1\n;continue;}cout query(1,2,n,l1,r)[1]endl;}else if(op4){if(l r){cout 1\n;continue;}cout query(1,2,n,l1,r)[2]endl;}else{cout query(1,2,n,l1,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 的城市所需的最短时间。 解析 代码
#includeiostream
#includequeue
#includecstring
using namespace std;
const int N1e55;
struct point{int id,val; //起始点到该点当前的距离 bool operator (const point n1)const{return valn1.val; //从小到大 }
};
priority_queuepointq;
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; cint;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 i1;im;i){int a,b,c; scanf(%d%d%d,a,b,c); add(a,b,c);add(b,a,c);}for(int j2;jn;j) add(1,j,1ll*k*(1|j));q.push({1,0});while(q.size()){point tpq.top(); q.pop();if(vist[tp.id]) continue;vist[tp.id]1;ans[tp.id]tp.val;for(int ih[tp.id];i;ine[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 i3;in;i)printf(%d ,ans[i]);printf(\n);for(int i1;in;i) mind[i]ans[i];for(int i2;in;i){if(ilowbit(i)) continue;for(int j1;jn;j1)if (ij) mind[i]min(mind[i],mind[i^j]);if(mind[i]1ll*k*ians[i]) ans[i]mind[i]1ll*k*i;}for (int i1;in;i) vist[i]0, q.push({i,ans[i]});while(q.size()){point tpq.top(); q.pop();if(vist[tp.id]) continue;vist[tp.id]1;ans[tp.id]tp.val;for(int ih[tp.id];i;ine[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 i3;in;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);求单峰函数的最值。
当n1e9时log(1.5)^(n)50;log(2)^(n)30;
核心代码 代码
#includeiostream
using namespace std;
typedef long long ll;
const int N2e55;
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;mxxmxy-0x3f3f3f,mnxmny0x3f3f3f;for(int i1;in;i){ll tpxx[i]t*fx[fid[i]],tpyy[i]t*fy[fid[i]];mxxmax(mxx,tpx);mxymax(mxy,tpy);mnxmin(mnx,tpx);mnymin(mny,tpy);}return (mxx-mnx)(mxy-mny);
}
int main(){cinn;for(int i1;in;i){char op;scanf(%d%d %c,x[i],y[i],op);if(opE) fid[i]0;else if(opW) fid[i]1;else if(opS) fid[i]2;else fid[i]3;}ll l0,r2e9;ll tpl,tpr;while(lr){tpll(r-l)/3,tprr-(r-l)/3;if(check(tpl)check(tpr)) rtpr-1;else ltpl1;} printf(%lld,2*check(l));return 0;
}
