A - 小蒟和他的樂譜

簽到題，將原序列對 7 取模之后將序列掃描一遍就可以得到答案
不過感覺題目意思還需要理解理解

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const ll mod=998244353; const int N=1000010; int a[N]; int n; int main() {IO;int T=1;//cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int res=0;int now=0;for(int i=1;i<=n;i++){int x=(a[i]%7+7)%7;if(x==1||x==2||x==3||x==5||x==6) {now++;res=max(res,now);}else now=0;}cout<<res<<'\n';}return 0; }

B - 小琛和他的學(xué)校

之前打cf的時候有一個類似的題目，這次就會了hh
維護(hù)sz[u]表示u子樹子節(jié)點(diǎn)的數(shù)量，cnt[u]表示u子樹學(xué)生的總數(shù)，然后考慮每條邊對答案的貢獻(xiàn)（之前cf求的是所有代價和這題求得每條邊的代價還給了一個提示）
這條邊分成兩個連通塊$i,j$，那么代價即為$i$連通塊的人跑到$j$連通塊的校區(qū)和$j$連通塊的人跑到$i$連通塊的校區(qū)注意來回路程要乘二

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const ll mod=998244353; const int N=200010; ll sz[N],cnt[N]; int n; ll ans[2*N]; int h[N],e[2*N],ne[2*N],idx; ll w[2*N]; void add(int a,int b,ll c) {e[idx]=b;ne[idx]=h[a];w[idx]=c;h[a]=idx++; } void dfs1(int u,int fa) {sz[u]=1;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dfs1(j,u);sz[u]+=sz[j];cnt[u]+=cnt[j];} } void dfs2(int u,int fa) {for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dfs2(j,u);ans[i]=ans[i^1]=2ll*(cnt[j]*(n-sz[j])+(cnt[1]-cnt[j])*sz[j])*w[i];} } int main() {IO;int T=1;//cin>>T;while(T--){memset(h,-1,sizeof h);cin>>n;for(int i=1;i<=n;i++) cin>>cnt[i];for(int i=1;i<n;i++){int a,b;ll c;cin>>a>>b>>c;add(a,b,c);add(b,a,c);}dfs1(1,-1);dfs2(1,-1);for(int i=0;i<2*n-2;i+=2) cout<<ans[i]<<'\n';}return 0;}

C - 小魂和他的數(shù)列

很明顯的dp題
狀態(tài)表示：$f_{(i,j)}$表示考慮前$i$個數(shù)，以第$i$個數(shù)結(jié)尾目前長度是$j$的嚴(yán)格遞增的數(shù)目
狀態(tài)轉(zhuǎn)移：$f_{(i,j)}={\sum }_{k=1}^{i?1}{f}_{(k,j?1)}(a_k<a_i)$
只需要用樹狀數(shù)組優(yōu)化轉(zhuǎn)移即可。
注意離散化
這幾天遇到了好多線段樹或者樹狀數(shù)組優(yōu)化dp的題目

// O(nlogn) #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const ll mod=998244353; const int N=500010; int a[N]; ll f[N][11]; int n,m; ll tree[11][N]; vector<int> da; int lowbit(int x) {return x&-x; } void modify(ll tree[],int k,ll x) {for(;k<=n;k+=lowbit(k)) tree[k]=(tree[k]+x)%mod; } ll query(ll tree[],int k) {ll res=0;for(;k;k-=lowbit(k)) res=(res+tree[k])%mod;return res; } int find(int x) {return lower_bound(da.begin(),da.end(),x)-da.begin()+1; } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++) {cin>>a[i];da.push_back(a[i]);}// 離散化sort(da.begin(),da.end());da.erase(unique(da.begin(),da.end()),da.end());//初始化for(int i=1;i<=n;i++) f[i][1]=1;for(int i=1;i<=n;i++){int x=find(a[i]);for(int j=1;j<=m;j++){f[i][j]+=query(tree[j-1],x-1);modify(tree[j],x,f[i][j]);}}ll res=0;for(int i=1;i<=n;i++) res=(res+f[i][m])%mod;cout<<res<<'\n';}return 0;}

D - 小翔和泰拉瑞亞

剛開始想的是最大值不變，只要區(qū)間不會讓最大值變小就施展魔法，否則不施展魔法，于是就寫了個區(qū)間最小、大值區(qū)修區(qū)間修改線段樹，但是很明顯該貪心策略不對。

看了下題解后正解是：枚舉最小值，如果枚舉$i$個數(shù)是最小值，那么只要施展魔法的區(qū)間包括第$i$個點(diǎn)就施展（使之盡可能小），可以把詢問拆開排序，按照掃描線的思路取±區(qū)間，枚舉最值即可。

線段樹只需要支持區(qū)間修改單點(diǎn)詢問即可，由于我再寫一遍就用的我錯誤思路的線段樹

//O(nlogn) #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #define x first #define y second using namespace std; typedef long long ll; typedef pair<int,int> pii; const ll INF=1e17; const int N=200010; int a[N]; int n,m; struct node1 {int l,r;ll mn,mx;ll lazy; }tree[N<<2]; struct node2 {int op;int p;int l,r;ll w;bool operator <(const node2& o)const {return p<o.p;}}q[2*N]; void pushup(int u) {tree[u].mn=min(tree[u<<1].mn,tree[u<<1|1].mn);tree[u].mx=max(tree[u<<1].mx,tree[u<<1|1].mx); } void build(int u,int l,int r) {tree[u]={l,r,INF,-INF,0};if(l==r) {tree[u].mn=tree[u].mx=a[l];return;}int mid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u); } void pushdown(int u) {if(tree[u].lazy==0) return;tree[u<<1].lazy+=tree[u].lazy;tree[u<<1|1].lazy+=tree[u].lazy;tree[u<<1].mx+=tree[u].lazy;tree[u<<1].mn+=tree[u].lazy;tree[u<<1|1].mx+=tree[u].lazy;tree[u<<1|1].mn+=tree[u].lazy;tree[u].lazy=0; } void modify(int u,int l,int r,int x) {if(tree[u].l>=l&&tree[u].r<=r){tree[u].mn+=x;tree[u].mx+=x;tree[u].lazy+=x;return;}pushdown(u);int mid=tree[u].l+tree[u].r>>1;if(l<=mid) modify(u<<1,l,r,x);if(r>mid) modify(u<<1|1,l,r,x);pushup(u); } ll query(int u,int l,int r,int op) {//if(l>r) return op==1?INF:-INF;if(tree[u].l>=l&&tree[u].r<=r) return op==1?tree[u].mn:tree[u].mx;pushdown(u);int mid=tree[u].l+tree[u].r>>1;ll v=op==1?INF:-INF;if(l<=mid) op==1?v=min(v,query(u<<1,l,r,op)):v=max(v,query(u<<1,l,r,op));if(r>mid) op==1?v=min(v,query(u<<1|1,l,r,op)):v=max(v,query(u<<1|1,l,r,op));return v; } int main() {IO;int T=1;//cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];build(1,1,n);for(int i=1;i<=m;i++) {int l,r,w;cin>>l>>r>>w;q[i]={-1,l,l,r,w};// l點(diǎn)加入該魔法q[i+m]={1,r+1,l,r,w};// r+1點(diǎn)刪去該魔法}m=2*m;sort(q+1,q+1+m);ll res=-INF;for(int i=1,j=1;i<=n;i++){while(j<=m&&q[j].p==i){modify(1,q[j].l,q[j].r,q[j].op*q[j].w);j++;}res=max(res,tree[1].mx-query(1,i,i,1));}cout<<res<<'\n';}return 0;}

E - 小雀和他的王國

還沒看，這題好像是tarjan的題，好久沒寫tarjan了，明天補(bǔ)了，熟悉熟悉板子——2020/10/07/00:17
板子題啊，求割邊，縮點(diǎn)成樹，然后求樹上直徑即可。1發(fā)AC

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int mod=1e9+7; const int N=200010; int n,m; int qmi(int a,int b,int p) {int res=1;while(b){if(b&1) res=1ll*res*a%p;b>>=1;a=1ll*a*a%p;}return res; }int h1[N],h2[N],ne[4*N],e[4*N],idx; void add(int h[],int a,int b) {e[idx]=b;ne[idx]=h[a];h[a]=idx++; } int dfn[N],low[N],timestamp; bool bdg[2*N]; void tarjan(int u,int f) {dfn[u]=low[u]=++timestamp;for(int i=h1[u];i!=-1;i=ne[i]){int j=e[i];if(!dfn[j]){tarjan(j,i);low[u]=min(low[u],low[j]);if(dfn[u]<low[j]) bdg[i]=bdg[i^1]=1;}else if(i!=(f^1)) low[u]=min(low[u],dfn[j]);} } int id[N],dcnt; void dfs1(int u,int c) {id[u]=c;for(int i=h1[u];i!=-1;i=ne[i]){int j=e[i];if(id[j]||bdg[i]) continue;dfs1(j,c);} } int dist,p; void dfs2(int u,int fa,int d) {for(int i=h2[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;if(dist<d+1){dist=d+1;p=j;}dfs2(j,u,d+1);}} int main() {IO;int T=1;//cin>>T;while(T--){memset(h1,-1,sizeof h1);memset(h2,-1,sizeof h2);cin>>n>>m;for(int i=1;i<=m;i++){int a,b;cin>>a>>b;add(h1,a,b),add(h1,b,a);}tarjan(1,-1);for(int i=1;i<=n;i++)if(!id[i]) dfs1(i,++dcnt);for(int i=0;i<2*m;i+=2){int a=e[i^1],b=e[i];if(id[a]==id[b]) continue;add(h2,id[a],id[b]),add(h2,id[b],id[a]);}dfs2(1,-1,0);dist=0;dfs2(p,-1,0);int res=dcnt-1-dist;res=1ll*res*qmi(m+1,mod-2,mod)%mod;cout<<res<<'\n';}return 0;}

要加油哦~

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛 56 E tarjan 割边的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。