Educational Codeforces Round 161 (Rated for Div. 2)

__vector__ · 2024-01-27 13:51:57 · 个人记录

自己做出了 ABCDE，F 是个什么玩意啊。

A

如果忽略 c，那么 a,b 无论如何可以匹配。

只要有一个位置可以在匹配 a,b 的情况下不匹配 c，那么有解。

#include <bits/stdc++.h>
using namespace std;
int T;
const int maxn=25;
char a[maxn],b[maxn],c[maxn];
int n;
void solve()
{
    scanf("%d",&n);
    scanf("%s",a+1);
    scanf("%s",b+1);
    scanf("%s",c+1);
    bool flag2=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==b[i])
        {
            if(c[i]!=a[i])
            {
                flag2=1;
            }
        }
        else
        {
            if(a[i]!=c[i]&&b[i]!=c[i])
            {
                flag2=1;
            }
        }
    }
    puts(flag2?"YES":"NO");
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

B

按照枚举三角形最长边长度考虑。

显然最长边在三角形中出现次数大于等于两次。

然后推个柿子就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
int t,n;
int a[maxn];
int cnt[maxn];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            cnt[a[i]]++;
        }
        ll ans=0;
        ll pre=0;
        for(int i=0;i<=n;i++)
        {
            ans+=max(0ll,1ll*cnt[i]*(cnt[i]-1)*(cnt[i]-2)/6ll);
            if(i!=0)
            {
               ans+=max(0ll,1ll*cnt[i]*(cnt[i]-1)*pre/2ll);    
            }
            pre+=cnt[i];
        }
        printf("%lld\n",ans);
        // clean
        for(int i=0;i<=n;i++)cnt[i]=0;
    }
    return 0;
}

C

预处理正向和反向的捷径数量的前缀和。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
const int maxn=1e5+5;
int n,m;
int a[maxn];
ll tagpre[maxn],tagsuf[maxn];// 在到达他之前经过了多少个捷径
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    a[0]=-1e9;
    a[n+1]=2e9+1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]-a[i-1]<a[i+1]-a[i])
        {
            tagsuf[i-1]+=(a[i]-a[i-1]-1);
        }
        else
        {
            tagpre[i+1]+=(a[i+1]-a[i]-1);
        }
    }
    for(int i=1;i<=n;i++)
    {
        tagpre[i]+=tagpre[i-1];
    }
    for(int i=n-1;i>=1;i--)
    {
        tagsuf[i]+=tagsuf[i+1];
    }
    scanf("%d",&m);
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x<y)
        {
            printf("%lld\n",a[y]-a[x]-tagpre[y]+tagpre[x]);
        }
        else
        {
            swap(x,y);
            printf("%lld\n",a[y]-a[x]-tagsuf[x]+tagsuf[y]);
        }
    }
    // clean
    for(int i=0;i<=n+1;i++)
    {
        tagpre[i]=0;
        tagsuf[i]=0;
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0; 
}

D

注意，如果上一轮某一个 mob 及他的的左右邻居都还活着，那么他这一轮仍然活着，因为每一轮生命重置。综上，其实每一轮只需要考虑上一轮被击杀的怪的邻居（当然，不考虑已被击杀的怪）。

于是用链表维护存活的 monster。

然后先构建一个队列 qd，存放所有可能造成击杀的 monster，初始设置为全部 monster 加入。

每一轮依次进行一下操作：

遍历可能造成影响的 monster 队列 qd，并统计被伤害的 monster 有哪些，以及分别受到的伤害，将所有受到伤害的 monster 加入队列 wait。
遍历所有受到伤害的 monster 队列 wait，对于被杀死的 monster，将其从链表删除并加入队列 death。
遍历队列 death，将其存活的邻居加入集合 qd2
为了下一轮统计完整，遍历 qd2，将其存活邻居集合 qd3
合并 qd2,qd3，并将 qd 替换为 qd2 和 qd3 的并集。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
int T;
const int maxn=3e5+5;
int n;
int a[maxn],d[maxn];
struct List
{
    int lef[maxn],rig[maxn];
    void rebuild()
    {
        FOR(i,1,n)
        {
            lef[i]=i-1;
        }
        FOR(i,1,n-1)
        {
            rig[i]=i+1;
        }
        rig[n]=rig[n+1]=0;
        lef[0]=lef[n+1]=0;
    }
    void del(int pos)
    {
        rig[lef[pos]]=rig[pos];
        lef[rig[pos]]=lef[pos];
    }
}lst;
ll dam[maxn];
bool dead[maxn];
/*
hack.in:  
1
4
1 1 1 2 
1 2 1 1 

hack.out
1 1 1 0

(heal 1,dam 1),(heal 2,dam 1),(heal 1,dam 2) 
*/
void solve()
{
    scanf("%d",&n);
    FOR(i,1,n)
    {
        scanf("%d",&d[i]);
    }
    FOR(i,1,n)
    {
        scanf("%d",&a[i]);
    }
    // 按照我的习惯，d=damage=攻击
    lst.rebuild();
    queue<int> qd,death;
    set<int> wait,qd2,qd3;
    FOR(i,1,n)
    {
        qd.push(i);
    }
    FOR(rounds,1,n)
    {
     //  printf("\n round %d\n",rounds);
        while(!qd.empty())
        {
            int u=qd.front();
         //   printf("u = %d\n",u);
          //  printf("lef = %d rig = %d\n",lst.lef[u],lst.rig[u]);
            if(lst.lef[u])
            {
                dam[lst.lef[u]]+=d[u];
                wait.insert(lst.lef[u]);
            }
            if(lst.rig[u])
            {
                dam[lst.rig[u]]+=d[u];
                wait.insert(lst.rig[u]);
            }
            qd.pop();
        }// 计算攻击
        int cntdeath=0;
        for(int u:wait)
        {
        /// printf("dam[%d] = %d\n",u,dam[u]);
            if(dam[u]>a[u])
            {
                lst.del(u);
                death.push(u);
           //     printf("death = %d,dam = %d\n",u,dam[u]);
                cntdeath++;
                dead[u]=1;
            }
            dam[u]=0;
        }// 处理死亡
        wait.clear();
        while(!death.empty())
        {
            int u=death.front();
            death.pop();
            if(lst.lef[u])qd2.insert(lst.lef[u]);
            if(lst.rig[u])qd2.insert(lst.rig[u]);
        }// 将死亡的mob 的邻居加入

        for(int v:qd2)
        {
            if(!dead[v])
            {
                if(lst.lef[v])qd3.insert(lst.lef[v]);
                if(lst.rig[v])qd3.insert(lst.rig[v]);
            }
        }
        for(int v:qd2)if(!dead[v])qd3.insert(v);
        for(int v:qd3)if(!dead[v])qd.push(v);
        qd2.clear();   
        qd3.clear();
        printf("%d ",cntdeath);  
    }
    FOR(i,1,n)dead[i]=0;
    printf("\n");
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

E

先将 X 减一，这样只需要统计非空子序列了。

注意，一个长度为 n 的上升子序列造成的贡献是 2^n -1，初步考虑从大到小依次构造不同长度的上升序列（注意，需要满足互相不影响），最终使得总贡献为 X。

但是需要注意，长度限制是 200，如果这样构造，那么总长度是 O(log_2^2 n) 的，无法通过。

这时候，考虑一些数列之间进行共用。

此时，可以想到，先构造一个最大的上升序列 base 使得贡献不超过 X，然后让相邻元素差的很大以留出充足预备空间，然后，在后面降序插入数组，每插入一个数字 x，设序列 base 前 id 个数字小于 x，那么总贡献将增加 2^{id}，这样就可以根据二进制完成构造了。

#include <bits/stdc++.h>
using namespace std;
const int maxn=205;
typedef long long ll;
int T;
ll ans[maxn];
ll ar[maxn];
void solve()
{
    ll x;
    scanf("%lld",&x);
    x--;
    if(lower_bound(ans+1,ans+63,x)-ans==64)
    {
        puts("-1");
        return;
    }
    int unti=upper_bound(ans+1,ans+63,x)-ans-1;
    if(unti==64)
    {
        puts("-1");
        return;
    }
    x-=ans[unti];
    //printf("unti = %d\n",unti);
    ar[1]=1;
    for(int i=2;i<=unti;i++)
    {
        ar[i]=ar[i-1]+1000;
    }
    int id=unti;
    while(x)
    {
    //  printf("id = %d x = %lld\n",id,x);
        while(ans[id]+1>x)id--;
        x-=(ans[id]+1);
        ar[++unti]=ar[id]+1;        
    }
    printf("%d\n",unti);
    for(int i=1;i<=unti;i++)
    {
        printf("%d ",ar[i]);
    }
    printf("\n");
}
int main()
{
    ans[0]=0;
    for(int i=1;i<=63;i++)
    {
        ans[i]=(unsigned long long)(ans[i-1]+1)*2ll-1ll;
    } 
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

F

暂时没想出来。