钉耙编程（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;
}