1001深度自同構(gòu)

Problem Description

對于無向圖中的點，定義一個點的度為與其相連的邊的條數(shù)。

對于一棵有根樹，定義一個點的深度為該點到根的距離。

對于由若干有根樹構(gòu)成的森林，定義該森林是深度自同構(gòu)的，當且僅當森林中任意兩個深度相同的節(jié)點都有相同的度。

請計數(shù)有多少個深度自同構(gòu)的無編號有根樹森林，使得其恰好由?nn?個節(jié)點構(gòu)成，答案對?998244353998244353?取模。

Input

一個整數(shù)?N?(1≤N≤106)N?(1≤N≤106)，代表計數(shù)的范圍。

Output

輸出一行?NN?個整數(shù)，第?ii?個數(shù)代表?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 單峰數(shù)列

Problem Description

對于一個整數(shù)數(shù)列，如果其先嚴格遞增，然后在某一點后嚴格遞減，我們稱這個數(shù)列為單峰數(shù)列（嚴格遞增和嚴格遞減的部分均要是非空）。

給定長度為?𝑛n?的整數(shù)數(shù)列?𝑎1,𝑎2,…,𝑎𝑛a1?,a2?,…,an??，請你支持?𝑞q?次操作：

1. 1 l r x：將?𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟al?,al+1?,…,ar??的每個數(shù)加?𝑥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??是否為單峰數(shù)列。保證?𝑟?𝑙+1≥3r?l+1≥3。

Input

第一行輸入包含一個整數(shù)?𝑛?(3≤𝑛≤105)n?(3≤n≤105)。

第二行輸入包含?𝑛n?個整數(shù)?𝑎1,𝑎2,…,𝑎𝑛?(0≤𝑎𝑖≤109)a1?,a2?,…,an??(0≤ai?≤109)。

第三行輸入包含一個整數(shù)?𝑞?(1≤𝑞≤2×105)q?(1≤q≤2×105)。

接下來的?𝑞q?行，每行描述一個操作，格式見題目描述。對于第一類操作，保證??109≤𝑥≤109?109≤x≤109。

Output

對于每個詢問輸出一行一個整數(shù)，如果查詢符合要求輸出?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){ //現(xiàn)在：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)?的時間，其中?∣∣?表示按位或。比特跳躍可以使用任意多次。

現(xiàn)在請你計算出，從?11?號城市移動到每個城市所需的最短時間。

Input

第一行一個整數(shù)?t?(1≤t≤15)t?(1≤t≤15)，代表數(shù)據(jù)組數(shù)。

對于每組數(shù)據(jù)：

第一行三個整數(shù)?n,m,k?(2≤n≤105,0≤m≤105,0≤k≤106)n,m,k?(2≤n≤105,0≤m≤105,0≤k≤106)，代表城市個數(shù)，道路條數(shù)，比特跳躍的系數(shù)。

接下來?mm?行，每行三個整數(shù)?ui,vi,ti?(1≤ui,vi≤n,0≤ti≤109)ui?,vi?,ti??(1≤ui?,vi?≤n,0≤ti?≤109)?，代表一條道路的信息。

保證所有測試數(shù)據(jù)的?∑n≤106,∑m≤106∑n≤106,∑m≤106?。

Output

對于每組數(shù)據(jù)，輸出一行?n?1n?1?個整數(shù)，代表從?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]; //是否收錄進最優(yōu)路線，起始點到該點當前的距離；
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

學(xué)校里有?𝑛n?名同學(xué)，初始時第?𝑖i?位同學(xué)從?(𝑥𝑖,𝑦𝑖)(xi?,yi?)?出發(fā)，以每秒?11?米的速度散步。

同學(xué)們散步的方向有東南西北四種可能。假設(shè)有一位同學(xué)正在位于?(0,0)(0,0)，則下一秒︰

• 如果向東走，到達?(1,0)(1,0)
• 如果向西走，到達?(?1,0)(?1,0)
• 如果向南走，到達?(0,?1)(0,?1)
• 如果向北走，到達?(0,1)(0,1)

假設(shè)散步過程會進行無限長的時間，同學(xué)們散步的方向不會改變，并且忽略碰撞的情況（允許某個時刻多人在同一個點，互不影響）。

現(xiàn)在你可以選擇某個非負整數(shù)秒時刻抓拍照片。

一張照片可以用長方形?((𝑒,𝑛),(𝑤,𝑠))((e,n),(w,s))?表示，東北角為?(𝑒,𝑛)(e,n)，西南角為?(𝑤,𝑠)(w,s)。

只有抓拍的照片包含了所有同學(xué)時，我們才稱這張照片是完美的。

請選擇某個時刻抓拍一張完美的照片，使得照片的周長最小。

Input

第一行一個整數(shù)?𝑛?(1≤𝑛≤2×105)n?(1≤n≤2×105)，代表人數(shù)。

接下來?𝑛n?行，第?𝑖i?行包含兩個整數(shù)?𝑥𝑖,𝑦𝑖?(?109≤𝑥𝑖,𝑦𝑖≤109)xi?,yi??(?109≤xi?,yi?≤109)?和一個字符?𝑑𝑖di??，由空格分隔，描述第?𝑖i?位同學(xué)。

𝑑𝑖di??是 'E', 'W', 'S', 'N' 之一，分別代表第?𝑖i?位同學(xué)散步的方向是東、西、南、北。

Output

輸出一行一個整數(shù)，代表最短的完美照片的周長。

解析：

三分法：時間復(fù)雜度是log(1.5)^(n);求單峰函數(shù)的最值。

當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;
}