Just... A violent simulation.

\(T1 \) learn to speak

Find the maximum word length of a word string, and replace the spaces with underscores.

Run violently, update the maximum value \ (ans \) and reset \ (cnt \) every time you sweep the underline. Note that the maximum value of the last word should also be updated after the cycle.

string s;
int ans,cnt;
int main(){
    freopen("word.in","r",stdin);
    freopen("word.out","w",stdout);
    cin>>s;
    for(int i=0;i<s.size();i++){
        if(s[i]=='_'){
            ans=max(ans,cnt);
            cnt=0;
        }
        else{
            cnt++;
        }
    }
    ans=max(ans,cnt);
    printf("%d\n",ans);
    return 0;
}

\(T2 \) worship the big man

Question meaning: \ (m \) query whether a string is in the given \ (n \) strings at a time.

The violent use of \ (map \) containers for maintenance is a weakened version of \ (csp-j\ 2021 \ T3 \).

map<string,bool> mp;
int n,m;
string s;
int main(){
    freopen("dalao.in","r",stdin);
    freopen("dalao.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        cin>>s;
        mp[s]=1;
    }
    m=read();
    for(int i=1;i<=m;i++){
        cin>>s;
        cin>>s;
        cin>>s;
        if(mp[s]){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }
    return 0;
}

\(T3 \) maze walking

A standard \ (bfs \), no brain search is OK.

For the portal, it can be found that the portal must be transmitted. Set a group of portal \ (d_1,d_2 \). It is not difficult to find that when there is an open space around \ (d_2 \), it can return to \ (d_1 \), so when marking, only mark the point entering the portal, not the point leaving the portal.

int n,m;
char mp[305][305];
bool vis[305][305];
struct gate{
    int x1,y1;
    int x2,y2;
    int cnt;
}gt[30];
struct node{
    int x,y,t;
    node(int x,int y,int t):x(x),y(y),t(t){}
};
int sx,sy,ex,ey;
queue<node> q;
int ans=0x3f3f3f3f;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
inline void bfs(){
    while(!q.empty()) q.pop();
    q.push(node(sx,sy,0));
    while(!q.empty()){
        node tmp=q.front();
        q.pop();
        int x=tmp.x,y=tmp.y,t=tmp.t;
        if(x==ex&&y==ey){
            ans=min(ans,t);
            continue;
        }
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&mp[xx][yy]!='#'){
                //printf("%d %d %d %d\n",x,y,xx,yy);
                vis[xx][yy]=1;
                if(mp[xx][yy]<='Z'&&mp[xx][yy]>='A'){
                    int ch=mp[xx][yy]-'A'+1;
                    if(gt[ch].x1==xx&&gt[ch].y1==yy){
                        q.push(node(gt[ch].x2,gt[ch].y2,t+1));
                    }
                    else{
                        q.push(node(gt[ch].x1,gt[ch].y1,t+1));
                    }
                }
                else{
                    q.push(node(xx,yy,t+1));
                }
            }
        }
    }
    if(ans==0x3f3f3f3f){
        printf("-1\n");
    }
    else{
        printf("%d\n",ans);
    }
    return;
}
int main(){
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=30;i++){
        gt[i].x1=gt[i].y1=gt[i].y1=gt[i].y2=gt[i].cnt=0;
    }
    for(int i=1;i<=n;i++){
        scanf("%s",mp[i]+1);
        for(int j=1;j<=m;j++){
            if(mp[i][j]<='Z'&&mp[i][j]>='A'){
                int ch=mp[i][j]-'A'+1;
                if(gt[ch].cnt==0){
                    gt[ch].x1=i,gt[ch].y1=j;
                    gt[ch].cnt++;
                }
                else{
                    gt[ch].x2=i,gt[ch].y2=j;
                    gt[ch].cnt++;
                }
            }
            else if(mp[i][j]=='@'){
                sx=i,sy=j;
            }
            else if(mp[i][j]=='='){
                ex=i,ey=j;
            }
        }
    }
    bfs();
    return 0;
}

Another idea during the game

Through vigorous simulation, it can be found that the cost of going to the portal from one point and remaining at the portal is \ (3 \), that is, entering the portal - leaving the other portal - entering the other portal. To sum up, both locations can be put in the queue and marked.

However, it is actually wrong, and we still need to judge whether the special judgment can be passed back.

\(T4 \) Duck Game

In fact, there is the shadow of dynamic programming, but the core algorithm is difference.

Consider a question first. Does the final consistent number of cards have an impact? Yes, but not completely, because if we take the initial number of cards in any stack as the benchmark, the number of schemes will not change, because the relative increase and decrease can be offset. For example, the group of \ ({1,2,1,2,1,2} \) based on \ (1 \) and \ (2 \) are equivalent.

What about taking \ (3 \) as the benchmark? It is not difficult to find that \ (1 \) or \ (2 \) needs to be added to the whole. Therefore, the first conclusion of this question is that the final number of cards must be any one of the initial number. Let them all be \ (a_1 \).

Next, we consider the difference array \ (B \), so that \ (b_i = a_i-a {I-1} \), especially \ (b_1=0 \), and then we make all \ (a_i \) equal to the difference between the original number and \ (a_1 \).

It is not difficult to find that if there is a monotone Non rising sequence \ ([i,j] \) with more cards than the benchmark, the operands required are \ (a_i \) at the time of the largest stack. Similarly, if there is a monotone non falling sequence \ ([i,j] \) with less than the benchmark, the operands required are \ (a_i \) at the time of the smallest stack.

In this case, the answer can be updated within the complexity of \ (O(n) \). The scheme is as follows:

• If \ (a_i \) is different from \ (a_{i-1} \), add \ (|a_i124\) to the direct answer
• If \ (a_i \) and \ (a_{i-1} \) have the same number, and \ (| a_{i-1} > = | a_i124\), it indicates that the operation of the previous stack is enough to cover the current stack without changing the answer.
• If \ (a_i \) and \ (a_{i-1} \) have the same number, and \ (| a_{i-1}) < | a_i124\), it indicates that the operation of the previous stack is not enough to cover the current stack, and the answer is added with the differential array \ (b_i \)

You can find that every time we update to \ (a_i \), we guarantee that the first \ (I \) schemes are the benchmark.

int n;
int a[maxn],b[maxn];
int ans;
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    b[1]=0;
    for(int i=2;i<=n;i++){
        b[i]=a[i]-a[i-1];
    }
    for(int i=2;i<=n;i++){
        a[i]-=a[1];
    }
    a[1]=0;
    for(int i=2;i<=n;i++){
        if(a[i]>0){
            if(a[i-1]>=0){
                if(b[i]>=0){
                    ans+=b[i];
                }
            }
            else{
                ans+=a[i];
            } 
        }
        else if(a[i]<0){
            if(a[i-1]<=0){
                if(b[i]<=0){
                    ans+=abs(b[i]);
                }
            }
            else{
                ans+=abs(a[i]);
            }
        }
    }
    printf("%d\n",ans);
    return 0;   
}

However, there is a better solution.

Consider the following array \ (A=\{2,3,3,1,5 \} \), and there is \ (B=\{0,1,0,-2,4 \} \) after the difference. We can find that if you modify an interval \ ([l,r] \), the value of the difference array will change between \ (L \) and \ (r+1 \). For example, in the \ ([2,3] \) position \ (- 1 \), we get the array \ (A'=\{2,2,2,1,5 \} \) and the differential array \ (B'=\{0,0,0,-1,4 \} \). If you change \ (4 \) single point \ (+ 1 \), similarly, the difference array becomes \ (B''=\{0,0,0,0,3 \} \).

To sum up the above operations, we can draw a conclusion that any positive and negative difference value can be \ (- 1 \) and \ (+ 1 \) respectively in one modification. In other words, in fact, the number of modifications is actually the absolute value of the sum of positive numbers and negative numbers. Let's set \ (cnt1 = \ sum {I = 1} ^ n [b _i > 0], CNT2 = \ sum {I = 1} ^ n [b _i < 0] \). In this way, the number of operations \ (ans1 \) should be:

int n;
int a[maxn],b[maxn];
int cnt1,cnt2;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=2;i<=n;i++){
        b[i]=a[i]-a[i-1];
        if(b[i]>0){
            cnt1+=b[i];
        }
        else{
            cnt2-=b[i];
        }
    }
    printf("%d %d\n",max(cnt1,cnt2),abs(cnt1-cnt2)+1);
    return 0;
}