考前的模拟赛

respect_lowsmile · 2022-10-22 22:19:27 · 个人记录

10.22(10pts=5pts+0pts+5pts)

### [T285766 jump](https://www.luogu.com.cn/problem/T285766) 注意到这句话： ```可以将一个人传送[max(1, i − a[i]), min(n, i + a[i])]中的任何一个城市，且需要花费1块钱。``` ~~很明显~~，可以从当前点向区间中的所有点建一条权值为 $1$ 的边，然后最短路解决问题即可，可以获得 $60pts$ 。注意到是一个点向一个区间建边，考虑线段树优化建边。但是我不会。。。 $60 pts$ 应该还是很容易的，但是我没想到。。。 ``` #include<iostream> #include<queue> using namespace std; const int N=1e3+5; const int M=1e6+5; const int INF=0x3f3f3f3f; struct node { int to,next,w; }; struct Node { int id,w; bool operator < (const Node &a) const { return a.w<w; } }; node edge[M]; int num,n,res; int head[N],dis[N][N],vis[N]; priority_queue<Node> q; void add(int u,int v,int w) { ++num; edge[num].to=v; edge[num].next=head[u]; edge[num].w=w; head[u]=num; } void dij(int st) { while(!q.empty()) q.pop(); for(int i=1;i<=n;++i) dis[st][i]=INF,vis[i]=0; q.push(Node{st,0}); dis[st][st]=0,vis[st]=1; while(!q.empty()) { int now=q.top().id; q.pop(); vis[now]=1; for(int i=head[now];i;i=edge[i].next) { int v=edge[i].to,w=edge[i].w; if(dis[st][v]>dis[st][now]+w) { dis[st][v]=dis[st][now]+w; if(!vis[v]) q.push((Node){v,dis[st][v]}); } } } } int main() { scanf("%d",&n); for(int i=1;i<=n;++i) { int x; scanf("%d",&x); int minc=max(1,i-x),maxc=min(n,i+x); for(int j=minc;j<=maxc;++j) add(i,j,1); } for(int i=1;i<=n;++i) dij(i); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) dis[i][j]=min(dis[i][j],dis[j][i]),res=max(res,dis[i][j]); printf("%d",res); return 0; } ``` $T3$ 还稍微简单一点，下面这个题是真的不知道。这种题真的是自己的一大短板。 ### [P4667 [BalticOI 2011 Day1]Switch the Lamp On](https://www.luogu.com.cn/problem/P4667) 我只能说这种题我真的一会不会。。。 ``` #include<iostream> #include<queue> using namespace std; const int N=1e6+5; const int INF=0x3f3f3f3f; struct node { int to,next,w; }; struct Node { int id,w; bool operator < (const Node &a) const { return a.w<w; } }; node edge[N<<1]; priority_queue<Node> q; int n,m,num; int head[N],dis[N],vis[N]; void add(int u,int v,int w) { ++num; edge[num].to=v; edge[num].w=w; edge[num].next=head[u]; head[u]=num; } void dij() { for(int i=1;i<=(n+1)*(m+1);++i) dis[i]=INF; q.push(Node{1,0}); dis[1]=0,vis[1]=1; while(!q.empty()) { int now=q.top().id; q.pop(); vis[now]=1; for(int i=head[now];i;i=edge[i].next) { int v=edge[i].to,w=edge[i].w; if(dis[v]>dis[now]+w) { dis[v]=dis[now]+w; if(!vis[v]) q.push((Node){v,dis[v]}); } } } } int main() { scanf("%d %d",&n,&m); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { char ch; cin>>ch; if(ch=='\\') add((i-1)*(m+1)+j,i*(m+1)+j+1,0),add(i*(m+1)+j+1,(i-1)*(m+1)+j,0),add((i-1)*(m+1)+j+1,i*(m+1)+j,1),add(i*(m+1)+j,(i-1)*(m+1)+j+1,1); if(ch=='/') add((i-1)*(m+1)+j,i*(m+1)+j+1,1),add(i*(m+1)+j+1,(i-1)*(m+1)+j,1),add((i-1)*(m+1)+j+1,i*(m+1)+j,0),add(i*(m+1)+j,(i-1)*(m+1)+j+1,0); } dij(); if(dis[(n+1)*(m+1)]==INF) cout<<"NO SOLUTION"; else cout<<dis[(n+1)*(m+1)]; return 0; } ``` ## $10.23(125pts=70pts+50pts+0pts+5pts)

我严重怀疑我是唯一一个 T1 不会正解， T2 不会二分，打了 4 个暴力但是 100 pts 以上的人。/kk

T1

T286189 莫比乌斯反演(mobius)

第一题一开始花了不到 10 分钟写了一个 O(n^3) 的暴力，然后就在考虑优化。

也想到了枚举完前 2 个数后，gcd 可以确定，可以不用枚举第三维，但是不知道该怎么处理。

也想到了用 map 存符合的个数，但是不知道怎么控制这些值都在 i 和 j 位置之前。~~现在想想自己真NT~~

其实解决方案很简单，只需要将 j 按照倒序枚举即可，枚举一个数就加入一个数，这样就能保证 j 往前枚举的同时将 j 后面的加入桶中。

#include<iostream>
#include<map>
#define int long long
using namespace std;
const int N=3005;
map<int,int> Map;
int n,ans;
int a[N];
int gcd(int a,int b)
{
    if(b==0)  return a;
    else return gcd(b,a%b);
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
      scanf("%lld",&a[i]);
    for(int i=1;i<=n;++i)
    {
        Map.clear();
        for(int j=n;j>i;Map[a[j]]++,--j)
        {
            int Gcd=gcd(a[i],a[j]);
            ans+=Map[Gcd];
        }
    }
    printf("%lld",ans);
    return 0;
}

T2

T286185 柯西收敛准则 (cauchy）

思路：二分+dp

想到了二分这个 $k$ ，然后去判断是否合法。但是判断合法的方法想错了。没有想到是用 $dp$ 去维护，毕竟自己的 $dp$ 学的是真的不怎么样。设 $dp[i]$ 表示以 $i$ 为结尾的子序列中满足条件的子序列最长是多少。状态转移方程很显然。 $$ f[i]=max(f[j]+1) (j < i , abs(a[i]-a[j])<=k)$$ 但是没想到 $dp$ ，最后没办法，$dfs$ 跑路了，竟然拿了 $50$ 分，对暴力来说这个分不低了，证明之前练的 $dfs$ 有效果了。 ``` #include<iostream> #include<cstring> #define int long long using namespace std; const int N=1005; int n,m,ans; int a[N],f[N]; int judge(int x) { int res=0; for(int i=1;i<=n;++i) { f[i]=1; for(int j=1;j<i;++j) if(abs(a[i]-a[j])<=x) f[i]=max(f[i],f[j]+1); } for(int i=1;i<=n;++i) res=max(res,f[i]); if(res>=m) return 1; else return 0; } signed main() { scanf("%lld %lld",&n,&m); for(int i=1;i<=n;++i) scanf("%lld",&a[i]); int l=1,r=1e9; while(l<=r) { int mid=(l+r)>>1; if(judge(mid)) ans=mid,r=mid-1; else l=mid+1; } printf("%lld",ans); return 0; } ``` ### $T3

T286186 快速树论变换(ttt)

思路：树上贪心

白给的 5 分是真的很人性化。。。

正解一听学长讲好像也挺简单的，在这里感谢一下 zcx 学长。

首先，我们考虑最简单的情况。

我们设填满 x 所需的石子数为 ansx ，剩余的石子数为 restx ，填满 y 所需要的石子数为 ansy ，剩余的石子数为 resty 。

很明显，我们选择的顺序不同，结果是不同的，所以我们要考虑怎么选择顺序最优。

如果先处理 x 节点，那么处理完 x,y 节点的总花费为 ansx+ansy-restx ，（因为 x 剩下的可以回收给 y ），如果先处理 y 节点，那么处理完 x,y 节点的总花费为 ansy+ansx-resty 。

我们发现，花费只与 restx,resty 的大小有关，rest 越大，结果会越优。

而我们的 rest ，很明显，就等于 ans-val 。

所以，我们按照 ans_i-val_i 排序，然后根据题目要求进行计算即可。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1e6+5;
vector<int> son[N];
int val[N],ans[N];
int n;
int cmp(int a,int b)
{
    return ans[a]-val[a]>ans[b]-val[b];
}
void dfs(int now,int fa)
{
    for(int i=0;i<son[now].size();++i)
    {
        int v=son[now][i];
        if(v==fa)  continue;
        dfs(v,now);
    }
    sort(son[now].begin(),son[now].end(),cmp);
    int rest=0;
    for(int i=0;i<son[now].size();++i)
    {
        int v=son[now][i];
        if(rest-ans[v]>=0)   rest-=val[v];
        else
          ans[now]+=ans[v]-rest,rest=ans[v]-val[v];
    }
    ans[now]+=max(0,val[now]-rest);
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        son[x].push_back(i);
    }
    for(int i=1;i<=n;++i)
      scanf("%d",&val[i]);
    dfs(1,0);
    for(int i=1;i<=n;++i)
      printf("%d ",ans[i]);
    return 0;
}

~~T4就算了吧，又是树形dp又是组合数的~~

10.24(150pts=100pts+20pts+15pts+15pts)

~~终于考过了myf一次~~

T1

T286369 方程(equation)

很像数学但又不是数学的题目。

这里扯一下我考试时的做法。。。

发现题目限制 c \times d \le 1e6 ，说明解法肯定和 c \times d 有关。

题目的式子为：

\large \frac{a}{x} +\frac{b}{c}=\frac{d}{y}

发现可以把 y 代换成 c \times d ，那么式子变为：

\large \frac{a}{x} +\frac{b}{c}=\frac{1}{c}

由 a,b,c 都是正整数可得，上面的式子一定不成立。

所以 y 一定小于 c \times d ，暴力枚举 y ，判断 x 是否合法即可。

#include<iostream>
#define int long long
using namespace std;
int T;
signed main()
{
    freopen("equation.in","r",stdin);
    freopen("equation.out","w",stdout);
    scanf("%lld",&T);
    while(T--)
    {
        int ans=0;
        int a,b,c,d;
        scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
        int maxc=c*d;
        for(int i=1;i<maxc;++i)
        {
            int fz=a*c*i,fm=c*d-b*i;
            double A=(double)fz*1.0/fm*1.0;
            if(A<=0)  continue;
            int AA=A;
            if(A-AA==0)  ans++;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

T2

T286378 异或数列 (xor）

异或？基本没接触过，考试的时候看到就没想去写正解，写了 20 分的暴力之后就直接跑路了。

其实这个题只用到了异或的一个性质，那就是自反性，即 x \ xor \ y \ xor \ y=x

因为修改操作是在 p 和 p+1 这两个位置异或同一个数，所以考虑前缀和，可以发现只有 sum[p] 这一个地方的值需要改变。（根据自反性可证）

10.25(30pts=30pts+0pts+0pts+0pts)

大寄。

10.26(0pts......)

考前模拟赛保龄还有救吗。。。

10.27(0pts......)

不说了，满脸都是泪。。。

10.31(0pts?100pts=100pts+0pts+0pts)

突然发现自己的头文件写错了 3 年了。。。

最近模拟赛怎么都这么离谱，三个题一个数学+两个 dp 可还行。。。

T1

T288138 A

诈骗题。

考场上直接打表找规律，发现只有 1,2,3,5,7,11 无法构造出来，往后的每一个数都可以由前面能够构造的数拼凑出来，所以只要把这几个特判掉，其他输出 1 即可。

让我们看一下 gzn 大神的讲解。

最小的质数为 2 ，那么最小能用两个质数乘积表示的就是 4 。

然后分情况讨论与 4 取模的数的关系。

n \% 4=0

可以构造成 2 \times 2+2 \times 2+……

n \% 4=1

可以构造成 3 \times 3+2 \times 2+2 \times 2……

这种构造方式要求 n \ge 9 。

n \% 4=2

可以构造成 3 \times 2+2 \times 2+2 \times 2……

这种构造方式要求 n \ge 6 。

n \% 4=3

可以构造成 3 \times 5+2 \times 2+2 \times 2……

这种构造方式要求 n \ge 15 。

也就是说， n \ge 15 时，一定都能按照上面的方法构造出来。

剩下的一小部分数打个表即可。

#include<iostream>
//#include<cstdio> 
#define int long long
using namespace std;
int T;
inline int read()
{
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9')
   {  if(ch=='-')  w=-1;  ch=getchar();}
   while(ch>='0'&&ch<='9')
   {  s=s*10+ch-'0'; ch=getchar();}
   return s*w;
}
signed main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    T=read();
    while(T--)
    {
       int n=read();
       if(n==1||n==2||n==3||n==5||n==7||n==11)  printf("0\n");
       else printf("1\n");
    }
    return 0;
}

T2

T288157 b

怎么又是异或。。。

11.1(120pts=100pts+20pts+0pts)

11.2(CSP-S)(175pts=50pts+85pts+40pts+0pts)

今年的 csp-s 这么良心！！！

第二题漏了两种情况，挂了 15 分。。。

T1

第一题就不会。。。

50pts

#### $100pts

首先，预处理出每一个点通过不超过 k 次转移后能到达的所有点。

然后处理出所有点能到达的点的点权的最大值，次大值，次大值的次大值。

为什么要处理三个值呢？

因为题目要求选取 A,B,C,D 四个景点，我们可以只枚举 B,C ，然后计算选取最优的 A 和 D 。

如果只维护最大值和次大值，可能会造成因为两次重复而无法取到第三个点。

#include<bits/stdc++.h>
#include<iostream>
#include<bitset>
#include<cstdio>
#define int long long
using namespace std;
const int N=2505;
const int K=105;
const int M=1e5+5;
struct node
{
    int to,next;
};
node edge[M<<1];
bitset<N> Map[N][K];
int head[N],val[N],max1[N],max2[N],max3[N];
int n,m,kk,num,Ans;
inline int read()
{
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9')
   {  if(ch=='-')  w=-1;  ch=getchar();}
   while(ch>='0'&&ch<='9')
   {  s=s*10+ch-'0'; ch=getchar();}
   return s*w;
}
void add(int u,int v)
{
    ++num;
    edge[num].to=v;
    edge[num].next=head[u];
    head[u]=num;
}
signed main()
{
    n=read(),m=read(),kk=read();
    for(int i=2;i<=n;++i)   val[i]=read();
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read();
        add(u,v),add(v,u);
        Map[u][0].set(v),Map[v][0].set(u);
    }
    for(int k=1;k<=kk;++k)
        for(int now=1;now<=n;++now)
        {
            Map[now][k]=Map[now][k-1];
            for(int i=head[now];i;i=edge[i].next)
            {
                int v=edge[i].to;
                Map[now][k] |= Map[v][k-1];
            }
        }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            if(i==j)  continue;
            if(!Map[i][kk][j]||!Map[1][kk][j])  continue;
            if(val[j]>=val[max1[i]])
                max3[i]=max2[i],max2[i]=max1[i],max1[i]=j;
            else if(val[j]>=val[max2[i]])
                max3[i]=max2[i],max2[i]=j;
            else if(val[j]>val[max3[i]])
                max3[i]=j;
        }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
        {
            if(i==j)  continue;
            if(!Map[i][kk][j])  continue;
            int A=0,D=0;
            if(j!=max1[i])  A=max1[i];
            else if(j!=max2[i])  A=max2[i];
            else if(j!=max3[i])  A=max3[i];
            if(i!=max1[j]&&A!=max1[j])  D=max1[j];
            else if(i!=max2[j]&&A!=max2[j])  D=max2[j];
            else if(i!=max3[j]&&A!=max3[j])  D=max3[j];
            if(A&&D)  Ans=max(Ans,val[i]+val[j]+val[A]+val[D]);
        }
    printf("%lld",Ans);
    return 0;
}

复杂度 O(\frac{nmk}{64}+n^2) 。

T2

唯一会做的题目，还因为少考虑了两种情况挂了 15 分，这边建议直接退役。

很明显，答案只与两个区间的最大非负数，最大负数，最小非负数，最小负数有关。

建 2 发线段树，分别维护两个区间的以上 4 个信息，然后本着答案最小的原则计算，最后结果取最大值即可。

这边建议枚举所有算法然后进行选择，不建议列举所有情况，~~我才不会告诉你我因为枚举情况漏了2种挂了15分。~~

#include<iostream>
#define lc now<<1
#define rc now<<1|1
#define int long long
using namespace std;
const int N=1e5+5;
const int INF=0x3f3f3f3f;
struct node
{
    int maxz,minz,maxf,minf;
};
node tree[N<<2],Tree[N<<2];
int n,m,q;
inline int read()
{
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9')
   {  if(ch=='-')  w=-1;  ch=getchar();}
   while(ch>='0'&&ch<='9')
   {  s=s*10+ch-'0'; ch=getchar();}
   return s*w;
}
void push_up(int now)
{
    tree[now].maxz=max(tree[lc].maxz,tree[rc].maxz);
    tree[now].maxf=max(tree[lc].maxf,tree[rc].maxf);
    tree[now].minf=min(tree[lc].minf,tree[rc].minf);
    tree[now].minz=min(tree[lc].minz,tree[rc].minz);
}
void build(int now,int l,int r)
{
    tree[now].minz=INF,tree[now].maxf=-INF;
    if(l==r)
    {
        int x=read();
        if(x>=0)  tree[now].maxz=tree[now].minz=x;
        else  tree[now].maxf=tree[now].minf=x;
        return ;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    push_up(now);
}
int query_maxz(int now,int l,int r,int L,int R)
{
    int maxz=0;
    if(l>=L&&r<=R)
        return tree[now].maxz;
    int mid=(l+r)>>1;
    if(L<=mid)  maxz=max(maxz,query_maxz(lc,l,mid,L,R));
    if(R>mid)   maxz=max(maxz,query_maxz(rc,mid+1,r,L,R));
    return maxz; 
}
int query_maxf(int now,int l,int r,int L,int R)
{
    int maxf=-INF;
    if(l>=L&&r<=R)
        return tree[now].maxf;
    int mid=(l+r)>>1;
    if(L<=mid)  maxf=max(maxf,query_maxf(lc,l,mid,L,R));
    if(R>mid)   maxf=max(maxf,query_maxf(rc,mid+1,r,L,R));
    return maxf; 
}
int query_minz(int now,int l,int r,int L,int R)
{
    int minz=INF;
    if(l>=L&&r<=R)
        return tree[now].minz;
    int mid=(l+r)>>1;
    if(L<=mid)  minz=min(minz,query_minz(lc,l,mid,L,R));
    if(R>mid)   minz=min(minz,query_minz(rc,mid+1,r,L,R));
    return minz; 
}
int query_minf(int now,int l,int r,int L,int R)
{
    int minf=0;
    if(l>=L&&r<=R)
        return tree[now].minf;
    int mid=(l+r)>>1;
    if(L<=mid)  minf=min(minf,query_minf(lc,l,mid,L,R));
    if(R>mid)   minf=min(minf,query_minf(rc,mid+1,r,L,R));
    return minf; 
}
void Push_up(int now)
{
    Tree[now].maxz=max(Tree[lc].maxz,Tree[rc].maxz);
    Tree[now].maxf=max(Tree[lc].maxf,Tree[rc].maxf);
    Tree[now].minf=min(Tree[lc].minf,Tree[rc].minf);
    Tree[now].minz=min(Tree[lc].minz,Tree[rc].minz); 
}
void Build(int now,int l,int r)
{
    Tree[now].minz=INF,Tree[now].maxf=-INF;
    if(l==r)
    {
        int x=read();
        if(x>=0)  Tree[now].maxz=Tree[now].minz=x;
        else  Tree[now].maxf=Tree[now].minf=x;
        return ;
    }
    int mid=(l+r)>>1;
    Build(lc,l,mid);
    Build(rc,mid+1,r);
    Push_up(now);
}
int Query_maxz(int now,int l,int r,int L,int R)
{
    int maxz=0;
    if(l>=L&&r<=R)
        return Tree[now].maxz;
    int mid=(l+r)>>1;
    if(L<=mid)  maxz=max(maxz,Query_maxz(lc,l,mid,L,R));
    if(R>mid)   maxz=max(maxz,Query_maxz(rc,mid+1,r,L,R));
    return maxz; 
}
int Query_maxf(int now,int l,int r,int L,int R)
{
    int maxf=-INF;
    if(l>=L&&r<=R)
        return Tree[now].maxf;
    int mid=(l+r)>>1;
    if(L<=mid)  maxf=max(maxf,Query_maxf(lc,l,mid,L,R));
    if(R>mid)   maxf=max(maxf,Query_maxf(rc,mid+1,r,L,R));
    return maxf;
}
int Query_minz(int now,int l,int r,int L,int R)
{
    int minz=INF;
    if(l>=L&&r<=R)
        return Tree[now].minz;
    int mid=(l+r)>>1;
    if(L<=mid)  minz=min(minz,Query_minz(lc,l,mid,L,R));
    if(R>mid)   minz=min(minz,Query_minz(rc,mid+1,r,L,R));
    return minz; 
}
int Query_minf(int now,int l,int r,int L,int R)
{
    int minf=0;
    if(l>=L&&r<=R)
        return Tree[now].minf;
    int mid=(l+r)>>1;
    if(L<=mid)  minf=min(minf,Query_minf(lc,l,mid,L,R));
    if(R>mid)   minf=min(minf,Query_minf(rc,mid+1,r,L,R));
    return minf; 
}
signed main()
{
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    n=read(),m=read(),q=read();
    build(1,1,n);
    Build(1,1,m);
    while(q--)
    {
        int l1=read(),r1=read(),l2=read(),r2=read();
        int maxz=query_maxz(1,1,n,l1,r1),maxf=query_maxf(1,1,n,l1,r1),minf=query_minf(1,1,n,l1,r1),minz=query_minz(1,1,n,l1,r1);
        int Maxz=Query_maxz(1,1,m,l2,r2),Maxf=Query_maxf(1,1,m,l2,r2),Minf=Query_minf(1,1,m,l2,r2),Minz=Query_minz(1,1,m,l2,r2);
        if(Maxf==-INF&&maxz)   printf("%lld\n",maxz*Minz);
        else if(Maxf==-INF&&minz==INF)  printf("%lld\n",maxf*Maxz);
        else if(Maxf==-INF&&maxz&&minf!=0)  printf("%lld\n",maxz*Minz);  
        else if(Minz==INF&&minz==INF)  printf("%lld\n",minf*Maxf);
        else if(Minz==INF&&maxf==-INF)  printf("%lld\n",minz*Minf);
        else if(Minz==INF&&maxf!=-INF&&minz!=INF)   printf("%lld\n",minf*Maxf);
        else if(maxf==-INF&&Maxf!=-INF&&Minz!=INF)  printf("%lld\n",minz*Minf);
        else if(minz==INF&&Maxf!=-INF&&Minz!=INF)  printf("%lld\n",maxf*Maxz);
        else printf("%lld\n",max(maxf*Maxz,minz*Minf));
        //cout<<maxz<<"  "<<minz<<"  "<<maxf<<"  "<<minf<<"  "<<Maxz<<"  "<<Minz<<"  "<<Maxf<<"  "<<Minf<<endl;
    }
    return 0;
}

T3

成功颠覆我对于 hash 的认知。。。

40pts

发现可以发动反击的条件就是整个图是一个环，可以实现连续穿梭的条件就是这个点出度为 1 。

暴力按照题目的四种操作进行模拟即可。

#include<iostream>
using namespace std;
const int N=5e5+5;
struct node
{
    int to,next,flag;
};
node edge[N];
int head[N],vis[N],outd[N],qz[1005][1005];
int n,m,num,flag;
inline int read()
{
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9')
   {  if(ch=='-')  w=-1;  ch=getchar();}
   while(ch>='0'&&ch<='9')
   {  s=s*10+ch-'0'; ch=getchar();}
   return s*w;
}
void add(int u,int v)
{
    ++num;
    qz[u][v]=num;
    edge[num].to=v;
    edge[num].next=head[u];
    head[u]=num;
}
int dfs(int now,int tim)
{
    vis[now]=tim;
    for(int i=head[now];i;i=edge[i].next)
    {
        if(edge[i].flag)  continue;
        int v=edge[i].to;
        if(vis[v]==tim)  return 1;
        if(dfs(v,tim))  return 1;
    }
    return 0;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read();
        outd[u]++;
        add(u,v);
    }
    int q=read();
    while(q--)
    {
        int flag=1;
        int t=read();
        if(t==1)
        {
            int u=read(),v=read();
            outd[u]--;
            edge[qz[u][v]].flag=1;
        }
        if(t==2)
        {
            int u=read();
            for(int i=1;i<=n;++i)
            {
                if(qz[i][u]&&!edge[qz[i][u]].flag)
                {
                    edge[qz[i][u]].flag=1;
                    outd[i]--;
                }
            }
        }
        if(t==3)
        {
            int u=read(),v=read();
            edge[qz[u][v]].flag=0;
            outd[u]++;
        }
        if(t==4)
        {
            int u=read();
            for(int i=1;i<=n;++i)
            {
                if(qz[i][u]&&edge[qz[i][u]].flag)
                {
                    edge[qz[i][u]].flag=0;
                    outd[i]++;
                }
            }
        }
        for(int i=1;i<=n;++i)
        {
            if(vis[i]!=q&&!dfs(i,q))
            {
                flag=0;
                break;
            }
        }
        if(flag)
        {
            for(int i=1;i<=n;++i)  
                if(outd[i]!=1)  
                {
                    flag=0;
                    break;
                }
            if(flag==1)  printf("YES\n");
            else printf("NO\n");
        }
        else printf("NO\n");
    }
    return 0;
}

50pts

发现只要所有点的出度都为 1 ，那么这个图一定有环，所以反击的条件变为每个点的出度都为 1 。

维护全局答案，每次操作后判断。

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<map>
using namespace std;
const int N=5e5+5;
struct node
{
    int to,next,flag;
};
node edge[N];
map<int,int>  qz[N];
int head[N],outd[N];
int num,n,m,cnt;
inline int read()
{
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9')
   {  if(ch=='-')  w=-1;  ch=getchar();}
   while(ch>='0'&&ch<='9')
   {  s=s*10+ch-'0'; ch=getchar();}
   return s*w;
}
void add(int u,int v)
{
    ++num;
    qz[u][v]=num;
    edge[num].to=v;
    edge[num].next=head[u];
    head[u]=num;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read();
        add(u,v);
        outd[u]++;
    }
    for(int i=1;i<=n;++i)   
        if(outd[i]==1)  cnt++;
    int q=read();
    while(q--)
    {
        int t=read();
        if(t==1)
        {
            int u=read(),v=read();
            edge[qz[u][v]].flag=1;
            if(outd[u]==2)  cnt++;
            if(outd[u]==1)  cnt--;
            outd[u]--;
        }
        if(t==2)
        {
            int u=read();
            for(int i=1;i<=n;++i)
            {
                if(qz[i][u]&&!edge[qz[i][u]].flag)
                {
                    if(outd[i]==1)  cnt--;
                    if(outd[i]==2)  cnt++;
                    outd[i]--,edge[qz[i][u]].flag=1;
                }
            }
        }
        if(t==3)
        {
            int u=read(),v=read();
            edge[qz[u][v]].flag=0;
            if(outd[u]==1)  cnt--;
            if(outd[u]==0)  cnt++;
            outd[u]++;
        }
        if(t==4)
        {
            int u=read();
            for(int i=1;i<=n;++i)
            {
                if(qz[i][u]&&edge[qz[i][u]].flag)
                {
                    edge[qz[i][u]].flag=0;
                    if(outd[i]==1)  cnt--;
                    if(outd[i]==0)  cnt++;
                    outd[i]++;
                }
            }
        }
        if(cnt==n)  printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

10.3(30pts=30pts+0pts+0pts)

大寄。

$T2$ 这数组。。。我无语了。 $T3$ 我不想说什么，新建了几次被删几次。 ## $11.15(25pts=0pts+0pts+5pts+20pts)

感觉挺难受的。。。

其实现在想想也不能怪谁，饭卡是自己丢的，核酸码也是自己丢的，考试时间是自己浪费的，考完之后成绩不理想就开始埋怨，确实不应该这样。 $T2$ 考试的时候自己想出了正解，但是自己把自己給否定了，当时自己兴奋地以为自己要切了（大雾，但是最后还不是 $0$ 分。忽然又想起来初中老师说过的话，能做出难题不叫能力，能考出分来才叫能力，平时再厉害，思路再对，考不出分来啥也白搭，考出分来才叫实力，才叫能力，考不出来那叫潜力，一个人很有潜力是没有用的，只有潜力没有实力，也不能说是有能力。