牛客练习赛88 A~D 题解

A.活着的证据

算法

(贪心)

分析：

在数位没有达到最大上限的情况下，如果手中还有字符就优先扩展数位
在扩展数位的时候优先使用"V","V"不足了再使用"I"
数位达到上限后再从高位开始增加每一位的数值
由于第一次扩展数位的时候优先使用'V'，此时要么手中已经没有"V"了，要么手中还有"V"但是每一位都被填上了"V"

所以此时只能使用"I"。
如果扩展数位时当前位填的"V"那么这一位上限就是8，否则是3
当手中的"I"都用完或者每一位都达到上限数值了就结束，输出答案
用两次for循环就能解决

时间复杂度

$O(n)$

参考文献

C++ 代码

// Problem: 活着的证据
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11178/A
// Memory Limit: 1048576 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

// #define x first
// #define y second

#define P1 13331
#define P2 233

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const int N = 5e6 + 10;
char ans[N];
int cnt;
int s1,s2,n;

inline void solve()
{
    scanf("%d%d%d",&s1,&s2,&n);
    cnt = 0;
    for(int i = 0;i < n && (s1 != 0 || s2 != 0);i ++)
    {
        if(s1 != 0)
        {
            ans[cnt ++] = '5';
            s1 --;
        }
        else 
        {
            ans[cnt ++] = '1';
            s2 --;
        }
    }
    ans[cnt] = '\0';
    if(s2 != 0)
    {
        for(int i = 0;i < cnt && s2 != 0;i ++)
        {
            while(s2 !=0 && ans[i] >= '5' && ans[i] < '8') ans[i] ++,s2 --;
            while(s2 !=0 && ans[i] >= '1' && ans[i] < '3') ans[i] ++,s2 --;
        }    
    }
    printf("%s\n",ans);
}

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(N - 1); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    // cin >> _;
    scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

B.寻寻觅觅寻不到

算法

(字符串哈希)

分析：

已知被截取的字串的长度为k，且放在了最末尾的位置
所以新字符串的长度为k的后缀就是被截取的字符串
我们可以在原字符串中枚举被截取字串的起始位置，然后比较截取后各部分是否对应相同
比较可以使用字符串哈希

图片说明

时间复杂度

$O(n)$

参考文献

C++ 代码

// Problem: 寻寻觅觅寻不到
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11178/B
// Memory Limit: 1048576 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

// #define x first
// #define y second

#define P1 13331
#define P2 233

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 300010;
ULL p[N];
ULL h1[N],h2[N];
char str1[N],str2[N];
int n,k;

void init(int n)
{
    p[0] = 1;
    for(int i = 1;i <= n;i ++) p[i] = p[i - 1] * P1;
}

ULL get(ULL h[],int l,int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

bool check(int x1,int y1,int x2,int y2)
{
    return get(h1,x1,y1) == get(h2,x2,y2);
}

inline void solve()
{
    scanf("%s%s%d",str1 + 1,str2 + 1,&k);
    int n = strlen(str1 + 1),m = strlen(str2 + 1);
    if(n != m)
    {
        puts("NO");
        return;
    }
    for(int i = 1;i <= n;i ++)
    {
        h1[i] = h1[i - 1] * P1 + str1[i];
        h2[i] = h2[i - 1] * P1 + str2[i];
    }
    if(check(1,k,n - k + 1,n) && check(k + 1,n,1,n - k))
    {
        puts("YES");
        return;
    }
    if(check(1,n,1,n))
    {
        puts("YES");
        return;
    }
    for(int i = k + 1;i <= n - 1;i ++)
    {
        if(check(1,i - k,1,i - k) && check(i - k + 1,i,n - k + 1,n) && check(i + 1,n,i - k + 1,n - k))
        {
            puts("YES");
            return;
        }
    }
    puts("NO");
}

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    init(N - 1); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    // cin >> _;
    scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

C.踩不出足迹

算法

(位运算)

分析：

将异或运算和同或运算放在一起

a b a $\bigotimes$ b a $\bigoplus$ b

0 0 0 1

0 1 1 0

1 0 1 0

1 1 0 1

我们发现同或运算相当于异或运算后再进行取反操作
二进制位的取反操作等价于 $\bigotimes1$ ，当前位异或上1
所以如果对一个k位的二进制取反，等价于 $\bigotimes(\underbrace{111....1}_{k})_2$ ，异或上k位二进制表示下的最大值
根据异或运算的交换律和结合律我们可以将所有 $\bigotimes(\underbrace{111....1}_{k})_2$ 操作移动到最后
原式就变成了 $A1\bigotimes A2 \bigotimes ... \bigotimes An \bigotimes(\underbrace{111....1}_{k})_2 \bigotimes(\underbrace{111....1}_{k})_2 ...$
根据异或运算的自反性同一个数如果异或偶数次等于0，异或奇数次等于他本身
所以最终可能的结果只有两种 $A1\bigotimes A2 \bigotimes ... \bigotimes An$ 和 $A1\bigotimes A2 \bigotimes ... \bigotimes An \bigotimes(\underbrace{111....1}_{k})_2$
答案两者取最大值即可

a	b	a $\bigotimes$ b	a $\bigoplus$ b
0	0	0	1
0	1	1	0
1	0	1	0
1	1	0	1

细节：

输出 $2^{64} - 1$ 我用到了__int128,实际上输出long long 类型下的-1即可

时间复杂度

$O(n)$

参考文献：

发现和某位大佬的想法重了https://blog.nowcoder.net/n/4362d484984745e686dd743200bcc3fb

C++ 代码

// Problem: 踩不出足迹
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11178/C
// Memory Limit: 1048576 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

// #define x first
// #define y second

#define P1 13331
#define P2 233

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
__int128  bi[100];
int n,k;


inline __int128 read()
{
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void print(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
}

void init(int n)
{
    bi[0] = 1;
    for(int i = 1;i <= n;i ++) bi[i] = bi[i - 1] * 2;
}

__int128  inv(__int128 x,int k)
{    
    __int128 res = bi[k] - 1;
    return x ^ res;
}

inline void solve()
{
    scanf("%d%d",&n,&k);
    __int128  res = 0;
    for(int i = 1;i <= n;i ++)
    {
        __int128  x;
        x = read();
        res ^= x;
    }
    __int128  ans = max(res,inv(res,k));
    print(ans);
    puts("");
}

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    init(64); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    // cin >> _;
    // scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}

D.都市的柏油路太硬

算法

(最小瓶颈路 + kruskal重构数 + st表求lca + 欧拉序)

分析：

最小瓶颈路：

图中两点 $(u,v)$ 之间的所有路径中，最大边最小的路径，就是最小瓶颈路

分析：

根据题意我们将， $(u,v)$ 的最小瓶颈路中的最大边定义为 $<u,v>$ 的权值得到一个由原图点集构成的完全图
这个完全图的最小生成树，也一定是原图的最小生成树

kruskal重构树

在一棵树上求两点间路径中的最长边我们可以用倍增的方法，但时间复杂度是 $O(logn)$
kruskal重构树的一个性质：原树上任意两个点路径上边权的最大值为kruskal重构树中这两点的LCA的点权
树的构建:
- 再kruskal算法运行过程中，如果边<a,b>连接的两点a,b不在同一个连通块中
- 我们就将这条边断开，建立一个新点T，然后将a和b连向分别T，将T的点权定义为边<a,b>的权值
- kruskal算法算法结束后我们就得到一个大小为2 * n - 1的树了
- 由于加入的边权是从小到大递增的，所以新建的点的点权也是递增的，我们将最后一个新建的点作为这棵树的根节点，树的构建就完成了
将树建好后，离线处理每个询问的lca 或者用st表+欧拉序的方式预处理再 $O(1)$ 查询两点间lca即可

以下是用st表+欧拉序的方式预处理再 $O(1)$ 查询两点间lca的时间复杂度

时间复杂度

$O(mlogm + nlogn + q)$

参考文献：

kruskal重构树的构建：https://www.cnblogs.com/zwfymqz/p/9683523.html

C++ 代码

// Problem: 都市的柏油路太硬
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11178/D
// Memory Limit: 1048576 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

// #define x first
// #define y second

#define P1 13331
#define P2 233

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int N = 100010,M = 500010,mod = 1e9 + 7;
int lg2[N * 4];
int h[N * 2],ne[N * 4],e[N * 4],idx;
struct edge
{
    int a,b,w;
    bool operator < (const edge &A) const 
    {
        return w < A.w;
    }
}edges[M];
int p[N * 2];
int f[N * 4][22];
int dep[N * 2],seq[N * 4],tot;
int pos[N * 2];
int val[N * 2];
int n,m;

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

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

void kruskal()
{
    for(int i = 1;i <= n * 2;i ++) p[i] = i;
    sort(edges + 1,edges + 1 + m);
    int res = 0,cnt = n;
    for(int i = 1;i <= m;i ++)
    {
        int a = edges[i].a,b = edges[i].b,w = edges[i].w;
        a = find(a),b = find(b);
        if(a != b)
        {
            cnt ++;
            p[a] = p[b] = cnt;
            add(cnt,a);
            add(a,cnt);
            add(cnt,b);
            add(b,cnt);
            val[cnt] = w;
            res ++;
        }
        if(res == n - 1)
        {
            return;
        }
    }
}

void dfs(int u,int father)
{
    dep[u] = dep[father] + 1;
    seq[++ tot] = u;
    pos[u] = tot;
    for(int i = h[u];~i;i = ne[i])
    {
        int j = e[i];
        if(j == father) continue;
        dfs(j,u);
        seq[++ tot] = u;
    }
}

void init()
{
    for(int i = 2;i <= n * 4;i ++) lg2[i] = lg2[i >> 1] + 1;
    for(int j = 0;j <= 21;j ++)
        for(int i = 1;i + (1 << j) - 1 <= 4 * n;i ++)
            if(j == 0) f[i][0] = seq[i];
            else
            {
                f[i][j] = dep[f[i][j - 1]] < dep[f[i + (1 << (j - 1))][j - 1]]
                ? f[i][j - 1]
                : f[i + (1 << (j - 1))][j - 1];
            }
}

int lca(int x,int y)
{
    int l = pos[x],r = pos[y];
    if(l > r) swap(l,r);
    int k = lg2[r - l + 1];
    return dep[f[l][k]] < dep[f[r - (1 << k) + 1][k]]
            ? f[l][k]
            : f[r - (1 << k) + 1][k];
}

ull myRand(ull &k1, ull &k2){
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 <<23);
    k2 = k3 ^ k4 ^ (k3 >>17) ^ (k4 >>26);
    return k2 + k4;
}
pair<int,int>myRanq(ull&k1,ull&k2,int MAXN){
    int x=myRand(k1,k2)%MAXN+1,y=myRand(k1,k2)%MAXN+1;
    if(x>y)return make_pair(y,x);
    else return make_pair(x,y);
}

inline void solve()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d%d%d",&edges[i].a,&edges[i].b,&edges[i].w);
    }
    sort(edges + 1,edges + 1 + m);
    for(int i = 1;i <= n * 2;i ++) p[i] = i;
    kruskal();
    dfs(2 * n - 1,0);
    init();
    int q;
    ull a,b;
    scanf("%d",&q);
    scanf("%llu%llu",&a,&b);
    LL res = 0;
    while(q -- )
    {
        pair<int,int> t = myRanq(a,b,n);
        res ^= val[lca(t.first,t.second)];
    }
    printf("%lld\n",res);
}

int main()
{
    int _ = 1;

    // freopen("network.in","r",stdin);
    // freopen("network.out","w",stdout);
    // init(N - 1); 

    // std::ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
    // cin >> _;
    // scanf("%d",&_);
    while(_ --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}