字数
512 字
阅读时间
3 分钟
套题来源
2021-2022 ICPC Southwestern European Regional Contest (SWERC 2021-2022)
E - Evolution of Weasels
时间：2024-07-15
原题：Codeforces Round 617 (Div. 3) E2. String Coloring (hard version)
标签：[[../../../数据结构与算法/构造]]
题意
两串DNA，要求在对DNA进行增加或删除操作，能变成一样的
只能增删这几种串AA, BB, CC, ABAB or BCBC
思路
一开始想化成最简状态，在随便乱做后发现AB可以变成BA，BC可以变成CB
那就可以把B移到最后，比较数量后再把AC用一个栈化简（不过我当时在消消乐erase。。。）
B - Drone Photo
时间：2024-07-15
原题：Codeforces Round 592 (Div. 2) D. Paint the Tree
题意
思路
就是考虑不同的组合，以1234为例
12 34
12 43
13 42
就这三种，我们寻找共同的规律，比如第一种的数字2处于1 4之间，3处于1 4之间
如果我们将处于两数之间的数做标记
可以找出规律，一个符合条件的矩形的四个顶点，有两个被标记
代码
C++
#define rep(i,j,k) for(i=(j);i<(k);i++)
vector<int>line[N];
vector<int>row[N];
//bigline[i]存储比i大的当前行的数的个数
int bigline[N * N];
int bigrow[N * N];
int smallline[N * N];
int smallrow[N * N];
void solve() {
cin >> n;
// 每行每列获取大于该点的数量和小于该点的数量
//把每行每列的数加入到对应行列的vector中
int t;
rep(ii, 0, n) {
rep(jj, 0, n) {
cin >> t;
line[ii].emplace_back(t);
row[jj].emplace_back(t);
}
}
rep(ii, 0, n) { sort(all(line[ii])); }
rep(ii, 0, n) { sort(all(row[ii])); }
rep(ii, 0, n) {
for (int i = 0; i < n; i++) {
bigline[line[ii][i]] = n - i - 1;
smallline[line[ii][i]] = i;
bigrow[row[ii][i]] = n - i - 1;
smallrow[row[ii][i]] = i;
}
}
int ans = 0;
for (int i = 1; i <= n * n; i++) {
ans += bigline[i] * smallrow[i];
ans += smallline[i] * bigrow[i];
}
cout << ans / 2 << endl;
}贡献者
lulaalu