How to AK ABC252

__vector__ · 2022-05-22 14:48:23 · 个人记录

前言：

被 D 题降智，E 题写了个 kruskal 结果被卡了，F 题是个普及组难度的原题但是我没去看，最后 rating：

\color{brown}\text{706} \rightarrow \color{brown}\text{725}$，什么时候才能上 $\color{green}\text{6kyu}

A

int ch=getchar();
cout<<char(ch);
两行代码结束。
复杂度：O(1)

B

这个东西直接模拟就行了。
复杂度：O(n+k)

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=105;
    int a[maxn],b[maxn];
    int k,n;
    int imax=0;
    void main()
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            imax=max(imax,a[i]);
        }
        for(int i=1;i<=k;i++)
        {
            cin>>b[i];
            if(a[b[i]]==imax)
            {
                printf("Yes");
                return;
            }
        }
        printf("No");

    }
}
int main()
{
    Main::main();
    return 0;
}

C

可以枚举 0 \rightarrow 9 代表最终每个都显示的数字，然后枚举每一秒，每一秒再枚举每个可以点击的按钮即可。
算一下就可以发现，最多 1000 秒就能使所有的卷轴显示相同的数字，因为极端情况下 10 秒才能控制一个卷轴，最多有 n 个卷轴，n \le 100，10 \times 100 = 1000。
总复杂度： O(10 \times 1000 \times n) = O(10000n)

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=105;
    char s[maxn][15];
    int n;
    bool vis[maxn];
    void main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s[i]);
        }
        int ans=0x3f3f3f3f;
        for(int i=0;i<10;i++)//zimu
        {
            int col=0;
            for(int t=0;t<=1000;t++)//miaoshu
            {
                bool flag=1;
                for(int j=1;j<=n;j++)
                {
                    if(!vis[j])
                    {
                        if(s[j][t%10]==(i+'0'))
                        {
                            vis[j]=1;
                            break;
                        }
                    }
                }
                for(int j=1;j<=n;j++)
                {
                    if(!vis[j])
                    {
                        flag=0;
                        break;
                    }
                }
                if(flag)
                {
                    col=t;
                    break;
                }
            }
            ans=min(ans,col);
            for(int j=1;j<=n;j++)
            {
                vis[j]=0;
            }
        }
        printf("%d",ans);
    }
}
int main()
{
    Main::main();
    return 0;
}

D

可以先计算所有情况，然后再减去不合法情况。
假设由有 n 个元素，那么在其中任意选择 3 个元素的情况有 \dfrac{n \cdot (n-1) \cdot (n-2)}{6} 个，任意选择 2 个元素的情况有 \dfrac{n \cdot (n-1)}{2} 个。
那么先定义两个函数，方便后面使用：

long long sum_3(long long n)
{
    return n*(n-1)*(n-2)/6;
}
long long sum_2(long long n)
{
    return n*(n-1)/2;
}

设一个元素 a_i 在数组中重复出现了 x 次，数组有 n 个元素。将会出现两种不合法情况，来分类一下。

第一种情况是三元组的组成元素全都是 a_i，这种情况有 \dfrac{x \cdot (x-1) \cdot (x-2)}{6}个，也就是 sum_3(x)。
第二种情况是三元组的两个元素是 a_i，直接在数组所有重复的 a_i 中挑选有 \dfrac{x \cdot (x-1)}{2} 个组合，显然，每个组合都会与其他 n-2 个元素形成新的组合，有 \dfrac{x \cdot (x-1)}{2} \cdot (n-2) 个情况。但是别忘了，其中有 \dfrac{x \cdot (x-1)}{2} \cdot (x-2) 种情况会组合成三个元素都相等的三元组，而这些情况已经在第一条处理过，这里不需要再处理，所以实际上只用处理 \dfrac{x \cdot (x-1)}{2} \cdot [n-2-(x-2)]=\dfrac{x \cdot (x-1)}{2} \cdot (n-x) 个情况

综上，设每个元素出现了 x_i，数组有 n 个元素，那么答案就是：

\dfrac{n \cdot (n-1) \cdot (n-2)}{6} - \sum_{i=1}^{n} (\dfrac{x_i \cdot (x_i-1) \cdot (x_i-2)}{6} + \dfrac{x_i \cdot (x_i-1)}{2} \cdot (n-x_i))

复杂度 O(n)（unordered_map 是 O(1)的）

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=2e5+5;
    unordered_map<int,int> im;
    int a[maxn];
    int n;
    ll sum_3(ll n)
    {
        return n*(n-1)*(n-2)/6ll;
    }
    ll sum_2(ll n)
    {
        return n*(n-1)/2ll;
    }
    void main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            im[a[i]]++;
        }
        ll ans=sum_3(n);
        for(int i=1;i<=n;i++)
        {
            if(im[a[i]])
            {
                ans-=sum_3(im[a[i]]);
                ans-=sum_2(im[a[i]])*ll(n-im[a[i]]);
                im[a[i]]=0;
            }
        }
        printf("%lld",ans);

    }
}
int main()
{
    Main::main();
    return 0;
}

E

不懂 prim 的~~请自行百度~~
这道题让构造一棵树使得 1 到每个点的距离之和最短。最短路 + 生成树，那么肯定就是 prim（赛时我不会 prim，所以寄了）。
这道题算是把堆优化版 prim 板子改改就能过的那种，来说一下：

把更新最短路的地方改成 dijkstra 的做法。
用 pair 的第一个关键字来存储边权，第二个关键字存储边的编号。当要取出队首节点时，直接取出 edge[que.top().second].to 即可。
如果 1 点存入小根堆种，取出队首节点时不会取出 1 点，而是取出 1 指向的节点，所以应该建立一个 0 号节点并将其连向 1 节点，初始时将 0 号节点压入小根堆。
用一个 queue<int> ans 来存储每个需要的边，每弹出队首，就将这条边加入其中，也就是：int id=que.top().second; ans.push((id+1)/2); 注：之所以 id 要加 1 然后除以 2 是因为建图的时候建的双向边，编号为 1,2 的是一条边，编号为 3,4 的是一条边..........

这道题就结束了。
复杂度： O((n+m)logm)

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=2e5+5;
    const int maxm=2e5+5;
    int head[maxn<<1];
    bool vis[maxn];
    ll dis[maxn];
    struct EDGE
    {
        int to,nxt,val;
    }edge[maxm<<1];
    int cnt;
    inline void add(int u,int to,int val)
    {
        edge[++cnt].to=to;
        edge[cnt].val=val;
        edge[cnt].nxt=head[u];
        head[u]=cnt;
    }
    int n,m;
    inline void prim()
    {
        queue<int> ans;
        priority_queue<pair<ll,int>> que;
        for(int i=0;i<=n;i++)
        {
            dis[i]=1e18;
        }
        dis[1]=0;
        que.push(make_pair(0,m*2+1));
        int tot=0;
        while(tot<n&&!que.empty())
        {
            int id=que.top().second;
            int u=edge[id].to;      
            que.pop();
            if(vis[u])continue;
            vis[u]=1;
            ans.push(((id+1)>>1));
            tot++;
            for(int i=head[u];i;i=edge[i].nxt)
            {
                int to=edge[i].to;
                if(dis[to]>dis[u]+ll(edge[i].val))
                {
                    dis[to]=dis[u]+ll(edge[i].val);
                    que.push(make_pair(-dis[to],i));
                }
            }
        }
        ans.pop();
        while(ans.size()!=0)
        {
            printf("%d ",ans.front());
            ans.pop();
        }
    }
    void main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int xi,yi,zi;
            scanf("%d%d%d",&xi,&yi,&zi);
            add(xi,yi,zi);
            add(yi,xi,zi);
        }
        add(0,1,0);
        prim();
    }
}
int main()
{
    Main::main();
    return 0;
}

F

这道题是合并果子原题，~~相信谁都会我就不说了~~
大意：给定一个大小为 l 的面包，要将面包分成 n 块，第 i 块面包大小为 a_i。
每次可以将一块面包切成两个任意大小的面包。每次切割面包都会产生相当于原来面包大小的代价，问完成操作的最小代价是多少。
把这个过程倒过来，变成合并面包就行了。现在问题转化为有 n 个大小为 a_i 的面包和一个大小为 l - \sum a_i 的面包，每次可以合并任意两个面包，合并的代价为两个面包大小之和。问合并出一个大小为 l 的面包的最小代价。
显然，每次选出大小最小的两个面包合并就能保证最后代价最小，用小根堆维护即可。
复杂度：O(nlogn)

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef long long ll;
    const int maxn=2e5+5;
    ll a[maxn];
    priority_queue<ll> que;
    int n;
    ll l;
    void main()
    {
        scanf("%d%lld",&n,&l);
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            que.push(-a[i]);
            l-=ll(a[i]);
        }
        if(l>0)
        {
            que.push(-l);
        }
        n=que.size();
        for(int i=1;i<n;i++)
        {
            ll t1=-que.top();
            que.pop();
            ll t2=-que.top();
            que.pop();
            ans+=t1+t2;
            que.push(-t1-t2);
        }
        printf("%lld",ans);
    }
}
int main()
{
    Main::main();
    return 0;
}

Ex

题目简略翻译：

有 C 个美丽值，分别为 1,2,......C
有 N 个宝石，每个宝石都有一个颜色 D_i，和一个美丽值 V_i（V_i \in {1,2,.....C}，每个美丽值都至少会在某个宝石上出现一次）

现在要在 n 个宝石中选 C 个颜色互不相同的宝石，每个方案的价值是选择的这 C 个宝石的美丽值的异或和。
问价值为第 k 大的方案的价值

题目分析：

老子不会

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    cout<<"老子不会";  
   return WA;
}