# 小红的闭合标签
一种方法是去掉字符串两边的 <> , 在输出的时候加上即可
代码：
1
2
3
4
5
6
7void work()
{
int n ; cin >> n ;
string s ; cin >> s ;
s = s.substr(1 , n - 2);
cout << "</" << s << ">" << endl ;
}
# 小红的众数
要想让 x 成为众数，只需要让 x 的出现次数达到最大即可
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20void 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 进行优化，查找有没有中间值即可。需要注意的是，这里我们尽量舍弃哈希表出现次数计数
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40void 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 的前一位，因为题目要求每个区间内必须有数
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44void 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 相同的位置，第三类是从终点到他的右边界，绕回来之后回到终点
至此路径构造完毕，根据情况判断是否反转即可
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119void 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 ;
}
}
