【自娱自乐】构造笔记 week 2

Day 1

1659D Codeforces Round #782 (Div. 2) Reverse Sort Sum

挺有意思的题

已知C数组去构造A数组

一个很显然的废话所有不被判断为0的点都是1。所以只需要判定当前节点或后继节点是不是0就好了。

还有一个很显然的废话，一个点最终为0或1，只有可能是被最终状态下某个0或1更新。抽屉原理，也就是把被推理出为0的点排除，就只能是1了。

当前节点没有被更新，那么判断0或1的手段是判断该点a[i]是否为0。

假设当前点为1，他想要被更新，则只能被0更新，这个不难发现。并且会发现只能被后继的0更新，且这个0是第a[i]+1个点。则我们得到了如果当前点是1，找到后继0的方法。

假设当前点为0，那么他可能中途变成1最后又变成0，也可能一直变成1，也可能不被更新。只讨论被后继0再次更新的情况。我们发现n-a[i]是当前节点i成为0的时间。那么(n-a[i])-(i-1)是被后继权值为0节点更新再次为0的时间，可以判断后继节点的位置是n-((n-a[i])-(i-1))+1==a[i]+i。同时发现一个很无聊的东西只要a[i]+i在n范围内则该点最终结果是0。

我们得到了任何情况下判定当前节点或后继是0的情况，其他情况都是1了

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int st[maxn],a[maxn];
void solve()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)st[i]=-1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    
    for(int i=1;i<=n;i++)
    {
        if(st[i]==-1)
        {
            if(a[i]==0)st[i]=0;
            else 
            {
                st[i]=1;
                if(st[a[i]+1]==-1)
                st[a[i]+1]=0;
            }
        }
        else if(st[i]==0)
        {
            if(st[a[i]+i]==-1)
            st[a[i]+i]=0;
        }
    }
    for(int i=1;i<=n;i++)
    printf("%d%c",st[i]," \n"[i==n]);
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        solve();
    }
}

Codeforces Round #764 (Div. 3) E. Masha-forgetful

哈希，挺暴力的

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int maxn=1e3+10;
int f[maxn];
struct Node
{
    int l,r,p;
    Node(){l=r=p=0;}
};
Node get(int l,int r,int p)
{
    Node x;x.l=l,x.r=r,x.p=p;
    return x;
}
void solve()
{
    map<string,Node> mp;
    int n,m;scanf("%d%d",&n,&m);
    string s;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        for(int j=0;j+1<(int)s.size();j++)
        mp[s.substr(j,2)]=get(j,j+1,i);
        for(int j=0;j+2<(int)s.size();j++)
        mp[s.substr(j,3)]=get(j,j+2,i);
    }
    cin>>s;
    for(int i=1;i<=m;i++)f[i]=0;
    f[0]=1;
    for(int i=2;i<=m;i++)
    {
        if(i>=3&&f[i-3]&&mp.find(s.substr(i-3,3))!=mp.end())f[i]=3;
        else if(i>=2&&f[i-2]&&mp.find(s.substr(i-2,2))!=mp.end())f[i]=2;
    }
    if(!f[m]){printf("-1\n");return ;}
    vector<Node> res;
    int p=m;
    while(p){res.push_back(mp[s.substr(p-f[p],f[p])]);p-=f[p];}
    reverse(res.begin(),res.end());
    printf("%d\n",res.size());
    for(auto [l,r,p]:res)
    printf("%d %d %d\n",l+1,r+1,p);
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        solve();
    }
}

Educational Codeforces Round 119 (Rated for Div. 2)D. Exact Change

暴力，不过我没想到，我太菜了

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e2+10;
int a[maxn];
typedef long long ll;
int get(int n,int d1,int d2)
{
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int t=0x3f3f3f3f;
        for(int j=0;j<=d1;j++)
        for(int k=0;k<=d2;k++)
        {
            int r=a[i]-j-2*k;
            if(r<0)break;
            if(!(r%3))t=min(t,r/3);
        }
        res=max(res,t);
    }
    return res+d1+d2;
}
void solve()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int res=0x3f3f3f3f;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)res=min(res,get(n,i,j));
    printf("%d\n",res);
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        solve();
    }
}