AtCoder Beginner Contest 216

https://atcoder.jp/contests/abc216

F - Max Sum Counting

题意

给定长度为 $n$ 的数组 $a,b$。求满足 $\max_{i\in S} a_i\geq \sum_{i\in S}b_i$ 的非空集合 $s$ 的数量。

数据范围：$1\leq n,a_i,b_i\leq 5000$。

题解

最关键的一步就是将数组按照 $a$ 排序。

然后就是做一遍背包，求出 $b$ 中前 $i$ 个数和为 $j$ 的方案，将和不超过 $a_i$ 的加入答案。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5005;
const int p=998244353;
pair<int,int> a[N];
ll f[N][N][2],sum[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first;
    for(int i=1;i<=n;i++) cin>>a[i].second;
    sort(a+1,a+n+1);
    ll ans=0;
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=5000;j++)
        {
            f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%p;
            if(j>=a[i].second) 
            {
                f[i][j][1]=(f[i-1][j-a[i].second][0]+f[i-1][j-a[i].second][1])%p;
                if(j<=a[i].first) ans=(ans+f[i][j][1])%p;
            }
        }
    cout<<ans<<'\n';
    return 0;
}

G - 01Sequence

题意

给出一个长度为 $n$ 的 $01$ 串 $a$，给出 $m$ 组限制 $(l,r,x)$，代表 $a_l\sim a_r$ 中至少有 $x$ 个 $1$。要求构造一个含 $1$ 最少的符合限制的 $a$。

数据范围：$1\leq n,m\leq2\times10^5$.

题解

记 $sum_i$ 为 $a$ 中前 $i$ 个位置 $0$ 的总数，则每组限制可以写为

$$sum_{r}-sum_{l-1}\leq r-l+1-x$$

这正是差分约束的形式。

所以再加上 $sum_i$ 自带的限制

$$\begin{aligned} &sum_i-sum_{i-1}\leq 1\\ &sum_{i-1}-sum_u\leq 0 \end{aligned}$$

然后跑差分约束就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct edge
{
    int v,w;
};
struct node 
{
    int dis,u;
    bool operator<(const node& a)const {return dis>a.dis;}
};
int dis[N];
bool vis[N];
vector<edge> g[N];
priority_queue<node> q;
void dijkstra(int s) 
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    q.push({0,s});
    while(!q.empty()) 
    {
        int u=q.top().u;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto i:g[u]) 
        {
            int v=i.v,w=i.w;
            if(dis[v]>dis[u]+w) 
            {
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int l,r,x;cin>>l>>r>>x;
        g[l-1].push_back({r,r-l+1-x});
    }
    for(int i=0;i<n;i++) g[i].push_back({i+1,1}),g[i+1].push_back({i,0});
    dijkstra(0);
    for(int i=1;i<=n;i++) cout<<1-(dis[i]-dis[i-1])<<" \n"[i==n];
    return 0;
}