小红的闭合标签

一种方法是去掉字符串两边的<> , 在输出的时候加上即可 代码：

void work()
{
    int n ; cin >> n ;
    string s ; cin >> s ; 
    s = s.substr(1 , n - 2);
    cout << "</" << s << ">" << endl ;  
}

小红的众数

要想让x成为众数，只需要让x的出现次数达到最大即可 代码：

void work()
{
    int n , x ; cin >> n >> x ;
    unordered_map<int , int>mp ; 
    int mx = 0 ; 
    for(int i = 1 ; i <= n ; i++)
    {
        int u ; cin >> u ; 
        mp[u]++ ;
        mx = max(mx , mp[u]) ;
    }
    if(mp[x] == mx)
    {
        cout << 0 << endl ; 
    }
    else
    {
        cout << mx - mp[x] << endl ; 
    }
}

小红的数字查找

由于l和r的数据范围已经超出暴力的范围，所以我们尝试取巧的方法，观察到如果想让x * y是一个完全平方数的话，y应该是一个k * n^2的形式，其中k是x中出现次数为奇数的质因数的个数，由此对l和r进行优化，查找有没有中间值即可。需要注意的是，这里我们尽量舍弃哈希表出现次数计数 代码：

void work()
{
    int x , l , r ; cin >> x >> l >> r ;
        int kj = 1 ; 
    for(int i = 2 ; i * i <= (x) ; i++)
    {
        int count = 0 ; 
        while(x % i == 0)
        {
            count++ ;
            x /= i ; 
        }
        if(count & 1)
        {
            kj *= i ;
        }
        if(x == 1)
        {
            break ; 
        }
    }
    if(x != 1)
    {
        kj *= x ; 
    }
    
    if(l <= kj && kj <= r)
    {
        cout << kj << endl ; 
        return ; 
    }
    int a1 = sqrt(l / kj) ; 
    int a2 = sqrt(r / kj) ; 
    if(a2 - a1 != 0)
    {
        cout << (a1 + 1) * (a1 + 1) * kj << endl ; 
        return ; 
    }
    cout << -1 << endl ; 
}

小红的异或分组

从大局着眼，如果三个区间的异或和相等，那么整个数组的异或值应该是S ^ S ^ S = S , 所以我们在读取数据的时候顺便计算出异或和是多少，这里分两种情况讨论

1、如果S == 0 ，那么我们应该寻找前缀为0的位置，最后利用组合数从中选取两个分段点即可

2、如果S != 0 ， 那么为了优化时间复杂度，我们考虑到前两个区间的异或前缀应该为0，而第一个区间的异或前缀为S ，所以我们统计异或前缀为S的数量，在遇到0的时候加上前面找到的即可 需要注意的是：前缀只能进行到n的前一位，因为题目要求每个区间内必须有数 代码：

void work()
{
    int n ; cin >> n ;
    vi a(n) ;
    int ans = 0 ; 
    for(int i = 0 ; i < n ; i++)
    {
        cin >> a[i] ;
        ans ^= a[i] ;
    }
    int res = 0 ; 
    if(ans != 0)
    {
        int count = 0 ; 
        int cur = 0 ;
        for(int i = 0 ; i < n - 1 ; i++)
        {
            cur ^= a[i] ;
            if(cur == ans)
            {
                count++ ;
            }
            else if(cur == 0)
            {
                res += count ; 
            }
        }
        cout << res << endl ; 
    }
    else
    {
        int count = 0 ; 
        int cur = 0 ; 
        for(int i = 0 ; i < n - 1 ; i++)
        {
            cur ^= a[i] ; 
            if(cur == 0)
            {
                count++ ;
            }
        }
        cout << count * (count - 1) / 2 << endl ; 
    }
}

小红的路径

首先我们来讨论一下不可能的情况，首先了解到如果我们想要走完所有的格子，我们必须走2*n - 1步，这必定是一个奇数，而后我们发现如果把整个矩阵看作一个棋盘的话，走奇数步（x + y）% 2的值是相反的，所以知道起点和终点的(x + y) % 2一定是不同的。

此外，我们注意一种特殊情况，也就是x1 == x2的情况，这种情况下如果x1不是1或者n，那我们是不可能构造出来的，通过第一种判断方法并不能排除他

下面开始构造

第一种情况：x1 == x2的时候，如果满足构造条件，只需要三段构造即可

第二种情况：为了减少计算量，我们可以把终点放在起点右边，打一个标记，最后反转字符串并转变方向就可以了。

我们进行三类构造，第一类是从起点到他的左边界，绕回来后到和起点x相同的位置，第二类是然后从起点到终点的部分进行蛇形构造，去到和终点x相同的位置，第三类是从终点到他的右边界，绕回来之后回到终点

至此路径构造完毕，根据情况判断是否反转即可 代码：

void work()
{
    int n, x1, y1, x2, y2;
    cin >> n >> y1 >> x1 >> y2 >> x2 ;
    if ((x1 + y1) % 2 == (x2 + y2) % 2)
    {
        cout << -1 << endl;
        return;
    }
    if (x1 == x2)
    {
        if (x1 != 1 && x1 != n)
        {
            cout << -1 << endl;
        }
        else
        {
            if (x1 == 1)
            {
                cout << string(n - 1 , 'R');
                if (y1 == 1)
                {
                    cout << "D";
                }
                else
                {
                    cout << "U";
                }
                cout << string(n - 1, 'L');
            }
            else
            {
                cout << string(n - 1, 'L');
                if (y1 == 1)
                {
                    cout << "D";
                }
                else
                {
                    cout << "U";
                }
                cout << string(n - 1, 'R');
            }
        }
    }
    else
    {
        bool sw = false ; 
        if(x1 > x2)
        {
            sw = true ; 
            swap(x1 , x2) ;
            swap(y1 , y2) ;
        }
        string ans ;
        if(x1 != 1)
        {
            ans += string(x1 - 1 , 'L') ;
            if (y1 == 1)
            {
                ans += "D";
            }
            else
            {
                ans += "U";
            }
            ans += string(x1 - 1 , 'R') ;
        }
        else
        {
            if (y1 == 1)
            {
                ans += "D";
            }
            else
            {
                ans += "U";
            }
        }
        ans += 'R' ;
        for(int i = 1 ; i < (x2 - x1) ; i++)
        {
            if(i & 1)
            {
                ans += (y1 == 1 ? 'U' : 'D') ;
            }
            else
            {
                ans += (y1 == 1 ? 'D' : 'U') ; 
            }
            ans += 'R' ;
        }
        
        
        if(x2 != n)
        {
            ans += string(n - x2 , 'R');
            ans += (y2 == 1 ? 'U' : 'D') ;
            ans += string(n - x2 , 'L') ;
        }
        else
        {
            ans += (y2 == 1 ? 'U' : 'D') ; 
        }
        
        if(sw)
        {
            reverse(all(ans)) ;
            for(int i = 0 ; i < ans.size() ; i++)
            {
                if(ans[i] == 'L')ans[i] = 'R' ;
                else if(ans[i] == 'R')ans[i] = 'L' ;
                else if(ans[i] == 'U')ans[i] = 'D' ;
                else ans[i] = 'U' ;
            }
        }
        cout << ans << endl ; 
    }
}