第四题 传纸条

去一趟 回来一趟 可以看成是从起点走到终点两趟
两次不能走相同的格子

#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m;
int g[N][N];
int f[N * 2][N][N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }

    for (int k = 2; k <= n + m; k++) {
        for (int i = max(1, k - m); i <= n && i < k; i++) {
            for (int j = max(1, k - m); j <= n && j < k; j++) {
                for (int a = 0; a <= 1; a++) {
                    for (int b = 0; b <= 1; b++) {
                        int t = g[i][k - i];
                        if (i != j || k == 2 || k == n + m) {
                            t += g[j][k - j];
                            f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
                        }
                    }
                }
            }
        }
    }
    cout << f[n + m][n][n] << endl;

    return 0;
}

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
int main(void)
{
    scanf("%d",&n); 
    int a1,a2,a3;
    a1=n/3600; a2=(n%3600)/60;a3=n%60;
    printf("%d:%d:%d\n",a1,a2,a3);

    return 0;
}

题目描述

给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。

请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

算法：深度优先搜索

时间复杂度：O(N)

需要注意

(1)本题的树存储的是双向边，因此需要布尔数组防止出现循环调用。
(2)由子节点信息更新父节点信息，先更新子节点信息。
(3)树定义是当且仅当任何两个点之间仅有一条路径的图,N个点共有N-1个边

C++代码

#include<iostream>
#include<cstring>

using namespace std;
const int N=100010,M=N*2;
int h[N],e[M],ne[M],idx;
bool st[N];
int n;
int res=N;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int dfs(int u)
{
    int s=0;
    int sum=0;
    st[u]=true;

    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(st[j])continue;
        int cnt=dfs(j);
        s=max(s,cnt);
        sum+=cnt;
    }
    s=max(s,n-sum-1);
    res=min(res,s);
    return sum+1;
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);

    for(int i=0;i<n-1;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1);
    cout<<res<<endl;
    return 0;
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
int main(void)
{
    scanf("%d",&n); 
    printf("%d\n",n);
    int a1,a2,a3,a4,a5,a6,a7;
    a1=n/100; a2=(n%100)/50;a3=(n-a1*100-a2*50)/20;
    a4=(n-a1*100-a2*50-a3*20)/10;
    a5=n%10/5; a6=(n%10-a5*5)/2;a7=n%10-a5*5-a6*2;
    printf("%d nota(s) de R$ 100,00\n",a1);
    printf("%d nota(s) de R$ 50,00\n",a2);
    printf("%d nota(s) de R$ 20,00\n",a3);
    printf("%d nota(s) de R$ 10,00\n",a4);
    printf("%d nota(s) de R$ 5,00\n",a5);
    printf("%d nota(s) de R$ 2,00\n",a6);
    printf("%d nota(s) de R$ 1,00\n",a7);

    return 0;
}

y总讲的是手写队列，我的是STL队列实现，供大家参考

#include<bits/stdc++.h>
using namespace std;
typedef pair<int ,int > PII;
const int N=105;
int n,m;
int g[N][N];
int ans[N][N];
int bfs()
{
    queue<PII> q;

    q.push({0,0});
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};

    ans[0][0]=0;
    while(!q.empty())
    {
        PII x;
        x.first=q.front().first;
        x.second=q.front().second;
        q.pop();

        for(int i=0;i<4;i++)
        {
            int nx=x.first+dx[i];
            int ny=x.second+dy[i];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&g[nx][ny]==0)
            {
                g[nx][ny]=1;
                q.push({nx,ny});
                ans[nx][ny]=ans[x.first][x.second]+1;
            }
        }
    }
    return ans[n-1][m-1];
}
int  main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%d",&g[i][j]);
        }
    }
    cout<<bfs();
}

更好的阅读体验

Statement

给定一棵以 $1$ 为根的括号树，每个点恰有一个 ( 或 ) ，定义 $s(i)$ 为将根节点到 $i$ 号点的简单路径按经过顺序排列形成的字符串。

设 $k(i)$ 表示 $s(i)$ 中互不相同的子串是合法括号串的个数。求 $\forall1\leq i\leq n,\sum i\times k(i)$ ，这里的求和表示异或和。

Thoughts & Solution

终于补完模拟赛来继续写题了

题外话：今天模拟赛也有一道括号匹配题，但是是奇妙的贪心，要写两个栈+一个双端队列（

STL永远的神！

显然如果对这棵树进行 DFS ，那么根到 $i$ 的路径上的点可以用栈得到。

那么一遍 DFS 就可以处理出根到 $i$ 的路径上 互不相同的子串是合法括号串 的个数。

设 $endpos[i]$ 为以节点 $i$ 结尾的，根到 $i$ 中互不相同的合法括号子串的个数。类似括号匹配的思路，如果当前为左括号那么直接进栈；如果是右括号且栈不为空，那么栈顶就能和当前点配对，这样就形成了一个新的合法子串 sta.top(),i ，那么当前节点的 $endpos$ 就可以由这一对括号之前的东西推知。

令 $fa[i]$ 表示括号树上点 $i$ 的父亲节点，那么 $endpos[i]=endpos[fa[sta.top()]]+1$ （因为 $endpos[fa[sta.top()]]$ 这些串都能和当前这一对括号接起来，成为一个新的合法子串；或者当前这个单独成串）

最后 $k(i)$ 就是根到 $i$ 的路径上所有的 $endpos$ 之和，这个也可以在 DFS 的时候顺带求出来。

注意递归完之后要记得还原，pop 掉的左括号搞回去，push 的左括号拿出来。

//Author: RingweEH
const int N=5e5+10;
int n,fa[N],endpos[N];
ll f[N];
stack<int> sta;
vector<int> son[N];
char s[N];

void dfs( int u )
{
    bool pu=0; int las=0;
    if ( s[u]=='(' ) sta.push( u ),pu=1;
    else if ( !sta.empty() ) { endpos[u]=endpos[fa[sta.top()]]+1; las=sta.top(); sta.pop(); }
    f[u]=f[fa[u]]+endpos[u];
    for ( int i=0; i<son[u].size(); i++ )
        dfs( son[u][i] );
    if ( pu && sta.top()==u ) sta.pop();
    if ( las ) sta.push( las );
}

int main()
{
    n=read(); scanf( "%s",s+1 );
    for ( int i=2; i<=n; i++ )
        fa[i]=read(),son[fa[i]].push_back(i);

    endpos[1]=0; f[1]=0; dfs( 1 );

    ll ans=0;
    for ( int i=1; i<=n; i++ )
        ans^=(i*f[i]);

    printf( "%lld\n",ans );

    return 0;
}

题目描述

在一个3×3的网格中，1~8这8个数字和一个“x”恰好不重不漏地分布在这3×3的网格中。

例如：

1 2 3
x 4 6
7 5 8

在游戏过程中，可以把“x”与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x

例如，示例中图形就可以通过让“x”先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

算法：宽度优先搜索

时间复杂度：指数

C++代码

#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<iostream>

using namespace std;
string ter="12345678x";
string str;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int bfs(string s)
{
    unordered_map<string,int>d;
    d[s]=0;
    queue<string>q;
    q.push(s);

    while(q.size()){
        auto t=q.front();
        q.pop();
        if(t==ter)return d[t];
        int k=t.find('x');
        int x=k/3,y=k%3;
        int distance=d[t];
        for(int i=0;i<4;i++){
            int a=x+dx[i],b=y+dy[i];
            if(a<0 || a>=3 || b<0 || b>=3)continue;
            swap(t[k],t[a*3+b]);
            if(!d.count(t)){
                d[t]=distance+1;
                q.push(t);
            }
            swap(t[k],t[a*3+b]);
        }
    }
    return -1;
}

int main()
{
    char s[2];
    while(scanf("%s",s)!=-1)str+=*s;
    cout<<bfs(str)<<endl;
    return 0;
}

import java.util.*;
import java.io.*;

class Main {
    static int N = 1010;
    static int[] heap = new int[N];
    static int size = 1;
    public static void main (String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(reader.readLine());
        String[] s = reader.readLine().split(" ");
        for (int j = 1; j <= n; j++) heap[j] = Integer.parseInt(s[j - 1]);
        size = n;

        getLog(writer);

        // 判断是否为大根堆
        boolean isMax = true;
        for (int k = 1; k <= n; k++) {
            int root = heap[k];
            int left = k * 2 <= size ? heap[k * 2] : Integer.MIN_VALUE;
            int right = k * 2 + 1 <= size ? heap[k * 2 + 1] : Integer.MIN_VALUE;
            if (root < left || root < right) {
                isMax = false;
                break;
            }
        }
        if (isMax) {
            writer.write("Max Heap");
        }

        // 判断是否为小根堆
        boolean isMin = true;
        for (int k = 1; k <= n; k++) {
            int root = heap[k];
            int left = k * 2 <= size ? heap[k * 2] : Integer.MAX_VALUE;
            int right = k * 2 + 1 <= size ? heap[k * 2 + 1] : Integer.MAX_VALUE;
            if (root > left || root > right) {
                isMin = false;
                break;
            }
        }
        if (isMin) {
            writer.write("Min Heap");
        }

        // 都不是
        if (!isMax && !isMin) {
            writer.write("Not Heap");  
        } 

        reader.close();
        writer.flush();
        writer.close();
    }

    private static void getLog(BufferedWriter writer) throws IOException {
        ArrayList<Integer> list = new ArrayList<>();
        dfs(1, size, list, writer);
    }

    private static void dfs(int i, int n, ArrayList<Integer> list, BufferedWriter writer) throws IOException {
        if (i * 2 > n) {
            if (i <= n) list.add(heap[i]);
            for (int item : list) {
                writer.write(item + " ");
            }
            writer.write("\n");
            return;
        }

        list.add(heap[i]);

        if (i * 2 + 1 <= n) {
            ArrayList<Integer> copy2 = new ArrayList<>(list);
            dfs(i * 2 + 1, n, copy2, writer);   
        }

        if (i * 2 <= n) {
            ArrayList<Integer> copy1 = new ArrayList<>(list);
            dfs(i * 2, n, copy1, writer);   
        }
    }
}