今日得分:20+20+70
T1
題目大意：
題解：
然而，我成功地調了一天這個代碼，死活跑不過去，隨機資料下表現還挺優異，最終要了資料發現跑的次數不對，定睛一看，發現……
原代碼：
bool operator <(que x,que y){if(gx[x.l]!=gx[y.l])return dfn1[gx[x.l]]<dfn1[gx[y.l]];return dfn2[gx[x.r]]<dfn2[gx[y.r]];}改后代碼：
bool operator <(que x,que y){if(gx[x.l]!=gx[y.l])return dfn1[gx[x.l]]<dfn1[gx[y.l]];return dfn2[x.r]<dfn2[y.r];}……
AC代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
inline int re_ad()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
return x*f;
}
inline int ma(int x,int y){return x>y?x:y;}
inline int mi(int x,int y){return x<y?x:y;}
int T,n,m;
vector<int> g1[51000],g2[51000];
int fa1[51000],fa2[51000],f[51000],ans,r[51000],sc[51000],an[51000];
int dep1[51000],dep2[51000],D,dfn1[51000],dfn2[51000],tot,gx[51000],ann;
bool vis[51000],used1[51000],used2[51000];
struct node{int x,y;}e1[51000],e2[51000];
struct nod{int x,r;}z[111111];int top;
struct que{int l,r;}xw[51000];
bool operator <(que x,que y){if(gx[x.l]!=gx[y.l])return dfn1[gx[x.l]]<dfn1[gx[y.l]];return dfn2[x.r]<dfn2[y.r];}
void dfs1(int x)
{
register int i,sz=g1[x].size(),v;
sc[x]=0;vis[x]=false;dfn1[x]=++tot;
for(i=0;i<sz;++i)
{
v=g1[x][i];if(v==fa1[x])continue;
dep1[v]=dep1[x]+1;fa1[v]=x;dfs1(v);sc[x]=ma(sc[x],sc[v]+1);
}
if(sc[x]==D){vis[x]=true;sc[x]=0;}
}
void dfs2(int x)
{
register int i,sz=g2[x].size(),v;
dfn2[x]=++tot;
for(i=0;i<sz;++i)
{
v=g2[x][i];if(v==fa2[x])continue;
dep2[v]=dep2[x]+1;fa2[v]=x;dfs2(v);
}
}
void cx1(int x,int to)
{
if(used1[x])
{
used1[x]=false;
r[f[z[top].x]]-=z[top].r;
f[z[top].x]=z[top].x;
--top;++ans;
}++ann;
if(x!=to)cx1(fa1[x],to);
}
void cx2(int x,int to)
{
if(used2[x])
{
used2[x]=false;
r[f[z[top].x]]-=z[top].r;
f[z[top].x]=z[top].x;
--top;++ans;
}++ann;
if(x!=to)cx2(fa2[x],to);
}
int find(int x){return x==f[x]?f[x]:find(f[x]);}
void jr1(int x,int to)
{//cout<<x<<" "<<to<<endl;
if(x!=to)jr1(fa1[x],to);++ann;
{
int fx=find(e1[x].x),fy=find(e1[x].y);
if(fx!=fy)
{
used1[x]=true;--ans;
if(r[fx]<=r[fy])f[fx]=fy,z[++top].x=fx;else f[fy]=fx,z[++top].x=fy;
if(r[fx]==r[fy])++r[fy],z[top].r=1;else z[top].r=0;
}
}
}
void jr2(int x,int to)
{//cout<<x<<" "<<to<<endl;
if(x!=to)jr2(fa2[x],to);++ann;
{
int fx=find(e2[x].x),fy=find(e2[x].y);
if(fx!=fy)
{
used2[x]=true;--ans;
if(r[fx]<=r[fy])f[fx]=fy,z[++top].x=fx;else f[fy]=fx,z[++top].x=fy;
if(r[fx]==r[fy])++r[fy],z[top].r=1;else z[top].r=0;
}
}
}
int lca1(int x,int y)
{
if(dep1[x]<dep1[y])swap(x,y);
while(dep1[x]>dep1[y])x=fa1[x];
if(x==y)return x;
while(x!=y)x=fa1[x],y=fa1[y];
return x;
}
int lca2(int x,int y)
{
if(dep2[x]<dep2[y])swap(x,y);
while(dep2[x]>dep2[y])x=fa2[x];
if(x==y)return x;
while(x!=y)x=fa2[x],y=fa2[y];
return x;
}
int main()
{
freopen("camphor.in","r",stdin);
freopen("camphor.out","w",stdout);
T=re_ad();
register int i,x,y,lc;
while(T--)
{
n=re_ad();m=re_ad();D=(int)(sqrt(n))*1.2;
for(i=1;i<=n;++i)g1[i].clear(),g2[i].clear();
for(i=1;i<=n;++i)e1[i].x=re_ad(),e1[i].y=re_ad();
for(i=1;i<n;++i){x=re_ad();y=re_ad();g1[x].push_back(y);g1[y].push_back(x);}
for(i=1;i<=n;++i)e2[i].x=re_ad(),e2[i].y=re_ad();
for(i=1;i<n;++i){x=re_ad();y=re_ad();g2[x].push_back(y);g2[y].push_back(x);}
tot=0;dfs1(1);vis[1]=true;//cout<<n<<" "<<m<<endl;
for(i=1;i<=n;++i)
{
x=i;while(!vis[x])x=fa1[x];gx[i]=x;
}
tot=0;dfs2(1);
for(i=1;i<=m;++i)f[i]=i,r[i]=0;ans=m;
for(i=1;i<=n;++i)used1[i]=used2[i]=false;top=0;
for(i=1;i<=n;++i)xw[i]=(que){i,i},an[i]=0;
sort(xw+1,xw+n+1);
for(i=1;i<=n;++i)
{
if(gx[xw[i].l]!=gx[xw[i-1].l])
{
if(xw[i-1].r){cx2(xw[i-1].r,1);}
if(xw[i-1].l)
{
lc=lca1(gx[xw[i-1].l],gx[xw[i].l]);
jr1(gx[xw[i-1].l],gx[xw[i-1].l]);
cx1(gx[xw[i-1].l],lc);
jr1(gx[xw[i].l],lc);
}
else jr1(gx[xw[i].l],1);
cx1(gx[xw[i].l],gx[xw[i].l]);
jr2(xw[i].r,1);
}
else
{
lc=lca2(xw[i-1].r,xw[i].r);
cx2(xw[i-1].r,lc);
jr2(xw[i].r,lc);
}/**/
jr1(xw[i].l,gx[xw[i].l]);
an[xw[i].l]=ans;
cx1(xw[i].l,gx[xw[i].l]);
}
for(i=1;i<=n;++i)printf("%d\n",an[i]);
}
//cout<<ann<<endl;
//for(i=1;i<=n;++i)if(vis[i])++ans;cout<<ans<<endl;
return 0;
}T2
題目大意：給你一個n行m列的網格圖，在每個格子里填非負整數，要求第i行最大值為ai，第j列最大值為bj，求方案數對1e9+9取模，n,m<=1e6,0<=ai,bi<=1e9，
題解：
AC代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
inline int re_ad()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
return x*f;
}
const int mo=1e9+9;
inline int ksm(int x,long long y){x%=mo;int ret=1;y%=mo-1;if(y<0)y=-y,x=ksm(x,mo-2);while(y){if(y&1)ret=1ll*ret*x%mo;y>>=1;x=1ll*x*x%mo;}if(ret<0)ret+=mo;return ret;}
int n,m;
int a[1000010],b[1000010],ans;
int pre[1000010],ni[1000010];
int C(int x,int y){if(x<y)return 0;return 1ll*pre[x]*ni[y]%mo*ni[x-y]%mo;}
int lsh[2000010],cnt;
int f[2000010];
signed main()
{
freopen("newyear.in","r",stdin);
freopen("newyear.out","w",stdout);
register int i,j,now,ii,x=0,y=0,xx=0,yy=0,s;
n=1000000;pre[0]=1;
for(i=1;i<=n;++i)pre[i]=pre[i-1]*1ll*i%mo;
ni[n]=ksm(pre[n],mo-2);
for(i=n;i>=1;--i)ni[i-1]=1ll*ni[i]*i%mo;
n=re_ad();m=re_ad();
for(i=1;i<=n;++i)a[i]=lsh[++lsh[0]]=re_ad();
for(i=1;i<=m;++i)b[i]=lsh[++lsh[0]]=re_ad();
sort(a+1,a+n+1);sort(b+1,b+m+1);
sort(lsh+1,lsh+n+m+1);
cnt=unique(lsh+1,lsh+n+m+1)-lsh-1;
i=n;j=m;if(a[n]!=b[m]){cout<<0<<endl;return 0;}
for(now=cnt;now>=1;--now)
{
xx=yy=0;s=lsh[now];
while(i&&a[i]==s)--i,++xx;
while(j&&b[j]==s)--j,++yy;//cout<<s<<" "<<xx<<" "<<yy<<endl;
if(s==0)f[now]=1;
else
{
for(ii=0;ii<=xx;++ii)
{
f[now]=(f[now]+
1ll*ksm(-1,(ii+yy)&1)*C(xx,ii)%mo*ksm(s,1ll*ii*(y+yy))%mo*ksm(s+1,1ll*(x+xx-ii)*(y+yy)-1ll*x*y)%mo
*ksm(1ll*ksm(s,x+xx-ii)*ksm(s+1,ii-x-xx)%mo-1,yy%mo)%mo)%mo;
}
//cout<<f[now]<<endl;
}
f[now]=(f[now]+mo)%mo;
x+=xx;y+=yy;
}
ans=1;
for(i=1;i<=cnt;++i)ans=1ll*ans*f[i]%mo;
cout<<ans<<endl;return 0;
}T3
題目大意：
題解：
AC代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
inline int re_ad()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
return x*f;
}
int n,n2,n4;
int a[4000010],pla[4000010];
int head[1000010],cnt=-1;
struct node{int v,nex,w;}f[4000010];
bool vis[4000010];int ans[4000010];
bool an[4000010];
inline void add(int u,int v,int co)
{
f[++cnt]=(node){v,head[u],co};head[u]=cnt;
}
void dfs(int x)
{
register int i,v;
for(i=head[x];i+1;i=f[i].nex)
{
if(!vis[i])
{
vis[i]=vis[i^1]=true;
dfs(f[i].v);
ans[++ans[0]]=i;
}
}
}
int main()
{
freopen("slp.in","r",stdin);
freopen("slp.out","w",stdout);
register int i,j,x,y;
n=re_ad();memset(head,-1,sizeof(head));
n2=n*2;n4=n2*2;
for(i=1;i<=n4;++i)a[i]=re_ad(),pla[a[i]]=i;
for(i=1;i<=n2;++i)
{
j=n4+1-i;
x=((pla[i]-1)>>2)+1;y=((pla[j]-1)>>2)+1;
add(x,y,j);add(y,x,i);
}
for(i=1;i<=n;++i)dfs(i);
for(i=1;i<=ans[0];i+=2)an[pla[f[ans[i]].w]]=an[pla[f[ans[i]^1].w]]=true;
for(i=1;i<=n4;++i)if(an[i])putchar('1'),putchar(' ');else putchar('0'),putchar(' '); cout<<endl;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282741.html
標籤：其他