csp-s模拟测试77_78部分题解
rtrt
3月 14, 2025
归档于 2019-10-22 06:38
Day1T2
题解
集合求交,求并维护时间戳,整体+,-维护一个变量
其实都挺套路的,但我考场什么都没想到,竟然还有60
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 3444444
const ll sz=5000000;
ll a[sz];
ll *b=a+2500000;
ll ans,m,opt,mark,n,k,size,T=1;
int main(){
// freopen("ex_jihe3.in","r",stdin);
// freopen("zj.out","w",stdout);
scanf("%lld",&m);
for(ll i=1;i<=m;i++){
scanf("%lld",&opt);
if(opt==1){
scanf("%lld",&k);
for(ll i=1;i<=k;i++){
scanf("%lld",&n);
if(b[n-mark]!=T){
b[n-mark]=T;
ans+=n-mark;
size++;
}
}
}
else if(opt==2){
++T;ans=0;size=0;
scanf("%lld",&k);
for(ll i=1;i<=k;i++){
scanf("%lld",&n);
if(b[n-mark]==T-1){
b[n-mark]=T;
ans+=n-mark;
size++;
// printf("n-mark=%lld sz=%lld\n",n-mark,size);
}
}
}
else if(opt==3){
mark++;
}
else if(opt==4){
mark--;
}
printf("%lld\n",ans+mark*size);
}
}
View Code
Day1T3
题解
部分分有一部分是$C_m^2$提示
我们其他也可以这么做,找到每一个极大联通空地同时联通相同颜色每一对都会造成贡献
但是这样会有多个联通的情况
可能会出现最多会出现两个颜色之间四联通,会算重
必须容斥
记录下每个块被那个极大联通空地链接
f1[x][col]记录被x连接颜色为col的情况
f2[x][y][col]记录被x,y两个联通块链接颜色为col的情况
f3[x][y][z][col],f4[w][x][y][z][col]
奇加偶减,f1,f2,f3,f4用map存一下即可
相邻单独考虑
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 1111
struct node{
ll bl1,bl2,bl3,bl4,col;
node(){}
node(const ll &a,const ll &b,const ll &c,const ll &d,const ll &e){
bl1=a,bl2=b,bl3=c,bl4=d,col=e;
}
friend bool operator < (const node &a,const node &b){
if(a.bl1!=b.bl1) return a.bl1<b.bl1;
if(a.bl2!=b.bl2) return a.bl2<b.bl2;
if(a.bl3!=b.bl3) return a.bl3<b.bl3;
if(a.bl4!=b.bl4) return a.bl4<b.bl4;
return a.col<b.col;
}
};
map<node,ll> mp;
ll bl[5][A][A],vis[A][A],col[A][A];
ll nowx[5]={0,1,-1,0,0};
ll nowy[5]={0,0,0,1,-1};
ll n,m,k,tim,ans;
void dfs(ll x,ll y){
vis[x][y]=tim;
if(col[x][y]){
if(!bl[1][x][y]) bl[1][x][y]=tim;
else if(!bl[2][x][y]) bl[2][x][y]=tim;
else if(!bl[3][x][y]) bl[3][x][y]=tim;
else if(!bl[4][x][y]) bl[4][x][y]=tim;
return ;
}
for(ll i=1;i<=4;i++){
ll xnow=nowx[i]+x,ynow=nowy[i]+y;
if(xnow>=1&&xnow<=n&&ynow>=1&&ynow<=m&&vis[xnow][ynow]!=tim){
dfs(xnow,ynow);
}
}
}
int main(){
// freopen("ex_link4.in","r",stdin);
ll kk;
scanf("%lld%lld%lld",&n,&m,&kk);
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
scanf("%lld",&col[i][j]);
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++){
if(!vis[i][j]&&col[i][j]==0){
tim++;
dfs(i,j);
}
}
for(ll i=1;i<=n;i++)
for(ll j=1;j<=m;j++)
if(col[i][j]){
if(bl[1][i][j]){
ans+=mp[node(bl[1][i][j],0,0,0,col[i][j])]++;
}
if(bl[2][i][j]){
ans+=mp[node(bl[2][i][j],0,0,0,col[i][j])]++;
ans-=mp[node(bl[1][i][j],bl[2][i][j],0,0,col[i][j])]++;
}
if(bl[3][i][j]){
ans+=mp[node(bl[3][i][j],0,0,0,col[i][j])]++;
ans-=mp[node(bl[2][i][j],bl[3][i][j],0,0,col[i][j])]++;
ans-=mp[node(bl[1][i][j],bl[3][i][j],0,0,col[i][j])]++;
ans+=mp[node(bl[1][i][j],bl[2][i][j],bl[3][i][j],0,col[i][j])]++;
}
if(bl[4][i][j]){
ans+=mp[node(bl[4][i][j],0,0,0,col[i][j])]++;
ans-=mp[node(bl[1][i][j],bl[4][i][j],0,0,col[i][j])]++;
ans-=mp[node(bl[2][i][j],bl[4][i][j],0,0,col[i][j])]++;
ans-=mp[node(bl[3][i][j],bl[4][i][j],0,0,col[i][j])]++;
ans+=mp[node(bl[1][i][j],bl[2][i][j],bl[4][i][j],0,col[i][j])]++;
ans+=mp[node(bl[1][i][j],bl[3][i][j],bl[4][i][j],0,col[i][j])]++;
ans+=mp[node(bl[2][i][j],bl[3][i][j],bl[4][i][j],0,col[i][j])]++;
ans-=mp[node(bl[1][i][j],bl[2][i][j],bl[3][i][j],bl[4][i][j],col[i][j])]++;
}
// printf("%lld bl 4=%lld 3=%lld 2=%lld 1=%lld\n",ans,bl[4][i][j],bl[3][i][j],bl[2][i][j],bl[1][i][j]);
}
// printf("%lld\n",ans);
for(ll i=1;i<=n;i++)
for(ll j=2;j<=m;j++)
if(col[i][j-1]&&col[i][j]&&col[i][j]==col[i][j-1]){
ll ok=1;
for(ll k=1;k<=4;k++)
for(ll e=1;e<=4;e++)
if(bl[k][i][j]&&bl[e][i][j-1]&&bl[k][i][j]==bl[e][i][j-1])
ok=0;
ans+=ok;
}
for(ll i=2;i<=n;i++)
for(ll j=1;j<=m;j++)
if(col[i-1][j]&&col[i][j]&&col[i][j]==col[i-1][j]){
ll ok=1;
for(ll k=1;k<=4;k++)
for(ll e=1;e<=4;e++)
if(bl[k][i][j]&&bl[e][i-1][j]&&bl[k][i][j]==bl[e][i-1][j])
ok=0;
ans+=ok;
}
printf("%lld\n",ans);
}
View Code
Day2T3
题解
假设环上点为黑点,其他点为白点,我们现在要统计的就是max(白点到最近黑点距离)
假设黑点中深度最小的为B
开这样几个数组ff[x]表示从x走到父亲后能走到最远距离
g[x]表示从x向下走到距离最远是多少
然而可能有最多两个黑点将路径堵塞,所以记录最大值,次大值,次次大值,
黑点即使将最大值次大值堵上,你可以走次次大值
然后贡献可以分为两部分
每个黑点g,最上点ff
这样复杂度仍然会炸
考虑优化求每个黑点g
发现lca路径上除了lca其他点只和一个儿子黑点相邻
q[x]表示从x走到父亲路径上向下走但不经过x达到最远点
然后倍增优化一下
现在贡献变成g[lca],g[x],g[y],q[lca路径上],ff[lca]
分别维护一下
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 1111111
ll n,tot=1,tim,m,t;
ll head[A],ver[A],nxt[A],du[211111],deep[A],qjdis[A],zj[A];
ll maxcost[A][25],f[A][25];
ll ans=0;
pair<ll,ll>g[A][3],dis[A],ff[A],q[A][25];
pair<ll,ll>tmp;
void add(ll x,ll y){
nxt[++tot]=head[x],head[x]=tot,ver[tot]=y;
}
ll lca(ll x,ll y){
pair<ll,ll> pr;ll now=0;
pr=make_pair(0,0);
if(deep[x]>deep[y]) swap(x,y);
ll lastx=x,lasty=y;
for(ll i=t;i>=0;i--){
if(deep[x]==deep[y]) break;
if(deep[x]<=deep[f[y][i]]) {
pr=max(pr,q[y][i]);
y=f[y][i];
}
}
if(x==y) {
ll lcq=x;
return max(pr.first,max(ff[lcq].first,g[lasty][0].first));
}
for(ll i=t;i>=0;i--){
if(f[x][i]!=f[y][i]) {
pr=max(pr,q[x][i]);
pr=max(pr,q[y][i]);
x=f[x][i],y=f[y][i];
}
}
ll lcq=f[x][0];
if((g[lcq][0].second==x&&g[lcq][1].second==y)||(g[lcq][1].second==x&&g[lcq][0].second==y)){
now=max(g[lcq][2].first,pr.first);
}
else if((g[lcq][0].second==x&&g[lcq][1].second!=y)||(g[lcq][0].second==y&&g[lcq][1].second!=x)){
now=max(g[lcq][1].first,pr.first);
}
else {
now=max(g[lcq][0].first,pr.first);
}
now=max(now,ff[lcq].first);
now=max(now,max(g[lastx][0].first,g[lasty][0].first));
return now;
}
pair<ll,ll> dfs1(ll x,ll pre){
dis[x]=make_pair(0,0);
for(ll i=head[x];i;i=nxt[i]){
ll y=ver[i];
if(y==pre) continue ;
f[y][0]=x;
deep[y]=deep[x]+1;
pair<ll,ll> d=dfs1(y,x);
dis[x]=max(dis[x],d);
}
return make_pair(dis[x].first+1,dis[x].second);
}
void dfs2(ll x,ll pre){
pair<ll,ll> fir,sec,thi,tmp;
for(ll i=head[x];i;i=nxt[i]){
ll y=ver[i];
if(y==pre) continue ;
if((dis[y].first+1)>fir.first){
thi=sec;sec=fir;fir=make_pair(dis[y].first+1,y);
}
else if((dis[y].first+1)>sec.first){
thi=sec;
sec=make_pair(dis[y].first+1,y);
}
else if((dis[y].first+1)>thi.first){
thi=make_pair(dis[y].first+1,y);
}
}
g[x][0]=make_pair(fir.first,fir.second);
g[x][1]=make_pair(sec.first,sec.second);
g[x][2]=make_pair(thi.first,thi.second);
for(ll i=head[x];i;i=nxt[i]){
ll y=ver[i];
if(y==pre) continue ;
if(dis[y].first+1==fir.first) q[y][0]=sec;
else q[y][0]=fir;
}
for(ll i=head[x];i;i=nxt[i]){
ll y=ver[i];
if(y==pre) continue ;
dfs2(y,x);
}
}
void redfs(ll x,ll pre){
for(ll i=head[x];i;i=nxt[i]){
ll y=ver[i];
if(y==pre) continue ;
ff[y]=ff[x];
if(y==g[x][0].second)
ff[y]=max(ff[y],g[x][1]);
else ff[y]=max(ff[y],g[x][0]);
ff[y]=make_pair(ff[y].first+1,ff[y].second);
}
for(ll i=head[x];i;i=nxt[i]){
ll y=ver[i];
if(y==pre) continue ;
redfs(y,x);
}
}
void dfs3(ll x,ll pre){
for(ll i=head[x];i;i=nxt[i]){
ll y=ver[i];
if(y==pre) continue ;
dfs3(y,x);
ans=max(zj[x]+zj[y]+1,ans);
zj[x]=max(zj[x],zj[y]+1);
}
}
int main(){
scanf("%lld",&n);
t=log(n)/log(2)+1;
for(ll i=1;i<n;i++){
ll a,b;
scanf("%lld%lld",&a,&b);
add(a,b);
add(b,a);
}
dfs1(1,0);
dfs2(1,0);
dfs3(1,0);
redfs(1,0);
f[1][0]=1;
for(ll j=1;j<=t;j++){
for(ll i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
q[i][j]=max(q[f[i][j-1]][j-1],q[i][j-1]);
}
}
scanf("%lld",&m);
for(ll i=1;i<=m;i++){
ll a,b;
scanf("%lld%lld",&a,&b);
if(a==b){
printf("%lld\n",(ans)/2+1);
continue ;
}
printf("%lld\n",lca(a,b));
}
}
View Code