海亮 2025暑 VII

· · 个人记录

0818

NOIP 模拟赛结算

不能操作的人将输掉这场游戏。二人都采取最优策略，问游戏的获胜者是谁？

解释为什么「末尾有 k 个 0」会等价于 n = m \cdot p^k \quad \text{且} \quad p \nmid m
在 p 进制下，一个数 n 可以写成： n = a_0 + a_1 p + a_2 p^2 + \dots + a_r p^r ，其中每个 a_i 都是 0 \le a_i < p 的整数。

「末尾有 1 个 0」在 p 进制下表示 a_0 = 0。
这说明：

n = a_1 p + a_2 p^2 + \dots + a_r p^r = p >\cdot (a_1 + a_2 p + \dots + a_r p^{r-1}),

也就是说 p \mid n。

「末尾有 2 个 0」表示 a_0 = a_1 = 0。于是：

n = a_2 p^2 + a_3 p^3 + \dots + a_r p^r = >p^2 \cdot (a_2 + a_3 p + \dots + a_r p^{r-2}),

所以 p^2 \mid n。

「末尾有 k 个 0」表示 a_0 = a_1 = \dots = a_{k-1} = 0，但 a_k \neq 0。
于是：

n = a_k p^k + a_{k+1} p^{k+1} + \dots + a_r >p^r = p^k \cdot (a_k + a_{k+1} p + \dots + >a_r p^{r-k}),

其中括号里的数记作 m。
因为 a_k \neq 0，所以 m 不可能再被 p 整除。
「末尾有 k 个 0」⇔ n = m \cdot >p^k，并且 p \nmid m。

  • 有指数 \ge k → 先手一次性除尽该质因子，使后手无招可走 → 先手必胜（输出 Alice）。
  • 所有指数 <k → 起手即无合法操作 → 先手输（输出 Bob）。
  • 特例 k=1 → 只要 n>1 必有质因子，先手必胜。

    0821

1. 强连通分量

原理

特点

2. 割点

原理

特点

3. 割边（桥）

原理

特点

4. 点双连通分量

原理

特点

5. 边双连通分量

原理

算法 作用对象 条件判断 关注重点 结果
强连 有向图 dfn[u]==low[u] 栈中的点 每个强连通分量
割点 无向图 low[v] >= dfn[u] 点 哪些点是割点
割边 无向图 low[v] > dfn[u] 边 哪些边是割边
点双 无向图 low[v] >= dfn[u] 点集 输出点双分量
边双 无向图 dfn[u]==low[u] 边集/点集 输出边双分量

受欢迎的牛 G

校园网络

很多情况我们需要 DAG，对有环图，考虑通过强连通分量来缩点。

void tarjan(int u, int fa)
{

    int child = 0;
    vis[u]=1;
    low[u]=dfn[u]=++idx;
    hasb[u]=(u==b);
    for(int v : g[u])
    {
        if(v==fa) continue;
        if(!vis[v])
        {

            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(hasb[v] && fa!=u && low[v]>=dfn[u] && u!=a&& u!=b)
            {
                ans=min(ans,u);
            } 
            if(hasb[v]) hasb[u]=1;
        }
        else if(v!=fa)
        {
            low[u]=min(low[u],dfn[v]);
        }
    }

}

int main()
{
    cin >> n ;
    for (int i = 1; i <= 50000000; i++)
    {
        int x, y;
        cin >> x >> y;
        if(x==0 && y==0 ) break;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    cin>>a>>b;

    tarjan(a, -1);

    if(ans==0x3f3f3f3f)
    {
        cout<<"No solution"<<endl;
    }
    else cout<<ans<<endl;
    return 0;
}

间谍网络

}

int main() { int p; cin>>n>>p; for(int i=1;i<=n;i++) { my[i]=0x3f3f3f3f; w[i]=0x3f3f3f3f;

}
for(int i=1; i<=p; i++)
{
    int hao,shu;
    cin>>hao>>shu;
    my[hao]=shu;
}
int r;
cin>>r;
for(int i=1;i<=r;i++)
{
    cin>>u[i]>>v[i];
    g[u[i]].push_back(v[i]);
} 
for(int i=1; i<=n; i++)
{
    if(!dfn[i]&& my[i]!=0x3f3f3f3f ) tarjan(i);
}
for(int i=1;i<=n;i++)
{
    if(!dfn[i])
    {
        cout<<"NO"<<endl;
        cout<<i<<endl;
        return 0;
    }
}
for(int i=1; i<=r; i++)
{
    int x=scc[u[i]];
    int y=scc[v[i]];
    if(x!=y)
    {
        ng[x].push_back(y);
        rd[y]++;
    }
}

int ans=0;
for(int i=1; i<=num; i++)
{
    if(rd[i]==0)ans+=w[i];
}
cout<<"YES"<<endl<<ans<<endl;
return 0;

}

## [[POI 2008] BLO-Blockade](https://www.luogu.com.cn/problem/P3469)
- 求**类似于**割点状物，割开以后子树和非子树相乘有贡献。

- 下面的点和上面的点有贡献。

- 自己和任何其他点有贡献。

- 图一定联通，跑一遍 tarjan 即可。
```cpp
void tarjan(int u, int fa)
{
    sz[u]=1;
    int child = 0;
    vis[u]=1;
    low[u]=dfn[u]=++idx;int sum=0;
    for(int v : g[u])
    {
        if(!vis[v])
        {
            child++;
            tarjan(v,u);
            sz[u]+=sz[v];
            low[u]=min(low[u],low[v]);
            if( low[v]>=dfn[u])
            {
                flag[u]=1;
                sum+=sz[v];
                ans[u]+=(ll)(sz[v]*(n-sz[v]-1));

            } 
        }
        else if(v!=fa)
        {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(fa==u && child>=2)
    {
        flag[u]=1;
    }
    if(flag[u])
    {
        ans[u]+=(ll)sum*(n-1-sum);
    }
    ans[u]+=(ll)(2*(n-1));
}

signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    tarjan(1,1);

    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

[APIO2009] 抢掠计划

int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

cin>>n>>m;
for(int i=1; i<=m; i++)
{
    cin>>u[i]>>v[i];
    g[u[i]].push_back(v[i]);
}
for(int i=1; i<=n; i++)
{
    cin>>a[i];
}
int s,p;
cin>>s>>p;

for(int i=1; i<=p; i++)
{
    cin>>bar[i];
}
tarjan(s);
for(int i=1; i<=m; i++)
{
    int x=scc[u[i]],y=scc[v[i]];
    if(x!=y && y!=0 && x!=0)
    {
        ng[x].push_back(y);
        rd[y]++;
    }
}
for(int i=1; i<=num; i++)
{
    dp[i]=-1;
}
int ss = scc[s];
dp[ss] = w[ss];

toposort(ss);

ll ans = 0;
for (int i=1; i<=p; i++)
{
    ans = max(ans, dp[scc[bar[i]]]);
}

cout << ans <<endl;
return 0;

}