2019牛客暑期多校训练营第八场

 2019-08-11 /  Luo Jinrong

进度

A	B	C	D	E	F	G	H	I	J
√	√	√				√

A. All-one Matrices

题意

找全一矩阵，满足它不是其他全一矩阵的子矩阵。问这样的全一矩阵的个数。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define pi 3.1415926
#define mp(x, y) make_pair(x, y)
#define vi vector<int>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pair;
const int MAX = 3e3 + 10;
 
int N, M;
int grap[MAX];
int l[2][MAX], r[2][MAX], h[2][MAX];
char str[MAX];
 
int main() {
#ifdef ACM_LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int sum = 0, pre_l = 0, pre_r = 0, pre_h = 0;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i++) {
        scanf("%s", str + 1);
        int now = i % 2, pre = now ^ 1;
        for (int j = 1; j <= M; j++) {
            if (str[j] == '1')grap[j] = 1, h[now][j] = h[pre][j] + 1, l[now][j] = r[now][j] = j;
            else grap[j] = 0, h[now][j] = 0, l[now][j] = r[now][j] = 0;
        }
 
        //左边界
        for (int j = 2; j <= M; j++)
            if (grap[j] == 1 && grap[j - 1] == 1)
                l[now][j] = l[now][j - 1];
        //右边界
        for (int j = M - 1; j >= 1; j--)
            if (grap[j] == 1 && grap[j + 1] == 1)
                r[now][j] = r[now][j + 1];
 
        for (int j = 1; j <= M; j++) {
            if (grap[j] != 1)continue;
            if (i > 1 && h[pre][j]) {
                l[now][j] = max(l[now][j], l[pre][j]);
                r[now][j] = min(r[now][j], r[pre][j]);
            }
            if (l[now][j] != l[pre][j] || r[now][j] != r[pre][j])
                if (l[now][j] != pre_l || r[now][j] != pre_r || h[now][j] != pre_h) {
                    pre_l = l[now][j], pre_r = r[now][j], pre_h = h[now][j];
                    sum++;
                }
        }
    }
    printf("%d\n", sum);
    return 0;
}

B. Beauty Values

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
 
const int MAXN(1e5+7);
int n, a[MAXN], nm[MAXN];
int t[MAXN];
ll summ, x;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    per(i, 1, n+1) { cin>>a[i]; t[i]=i-nm[a[i]]; nm[a[i]]=i; }
    per(i, 1, n+1) {
        x += t[i];
        summ += x;
    }
    cout << summ << '\n';
 
    return 0;
}

m=2时为
$$
\begin{matrix}
1&1\
1&-1
\end{matrix}
$$
预处理从小到大构造，大的可以根据小的状态得到。当m大于2时第一行为全1，第二行前一半为1，后一半为-1，接下来两行将m分成两份，一个m/2把前一半1后一半-1映射为1，前一半-1后一半1映射为-1，然后根据2的状态构造。后面四行把m分成四份，对于m/4把前一半1后一半-1映射为1，前一半-1后一半1映射为-1，然后根据4的状态构造。以此类推。

#include<bits/stdc++.h>
using namespace std;
int mat[11][1500][1500];
int m;
void dfs(int now, int l, int m, int one[], int neone[]) {
    int len = pow(2, now - m), lem = pow(2, m),nl;
    for (int i = 1; i <= lem; i++) {
        nl = 1;
        for (int j = 1; j <= lem; j++) {
            if (mat[m][i][j] == 1) {
                for (int k = 0; k < len; k++) {
                    mat[now][l + i - 1][nl++] = one[k];
                }
            }
            else {
                for (int k = 0; k < len; k++) {
                    mat[now][l + i - 1][nl++] = neone[k];
                }
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m;
    int k = 0;
    while (m!=1) {
        k++;
        m /= 2;
    }
    m = k;
    mat[1][1][1] = mat[1][1][2] = mat[1][2][1] = 1, mat[1][2][2] = -1;
    for (int i = 2; i < 11; i++) {
        for (int j = 1; j <= pow(2, i); j++) {
            mat[i][1][j] = 1;
        }
        for (int j = 1; j <= pow(2, i - 1); j++) {
            mat[i][2][j] = 1;
        }
        for (int j = pow(2, i - 1) + 1; j <= pow(2, i); j++) {
            mat[i][2][j] = -1;
        }
        int tmp = 2, one[1500], neone[1500];
        for (int j = 1; j < i; j++) {
            for (int k = 0; k < pow(2, i - j - 1); k++) {
                one[k] = 1;
                neone[k] = -1;
            }
            for (int k = pow(2, i - j - 1); k < pow(2, i - j); k++) {
                one[k] = -1;
                neone[k] = 1;
            }
            dfs(i, tmp + 1, j, one, neone);
            tmp += pow(2, j);
        }
    }
    for(int i = 1; i <= pow(2, m); i++) {
        for (int j = 1; j <= pow(2, m); j++) {
            cout << mat[m][i][j] << " \n"[j == pow(2, m)];
        }
    }
}

G. Gemstones

题意

连连看游戏，只能消去连续三个的，大于三个也只能消去三个，问最多可以消几次。

做法

从左往右遍历一遍，遍历到连续三个相同字符时，删掉这三个，将遍历到的位置回退两位，继续遍历，直到遍历到最后。

#include<bits/stdc++.h>
using namespace std;
const int maxn(1e5 + 5);
string s;
list<char> l;
list<char>::iterator iter, jter;
int len, ans, flag[maxn], nl, nn[3];
char nc;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    len = s.length();
    for (int i = 0; i < len; i++) {
        l.push_back(s[i]);
    }
    for (iter=l.begin(); iter!=l.end();) {
        nl = 0, nc = *iter;
        for (jter=iter;jter!=l.end(); jter++) {
            if (*jter == nc) {
                nl++;
                if (nl == 3) {
                    break;
                }
            }
            else {
                break;
            }
        }
        if (nl == 3) {
            ans++;
            for (int i = 0; i < 3; i++) {
                iter = l.erase(iter);
            }
            for (int i = 0; i < 3; i++) {
                if (iter == l.begin()) {
                    break;
                }
                iter--;
            }
        }
        else {
            for (int i = 0; i < nl; i++) {
                iter++;
            }
        }
    }
    cout << ans << "\n";
}

return 0;

本文链接：
https://luojinrong.github.io/2019/08/11/2019牛客暑期多校训练营第八场/

进度

A. All-one Matrices

题意

B. Beauty Values

C. CDMA

题意

做法

G. Gemstones

题意

做法