ABC371总结

AtCoder Beginner Contest 371

一些废话

想着以后换一种方式写总结，不再以那种题解形式，写起来又累又难写，只对其中部分有意思的题目写出完整的题解。就是以随笔的形式，在打完比赛后写出自己的一些感悟，每道题做的过程中的一些思路、用时和需要改进的地方，就是类似随笔之类的，随便写写。

A

用时：8分37秒

很基础的语法题，可是我当场降智，正解应该是判断 \(a,b,c\)，中是否满足第二大，我竟然直接对其大小情况进行枚举然后判断是否合法再输出第二大，硬是搞了 \(8\) 分钟

赛时code

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


int main ()
{
    char a,b,c;
    int x,y,z;
    cin>>a>>b>>c;
    for(int x=1;x<=3;x++)
        for(int y=1;y<=3;y++)
            for(int z=1;z<=3;z++) 
            {
                if(x!=y&&y!=z&&x!=z)
                {
                    if(a=='<') if(x>y) continue;
                    if(a=='>') if(x<y) continue;
                    if(b=='<') if(x>z) continue;
                    if(b=='>') if(x<z) continue;
                    if(c=='<') if(y>z) continue;
                    if(c=='>') if(y<z) continue;
                    if(x==2) cout<<'A'<<"\n";
                    if(y==2) cout<<'B'<<"\n";
                    if(z==2) cout<<'C'<<"\n";
                    return 0;
                }
            }
    return 0;
}

code

B

这就没啥好说的了，记录下长子是谁，判断一下就好了。

用时：4分57秒

code

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

const int N=105;
int n,m;
int st[N];
int ans[N];

int main ()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int id;
        char c;
        cin>>id>>c;
        st[i]=id;
        if(c=='F') continue;
        if(ans[id]==0) ans[id]=i;
    }
    for(int i=1;i<=m;i++) 
    {
        if(ans[st[i]]==i)  cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
}

C

用时：22分03秒

一开始是没想出来的，后面写完 \(D\) 回来看到数据范围，\(n\) 特别小，就想到枚举 \(p\) 的全排列，再进行统计。双向的问题还搞了我一会。

code

#include <bits/stdc++.h>
using namespace std;
const int N=10;
int n;
int m1,m2;
int p[N];
int g[N][N],h[N][N],a[N][N];
int ans=0x3f3f3f3f;
int main ()
{
    cin>>n;
    cin>>m1;
    for(int i=1;i<=m1;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x][y]=g[y][x]=1;
    }
    cin>>m2;
    for(int i=1;i<=m2;i++)
    {
        int x,y;
        cin>>x>>y;
        h[x][y]=h[y][x]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            cin>>a[i][j],a[j][i]=a[i][j];
    for(int i=1;i<=n;i++) p[i]=i;
    do
    {
        int cnt=0;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                int x=p[i],y=p[j];
                if(g[i][j]!=h[x][y]) cnt+=a[x][y];
            }
        ans=min(ans,cnt);
        
    }while(next_permutation(p+1,p+n+1));
    cout<<ans<<"\n";
    return 0;
}

D

用时：20分18秒

没啥好说的，简单的离散化加前缀和。一开始我空间开小了，吃了一次罚时。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,q;
int p[N];
int b[N*3];
int tot;
ll a[N],c[N];
int l[N],r[N];

int main ()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i],b[++tot]=p[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>l[i]>>r[i];
        b[++tot]=l[i];
        b[++tot]=r[i];
    }
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=n;i++)
    {
        int id=lower_bound(b+1,b+tot+1,p[i])-b;
        c[id]=a[i];
    }
    for(int i=1;i<=tot;i++) c[i]+=c[i-1];
    for(int i=1;i<=q;i++)
    {
        int x=lower_bound(b+1,b+tot+1,l[i])-b;
        int y=lower_bound(b+1,b+tot+1,r[i])-b;
        cout<<c[y]-c[x-1]<<"\n";
    }
    return 0;
}

E

用时：35分51秒

也是一开始没有思路，瞪了十分钟 \(F\) 以后回来想，不能 \(n^2\)，考虑前缀和思想。整体考虑 \(sum_i\) 表示以 \(i\) 作为左端点的所有子序列产生的贡献。从 \(sum_1\) 开始，依次考虑每次删去第一个数后 \(sum\) 如何变化。
考虑子序列 \([i,r]\)，删去 \(i\) 后，什么情况下才能使该子序列不同元素的个数减一？
当然是当后面没有 \(a_i\) 的情况下。也就是说我们要找到最大的 \(r\) 使 \([i+1,r]\) 中没有 \(a_i\)，比他小的子序列如果还有元素的话就都应该减一。
因此按元素记录下所有元素所出现的位置，每次找到下一个 \(a_i\) 出现的位置，再对 \(sum\) 进行更新。

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n;
int a[N],b[N],c[N];
vector<int> g[N];
int v[N];
ll ans,sum;
int main ()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) 
    {
        g[a[i]].push_back(i);
        b[i]=b[i-1];
        if(c[a[i]]==0) b[i]++;
        c[a[i]]++;
        sum+=b[i];
    }
    for(int i=1;i<=n;i++) g[i].push_back(n+1);
    ans+=sum;
    for(int i=1;i<n;i++)
    {
        int id=g[a[i]][++v[a[i]]];
        sum-=(id-i);
        ans+=sum;
    }
    cout<<ans<<"\n";
    return 0;
}

剩下的就等补完题再写了。