[self entertainment] construction notes week 2

Day 1

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

Interesting question

It is known that C Array to construct A Array

An obvious nonsense is not judged as 0 All the points are 1. Therefore, you only need to determine whether the current node or the successor node is 0 Just fine .

There is another obvious nonsense , A point is finally 0 or 1, It's only possible to be in the final state 0 or 1 to update . The drawer principle , That is to infer that 0 Point exclusion , It can only be 1 了 .

The current node has not been updated , So judge 0 or 1 The best way is to judge the point a[i] Is it 0.

Assume the current point is 1, He wants to be updated , It can only be 0 to update , This is not difficult to find . And you will find that it can only be followed 0 to update , And this 0 It's No a[i]+1 A little bit . Then we get if the current point is 1, Find a successor 0 Methods .

Assume the current point is 0, Then he may become 1 Finally, it becomes 0, It may also always become 1, It may not be updated . Only discuss the following 0 Update again . We found that n-a[i] Is the current node i Become 0 Time for . that (n-a[i])-(i-1) Is followed by a weight of 0 Node update again as 0 Time for , It can be judged that the position of the successor node is n-((n-a[i])-(i-1))+1==a[i]+i. At the same time, I found a very boring thing as long as a[i]+i stay n Within the range, the final result of this point is 0.

In any case, we can determine whether the current node or the successor is 0 The situation of , Everything else is 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

Hash , It's violent

#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

violence , But I didn't expect , I'm too fond of vegetables.

#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();
    }
}