ABC-271解题报告

发表于 2022-10-04 分类于解题报告

C. Manga

题意：有一本书有 $n$ 卷，你需要从第一卷开始依次看，一旦没有某一卷就停止。在看之前你可以进行若干次操作，每次卖掉任意两卷并买新的任意一卷。问操作结束后最多能看多少卷。

做法 1

注意到拥有的重复的卷都可以没有损失地卖掉，提前记录一下。然后从小到大扫，如果没有这一卷就尝试卖两本并买这一本。卖的两本优先从重复的卷里考虑，然后再贪心从大到小卖。正确性显然，数据结构维护即可。

#include <bits/stdc++.h>
using namespace std;

int n;
set <int> S;
int cur;

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a; scanf("%d", &a);
        if (S.count(a)) cur++;
        else S.insert(a);
    }
    for (int i = 1; ; i++)
        if (!S.count(i)) {
            while (cur < 2 && !S.empty() && *S.rbegin() > i) {
                auto it = S.end(); it--;
                cur++; S.erase(it);
            }
            if (cur >= 2) {
                cur -= 2;
                S.insert(i);
            } else {
                printf("%d\n", i - 1);
                return 0;
            }
        }
    return 0;
}

做法 2

考虑二分答案。对于读 $i$ 卷的情况，将 $>i+1$ 的卷和 $\le i$ 的重复的卷全部卖掉替换，判断是否能填补空隙。

By heno239

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    rep(i, n)cin >> a[i];
    //[1,x]
    auto can = [&](int x) {
        vector<int> cnt(x+1);
        int z = 0;
        rep(i, n) {
            if (a[i] > x)z++;
            else {
                if (cnt[a[i]])z++;
                cnt[a[i]] = 1;
            }
        }
        int r = 0;
        rep1(i, x) {
            if (!cnt[i])r++;
        }
        if (z >= 2 * r)return true;
        return false;
    };
    int le = 0, ri = n + 5;
    while (ri - le > 1) {
        int m = (le + ri) / 2;
        if (can(m)) {
            le = m;
        }
        else {
            ri = m;
        }
    }
    cout << le << "\n";
}

做法 3

与二分答案类似，但将二分改成了枚举。注意到读的卷数一定不会超过 $n$ ，所以 $>n$ 的卷都可以直接卖掉。考虑统计能否读 $i$ 卷。考虑设计 $bak[i]$ 表示 $\le i$ 的卷有多少种，则如果要读 $i$ 卷，将会有 $i-bak[i]$ 个位置空缺。这些位置可以使用多余的补上，而只有 $bak[i]$ 卷是不多余的（每种只有一卷不多余，剩下的都多余），所以总的多余的数量为 $n-bak[i]$ ，比较空缺位置与多余数量的一半即可。

By He_Ren

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 3e5 + 5;

int a[MAXN], bak[MAXN];

int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
        scanf("%d",&a[i]);

    for(int i=1; i<=n; ++i)
        if(a[i] <= n) bak[a[i]] = 1;
    for(int i=1; i<=n+1; ++i)
        bak[i] += bak[i-1];

    for(int i=1; i<=n+1; ++i)
    {
        if(i - bak[i] > (n - bak[i]) / 2)
        {
            printf("%d\n",i-1);
            return 0;
        }
    }
    return 0;
}

错解

By daisybunny

#include<bits/stdc++.h>
using namespace std;
int n;
int a[300005];
map<int,int> mp;
int ba;
int ans;
int main()
{
    cin>>n;
    for(int t=0;t<n;t++)
    {
        cin>>a[t];
        mp[a[t]]++;
    }
    sort(a,a+n);
    for(int t=1;;t++)
    {
        if(mp[t]==0)
        {
            if(ba>1)
            {
                ba-=2;
                ans++;
            }
            else if(n>=1&&t<a[n-1]&&ba==1)
            {
                mp[a[n-1]]--;n--;ba--;ans++;
            }
            else if(n>=2&&t<a[n-2])
            {
                mp[a[n-1]]--;mp[a[n-2]]--;n-=2;ans++;
            }
            else
                break;
        }
        else
        {
            ans++;
            ba+=mp[t]-1;
            mp[t]--;
        }
    }
    cout<<ans;
    return 0;
}

一组 hack 数据为

1 2	6 1 3 4 4 5 5

此时在算到 2 的空缺时，该代码会优先卖掉两个 5，而最优解应该卖掉多余的一个 4 一个 5。此程序的问题在于，他考虑到了优先卖掉重复的，但只判断了优先卖掉 $\le i$ 的重复的，而没有优先处理 $>i$ 的重复。

D. Flip and Adjust

题意：有 $n$ 张卡片，第 $i$ 张正面为 $a_i$ ，反面为 $b_i$ ，问是否存在一种翻转方案使得卡片的和为 $S$ 。如果有，输出方案。

设 $dp[i][j]=0/1$ 表示前 $i$ 张卡片能否得到 $j$ ，则

dp[i][j]=dp[i-1][j-a_i] \text{ or } dp[i-1][j-b_i]

#include<bits/stdc++.h>
using namespace std;
int a[110],b[110];
bool f[110][10010],pre[110][10010];
void get(int now,int x) {
    if(now==0) return;
    if(pre[now][x])
        get(now-1,x-a[now]);
    else get(now-1,x-b[now]);
    cout<<(pre[now][x]?'H':'T');
}
signed main() {
    int n,s;
    cin>>n>>s;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=s;j++) {
            if(j>=a[i]&&f[i-1][j-a[i]])
                f[i][j]=1,pre[i][j]=1;
            if(j>=b[i]&&f[i-1][j-b[i]])
                f[i][j]=1,pre[i][j]=0;
        }
    if(f[n][s]) {
        cout<<"Yes"<<endl;
        get(n,s);
        cout<<endl;
    }
    else cout<<"No"<<endl;
    return 0;
}

E. Subsequence Path

题意：有 $n$ 个点 $m$ 条有向有权边 $u_i\xrightarrow{w_i} v_i$ 和一个边的编号序列 $e_i$ ，你可以选择编号序列的一个子序列，使得该子序列的边构成一条 $1\to n$ 的路径，求最短路径。

直接 DP。令 $f_{i,j}$ 表示只考虑序列中前 $j$ 条边， $1\to j$ 的最短路径，则

f_{i,j}=\begin{cases}\min(f_{i-1,j},f_{i-1,u_{e_i}}+w_{e_i})\text{ if }v_{e_i}=j\\f_{i-1,j}\text{ otherwise}\end{cases}

此时第一维可以省略。转移时只需要更新 $f_{v_{a_i}}$ 即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct edge {
    int u,v,w;
} a[200010];
int e[200010];
int f[200010];
signed main() {
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
        cin>>a[i].u>>a[i].v>>a[i].w;
    for(int i=1;i<=k;i++)
        cin>>e[i];
    memset(f,-1,sizeof(f));
    f[1]=0;
    for(int i=1;i<=k;i++) {
        if(f[a[e[i]].u]==-1) continue;
        if(f[a[e[i]].v]==-1||f[a[e[i]].v]>f[a[e[i]].u]+a[e[i]].w)
            f[a[e[i]].v]=f[a[e[i]].u]+a[e[i]].w;
    }
    cout<<f[n]<<endl;
    return 0;
}

F. XOR on Grid Path

题意：有一个 $n\times n$ 的矩阵，每个格子有一个正整数，每次只能向右走或向下走，问有多少条路径能从 $(1,1)$ 走到 $(n,n)$ ，且路径异或和为 $0$ 。

双向搜索。搜索从 $(1,1)$ 到副对角线的所有方案，存到 $map$ 里，再搜索从 $(n,n)$ 到副对角线的所有方案，计算答案。

#include<bits/stdc++.h>
using namespace std;
int n,a[30][30];
map<int,int> m[2][21];
void dfs(int x,int y,int f,int flag) {
    f^=a[x][y];
    if(x+y==n+1) m[flag][x][f]++;
    else if(flag) dfs(x-1,y,f,flag),dfs(x,y-1,f,flag);
    else dfs(x+1,y,f,flag),dfs(x,y+1,f,flag);
}
signed main() {
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    dfs(1,1,0,0);
    dfs(n,n,0,1);
    long long ans=0;
    for(int i=1;i<=n;i++) {
        int x=a[i][n+1-i];
        for(auto tmp:m[0][i])
            ans+=1ll*tmp.second*m[1][i][tmp.first^x];
    }
    cout<<ans<<endl;
    return 0;
}