总体

这一次的训练赛整体上来说比起上一次的训练要好上很多，可能是因为上一周的训练让状态多少找回来一点，不过进步的空间还是很大。以此来记录每一次补题和进步。
题目集链接

题目B

题解链接
题目大意就是给定n个点，m条边，每条边的边权为w，是其连边两点的异或和，求出满足题意的图的最小点权和，如果不存在这样的图则输出-1。

在这道题目上我们根据题意建图，因为考虑到每一块连通区域，若合法，则只需对其中任意一点确定权值，则能确定连通块中每一点的权值，并且任选其中一个点为该连通块的基点，能确定该连通块内任何一点与基点的异或和。

因此，我们可以从1开始对所有未经过的点dfs，dfs过程中若某点已经被访问过且无法拥有唯一确定点权（这样就表明成环了），因此直接输出-1，且退出遍历，否则在dfs过程中建立以本次dfs基点为中心的菊花图。
边权为基点与目标点连边的异或和对每个建的新连通块，基点的每一位都可以枚举0和1两种情况，取更小的（dfs时我们假设基点是000…0，如果某一位上这个连通区域内1的个数大于0的个数，基点的这一位就放1，因为原先异或性质导致一条边的两个端点同一位肯定是同时变化的）。
统计当前连通区域点权和时，已经确定连通块基点点权为x，当前该点在基点为全0时取的是f[v]，考虑某一位，x现在仍是0，该点如果原先是0，现在也是0，该点如果原先是1，现在也是1；x现在如果是1，该点如果原先是0，现在应是1，该点如果原先是1，现在是0，所以累加答案$f[v]\oplus x$。

代码

#include <bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
#define pb push_back

using namespace std;
using ll = long long;

typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, m;
bool flag = true;
vector<PII> g[N];
vector<int> res[N];
int f[N];
bool st[N];

void dfs(int u, int lt)
{
    st[u] = true;

    for (auto pii : g[u])
    {
        int v = pii.fi, w = pii.se;
        if (st[v])
        {
            if (f[v] != (f[u] ^ w))
            {
                flag = false;
                return ;
            }
        }
        else
        {
            f[v] = (f[u] ^ w);
            res[lt].pb(v);
            dfs(v, lt);
        }
    }
}

ll add(int lt)
{
    int x = 0;
    for (int i = 0; i < 30; i ++ )
    {
        int cnt = 0;
        for (auto u : res[lt])
            if (f[u] >> i & 1)
                cnt ++ ;
        if (cnt > (int) res[lt].size() / 2)
            x += (1 << i);
    }

    ll ans = x;
    for (auto u : res[lt]) ans += x ^ f[u];
    return ans;
}

int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    for (int i = 0, u, v, w; i < m; i ++ )
    {
        scanf("%d%d%d",&u,&v,&w);
        g[u].pb({v, w}); g[v].pb({u, w});
    }
    ll ans = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (!st[i] && flag)
        {
            dfs(i, i);
            ans += add(i);
        }
    }
    if(flag)
        printf("%lld\n",ans);
    else
        printf("-1\n");
    return 0;
}

题目E

签到题，差不多就是一个找固定字串的问题，最后统计出数量然后输出即可。这里直接摆上队友的代码。

代码

#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=2e5+10;
int ans,P[maxn];
char A[maxn],B[maxn]= {"\0edgnb"};
//这里的A和B串以1开始存储
void Pre() {
    int j=0,m=strlen(B+1);
    P[1]=0;
    for(int i=1; i<m; i++) {
        while(j>0&&B[i+1]!=B[j+1])
            j=P[j];
        if(B[i+1]==B[j+1])
            j++;
        P[i+1]=j;
    }
}
int KMP() {
    int j=0,n=strlen(A+1),ans=0,m=strlen(B+1);
    for(int i=0; i<n; i++) {
        while(j>0&&A[i+1]!=B[j+1])
            j=P[j];
        if(A[i+1]==B[j+1])
            j++;
        if(j==m) {//匹配成功，记录数量并且清零
            ans++;
            j=0;
        }
    }
    return ans;
}
signed main() {
    scanf("%s",A+1);
    Pre();
    cout <<KMP();
    return 0;
}

题目F

这道题目的弯弯绕挺多的，主要还是在题意上的。题意大致就是，首先处理的对象是给定字符串的所有非空前缀，因为字符串由固定的二十种字符构成，因此相当于是有n个非空前缀。然后我们要找的就是当前字符在该前缀种出现的最后一个位置后面的字符数。找到这个数之后再让’a’加上这个数量后得到的字符来替代这个位置，把所有的位置处理完之后相当于得到了一个新的字符串。然后比较这所有得到的n个字符串，在里面找到字典序最大的那个然后输出。
基本的思路就是用两个辅助数组标记一下，其中一个标记该字符在字符串中最后出现的位置，另一个标记的是在当前字符出现的最后一个位置之后出现的字符的种类数。剩下的就是常规思路了。

代码

#include <bits/stdc++.h>
 
using namespace std;
int a[1005];
int marks[30];//标记位置
int marks2[30];//标记数量
string str;
int judge(int k,int n)
{
    if(k==-1)
        return 0;
    int biao[30]= {0};
    int num=0;
    for(int i=k+1; i<n; i++)
    {
        if(biao[str[i]-'a']==0)
        {
            biao[str[i]-'a']=1;
            num++;
        }
    }
    return num;
}
 
void solve()
{
    int n;
    scanf("%d",&n);
    cin>>str;
    int nn=1;
    string strr="_";
    for(int i=0; i<n; i++)
    {
        memset(marks,-1,sizeof(marks));
        memset(marks2,0,sizeof(marks2));
        for(int j=nn-1; j>=0; j--)
        {
            if(marks[str[j]-'a']==-1)
                marks[str[j]-'a']=j;
        }
        for(int j=0; j<=19; j++)
        {
            marks2[j]=judge(marks[j],nn);
        }
        string str2="";
        for(int j=0; j<=i; j++)
        {
            str2+=('a'+marks2[str[j]-'a']);
        }
        if(str2>strr)
            strr=str2;
        nn++;
    }
    cout<<strr<<endl;
}
 
 
int main()
{
    int t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}

题目J

这道题当时做的时候耗费了太长时间，其实完全不用的，这种题目只要是思路打开了最后就能够将答案得出来，之前我们想的是直接将所有的情况都搜一下，然后最后得出结果。但是直接这样搜的话最后的答案肯定会超时。但是后来发现其实有很多种情况之间其实是可以转换的，换句话来说他们之间是等价的，答案也是相同的，因此，我们只需要知道两个对应位置上的差值是多少就行了，然后将答案预处理到一个数组中去，最后更具不同的用例然后直接输出数组中的结果即可，大大降低了时间复杂度。

代码

#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e5+5;
vector<int> mm[N];
int dis[N];
bool flag[N];
void init(int n)
{
    int a[4]={0},b[4];
    int cnt = 0;
    int x = n;
    while(n)
    {
        a[cnt]=n%10;
        n/=10;
        cnt++;
    }
    int t = 0;
    for(int i = 1;i <= 4;i++)
    {
        for(int j = 0;j < 5-i;j++)
        {
            for(int k = 0;k < 4;k ++)
            {
                b[k]=a[k];
            }
            for(int k = j;k < j+i;k++)
            {
                b[k]=(a[k]+1)%10;
            }
            for(int tt = 3;tt >= 0;tt--)
            {
                t=t*10+b[tt];
            }
            mm[x].push_back(t);
            t = 0;
            for(int k = j;k < j+i;k++)
            {
                b[k]=(a[k]-1+10)%10;
            }
            for(int tt = 3;tt >= 0;tt--)
            {
                t=t*10+b[tt];
            }
            mm[x].push_back(t);
            t = 0;
        }
    }
}
void BFS()
{
    int d=1;
    queue<int> q;
    q.push(0);
    while(!q.empty())
    {
        int leng = q.size();
        while(leng--)
        {
            int t = q.front();
            q.pop();
            int n = mm[t].size();
            for(int i = 0;i < n;i++)
            {
                if(!flag[mm[t][i]])
                {
                    dis[mm[t][i]]=d;
                    q.push(mm[t][i]);
                    flag[mm[t][i]]=true;
                }
            }
        }
        d++;
    }
}
void solve()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a==b)
    {
        printf("0\n");
        return;
    }
    int aa[4]={},bb[4]={},cc[4];
    int cnt=0;
    while(a)
    {
        aa[cnt++]=a%10;
        a/=10;
    }
    cnt=0;
    while(b)
    {
        bb[cnt++]=b%10;
        b/=10;
    }
    for(int i = 0;i < 4;i++)
    {
        cc[i]=(bb[i]-aa[i]+10)%10;
    }
    int t = 0;
    for(int i = 3;i >=0;i--)
    {
        t=t*10+cc[i];
    }
    printf("%d\n",dis[t]);
}
 
int main()
{
//  freopen("in.txt","r",stdin);
//  int t = 1;
    int t;
    scanf("%d",&t);
    for(int i = 0;i<=9999;i++)
    {
        init(i);
    }
    BFS();
    while(t--)
    {
        solve();
    }
    return 0;
}

题目M

题目大意就是给你一个字符串，求这个字符串所有前缀字符串中最大字典序字符串。这道题写道这里思路还是很简单的，首先我们可以知道一个规律：对于一个字符串来说，其字典序最大的子串，其结尾一定是整个字符串的结尾，所以我们只需要找到前缀字符串最大字典序开头即可。这里就不再证明了，结论其实稍微想一下就能够想到。
但是我们需要知道的是，字符串最大长度为1e6，如果直接按照那种暴力的解法是一定会超时的。不过有了上面的结论，那我们就没必要把所有的情况都排除一遍，而是从前往后遍历，在遍历的过程中更新当前最大字典序的前缀。最后遍历完整个字符串的时候，答案也就出来了。
感想：说实话，在一开始看这道题的时候我感到了十分迷惑，总觉得情况很多，现在想来是没有将题目中所提取到的信息给整理起来，系统整理起来之后发现这道题其实思路是很简单的，还是要提高对一些信息的敏感度，和一些平常不经常用到的规律的积累。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int l[N];
char s[N];
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=1; i<=n;)
    {
        if(!l[i]) l[i]=i;
        int j=i,k=i+1;
        while(k<=n&&s[j]>=s[k])
        {
            if(!l[k]) l[k]=i;
            if(s[j]==s[k]) j++;
            else j=i;
            k++;
        }
        while(i<=j)
            i+=k-j;
    }
    for(int i=1; i<=n; i++)
        printf("%d %d\n",l[i],i);
    return 0;
}