第52场周赛

第二题：（简单模拟）

https://www.acwing.com/problem/content/4426

• 做的时候最头疼的点：不知道怎么表示离0最近的距离
• 比较好的方法：从头和从尾遍历两遍，取最小值

• 先把计数器初始化为 正无穷，因为要碰到0之后，才开始从1标记非0点的距离

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  const int N = 2 * 100010;
  int a[N], ans[N], n;
  int main(){
    cin >> n;
    for(int i = 0;i < n;i ++ ) cin >> a[i];
    for(int i = 0,cnt = 2e9;i < n;i ++ )
        if(a[i] == 0) cnt = 0;
        else ans[i] = ++cnt;
    for(int i = n - 1,cnt = 2e9;i >= 0;i -- )
        if(a[i] == 0) cnt = 0;
        else ans[i] = min(ans[i], ++cnt);
    for(int i = 0;i < n;i ++ ) cout << ans[i] <<" ";
    return 0;
  }

  第三题：（浮点数类型的二分）

• 找到函数二分即可

• 要注意精度问题，如果是个逼近值，等于号最好写成 > 1e-12 这种类型 ```cpp

  include

  include

  include

using namespace std;

const int N = 1010;

double f(double a,int d){

return -a * a + a * d - d;

}

int main(){

int t;
cin >> t;

while(t -- ){

    int d;
    cin >> d;
    double l = d * 1.0 / 2,r = 10000;

    bool flag = true;
    if(d * d * 1.0 / 4 - d < 0) flag = false;  
    while(flag && r - l > 1e-12){
        double mid = (l + r) / 2;
        if(f(mid, d) >= 0) l = mid;
        else r = mid;
    }
    if(flag){
        double a = l;
        if(d - a >= 0){
            printf("Y %.10lf %.10lf",a, d - a);
        }else{
            cout << "N";
        }
    }else{
        cout << "N";
    }  
    cout << endl;
}


return 0;

}

<a name="ZP3qk"></a>
### 第51场周赛

<a name="KjkM2"></a>
##### 第一题：
水过
<a name="vDYED"></a>
##### 第二题：连通分量（DFS或者并查集）
[https://www.acwing.com/problem/content/4423/](https://www.acwing.com/problem/content/4423/)

做题思考：最开始无脑DFS对每一个非空地的位置全部进行搜索，然后超时了。。。

然后使用了并查集 + DFS ~~乱搞一通 ~~  成功AC

以下为~~绞尽脑汁乱搞出来的~~AC代码（代码略显臃肿）：
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;


char a[N][N];
char ans[N][N];
int cnt;
int num[N*N];
int p[N*N];
int n, m;
bool st[N*N];

int get(int x, int y){  // 这里比较乱搞，只是单纯找一个映射关系。。。
    return x + 1000 * y;
}

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

int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

void dfs(int x, int y,int father) {
    for (int i = 0; i < 4; i++) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && p[get(tx, ty)] != father && a[tx][ty] == '.') {
            p[get(tx, ty)] = father;
            num[father] += 1;
            dfs(tx, ty, father);
        }
    }
}


int main() {

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            p[get(i, j)] = get(i, j);
            num[get(i, j)] = 1;
        }
    }



    for(int i = 1;i <= n;i ++ ){
        for(int j = 1;j <= m;j ++ ){
            if(a[i][j] == '.' && p[get(i, j)] == get(i, j)){
                dfs(i, j,get(i, j));    
            }
        }
    }

    for(int i = 1;i <= n;i ++ ){
        for(int j = 1;j <= m;j ++ ){
            if(a[i][j] == '*'){
                int res = 1;
                for(int k = 0;k < 4;k ++ ){
                    int x = i + dx[k], y = j + dy[k];
                    int father = find(get(x, y));
                    if(x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == '.' && !st[father]){
                        res += num[father];
                        st[father] = true;
                    }
                }
                for(int k = 0;k < 4;k ++){
                    int x = i + dx[k], y = j + dy[k];
                    int father = find(get(x, y));
                    st[father] = false;
                }
                ans[i][j] = (res % 10) + '0';
            }else{
                ans[i][j] = '.';
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << ans[i][j];
        }
        cout << endl;
    }
    return 0;
}

发现可以使用DFS优化，或者直接使用并查集就能过

并查集的Debug过程：

• 用一个fathers数组来存当前点的周围的所有father，但是要记得判重，这里最开始我把fathers数组和cnt位置放错了，应该放在两层for循环里面
• 坐标偏移量， 这次出大问题
  • 首先是在得到偏移坐标后忘记判断该点是否合法
  • 然后是y的偏移量写成了 dx… 找了半天才找到这个错
• 最后的答案要对10取模

• 二维坐标展开的get函数

  //    下标从1开始的二维数组展开，行要减1，从0开始，行不减一
  int get(int x, int y){
   return (x - 1) * m + y;
  }
  

  本题新获得的知识点：

• unique的相关使用

  // unique 函数用来去重，但先要排序，然后返回的是去重后的第一个数的地址
  // unique 实际只是调换了数组的位置，并没有真正的把数组元素删除
  // 两个地址相减为这两个地址之间的元素个数，并不是地址的差值 ！！！
  sort(a,a + n);
  int num = unique(a, a + n) - a;
  

• 并查集可以把二维数组直接展开的方式来看

• 以下为并查集AC代码（模板： 并查集 + 最大连通块数量）

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int p[N*N],s[N*N];  // 这里是二维数组展开来看，所以总数为 N^2
char g[N][N];
int n,m;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

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

int get(int x, int y){  // 坐标转换为展开后的第几个数

    return (x - 1) * m + y; 
}  

int main(){


    cin >> n >> m;
    for(int i = 1;i <= n;i ++ ){
        for(int j = 1;j <= m;j ++ ){
            cin >> g[i][j];
        }
    }
    for(int i = 1;i <= n * m;i ++ ){  //初始化并查集
        p[i] = i;
        s[i] = 1;
    }

    for(int i = 1;i <= n;i ++ ){
        for(int j = 1;j <= m;j ++ ){
            if(g[i][j] == '.'){
                for(int k = 0;k < 4;k ++ ){
                    int x = i + dx[k],y = j + dy[k]; // 易错
                    if(x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == '.'){
                        int a = get(i, j);
                        int b = get(x, y);
                        a = find(a),b = find(b);
                        if(a != b){
                            p[a] = b;
                            s[b] += s[a];
                        }
                    }
                }
            }
        }
    }

    for(int i = 1;i <= n;i ++ ){
        for(int j = 1;j <= m;j ++ ){
            int fathers[4],cnt = 0;
            if(g[i][j] == '*'){
                for(int k = 0;k < 4;k ++ ){
                    int x = i + dx[k],y = j + dy[k];
                    if(x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == '.'){
                        int a = get(x, y);
                        a = find(a);
                        fathers[cnt ++ ] = a; 
                    }
                }

            //unique函数使用的时候需要先排序
            sort(fathers,fathers + cnt);

            // 两个地址相减返回的结果是在这两个地址之间的个数，不是地址相减的数
            int num = unique(fathers,fathers + cnt) - fathers; 
            int ans = 1;
            for(int k = 0;k < num;k ++){
                ans += s[fathers[k]];
            }
            cout << ans % 10;
            }
            else cout << g[i][j];
        }
        cout << endl;
    }
    return 0;
}

• 以下为DFS方法（本质和并查集非常像）

• 思路：

  • 对每一个空地进行DFS，然后把搜到的空地加到当前的集合中，建立一个映射关系，当前二维数组的坐标对应一个所属集合，值随集合改变（并查集的思想）
  • 后面的循环遍历和并查集一模一样

// 判重的一个模板
sort(fathers,fathers + num);
int u = unique(fathers,fathers + num) - fathers;
for(int k = 0;k < u;k ++){
    ans += sum[fathers[k]];
}

• DFS（完整AC代码） ```cpp

  include

  include

  include

using namespace std;

const int N = 1010;

char g[N][N]; int mp[N][N],sum[N*N]; int n,m,idx = 1;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x,int y){

if(mp[x][y]) return; 
mp[x][y] = idx;
sum[idx] += 1;
for(int i = 0;i < 4; i++ ){
    int tx = x + dx[i], ty = y + dy[i];
    if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && g[tx][ty] == '.'){
        dfs(tx, ty);
    }
}

}

int main(){

cin >> n >> m;
for(int i = 1;i <= n;i ++ ){
    for(int j = 1;j <= m;j ++ ){
        cin >> g[i][j];
    }
}

for(int i = 1;i <= n;i ++ ){
    for(int j = 1;j <= m;j ++ ){
        if(g[i][j] == '.'){
            dfs(i, j);
            idx ++;
        }
    }
}
for(int i = 1;i <= n;i ++ ){
    for(int j = 1;j <= m;j ++ ){
        if(g[i][j] == '.') cout << g[i][j];
        else{
            int fathers[4],num = 0;
            for(int k = 0;k < 4;k ++ ){
                int x = i + dx[k],y = j + dy[k];
                if(x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == '.'){
                    fathers[num ++] = mp[x][y];
                }
            }
            int ans = 1;
            sort(fathers,fathers + num);
            int u = unique(fathers,fathers + num) - fathers;
            for(int k = 0;k < u;k ++){
                ans += sum[fathers[k]];
            }
            cout << ans%10;
        }
    }
    cout << endl;
}

return 0;

}

<a name="dpzh4"></a>
##### 第三题：信号（贪心：最小区间合并的问题）
[https://www.acwing.com/problem/content/4424/](https://www.acwing.com/problem/content/4424/)

- 做的时候完全没想到是区间合并的贪心问题，但还是恩贪出来了

以下为AC代码：

- 这个代码的具体思路就是移动边界，然后选出一定会被选到的点
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int st[N];
int a[N],has[N];
int main(){

    int n, r;
    cin >> n >> r;
    int cnt = 0;
    for(int i = 1;i <= n;i ++ ){
        cin >> a[i];
        if(a[i]) has[cnt ++] = i; 
    }

    int bound = 0;
    int sum = 0;
    for(int i = 0;i < cnt;i ++ ){
        if(i != cnt - 1 && has[i] - r + 1 <= bound + 1 && has[i + 1] - r + 1 > bound + 1){
             bound = has[i] + r - 1;
             sum ++;
             if(bound == n) break;
        }
        if(i + 1 == cnt && has[i] - r + 1 <= bound + 1){
            bound = has[i] - r + 1;
            sum ++;
        }
    }

    if(!bound || bound < n){
        cout << -1 << endl;
    }else{
        cout << sum << endl;
    }

    return 0;
}

• 完全按着基础课的板子题就可以求解
• 需要注意的点是 begin代表的是上一个已经被覆盖的点 ```cpp

  include

  include

  include

using namespace std;

const int N = 1010;

int a[N]; pair p[N]; int main(){

int n, r;
cin >> n >> r;
int cnt = 0;
for(int i = 1;i <= n;i ++ ){
    cin >> a[i];
    if(a[i] == 1){
        p[cnt ++ ] = {i - r + 1,i + r - 1};
    }
} 

bool flag = false;
int begin = 0,ans = 0;  // 把begin想成是最后一个被覆盖的区域
int mx = -2e9;
for(int i = 0;i < cnt;i ++ ){
    int j = i;

    if(p[j].first > begin + 1) break;

    while(j < cnt && p[j].first <= begin + 1){
        if(mx <= p[j].second){
            mx = p[j].second;
        }
        j ++;
    }
    i = j - 1;

    if(mx <= begin) continue;
    begin = mx;
    ans ++;

    if(p[i].second >= n){
        flag = true;
        break;
    }
}

if(flag) cout << ans << endl;
else cout << -1 << endl;

return 0;

}

- 还可以用更加简洁的代码实现
   - 只用存每个可以有发射器的点
   - 这里默认已经排序了，不需要在自己排
   - 每一次更新边界点，只需要找最后一个满足要求的就可以，因为右端点一定单调递增
   - 当满足要求后记得break，并且要在ans已经更新的情况下再break
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int q[N];
int main(){

    int n, r;
    cin >> n >> r;
    int cnt = 0;
    for(int i = 1;i <= n;i ++ ){
        int a;
        cin >> a;
        if(a) q[cnt ++ ] = i;
    }

    int last = 0,ans = 0;
    for(int i = 0;i < cnt;i ++ ){

        if(q[i] - r + 1 > last + 1) break;
        int j = i;
        while(j + 1 < cnt && q[j + 1] - r + 1 <= last + 1) j ++;

        last = q[j] + r - 1;

        ans ++;

        if(last >= n) break;

        i = j;
    }

    if(last < n) ans = -1;
    cout << ans << endl;

    return 0;
}

第50场周赛

第一题：

水

第二题： 选区间（简单模拟就可）

思路：最开始以为是区间问题，还用了pair数组来存下标，后面发现根本不需要这么麻烦，只用存点就行

• AC 代码（第一版还是略显复杂了，因为实际上用到的只有4个点，可以再优化） ```cpp

  include

  include

  include

using namespace std;

const int N = 200010;

int main(){

vector<int> aL,aR,bL,bR;
int n;
cin >> n;
for(int i = 0;i < n; i++ ){
    int l, r;
    cin >> l >> r;
    aL.push_back(l);
    aR.push_back(r);
}
int m;
cin >> m;
for(int i = 0;i < m; i++ ){
    int l,r;
    cin >> l >> r;
    bL.push_back(l);
    bR.push_back(r);
}
sort(aL.begin(),aL.end());
sort(aR.begin(),aR.end());
sort(bL.begin(),bL.end());
sort(bR.begin(),bR.end());

if(aR[0] >= bL[bL.size() - 1] && aL[aL.size() - 1] <= bR[0]){
    cout << 0 << endl;
}else{
    cout << max(bL[bL.size() - 1] - aR[0], aL[aL.size() - 1] - bR[0]) << endl;
}

return 0;

}

- 只用4个点进行操作的AC代码
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int main(){

    int n;
    cin >> n;
    int max_1L = -2e9,min_1R = 2e9;
    for(int i = 0;i < n;i ++ ){
        int a,b;
        cin >> a >> b;
        max_1L = max(max_1L, a);
        min_1R = min(min_1R, b);
    }

    int m;
    cin >> m;
    int max_2L = -2e9,min_2R = 2e9;
    for(int i = 0;i < m;i ++){
        int a,b;
        cin >> a >> b;
        max_2L = max(max_2L,a);
        min_2R = min(min_2R,b);
    }
    if(min_1R >= max_2L && max_1L <= min_2R){
        cout << 0 << endl;
    }else{
        cout << max(max_2L - min_1R, max_1L - min_2R) << endl;
    }

    return 0;
}

• 代码更加简洁的AC代码
  • 优化部分：在得到第一类区间的两个点后直接在第二类区间进行遍历是比较得到结果 ```cpp

    include

    include

    include

using namespace std;

const int N = 200010;

int main(){

int n;
cin >> n;
int a = -2e9,b = 2e9;
for(int i = 0;i < n;i ++ ){
    int l,r;
    cin >> l >> r;
    a = max(a, l);
    b = min(b, r);
}
int m;
cin >> m;
int res = 0;
for(int i = 0;i < m;i ++ ){
    int l,r;
    cin >> l >> r;
    if(a - r > 0) res = max(res, a - r);
    if(l - b > 0) res = max(res, l - b);
}
cout << res << endl;

return 0;

}

<a name="Aq9mg"></a>
##### 第三题：选元素（带有条件的动态规划）

// TODO

- 第一种状态表示
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210;
typedef long long LL;

LL f[N][N]; // 从前i个数当中选j个数，且在连续k个子序列中含有被选元素

LL a[N];
int main(){

    int n, k, x;
    cin >> n >> k >> x;

    memset(f, -0x3f, sizeof f);
    for(int i = 1;i <= n;i ++ ) cin >> a[i];

    for(int i = 0;i < k;i ++ ){
        f[i][0] = 0;
    }

    for(int i = 1;i <= n;i ++ ){
        for(int j = 1;j <= i;j ++ ){
            int u = max(0,i - k);
            for(;u < i;u ++ ){
                f[i][j] = max(f[i][j], f[u][j - 1] + a[u + 1]);
            }
        }
    }
    LL res = -1;
    cout << max(res, f[n][x]) << endl;

    return 0;
}

• 第二种状态表示 ```cpp

  include

  include

  include

using namespace std;

const int N = 210;

typedef long long LL;

LL f[N][N]; // f[i, j] 代表从前i个数中选，且选择了j个数，并且第i个数被选的最大值

/* 找前一个被选择的数 状态划分：

*/

int a[N]; int main(){

int n, k, x;
cin >> n >> k >> x;

memset(f, -0x3f, sizeof f);
f[0][0] = 0;
for(int i = 1;i <= n;i ++ ) cin >> a[i];

for(int i = 1;i <= n;i ++ ){
    for(int j = 1;j <= i;j ++ ){
        int v;
        v = max(i - k, 0);
        for(;v < i;v ++ ){
            f[i][j] = max(f[i][j], f[v][j - 1] + a[i]);   
        }
    }
}

LL ans = -1;
for(int i = n - k + 1;i <= n;i ++ ) ans = max(ans, f[i][x]);
cout << ans << endl;

return 0;

}

<a name="Crxnw"></a>
### 第49场周赛

<a name="hu8cG"></a>
##### 第一题

<a name="gtAEh"></a>
##### 第二题：（模拟或者动态规划）
[https://www.acwing.com/problem/content/4417/](https://www.acwing.com/problem/content/4417/)

思路：一开始想过动态规划来做，但是没想到怎么进行状态转移，但也有更简单的思路来做

- 模拟：将所用大于0的数相加得到sum，最终的结果为 (sum, sum + max_num, sum - min_num )中的一个

- 以下为模拟的AC代码
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];
int main(){

    int n;
    cin >> n;
    for(int i = 0;i < n;i ++ ) cin >> a[i];
    int ans = 0;
    int min_num = 2e9,max_num = -2e9;
    for(int i = 0;i < n;i ++ ){
        if(a[i] > 0){
            ans += a[i];
        }
        if(a[i] & 1){  //统计最小的正奇数，或者最大的负奇数
            if(a[i] > 0) min_num = min(min_num, a[i]);
            else max_num = max(max_num, a[i]);
        }
    }
    if(ans & 1){  // 如果是奇数，直接输出结果
        cout << ans << endl;
    }else{
        cout << max(ans - min_num, ans + max_num) << endl;
    }

    return 0;
}

以下为动态规划做法

动态规划的难点在于找状态转移方程式：这道题可以将分为f[N][0] 和 f[N][1] 分别讨论
然后找对递推条件即可（可以带人状态转移方程和题目要求得到递推边界）
技巧，找最大值问题，一般先把所有的结果初始化为-0x3f3f3f3f 不会影响正常结果

• AC 代码 ```cpp

  include

  include

  include

using namespace std;

const int N = 100010;

int a[N]; int f[N][2]; // 从前i个数中选最大的偶数或者奇数

int main(){

int n;
cin >> n;
for(int i = 1;i <= n;i ++ ) cin >> a[i];

memset(f,-0x3f,sizeof f);
if(a[0] & 1) f[0][1] = 0;
else f[0][0] = 0;
for(int i = 1;i <= n;i ++ ){
    if(a[i] & 1){
        f[i][0] = max(f[i - 1][0], f[i - 1][1] + a[i]);
        f[i][1] = max(f[i - 1][1], f[i - 1][0] + a[i]);
    }else{
        f[i][0] = max(f[i - 1][0], f[i - 1][0] + a[i]);
        f[i][1] = max(f[i - 1][1], f[i - 1][1] + a[i]);
    }
}
cout << f[n][1] << endl;
return 0;

}

<a name="PlNJR"></a>
##### 第三题：点的赋值（二分染色法+快速幂）
[https://www.acwing.com/problem/content/4418/](https://www.acwing.com/problem/content/4418/)

- 思路：需要找到规律
   - 因为只有1,2,3三个数，且要求相邻两个点相加为奇数，那相邻两个点一定一个是偶数，另一个是奇数
   - 所有判断这个图是否是二分图，如果不是，直接打印0
   - 如果是二分图，记下来每个环的奇数个数和偶数个数
      - 每个奇数要么是1要么是3，偶数只有可能是2,
      - 所有的情况 = 2^所有奇数个数 + 2^所有偶数个数
      - 因为所有环相互独立，所有将这些答案全部相乘即为最后的答案 （一开始就想错了）
   - 注意快速幂不要写错了。。。
   - N的取值虽然是3 * 1e5 但这是无向边，需要开两倍的数组大小
   - 注意每组测试用例有多个，所有在初始化 h, color 数组时只初始化 4（n + 1） 字节大小的地方
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3 * 1000010, MOD = 998244353;

typedef long long LL;

int h[N],e[N],ne[N],idx;
int x,y;
int color[N];

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

bool dfs(int u,int c){

    color[u] = c;
    if(c == 1) x ++;
    else y ++;

    for(int i = h[u];i != -1;i = ne[i]){
        int j = e[i];
        if(!color[j]){
            if(!dfs(j, 3 - c)) return false;
        }else if(color[j] == c) return false;
    }
    return true;
}


// 快速幂需要在多熟悉以下
LL qmi(int a, int b, int p)
{
    LL res = 1 % p;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}


int main(){

    int t;
    cin >> t;
    while(t -- ){
        int n,m;
        cin >> n >> m;
        memset(h, -1, 4 * (n + 1));
        memset(color,0,4 * (n + 1));
        idx = 0;
        for(int i = 0;i < m;i ++ ){
            int a,b;
            cin >> a >> b;
            add(a,b),add(b,a);
        }

        bool flag = true;
        long long ans = 1;
        for(int i = 1;i <= n;i ++ ){
            x = y = 0;
            if(!color[i]){
                if(!dfs(i, 1)){
                    flag = false;
                    break;
                }else{
                    ans = ans * ((qmi(2, x, MOD) + qmi(2, y, MOD)) % MOD) % MOD;
                }
            }
        }

        if(flag){
            cout << ans << endl;
        }
        else cout << 0 << endl;
    }

    return 0;
}

第48场周赛

第一题：

水题，略过

第二题：三仙归洞（模拟）

https://www.acwing.com/activity/content/problem/content/6864/

思路：找规律

做题思考过程：
在第一次做的时候，意识到这是一道找规律的题目，但是代码比较繁杂

• 分成了n为奇数和偶数分别讨论
• 每一种情况都有3种循环规律
• 代码量有点多 ```cpp

  include

  include

  include

  using namespace std;

const int N = 2e9;

int main(){

int n, x;
cin >> n >> x;

int res = 0;
if(n % 2 == 0){
    if(x == 0){
        n = n % 6;
        int d[6] = {0,1,1,0,-1,-1};
        for(int i = 0;i < n;i ++ ){
             res += d[i];
        }

    }
    if(x == 1){
        n %= 6;
        int d[6] = {1,0,-1,-1,0,1};
        for(int i = 0;i < n; i++ ){
             res += d[i];
        }
        res += 1;

    }
    if(x == 2){
        n %= 6;
        int d[6] = {-1,-1,0,1,1,0};
        for(int i = 0;i < n;i ++ ){
            res += d[i];
        }
        res += 2;
    }
}
else{
    if(x == 0){
        n = n % 6;
        int d[6] = {1,1,0,-1,-1,0};
        for(int i = 0;i < n;i ++ ){
             res += d[i];
        }

    }
    if(x == 1){
        n %= 6;
        int d[6] = {-1,0,1,1,0,-1};
        for(int i = 0;i < n; i++ ){
             res += d[i];
        }
        res += 1;

    }
    if(x == 2){
        n %= 6;
        int d[6] = {0,-1,-1,0,1,1};
        for(int i = 0;i < n;i ++ ){
            res += d[i];
        }
        res += 2;
    }
}

cout << res << endl;

return 0;

}

最优解决方式：

- 记下最开始位置的情况为{0， 1， 2}，然后交换后得到最后的情况

- 例如 最开始是 0 1 2  代表初始位置  交换后变成了  2 1 0 这些数代表最开始位置的数现在的位置，所有根据最后下标能够找到一开始的位置
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int main(){

    int n, x;
    cin >> n >> x;

    n %= 6;
    int state[3] = {0,1,2};
    for(int i = 1;i <= n;i ++ ){
        if(i % 2 == 1) swap(state[0],state[1]);
        else swap(state[1],state[2]);
    }
    cout << state[x] << endl;

    return 0;
}

第三题：构造数组（区间合并）

https://www.acwing.com/problem/content/4415/

做题思路：
没有想到如何计算所有状态，以为是dfs问题
只是发现了规律： 就是 a[i] 和 a[j] 相等的情况下，b[i ~ j] 全部相等

在看过题解之后，发现可以用区间合并的方式做

记录所有 b[i ~ j] 一定相等的 i 和 j，然后合并这些区间，最后得到的区间每个区间有两种取值
一种是与前面的相等，一种是比前面的多1，因为b[0] = 1,所有 答案就为 2 ^ (所有区间数- 1)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

const int N = 2e5 + 10;

int a[N];
pair<int, int> p[N];
vector<pair<int, int>> v;
int main(){

    int n;
    cin >> n;
    for(int i = 0;i < n;i ++ ) cin >>a[i];

    map<int, int> L, R;

    for(int i = 0;i < n;i ++ ){

        R[a[i]] = i;
        if(!L.count(a[i])) L[a[i]] = i;
    }

    map<int, int>:: iterator it;

    int cnt = 0;
    for(it = L.begin();it != L.end();it ++){
        p[cnt ++ ] = {L[(*it).first], R[(*it).first]};
    }

    sort(p,p + cnt);

    int st = -2e9,ed = -2e9;
    for(int i = 0;i < cnt;i ++ ){

        if(p[i].first >= ed){
            if(ed != -2e9) v.push_back({ed, st});
            ed = p[i].second;
            st = p[i].first;
        }
        else{
            ed = max(ed,p[i].second);
        }
    }
    v.push_back({ed, st});

    int ans = 1;
    for(int i = 1;i < v.size();i ++ ){
        ans = (ans * 2) % 998244353;
    }

    cout << ans << endl;


    return 0;
}

以下为这道题的细节：
本题故意卡了unoredered_map，所以用这个会超时, up 最坏会被卡成 O(n) 的复杂度
解决方法：

1. 使用map，map速度稳定的慢，但不会被卡
2. 将um初始化大小变大，这样的映射就不至于到一个点，这道题可以初始化 300000 的大小

得到map的key值，可以通过迭代提进行遍历

map<int, int>:: iterator it;  // 这里是得到迭代器

    int cnt = 0;
    for(it = L.begin();it != L.end();it ++){  // 具体迭代过程
        p[cnt ++ ] = {L[(*it).first], R[(*it).first]}; // 同一组L和R对应同一个key
    }

合并区间的时候要先进行判断

if(p[i].first >= ed){
            if(ed != -2e9) v.push_back({ed, st});  // 这里要先进行判断，放在后面ed已经被更新
            ed = p[i].second;
            st = p[i].first;
        }

TODO
该题还可以使用并查集的方式做，暂时留到后面解决

第46场周赛

第一题：

水过

第二题：卡牌（贪心）

https://www.acwing.com/problem/content/4400/

做题思路：

• 个人思路： 定义一个结构体，按照 a - b 的差值 从大到小排序，用到了针对的结构体排序

AC 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 200010;  // 

struct node{
    int a,b;
    bool operator< (const node &W)const{  // 定义结构体排序，a - b 从大到小排序
        return a - b > W.a - W.b;
    }
}p[N];

int a[N],b[N];
int main() {

    int n,k;
    cin >> n >> k;  // n代表总牌数，k保证一共有多少张牌正面朝上
    for(int i = 0;i < n;i ++ ) cin >> a[i];
    for(int i=  0;i < n;i ++ ) cin >> b[i];

    for(int i = 0;i < n;i ++ ){
        p[i].a = a[i],p[i].b = b[i];
    }

    sort(p,p + n);

    int ans = 0;
    int cnt = 0;
    for(int i = 0;i < n - k;i ++){  // 将正面的排替换成反面，并将结果累加

        if(p[i].a - p[i].b < 0){  // 当正面比反面的数小时，直接退出
            break;
        }
        cnt ++;
        ans += p[i].b;
    }
    for(int i = cnt;i < n;i ++ ) ans += p[i].a; // 从退出开始，剩余的就只加上正面即可

    cout << ans << endl;
    return 0;
}

• 附上yxc思路的超简洁代码，没有新开一个结构体，直接用一个数组d 来存b - a的差值 ```cpp

  include

  include

using namespace std;

const int N = 200010;

int a[N],b[N],d[N]; // d[N] 来存b - a 的差值 int main() {

int n,k;
cin >> n >> k;
int sum = 0;
for(int i = 0;i < n;i ++ ) cin >> a[i], sum += a[i];  // 先将正面全部相加
for(int i = 0;i < n;i ++ ) cin >> b[i], d[i] = b[i] - a[i]; 

sort(d,d + n); // 因为b - a 是负数，所以是从小到大排序

for(int i = 0;i < n - k;i ++ ){
    if(d[i] > 0) break; // 如果是正数，结果就不变，就存正面
    else sum += d[i]; // 如果是负数，就更新这个值为负面
}

cout << sum << endl;

return 0;

}

<a name="ftBeE"></a>
##### 第三题：查询字符串（哈希表的应用）

[https://www.acwing.com/problem/content/4401/](https://www.acwing.com/problem/content/4401/)

做题思路：

- 因为字符串的大小最大为8，所有想两层for遍历出所有子串
- 将所有子串全部放到hash表中，一共开两个hash，一个存该子串对应的字符串，一个存该子串的总个数

**第一次做法思路（6/10） TLE**

**没有把所有的字符串看成一个整体，只是单一的统计每一个字符串的子串情况，将问题复杂化了**
```cpp
#include<iostream>
#include<unordered_map>
using namespace std;

const int N = 10010;

string alls[N];
unordered_map<string,string> up[N];  // 开n个hashmap，每一个都存该字符串的子串
int main() {


    int n;
    cin >> n;
    for(int i = 0;i < n; i ++){
        cin >> alls[i];
    }

    for(int i = 0;i < n;i ++ ){
        string s = alls[i];
        for(int j = 0;j < s.size();j ++ ){
            string ans = "";
            for(int k = j;k < s.size();k ++ ){
                ans += s[k];
                up[i][ans] = s;
            }
        }
    }

    int q;
    cin >> q;
    for(int i = 0;i < q;i ++ ){

        bool flag = false;
        string x;
        cin >> x;
        int cnt = 0;
        int ans = 0;
        for(int j = 0;j < n;j ++ ){
            if(up[j][x] != ""){
                flag = true;
                cnt ++;
                ans = j;
            }
        }
        if(flag) cout << cnt << " " << up[ans][x] << endl;
        if(!flag) cout << "0 -" << endl;
    }
    return 0;
}

第二次（6/10） TLE 问题在于遍历hashmap清空，字符串越多，存储的键值对越多，会超时

#include<iostream>
#include<unordered_map>
using namespace std;

const int N = 10010;

string alls[N];
unordered_map<string,int> up;
unordered_map<string,string> res;
unordered_map<string,int> is_add;
int main() {


    int n;
    cin >> n;
    for(int i = 0;i < n; i ++){
        cin >> alls[i];
    }

    for(int i = 0;i < n;i ++ ){
        string s = alls[i];
        for(int j = 0;j < s.size();j ++ ){
            string ans = "";
            for(int k = j;k < s.size();k ++ ){
                ans += s[k];
                res[ans] = s;
                if(!is_add[ans]){
                    up[ans] += 1;
                    is_add[ans] = 1;
                }
            }

        }

        // 这里遍历hashmap，字符串多起来之后，存放的键值对会越来越多，所有会超时
        for(auto it = is_add.begin();it != is_add.end();it ++ ){
            it->second = 0;
        }
    }

    int q;
    cin >> q;
    for(int i = 0;i < q;i ++ ){
        string s;
        cin >> s;
        if(up[s]){
            cout << up[s] <<" " << res[s] << endl;
        }
        else{
            cout << 0  <<" "<< "-" << endl;
        }


    }

    return 0;
}

第三次 AC代码

清空hashmap的最好方式便是重新创建一次

#include<iostream>
#include<unordered_map>
using namespace std;

const int N = 10010;

string alls[N];
unordered_map<string,int> up;
unordered_map<string,string> res;  
int main() {


    int n;
    cin >> n;
    for(int i = 0;i < n; i ++){
        cin >> alls[i];
    }

    for(int i = 0;i < n;i ++ ){ //n = 10000

        // is_add 用来查询该子串在该字符串中是否已经出现过
        unordered_map<string,int> is_add;  // 关键在这里，在每一个字符串遍历完之后直接清空
        // hashmap 最直接有效的方式
        string s = alls[i];
        for(int j = 0;j < s.size();j ++ ){  // j = 8
            string ans = "";
            for(int k = j;k < s.size();k ++ ){  // k = 8
                ans += s[k];
                res[ans] = s;
                if(!is_add[ans]){ 
                    up[ans] += 1;
                    is_add[ans] = 1;
                }
            }   
        }   
    }

    int q;
    cin >> q;
    for(int i = 0;i < q;i ++ ){
        string s;
        cin >> s;
        if(up[s]) cout << up[s] <<" " << res[s] << endl;
        else cout << 0  <<" "<< "-" << endl;
    }

    return 0;
}

第47场周赛

第一题：

略过

第二题：玩游戏 （队列）

https://www.acwing.com/problem/content/4403/

做题思路：

• 第一次思考的时候老想着用数组进行循环模拟，但边界的判断条件太容易出错了
• 所以后来想到这种题就是队列的最典型应用
• 需要注意的是 操作数 a 的数据范围是 10^9 次方，如果直接做肯定TLE
• 解题关键：把 操作数变为很小的数，具体操作就是对 当前没被淘汰的小朋友数进行取模操作

以下为AC代码(YXC 代码简化版)

#include<iostream>
#include<queue>
using namespace std;

const int N = 110;

queue<int> q;
int main(){

    int n, k;
    cin >> n >> k; // n 代表总人数，k代表总共有几轮

    for(int i = 1;i <= n;i ++ ) q.push(i);  

    for(int i = 0;i < k;i ++ ){  // 100

        int cnt;
        cin >> cnt,cnt %= q.size();  // cnt 代表操作数，对队列取模

        while(cnt -- ){  
            q.push(q.front());  // 这里的操作就简化了代码，不需要创建临时变量
            q.pop();
        }

        cout << q.front() << " ";  
        // 这里也是，直接将要淘汰的小朋友打印出来即可，不需要在把它放在vector中再打印
        q.pop();
    }
    return 0;
}

以下为自己写出的比较丑的AC代码

#include<iostream>
#include<queue>
using namespace std;

const int N = 110;

queue<int> q;
queue<int> res;
int a[N];
int main(){

    int n, k;
    cin >> n >> k; // n 代表总人数，k代表总共有几轮

    for(int i = 0;i < k;i ++ ) cin >> a[i];

    for(int i = 1;i <= n;i ++ ) q.push(i);

    for(int i = 0;i < k;i ++ ){  // 100

        int t;
        int cnt = a[i] % q.size();
        while(cnt -- ){  
            t = q.front();
            q.pop();
            q.push(t);
        }
        t = q.front();
        q.pop();
        res.push(t);
    }
    while(res.size()){
        cout << res.front() << " ";
        res.pop();
    }

    return 0;
}

第三题：找回数组（根据式子找条件）

https://www.acwing.com/problem/content/4404/

做题思路：
题目给出递推式：

• a0=0。
• 对于 1 ≤ i ≤n，ai=x(i−1)modk+ai−1ai=x(i−1)modk+ai−1。

简单移项后：
x[(i - 1) % k] = a[i] - a[i - 1];

所以得出k成立的条件为 同一项x在前后 a[i] - a[i - 1] 得到的数应该是相等的
对某一个k，得到所有的 a[i] - a[i - 1] 值，如果中途有条件矛盾的数就直接break，否则结果数加1，并存入当前k值

以下为自己第一次的AC代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include<vector>
using namespace std;

const int N = 1010;

vector<int> v;
int x[N];
int a[N];
int main(){

    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++ ) cin >> a[i];

    for(int k = 1;k <= n;k ++ ){
        memset(x,0x3f,sizeof x); 
         // 每一次改变k后都要重新初始化x数组，不能初始化为-1，因为x[i]本身有可能是-1
        int flag = 1;
        for(int i = 1;i <= n;i ++ ){
            if(x[(i - 1) % k] == 0x3f3f3f3f) x[(i - 1) % k] = a[i] - a[i - 1];
            else{
                if(x[(i - 1) % k] != a[i] - a[i - 1]){
                    flag = 0;
                    break;
                }
            }
        }
        if(flag) v.push_back(k);
    }

    sort(v.begin(),v.end());

    cout << v.size() << endl;
    for(int i = 0;i < v.size();i ++ ) cout << v[i] << " ";

    return 0;
}

更加简洁的AC代码
更加优化的点：
不需要再初始化一个数组x，只需要判断 a[i] - a[i - 1] 是否等于 a[i - k] - a[i - 1 - k] 即可
因为 x[i - 1] = a[i - k] - a[i - 1 - k] 跟当前的 x[(i - 1) % k] 是同一个值，只要判断他们是否相等即可

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 1010;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    vector<int> res;
    for (int k = 1; k <= n; k ++ )
    {
        bool is_match = true;
        for (int i = k + 1; i <= n; i ++ )
            if (a[i] - a[i - 1] != a[i - k] - a[i - 1 - k])
            {
                is_match = false;
                break;
            }

        if (is_match) res.push_back(k);
    }

    cout << res.size() << endl;
    for (auto k: res)
        cout << k << ' ';

    return 0;
}