8.19 模拟赛小结
前言
结束了 也许这几天很苦 但也是最有意义的几天 这篇写简单一点吧
T1 颠倒黑白
很强的构造题
根据打表找出思路
因为最左下角的是一定要点的 就考虑它
- 如果是先手 左下角有黑色 就把它点了 后手只能帮我们把其它黑色点了 最后还是我们先点完
- 若是后手 左下角是白色 与先手同理
一个简单判断即可
#include<bits/stdc++.h>
using namespace std;
int g,n,m,c;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>g;
while(g--)
{
cin>>n>>m;
for(int i=1;i<=n-1;i++)
for(int j=1;j<=m;j++)
cin>>c;
cin>>c;
if(c) cout<<"T\n";
else cout<<"F\n";
for(int j=2;j<=m;j++)
cin>>c;
}
return 0;
}
T2 糖果数 原题
题意：给定一个 \(n\space (n\leq 10^{18})\) 求在 \(n\) 位数以内有多少个包含 \(111\) 的数
推荐我的博客：矩阵快速幂
这题就是原题换了一下 不想说了 容斥一下转为求没有 \(111\) 的数即可
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll mod=998244353;
ll n;
struct node{
ll r[4][4];
int n,m;
}ans,a;
node clear(int n,int m)
{
node c;
c.n=n,c.m=m;
memset(c.r,0,sizeof(c.r));
return c;
}
node operator *(node a,node b)
{
node c=clear(a.n,b.m);
for(int i=1;i<=a.n;i++)
for(int k=1;k<=a.m;k++)
for(int j=1;j<=b.m;j++)
c.r[i][j]=(c.r[i][j]+a.r[i][k]*b.r[k][j])%mod;
return c;
}
ll Qpow(ll a,ll x)
{
ll sum=1;
while(x)
{
if(x&1) sum=sum*a%mod;
a=a*a%mod;
x/=2;
}
return sum;
}
node Qpow(node a,ll x)
{
node sum=clear(a.m,a.m);
for(int i=1;i<=a.m;i++)
sum.r[i][i]=1;
while(x)
{
if(x&1) sum=sum*a;
a=a*a;
x/=2;
}
return sum;
}
int main()
{
scanf("%lld",&n);
ans.n=1,ans.m=3;
ans.r[1][1]=9,ans.r[1][2]=1,ans.r[1][3]=0;
a.n=a.m=3;
a.r[1][1]=9,a.r[1][2]=1,a.r[1][3]=0;
a.r[2][1]=9,a.r[2][2]=0,a.r[2][3]=1;
a.r[3][1]=9,a.r[3][2]=0,a.r[3][3]=0;
ans=ans*Qpow(a,n-1);
printf("%lld",(Qpow(10,n)-(ans.r[1][1]+ans.r[1][2]+ans.r[1][3])%mod+mod)%mod);
return 0;
}
T3 天使玩偶 原题
题意：会动态加点 每次询问一个点离另一个点最小的曼哈顿距离
有很多情况 考虑 \(b_x\leq a_x\space b_y\leq a_y\) 的情况 即 \(b\) 在 \(a\) 左下角
那么问题转化为 求
\(a_{tim}\leq b_{tim},{a_x\leq b_x,a_y\leq b_y}\)
现在的问题转化为求 \(a_x-b_x+a_y-b_y\) 最小
移一下就是 \(a_x+a_y-b_x-b_y\)
树状数组位数 \(b_x+b_y\) 然后 CDQ 分治即可
考虑在左上的点
直接将整个矩阵翻转一下即可 可以用坐标轴理解
时间复杂度太大了 会 TLE
所以 CDQ 的 sort 不能用 用归并排序就可以了
不开 O2 能过
#include<bits/stdc++.h>
//#pragma GCC optimize (1)
//#pragma GCC optimize (2)
//#pragma GCC optimize (3,"Ofast","inline")
#define reg register
#define N 300005
#define M 1000005
using namespace std;
int n,m,ans[N*2],maxy;
struct oper{
int opr,x,y,id;
}q[N*2],b[N*2],t[N*2];
inline bool cmp(oper a,oper b)
{
return a.x<b.x;
}
struct BIT{
int tr[M];
inline void add(int x,int v)
{
while(x<=maxy)
{
tr[x]=max(tr[x],v);
x+=x&-x;
}
return;
}
inline int ask(int x)
{
int maxx=-1e9;
while(x)
{
maxx=max(maxx,tr[x]);
x-=x&-x;
}
return maxx;
}
inline void clear(int x)
{
while(x<=maxy)
{
tr[x]=-1e9;
x+=x&-x;
}
}
}tr;
int stk[4*N],top;
inline void solve(int l,int r)
{
if(l==r) return;
int mid=(l+r)/2;
solve(l,mid);
solve(mid+1,r);
int i=l,j=mid+1,len;
i=l,j=mid+1;
for(j=mid+1;j<=r;j++)
{
while(i<=mid&&q[i].x<=q[j].x)
{
if(q[i].opr==2)
{
++i;
continue;
}
tr.add(q[i].y,q[i].x+q[i].y);
stk[++top]=q[i].y;
++i;
}
if(q[j].opr==2)
ans[q[j].id]=min(ans[q[j].id],q[j].x+q[j].y-tr.ask(q[j].y));
}
while(top) tr.clear(stk[top--]);
i=l,j=mid+1,len=l-1;
for(i=l;i<=r;i++)
t[i]=q[i];
for(i=l;i<=mid;i++)
{
while(j<=r&&cmp(t[j],t[i])) q[++len]=t[j],j++;
q[++len]=t[i];
}
while(j<=r) q[++len]=t[j],j++;
}
int main()
{
scanf("%d%d",&n,&m);
for(reg int i=1;i<=n;i++)
{
q[i].id=i;
q[i].opr=1;
scanf("%d%d",&q[i].x,&q[i].y);
q[i].x++,q[i].y++;
maxy=max(maxy,q[i].y);
}
for(reg int i=n+1;i<=n+m;i++)
scanf("%d%d%d",&q[i].opr,&q[i].x,&q[i].y),q[i].id=i,
ans[i]=2e9,q[i].x++,q[i].y++,maxy=max(maxy,q[i].y);
maxy++;
fill(tr.tr,tr.tr+1+M-3,-1e9);
for(reg int i=1;i<=n+m;i++) b[i]=q[i];
solve(1,n+m);
for(reg int i=1;i<=n+m;i++)
q[i]=b[i],q[i].x=M-q[i].x;
solve(1,n+m);
for(reg int i=1;i<=n+m;i++)
q[i]=b[i],q[i].y=maxy-q[i].y;
solve(1,n+m);
for(reg int i=1;i<=n+m;i++)
q[i]=b[i],q[i].x=M-q[i].x,q[i].y=maxy-q[i].y;
solve(1,n+m);
for(reg int i=1;i<=n+m;i++) q[i]=b[i];
for(reg int i=n+1;i<=m+n;i++)
if(q[i].opr==2) printf("%d\n",ans[i]);
return 0;
}
T4 数学题 原题
可以先去做一下这题
发现删边很难 考虑加边
可以先把原本存在的边缩点成树
然后如果连上两个点可以发现这两个点之间的边都不是割边 因为已经变成一个环了
所以这两点之间的路径全部都打上不是割边的记录
树剖维护即可
#include<bits/stdc++.h>
#define N 100005
#define mp make_pair
using namespace std;
int n,m,q;
struct oper{
int u,v,opr;
}op[N];
int u[N],v[N];
map <pair<int,int> ,int> use;
//Edge
int head[N],tot=1;
struct edge{
int to,next;
}e[N*2];
void add(int u,int v)
{
e[tot]=(edge){v,head[u]};
head[u]=tot++;
}
//Tarjan
int stk[N],l;
int col[N],dfn[N],low[N],colcnt,ids;
void tarjan(int x,int fa)
{
low[x]=dfn[x]=++ids;
stk[++l]=x;
for(int i=head[x];i;i=e[i].next)
{
int to=e[i].to;
if(to==fa) continue;
if(!dfn[to]) tarjan(to,x);
low[x]=min(low[x],low[to]);
}
if(dfn[x]==low[x])
{
colcnt++;
while(stk[l+1]!=x)
col[stk[l--]]=colcnt;
}
}
//线段树
int tr[N*4],lz[N*4];
void Pushup(int x)
{
tr[x]=tr[x*2]+tr[x*2+1];
}
void Pushdown(int x,int l)
{
if(lz[x]==-1) return;
tr[x*2]=(l-l/2)*lz[x];
lz[x*2]=lz[x];
tr[x*2+1]=(l/2)*lz[x];
lz[x*2+1]=lz[x];
lz[x]=-1;
}
void updata(int l,int r,int L,int R,int x,int v)
{
if(l>R||r<L) return;
if(l>=L&&r<=R)
{
tr[x]=(r-l+1)*v;
lz[x]=v;
return;
}
Pushdown(x,r-l+1);
int mid=(l+r)/2;
updata(l,mid,L,R,x*2,v);
updata(mid+1,r,L,R,x*2+1,v);
Pushup(x);
}
int query(int l,int r,int L,int R,int x)
{
if(l>R||r<L) return 0;
if(l>=L&&r<=R) return tr[x];
int mid=(l+r)/2;
Pushdown(x,r-l+1);
return query(l,mid,L,R,x*2)+query(mid+1,r,L,R,x*2+1);
}
//树剖
int fa[N],dep[N],size[N],Son[N];
int cnt,id[N],top[N];
void dfs1(int now,int f)
{
fa[now]=f;
dep[now]=dep[f]+1;
int maxx=0;
size[now]=1;
for(int i=head[now];i;i=e[i].next)
{
int son=e[i].to;
if(son==f) continue;
dfs1(son,now);
size[now]+=size[son];
if(size[son]>maxx) maxx=size[son],Son[now]=son;
}
}
void dfs2(int now,int topf)
{
id[now]=++cnt;
top[now]=topf;
if(!Son[now]) return;
dfs2(Son[now],topf);
for(int i=head[now];i;i=e[i].next)
{
int son=e[i].to;
if(son==Son[now]||son==fa[now]) continue;
dfs2(son,son);
}
}
void Add(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
updata(1,colcnt,id[top[u]],id[u],1,0);
u=fa[top[u]];
}
if(u==v) return;
if(dep[u]>dep[v]) swap(u,v);
updata(1,colcnt,id[u]+1,id[v],1,0);
return;
}
int Ask(int u,int v)
{
int sum=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
sum+=query(1,colcnt,id[top[u]],id[u],1);
u=fa[top[u]];
}
if(u==v) return sum;
if(dep[u]>dep[v]) swap(u,v);
sum+=query(1,colcnt,id[u]+1,id[v],1);
return sum;
}
// end
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&u[i],&v[i]),use[mp(u[i],v[i])]=use[mp(v[i],u[i])]=1;
for(q=1;;q++)
{
scanf("%d",&op[q].opr);
if(op[q].opr==-1)
{
q--;
break;
}
scanf("%d%d",&op[q].u,&op[q].v);
if(op[q].opr==0) use[mp(op[q].u,op[q].v)]=use[mp(op[q].v,op[q].u)]=0;
}
for(int i=1;i<=m;i++)
if(use[mp(u[i],v[i])]) add(u[i],v[i]),add(v[i],u[i]);
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i,0);
//缩点
l=0;
tot=1;
memset(head,0,sizeof(head));
memset(lz,-1,sizeof(lz));
for(int i=1;i<=m;i++)
if(use[mp(u[i],v[i])]&&col[u[i]]!=col[v[i]])
add(col[u[i]],col[v[i]]),
add(col[v[i]],col[u[i]]);
//
dfs1(1,0);
dfs2(1,1);
updata(1,colcnt,2,colcnt,1,1);
for(int i=q;i>=1;i--)
if(op[i].opr==0)
Add(col[op[i].u],col[op[i].v]);
else
stk[++l]=Ask(col[op[i].u],col[op[i].v]);
while(l)
printf("%d\n",stk[l--]);
return 0;
}
写的比较草 没什么好的