The 13th Shandong ICPC Provincial Collegiate Programming Contest

https://codeforces.com/gym/104417

B. Building Company

题意

有一家建筑公司，一开始你有 $g$ 种员工。第 $i$ 种员工编号为 $t_i$，有 $u_i$ 个。一共有 $n$ 项任务，第 $i$ 项任务有 $m_i$ 个指标，第 $j$ 个指标需要编号为 $a_{i,j}$ 的员工至少有 $b_{i,j}$ 个。完成第 $i$ 项任务有 $k_i$ 个奖励，第 $j$ 个奖励为编号 $c_{i,j}$ 的员工 $d_{i,j}$ 个。每项任务只能完成一次，完成任务不消耗员工，只是需要员工数量达到要求。现在可以任意安排完成任务的顺序，问最多可以完成多少个任务。

题解

首先，我们有最朴素的做法：先看看一开始有哪些任务可以做，然后加上这些任务的奖励，看看又有哪些任务可以做了，依此类推，直到任务全都做完了或者没有可以做的任务了。但这样显然会超时。

我们考虑在此基础上优化：每当一个任务完成后，它给出奖励名额只针对了一些编号。我们可以只检查包含这些编号且未被完成的任务。但是，每次重新检查一个任务的开销同样很大，所以，我们可以对每个任务维护它还有多少个指标没有完成。同时，对于每个编号，我们只保存那些没有还没有满足的任务，按需要的人数插入一个小根堆。每当一个任务完成后，我们对每个奖励，检查对应编号的堆顶是否能被满足，若可以，则对应任务指标数减一，若为 $0$，则加入队列。

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=1e5+5;
int m[N];
pii a[N];
vector<pii> b[N];
unordered_map<int,priority_queue<pii,vector<pii>,greater<pii>>> mp;
unordered_map<int,ll> have;
queue<int> q;
void add(int t,int u)
{
    ll &val=have[t];
    val+=u;
    priority_queue<pii,vector<pii>,greater<pii>> &pq=mp[t];
    while(!pq.empty())
    {
        pii p=pq.top();
        if(p.first>val) break;
        pq.pop();
        if(!(--m[p.second])) q.push(p.second);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int g;cin>>g;
    for(int i=1;i<=g;i++) cin>>a[i].first>>a[i].second;
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>m[i];
        for(int j=1;j<=m[i];j++)
        {
            int x,y;cin>>x>>y;
            mp[x].push({y,i});
        }
        int k;cin>>k;
        for(int j=1;j<=k;j++)
        {
            int x,y;cin>>x>>y;
            b[i].push_back({x,y});
        }
    }
    for(int i=1;i<=n;i++)
        if(!m[i]) q.push(i);
    for(int i=1;i<=g;i++) add(a[i].first,a[i].second);
    int ans=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        ans++;
        for(auto i:b[u]) add(i.first,i.second);
    }
    cout<<ans<<'\n';
    return 0;
}

J. Not Another Path Query Problem

题意

给出一张 $n$ 个点 $m$ 条边的无向图。对于一条 $u$ 到 $v$ 的路径，定义路径的权值为该条路径上所有边的边权按位与的结果。现给出一个阈值 $V$。给出 $q$ 次询问，每次询问 $u$ 到 $v$ 是否存在一条路径的权值大于等于阈值。

题解

考虑大于等于阈值的数，一定有一段相同的公共前缀，然后下一位阈值为 $0$，该数为 $1$（也可能不存在这样的位），后面的位置没有限制。这样的限制至多有 $\log V$ 种。对于每一种限制，我们保留符合该限制的所有的边，然后判断一下每个点属于哪个连通块。如果点 $u$ 和点 $v$ 在某个限制下处于同一个连通块内，那么它们间就存在符合条件的路径。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct edge
{
    int v;
    ll w;
};
vector<edge> g[N];
pair<int,int> qry[5*N];
bool ans[5*N];
int n,m,q,f[N];
ll V;
void bfs(int s,ll x)
{
    queue<int> q;
    q.push(s);f[s]=s;
    while(!q.empty())
    {
        int u=q.front();q.pop(); 
        for(auto i:g[u])
        {
            int v=i.v;ll w=i.w;
            if(!f[v]&&(w&x)==x) 
            {
                q.push(v);
                f[v]=s;
            }
        }
    }
}
void solve(ll x)
{
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
        if(!f[i]) bfs(i,x);
    for(int i=1;i<=q;i++) ans[i]|=(f[qry[i].first]==f[qry[i].second]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>q>>V;
    for(int i=1;i<=m;i++)
    {
        int u,v;ll w;cin>>u>>v>>w;
        g[u].push_back({v,w}),g[v].push_back({u,w});
    }
    for(int i=1;i<=q;i++) cin>>qry[i].first>>qry[i].second;
    if(!V) solve(0);
    else 
    {
        for(ll i=V;i<(1ll<<60);i+=i&(-i)) solve(i);
    }
    for(int i=1;i<=q;i++) cout<<(ans[i]?"Yes":"No")<<'\n';
    return 0;
}