Educational codeforces round 132 (rated for Div. 2) C, d+ac automata

D. Rorororobot
The question ：n*m Matrix , From bottom to top is 1 To n That's ok , From left to right is 1 To m Column , Each column is continuous from bottom to top x Cells corrupted , If you give the starting and ending coordinates , And it is stipulated that it can only move in the same direction each time k Time , Whether we can reach the destination from the starting point .

Ideas ： Go to the top and go to the end , If it is blocked, you cannot , If there is one difference between the horizontal and vertical coordinates of two points that cannot be divided k Not good either. . So just look at the relationship between interval maximum and division

#include <iostream>
#include <cmath>
#define endl '\n'
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)/2)
using namespace std;
const int N = 2e5+100;

int tree[N<<2];
int a[N];

void up(int p)
{
    
    tree[p]=max(tree[ls],tree[rs]);
}
void bulid(int l,int r,int p)
{
    
    if(l==r)
    {
    
        tree[p]=a[l];
        return;
    }
    bulid(l,mid,ls);
    bulid(mid+1,r,rs);
    up(p);
}
int query(int nl,int nr,int l,int r,int p)
{
    
    if(nl<=l&&r<=nr)
    {
    
        return tree[p];
    }
    int res=-1;
    if(nl<=mid)
    {
    
        res=max(res,query(nl,nr,l,mid,ls));
    }
    if(nr>mid)
    {
    
        res=max(res,query(nl,nr,mid+1,r,rs));
    }
    return res;
}
int main()
{
    
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int n,m,q;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i];
    bulid(1,m,1);
    cin>>q;
    for(int i=1,xs,ys,xf,yf,k;i<=q;i++)
    {
    
        cin>>xs>>ys>>xf>>yf>>k;
        if(abs(xs-xf)%k||abs(ys-yf)%k)
        {
    
            cout<<"NO"<<endl;
            continue;
        }
        if(ys>yf)
            swap(ys,yf);
        int res=query(ys,yf,1,m,1);
        xs=n-((n-xs)%k);
        if(res>=xs)
        {
    
            cout<<"NO"<<endl;
        }
        else
        {
    
            cout<<"YES"<<endl;
        }

    }
    return 0;
}

C. Recover an RBS
The question ： Given a legal sequence of parentheses , Some characters use ’?' Instead of , Can you make all ‘?’ The only indication ？
Parenthesized ( The more forward, the easier it is to be legal , At least one legal filling method , Is to put all ( Fill out , Then fill in ). If there is a legal sequence , This must be legal
Then according to this conclusion , We put the first ‘)' And the last ‘(' swap , If it is still legal, then output no, Otherwise output yes.

Ideas ：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 5, INF = 0x3f3f3f3f;
char s[maxn];

int main(){
    

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
    
        cin >> s + 1;
        int n = strlen(s + 1);
        int cnt[2] = {
    0};
        for(int i = 1; i <= n; i++){
    
            if (s[i] == '(') cnt[0]++;
            else if (s[i] == ')') cnt[1]++;
        }
        if (cnt[0] == n / 2 || cnt[1] == n / 2){
    
            cout << "YES" << '\n';
            continue;
        }
        int left = n / 2 - cnt[0];
        int maxl = 0, minr = INF;
        for(int i = 1; i <= n; i++){
    
            if (s[i] == '?'){
    
                if (left){
    
                    left--, s[i] = '(';
                    maxl = max(maxl, i);
                }
                else{
    
                    s[i] = ')';
                    minr = min(minr, i);
                }
            }
        }
        swap(s[maxl], s[minr]);
        bool success = 0;
        int sum = 0;
        for(int i = 1; i <= n; i++){
    
            sum += (s[i] == '(' ? 1 : -1);
            if (sum < 0){
    
                success = 1;
                break;
            }
        }
        cout << (success ? "YES" : "NO") << '\n';
    }

}

C2. k-LCM (hard version)
Number theory ,, Inspected LCM The nature of .

#include <iostream>

using namespace std;

int main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=k-3;i++)
            cout<<1<<" ";
        n-=(k-3);
        if(n&1)
            cout<<1<<" "<<n/2<<" "<<n/2<<endl;
        else
        {
    
            n>>=1;
            if(n&1)
                cout<<2<<" "<<n-1<<" "<<n-1<<endl;
            else
                cout<<n/2<<" "<<n/2<<" "<<n<<endl;
        }
    }
    return 0;
}

AC automata

Pre knowledge ： Dictionary tree （ Master ）,KMP（ understand ）

use ：
Mainly used for multi pattern matching , To put it bluntly , Give you a string , I want to see how many strings this string can match . At this time , If you use kmp Violent solution , We are bound to require multiple strings of your next Array , Complexity explosion .

We need to use ACZ automata ACAM

Since you want to use AC automata , We need to construct a AC automata . The structure is divided into two parts ： Dictionary tree construction + Mismatch pointer construction

1. Make multiple mother strings used for matching into a dictionary tree , Learn the dictionary tree by default , So don't repeat

2.fail The pointer ,fali The purpose of pointer construction is to quickly find the next possible matching node , therefore fail The pointer always points to such a node The string represented by this node can contain the string represented by the current node , And it can match the remaining suffixes （ At least the next letter ）
We use it BFS The way to solve
Let's deal with it first 26 A string starting with an English letter fail, obviously , these fail Should point to the root node . Push them all into the queue
Then for each node that the queue points to , Each number in the queue represents the current node , And then according to == Of the child nodes of the current node fail The node pointed to by the pointer is the current node fail The pointer points to the child node of the node .== To construct the whole fail

AC automata

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
struct tree// Dictionary tree 
{
    
    int fail;// Mismatch pointer 
    int vis[26];
    int end;
};
tree AC[1000000];//Trie Trees , Size and depend on cnt Upper limit 
int cnt=0;//Trie The pointer to 
void add(string s)
{
    
    int l=s.length();
    int now=0;// Current pointer to the dictionary tree 
    for(int i=0;i<l;++i)// structure Trie Trees 
    {
    
        if(AC[now].vis[s[i]-'a']==0)//Trie The tree does not have this child node 
        {
    
            AC[now].vis[s[i]-'a']=++cnt;
        }
        now=AC[now].vis[s[i]-'a'];// Construct downward 
    }
    AC[now].end+=1;// Mark the end of the word 
}
void Get_fail()// structure fail The pointer 
{
    
    queue<int> Q;// queue 
    for(int i=0;i<26;++i)// Second floor fail Handle the pointer in advance 
    {
    
        if(AC[0].vis[i]!=0)
        {
    
            AC[AC[0].vis[i]].fail=0;// Point to the root node 
            Q.push(AC[0].vis[i]);// Push into the queue 
        }
    }
    while(!Q.empty())//BFS seek fail The pointer 
    {
    
        int u=Q.front();
        Q.pop();
        for(int i=0;i<26;++i)// Enumerate all child nodes 
        {
    
            if(AC[u].vis[i]!=0)// There is this child node 
            {
    
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];// Of the child nodes of the current node fail The node pointed to by the pointer is the current node fail The pointer points to the child node of the node .
           
                Q.push(AC[u].vis[i]);
            }
            else// This child node does not exist 
            AC[u].vis[i]=AC[AC[u].fail].vis[i];
            // This child node of the current node points to when 
            // Front node fail This child node of the pointer 
        }
    }
}
int AC_Query(string s)//AC Automata matching 
{
    
    int l=s.length();
    int now=0,ans=0;
    for(int i=0;i<l;++i)
    {
    
        now=AC[now].vis[s[i]-'a'];// Next level 
        for(int t=now;t&&AC[t].end!=-1;t=AC[t].fail)// Loop solution 
        {
    
            ans+=AC[t].end;
            AC[t].end=-1;
        }
    }
    return ans;
}
int main()
{
    
     int n;
     string s;
     cin>>n;
     for(int i=1;i<=n;++i)
     {
    
        cin>>s;
        add(s);
     }
     AC[0].fail=0;// There is no mismatch pointer in the root node 
     Get_fail();// Find the mismatch pointer 
     cin>>s;// Text string 
     cout<<AC_Query(s)<<endl;
     return 0;
}