写日报真的是很好的督促学习的方式

暑假以来比较浪，从今天开始改变自己

周一

Concatenation（字符串比较）

暴力排序竟然可以过……

显然难点在于前缀相同的情况，这个时候比较ab和ba即可

#include<bits/stdc++.h>
#define _for(i, a, b) for(int i = a; i <= b; i++)
#define rep(i, a, b) for(int i = a; i < b; i++)
using namespace std;

const int N = 2e6 + 10;
string a[N];

bool cmp(string x, string y)
{
    int len = min(x.size(), y.size());
    rep(i, 0, len)
        if(x[i] != y[i])
            return x[i] < y[i];
    return x + y < y + x;
}

int main()
{
    int n; scanf("%d", &n);
    _for(i, 1, n) cin >> a[i];

    sort(a + 1, a + n + 1, cmp);
    _for(i, 1, n) cout << a[i]; 
    puts("");

    return 0;
}

Ancestor（前缀后缀+代码技巧）

比赛时分类讨论去了，其实是弄复杂了

一个区间去掉一个点，就剩下前缀和后缀了，于是我们可以预处理出前缀lca和后缀lca

因为同样的代码要写两份，所以写个结构体可以大大简化代码

#include<bits/stdc++.h>
#define _for(i, a, b) for(int i = a; i <= b; i++)
#define rep(i, a, b) for(int i = a; i < b; i++)
using namespace std;

const int N = 1e5 + 10;
int k[N], n, m;

struct Tree
{
    int d[N], up[N][20], q[N], h[N], val[N];
    vector<int> g[N];

    void read()
    {
        _for(i, 1, n) scanf("%d", &val[i]);
        _for(i, 2, n)
        {
            int x; scanf("%d", &x);
            g[x].push_back(i);
        }
    }

    void dfs(int u, int fa)
    {
        d[u] = d[fa] + 1;
        up[u][0] = fa;
        _for(j, 1, 19) up[u][j] = up[up[u][j - 1]][j - 1];

        for(int v: g[u])
        {
            if(v == fa) continue;
            dfs(v, u);
        }
    }

    int lca(int u, int v)
    {
        if(!u || !v) return u + v;
        if(d[u] < d[v]) swap(u, v);
        for(int j = 19; j >= 0; j--)
            if(d[up[u][j]] >= d[v])
                u = up[u][j];
        if(u == v) return u;
        for(int j = 19; j >= 0; j--)
            if(up[u][j] != up[v][j])
                u = up[u][j], v = up[v][j];
        return up[u][0];
    }

    void init()
    {
        dfs(1, 0);
        q[1] = k[1];
        _for(i, 2, m) q[i] = lca(q[i - 1], k[i]);
        h[m] = k[m];
        for(int i = m - 1; i >= 1; i--) h[i] = lca(h[i + 1], k[i]);
    }

    int cal(int x)
    {
        return val[lca(q[x - 1], h[x + 1])];
    }

}A, B;

int main()
{
    scanf("%d%d", &n, &m);
    _for(i, 1, m) scanf("%d", &k[i]);
    A.read(); A.init();
    B.read(); B.init();

    int ans = 0;
    _for(i, 1, m)
        if(A.cal(i) > B.cal(i))
            ans++;
    printf("%d\n", ans);
    
    return 0;
}

Journey（0/1bfs）

边看作点，路口看作边建图，边的权值只有0和1，这时用0/1bfs即可，和bfs复杂度一样

注意一些细节，建图配id的时候，注意用unordered_map

0/1bfs和bfs的区别在于用双端队列，边权为0的点放前面，否则放后面

用松弛操作来更新，这样一个点最多入队两次。然后不需要vis数组

此外，第一次找到的点不一定是最优的，但第一次出队的点一定是最优的

其实0/1bfs就是一个特殊的dijsktra，只是说优先队列变成了双端队列，通过入队方式来保证单调性。

#include<bits/stdc++.h>
#define _for(i, a, b) for(int i = a; i <= b; i++)
#define rep(i, a, b) for(int i = a; i < b; i++)
using namespace std;

typedef long long ll;
const int N = 5e5 * 8 + 10;
unordered_map<ll, int> mp;
vector<pair<int, int>> g[N];
int d[N], vis[N], n, cnt;

int id(int x, int y)
{
    ll t = 1LL * x * 1e6 + y;
    if(!mp[t]) mp[t] = ++cnt;
    return mp[t];
}

int solve(int st, int dest)
{
    _for(i, 1, cnt) d[i] = 1e9;
    d[st] = 0;
    deque<int> q;                 //0/1bfs用双端队列
    q.push_back(st);

    while(!q.empty())
    {
        int u = q.front(); q.pop_front();
        if(u == dest) return d[u];            //0/1bfs中，出队的时候是最小值，第一次遇到不一定是最小值
        for(auto x: g[u])
        {
            int v = x.first, w = x.second;
            if(d[v] > d[u] + w)               //松弛操作
            {
                d[v] = d[u] + w;
                if(!w) q.push_front(v);       //0放队首 1放队尾
                else q.push_back(v);
            }
        }
    }
    return -1;
}

int main()
{
    scanf("%d", &n);
    _for(i, 1, n)
    {
        int c[5];
        _for(j, 1, 4) scanf("%d", &c[j]);
        _for(j, 1, 4)
        {
            if(!c[j]) continue;
            g[id(c[j], i)].push_back({id(i, c[j]), 1});
            int ii = j % 4 + 1;
            if(c[ii]) g[id(c[j], i)].push_back({id(i, c[ii]), 0});
            ii = (j + 1) % 4 + 1;
            if(c[ii]) g[id(c[j], i)].push_back({id(i, c[ii]), 1});
            ii = (j + 2) % 4 + 1;
            if(c[ii]) g[id(c[j], i)].push_back({id(i, c[ii]), 1});
        }
    }

    int s1, s2, t1, t2;
    scanf("%d%d%d%d", &s1, &s2, &t1, &t2);
    int st = id(s1, s2), dest = id(t1, t2);
    printf("%d\n", solve(st, dest));

    return 0;
}

这题直接dijsktra也可以过

当然要注意，第一次入队不一定是最优的，第一次出队才是最优的。或者干脆算法跑完后再输出。

#include<bits/stdc++.h>
#define _for(i, a, b) for(int i = a; i <= b; i++)
#define rep(i, a, b) for(int i = a; i < b; i++)
using namespace std;

typedef long long ll;
const int N = 5e5 * 8 + 10;
unordered_map<ll, int> mp;
int d[N], vis[N], n, cnt;
struct node
{
    int v, w;
    bool operator < (const node& rhs) const
    {
        return w > rhs.w;
    }
};
vector<node> g[N];

int id(int x, int y)
{
    ll t = 1LL * x * 1e6 + y;
    if(!mp[t]) mp[t] = ++cnt;
    return mp[t];
}

int solve(int st, int dest)
{
    _for(i, 1, cnt) d[i] = 1e9;
    d[st] = 0;
    priority_queue<node> q;
    q.push({st, d[st]});

    while(!q.empty())
    {
        node x = q.top(); q.pop();
        int u = x.v;
        if(u == dest) return d[u];
        if(d[u] != x.w) continue;

        for(auto x: g[u])
        {
            int v = x.v, w = x.w;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                q.push({v, d[v]});
            }
        }
    }
    return -1;

}

int main()
{
    scanf("%d", &n);
    _for(i, 1, n)
    {
        int c[5];
        _for(j, 1, 4) scanf("%d", &c[j]);
        _for(j, 1, 4)
        {
            if(!c[j]) continue;
            g[id(c[j], i)].push_back({id(i, c[j]), 1});
            int ii = j % 4 + 1;
            if(c[ii]) g[id(c[j], i)].push_back({id(i, c[ii]), 0});
            ii = (j + 1) % 4 + 1;
            if(c[ii]) g[id(c[j], i)].push_back({id(i, c[ii]), 1});
            ii = (j + 2) % 4 + 1;
            if(c[ii]) g[id(c[j], i)].push_back({id(i, c[ii]), 1});
        }
    }

    int s1, s2, t1, t2;
    scanf("%d%d%d%d", &s1, &s2, &t1, &t2);
    int st = id(s1, s2), dest = id(t1, t2);
    printf("%d\n", solve(st, dest));

    return 0;
}