A,B很簡單，跳過了。
C題規律相當明顯，可以直接對\(2^n-1\)打表，也可以不打表直接算最大因數。
D題兩種操作轉化一下DP即可。
E題考慮查分數組不變的性質。
F題考慮dfs時動態維護每個葉子的深度，從一個節點走向它的孩子相當于孩子對應的區間加，不包含孩子的區間減。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=1050000;
const int N=500010;
int u;
ll st[P],tag[P],tg;
void pushup(int x){st[x]=min(st[x<<1],st[x<<1|1])+tag[x];
}
void Add(int s,int t,ll v){int ss=u+s,tt=u+t;for (s+=u-1,t+=u+1; s^t^1; pushup(ss>>=1),pushup(tt>>=1),s>>=1,t>>=1){if (~s&1) st[s^1]+=v,tag[s^1]+=v;if (t&1) st[t^1]+=v,tag[t^1]+=v;}for (s>>=1,t>>=1; s!=t; s>>=1,t>>=1) pushup(s),pushup(t);for (; s; s>>=1) pushup(s);
}
ll ask(int s,int t){ll retl=LLONG_MAX>>1,retr=retl;int ss=u+s,tt=u+t;for (s+=u-1,t+=u+1; s^t^1; retl+=tag[ss>>=1],retr+=tag[tt>>=1],s>>=1,t>>=1){if (~s&1) retl=min(retl,st[s^1]);if (t&1) retr=min(retr,st[t^1]);}for (s>>=1,t>>=1; s!=t; s>>=1,t>>=1) retl+=tag[s],retr+=tag[t];retl=min(retl,retr);for (; s; s>>=1) retl+=tag[s];return retl;
}
int clk,dfn[N],en[N];
vector<pair<int,int> > g[N];
vector<int> a[N];
ll ans[N];
int la[N],ra[N];
void dfs(int x,ll dep){//cerr<<x<<" "<<dep<<endl;dfn[x]=++clk;if (!g[x].size()){st[u+clk]=dep;en[x]=clk;return;}st[u+clk]=LLONG_MAX>>1;for (auto j:g[x])dfs(j.first,dep+j.second);en[x]=clk;
}
void dfs2(int x){for (auto j:a[x]) ans[j]=tg+ask(la[j],ra[j]);for (auto j:g[x]){tg+=j.second;Add(dfn[j.first],en[j.first],-j.second*2);dfs2(j.first);Add(dfn[j.first],en[j.first],j.second*2);tg-=j.second;}
}
int n,q;
int main(){scanf("%d%d",&n,&q);for (int i=2; i<=n; ++i){int x,y;scanf("%d%d",&x,&y);g[x].push_back(make_pair(i,y));}for (u=1; u<n; u<<=1);--u;dfs(1,0);//for (int i=u+1; i<=u+n; ++i) cout<<st[i]<<" "; cout<<endl;for (int i=u+n+1; i<=u+u+1; ++i) st[i]=LLONG_MAX>>1;for (int i=u; i; --i) st[i]=min(st[i<<1],st[i<<1|1]);for (int i=1; i<=q; ++i){int x;scanf("%d%d%d",&x,&la[i],&ra[i]);a[x].push_back(i);}//cerr<<"????"<<endl;dfs2(1);for (int i=1; i<=q; ++i) cout<<ans[i]<<'\n';
}
這個zkw寫得我好惡心，早知道還是寫普通線段樹了。
G題非常神仙，先考慮構造一個
1------2---------3
......... |______4
來代替1這個原有的白點。
然后原圖就沒有染過色的點了。
考慮有度為4的點那么先手必勝。
如果有度為3且第二長的兒子比2長的點，那么先手必勝。
考慮你現在只可能有最多兩個度為3的點了。
只有0或1個3度點，那么是和局。
兩個的話，必定組成一根“骨頭”，分奇偶討論即可。
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > G;
vector<bool> vis;
void aDD(int x,int y){if (x>=G.size()) G.resize(x+1);if (y>=G.size()) G.resize(y+1);G[x].push_back(y);G[y].push_back(x);
}
bool dfs(int x,int len){vis[x]=1;if (G[x].size()>=3&&len&&len%2==0) return 1;for (auto j:G[x])if (!vis[j]&&dfs(j,len+1)) return 1;return 0;
}
int n,t;
string s;
int main(){ios_base::sync_with_stdio(false); cin.tie(NULL);int t; cin>>t;while (t--){cin>>n;G=*(new vector<vector<int> >(2));vis.clear();for (int i=1; i<n; ++i){int u,v;cin>>u>>v;aDD(u,v);}int cnt=n;cin>>s;for (int i=1; i<=n; ++i)if (s[i-1]=='W'){aDD(i,cnt+1);aDD(cnt+1,cnt+2);aDD(cnt+1,cnt+3);cnt+=3;}vis.resize(cnt+1);for (int i=1; i<=cnt; ++i) if (G[i].size()>=4) goto l1;for (int i=1; i<=cnt; ++i)if (G[i].size()>=3){vector<int> v;for (auto j:G[i])v.push_back(G[j].size());sort(v.rbegin(),v.rend());if (v[1]>=2) goto l1;}for (int i=1; i<=cnt; ++i)if (G[i].size()>=3&&dfs(i,0)) goto l1;puts("Draw");continue;l1:puts("White");}
}
H題雖然不那么神仙，但是代碼難度爆炸，錯了也不知道怎么調QAQ
首先每個符合區間限制的數肯定一一對應正則表達式的個數。
于是你只需要統計正則表達式的個數就可以了。
將正則表達式映射到AC自動機上，
DP時在AC自動機上走就行了，同時詢問一下該節點剩余長度匹配的正則表達式個數。
并不需要關心后面具體填了什么，因為只要長度夠，就符合正則表達式。
一堆細節，十分惡心。
#include <bits/stdc++.h>
using namespace std;
const int N=2005;
const int M=805;
const int NODE=M*20;
const int INF=~0u>>1;
int trans[NODE][10],fail[NODE],tot;
int val[NODE][M];
int f[N][NODE];
bool way[N][NODE];
string l,r;
int n,m;
void depth(int now,int p,bool dlim,bool ulim){if (now>=m){//cerr<<"ADD"<<p<<" "<<0<<endl;++val[p][0];return;}if (!dlim&&!ulim){//cerr<<"ADD"<<p<<" "<<m-now<<endl;++val[p][m-now];return;}//cerr<<now<<" "<<l.size()<<" "<<r.size()<<endl;int llim=(dlim?l[now]-'0':0);int rlim=(ulim?r[now]-'0':9);//cerr<<"????"<<llim<<" "<<rlim<<endl;for (int i=max(llim,(int)!now); i<=rlim; ++i){//cerr<<"I"<<p<<" "<<i<<endl;int to=(trans[p][i]?trans[p][i]:trans[p][i]=++tot);//cerr<<"dfs"<<p<<" "<<i<<" "<<to<<endl;depth(now+1,to,dlim&&i==llim,ulim&&i==rlim);//cerr<<"ED"<<endl;}
}
void build_fail(){/*for (int i=0; i<=tot; ++i)for (int j=0; j<=m; ++j)cerr<<i<<" "<<j<<" "<<val[i][j]<<endl;*///cerr<<val[8][2]<<endl;queue<int> q; q.push(0);while (!q.empty()){int x=q.front(); q.pop();//cerr<<x<<" ";for (int i=0; i<=9; ++i){int v=trans[x][i];//cerr<<"BBBBBB"<<x<<" "<<i<<" "<<fail[x]<<" "<<v<<endl;if (v){q.push(v);if (x){fail[v]=trans[fail[x]][i];}for (int i=0; i<=m; ++i)val[v][i]+=val[fail[v]][i];}else trans[x][i]=trans[fail[x]][i];}}for (int i=0; i<=tot; ++i){for (int j=1; j<=m; ++j)val[i][j]+=val[i][j-1];//cerr<<fail[i]<<endl;//for (int j=0; j<=m; ++j)//cout<<i<<" "<<j<<" "<<val[i][j]<<endl;}
}
int main(){//fprintf(stderr,"cfh.in");ios::sync_with_stdio(0);cin>>l>>r>>n;/*for (int i=1; i<=800; ++i) l+="1";for (int i=1; i<=800; ++i) r+="2";n=2000;*/if (l.size()==r.size()){m=r.size();depth(0,0,1,1);}else{int p=m=l.size();depth(0,0,1,0);//cerr<<"END"<<endl;m=r.size();while (l.size()<m) l="0"+l;depth(0,0,0,1);for (int i=p+1; i<m; ++i) ++val[0][i];}//return 0;build_fail();//cerr<<"!!!"<<endl;
//return 0;//return 0;/*for (int i=0; i<=tot; ++i){cerr<<"I----"<<i<<endl;cerr<<"fail"<<fail[i]<<endl;for (int j=0; j<=9; ++j) cerr<<trans[i][j]<<" ";cerr<<endl;}*///return 0;for (int i=0; i<=n; ++i)for (int j=0; j<=tot; ++j)f[i][j]=-INF;f[0][0]=val[0][min(n,m)];for (int i=0; i<n; ++i){for (int j=0; j<=tot; ++j){for (int k=0; k<=9; ++k){int v=trans[j][k];f[i+1][v]=max(f[i+1][v],f[i][j]+val[v][min(n-i-1,m)]);//cerr<<"dp"<<i+1<<" "<<v<<" "<<f[i+1][v]<<" "<<f[0][0]<<" "<<val[v][min(n-i-1,m)]<<" "<<j<<endl;}}}int ans=0;for (int i=0; i<=tot; ++i) ans=max(ans,f[n][i]);cout<<ans<<'\n';for (int i=0; i<=tot; ++i) way[n][i]=(f[n][i]==ans);for (int i=n-1; i>=0; --i)for (int j=0; j<=tot; ++j){for (int k=0; k<=9; ++k){int v=trans[j][k];if (way[i+1][v]&&f[i+1][v]==f[i][j]+val[v][min(n-i-1,m)]){way[i][j]=1;break;}}}int now=0,len=0;while (len<n){for (int k=0; k<=9; ++k){int v=trans[now][k];if (way[len+1][v]&&f[len+1][v]==f[len][now]+val[v][min(n-len-1,m)]){now=v;cout<<k;break;}}++len;}
}
轉載于:https://www.cnblogs.com/Yuhuger/p/10420898.html
總結
以上是生活随笔為你收集整理的codeforces global round 1题解搬运的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
