noip模擬38
\(\color{white}{\mathbb{深秋總有廖落處，雁歸每是菊敗時，名之以：殘菊}}\)
這場比賽幾乎全場都在打暴力，幾乎人均切掉的 \(t1\) 沒有想到雙指針，\(t3\) 的暴力也沒記憶化而太過暴力
A. a
很容易想到同時枚舉兩行，然后算列的貢獻
考場上只想到用數狀數組維護，但是很顯然 \(down\) 和 \(up\) 兩條線之間區域的邊界是單調的，雙指針維護即可
B.b
考慮對于每個 \(i\) 計算 \(i|gcd\) 的方案數，設每一組是 \(i\) 的倍數的數有 \(cnt_j\) 個，答案為 \(\prod (cnt_j+1)-1\)
但是此時每個 \(i\) 保存的是其所有倍數的值之和，那么考慮倒序枚舉所有數，其實大于當前數的所有數已經還原成 \(i=gcd\) 的值，那么用當前數的值減去所有倍數的值即可
C.c
一開始沒看見去重后是棵樹……
首先每條邊都有多種候選顏色，但只保留三種即可，即和上一個不重，和下一個不重
考慮點分治，從分治中心開始 \(dp\)，設 \(f[i][0/1/2][0/1/2]\) 表示從中心到第 \(i\) 個點，路徑上第一條邊的顏色為第幾種，最后一條邊的顏色是第幾種的最大價值
然后寫棵點分樹把詢問掛在點分樹上的 \(lca\) 就好了
代碼實現
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int maxm=1e6+5;
int hd[maxn],cnt,from[maxn],las[maxn],f[maxn][5][5],n,m,q,xx[maxn],yy[maxn],fa[maxn],fa1[maxn],dep[maxn],siz[maxn],rt,maxx[maxn],x,y,w,sum,sta[maxn],tp;
bool del[maxn];
vector<pair<int,int> >has[maxn];
map<pair<int,int>,int>ans,mp;
int read(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
struct Edge{
int nxt,to,val[4];
int numval;
}edge[maxm];
void add(int u,int v,int w){
edge[++cnt].nxt=hd[u];
edge[cnt].to=v;
edge[cnt].val[++edge[cnt].numval]=w;
hd[u]=cnt;
return ;
}
void dfs_w(int u,int father){
siz[u]=1;
maxx[u]=0;
for(int i=hd[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==father||del[v])continue;
dfs_w(v,u);
siz[u]+=siz[v];
maxx[u]=max(maxx[u],siz[v]);
}
maxx[u]=max(maxx[u],sum-siz[u]);
if(maxx[u]<maxx[rt])rt=u;
return ;
}
void dfs_dis(int u,int father,int last,int num){
// cout<<u<<" "<<father<<" "<<last<<" "<<num<<endl;
sta[++tp]=u;
from[u]=num;
las[u]=last;
for(int i=hd[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==father||del[v])continue;
for(int j=1;j<=edge[num].numval;j++){
for(int k=1;k<=edge[last].numval;k++){
for(int p=1;p<=edge[i].numval;p++){
f[v][j][p]=max(f[v][j][p],f[u][j][k]+(edge[last].val[k]!=edge[i].val[p]));
}
}
}
dfs_dis(v,u,i,num);
}
return ;
}
void calc(int u){
// cout<<u<<endl;
tp=0;
for(int i=hd[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(del[v])continue;
for(int j=1;j<=edge[i].numval;j++)f[v][j][j]=1;
dfs_dis(v,u,i,i);
}
for(int i=0;i<has[u].size();i++){
int x=has[u][i].first,y=has[u][i].second,mx=0;
// if(u==4)cout<<x<<" "<<y<<endl;
if(y==u)swap(x,y);
if(x==u){
for(int j=1;j<=edge[from[y]].numval;j++){
for(int k=1;k<=edge[las[y]].numval;k++){
mx=max(mx,f[y][j][k]);
}
}
ans[has[u][i]]=mx;
continue;
}
for(int j=1;j<=edge[from[x]].numval;j++){
for(int k=1;k<=edge[from[y]].numval;k++){
for(int l=1;l<=edge[las[x]].numval;l++){
for(int r=1;r<=edge[las[y]].numval;r++){
mx=max(mx,f[x][j][l]+f[y][k][r]-(edge[from[x]].val[j]==edge[from[y]].val[k]));
}
}
}
}
ans[has[u][i]]=mx;
}
// for(int i=1;i<=tp;i++)cout<<sta[i]<<" ";
// cout<<endl;
for(int i=1;i<=tp;i++){
for(int j=1;j<=3;j++){
for(int k=1;k<=3;k++){
// if(u==4)cout<<sta[i]<<" "<<edge[from[sta[i]]].val[j]<<" "<<edge[las[sta[i]]].val[k]<<" "<<f[sta[i]][j][k]<<endl;
f[sta[i]][j][k]=0;
}
}
}
return ;
}
void solve(int u){
// cout<<" "<<u<<endl;
del[u]=true;
calc(u);
for(int i=hd[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(del[v])continue;
rt=0;
maxx[rt]=sum=siz[v];
dfs_w(v,u);
solve(rt);
}
return ;
}
void solve0(int u){
// cout<<u<<endl;
del[u]=true;
// calc(u);
for(int i=hd[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(del[v])continue;
rt=0;
maxx[rt]=sum=siz[v];
dfs_w(v,u);
fa1[rt]=u;
dep[rt]=dep[u]+1;
solve0(rt);
}
return ;
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
while(dep[x]!=dep[y]){
x=fa1[x];
}
while(x!=y){
x=fa1[x];
y=fa1[y];
}
return x;
}
int main(){
// freopen("c0_1.in","r",stdin);
n=read();
m=read();
// memset(f,-1,sizeof f);
for(int i=1;i<=m;i++){
x=read();
y=read();
w=read();
if(mp.find(make_pair(x,y))==mp.end())mp[make_pair(x,y)]=mp[make_pair(y,x)]=cnt+1,add(x,y,w),add(y,x,w);
else{
int id=mp[make_pair(x,y)];
if(edge[id].numval<=2&&edge[id].val[1]!=w&&edge[id].val[2]!=w){
edge[id].val[++edge[id].numval]=w;
}
id++;
if(edge[id].numval<=2&&edge[id].val[1]!=w&&edge[id].val[2]!=w){
edge[id].val[++edge[id].numval]=w;
}
}
}
// for(int i=1;i<=cnt;i+=2){
// cout<<edge[i].to<<" "<<edge[i+1].to<<" "<<edge[i].val[1]<<" "<<edge[i].val[2]<<" "<<edge[i].val[3]<<endl;
// }
maxx[rt]=sum=n;
dfs_w(1,0);
// cout<<"ppp "<<rt<<endl;
solve0(rt);
// for(int i=1;i<=n;i++){
// cout<<fa1[i]<<" ";
// }
q=read();
for(int i=1;i<=q;i++){
xx[i]=read();
yy[i]=read();
// cout<<" "<<lca(xx[i],yy[i])<<endl;
has[lca(xx[i],yy[i])].push_back(make_pair(xx[i],yy[i]));
}
memset(del,0,sizeof del);
memset(maxx,0,sizeof maxx);
memset(siz,0,sizeof siz);
rt=0;
// cout<<"hhh"<<endl;
maxx[rt]=sum=n;
dfs_w(1,0);
solve(rt);
for(int i=1;i<=q;i++){
printf("%d\n",ans[make_pair(xx[i],yy[i])]);
}
return 0;
}
\(\color{white}{\mathbb{不是花中偏愛菊，此花開盡更無花。}}\)
浙公網安備 33010602011771號