【算法竞赛】CF #817(Div.4) A-G Rethink
【算法竞赛】CF #817(Div.4) A-G Rethink
闲言
呜，AB还好，C卡了一会儿（由于题意理解错误），D可以做差sort做，却模拟做，还WA了一发。
痛，太痛了。
E，赛时卡住没做出，看一个题解，差不多，但又差好多（（
然后，从E->G，把G在赛时最后1minA了。
DEF代码附在后面
A
题意：
判断字符串s是不是 Timur的某个排列。
赛时思路：
先判断个数对不对，在把字母都插到set里。（很蠢）
思路：
读入后，sort，字符串判等。
B
题意：
B与G一样，判断两个字符串是否相等
思路：
直接把B改正G，判等。
C
题意：
三个人各写了n个各长度为3的字符串。
如果那个字符串另外两人没有写，得3分；
如果那个字符串有一个人和他一样，得1分。
求每个人的分数。
赛时思路：
将每个人的词，分别用set记录下来，再每次都判断有没有在另外两人里面。
思路：
每个人写了哪些词记录下来，那个词的次数++，之后直接用那个词的次数判断加分就好。
D
题意：
给定一条线与这条线人的朝向，sum为所有人按照他的朝向能看到的人的总和。在进行最多1~n次改变任意一人的朝向的操作后，改变后的sum最大为多少。
赛时思路：
模拟，双指针。
显而易见，在左边的朝右看，在右边的朝左看最大。
左右两边扫过来，哪个离边缘越近改那个。（最终为RRR...LLL）
思路：
计算每个点修改前后的差值（后-前），sort，从1~n改过去。
（当然，只改>0的）
*E
题意：
你有i个高宽分别为hi, wi的矩形，现给出hs, ws, hb, wb,求所有满足hs<hi<hb且ws<wi<wb的矩阵的hi*wi之和。
思路：
不难发现，大的矩形包含小的矩形，且包含小矩形包含的所有矩形。
值得注意的是，重合的矩形不形成覆盖关系。
我们尝试设计状态。
状态表示：
设f[i][j]为大小为i*j的矩形所包含的之和。状态转移：
f[i][j] = f[i][j-1]+f[i-1][j] - f[i-1][j-1] + g[i-1][j-1];最终的结果为fhb - fhb - fhs+1 + fhs+1。
*F
题意：
给你一张n*m的图，图中 .代表空，*代表占据，请问图中占据的点，是否可以用L形占满且L形直接不互相接触（不share一个点or边）
思路：
遍历一遍，把过程中的(i, j)作为L的相连两条边的顶点。
L后，把三点都标记上，再check这个L有没有和别的L相邻。（用set存点）
如果有，返回false，flag = true;
再者，遍历下来可能没有问题，但是，有零散的 *，所以，再遍历一遍，若找到没有标记的 *，则flag = true;
补充jls的做法。
并查集，先把所有十字相邻的相同的点合并。
再遍历一遍，若字符为 *，集合大小却不等于3，false；若字符为 *，大小为3，但是是竖向或者横向的3个，false。
再遍历，合并斜线一格的点相同的点，再判断集合大小是否为3
G
题意：
给出n，求长度为n，奇数位上的异或和与偶数位上的异或和相等的序列。
思路：
首先，容易发现，一旦我们得到不含0的奇数位的结果，在末尾加0就可以得到偶数位的结果。
然后，我们同样可以发现，连续的1~n（n为偶数），在n为4的倍数的时候，我们发现奇数的0号为，异或和结果为0。
我们稍加思索，试着把这些奇数都减1，发现是0~n-2的偶数。
所以，第一种情况的答案出现了。
当 n%4 == 0，答案为0~n-1的序列。
同时，因为0的加入对异或和没有影响，我们顺势得出，
当 n%4 == 3时，答案为1~n的序列。
我们再顺着考虑 n%4==1的情况。
因为前面得出 n%4 == 0的情况，我们不妨从这个情况出发，看看能不能加一个数，使得它成立。
经过思考，发现，在第一种情况考虑的连续奇数和偶数的关系是一般性的，为了添加一个数，我们自然想要它在第一种的基础上，那么这个数最好为0，对原情况没有影响，那么我们再把第一种情况的序列整体加2，显然仍然满足第一类的性质（异或和相等）。
当 n%4 == 1时，答案为0, 2~n的序列。
再考虑 n%4 == 2的情况。
不难发现，这时候，不能继续从第一种情况出发了，因为，从第一种情况出发的话，前面的异或和相等，而最后两个数不能相等，那异或和必然不等。
所以，我们不妨让前面的异或和不等，再用最后两个数进行调和，因为调和可能会使其等于前面的数，我们再在调和的基础上加上1<<t（比n大的2的次方）避免冲突。
为了简单起见，我这边就选择1~n-2作为前面不等的序列，最后再加上前面的异或和，使得奇数位与偶数位的异或和都为1<<t。
CODE
D-sol1
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
cin >> T; // scanf("%d", &T);
while (T--)
{
int n;
cin >> n;
string str;
cin >> str;
LL tres = 0;
for (int i = 0; i < n; i++)
{
if (str[i] == 'L')
tres += i;
else
tres += n - i - 1;
}
vector<LL> ans;
LL l = 0, r = n - 1, mid = n / 2;
while (ans.size() < n && (l < mid || r > mid - (n % 2 == 0)))
{
while (l < mid && str[l] == 'R')
l++;
while (r > mid - (n % 2 == 0) && str[r] == 'L')
r--;
int dl = l, dr = n - r - 1;
if (l < mid && dl <= dr && str[l] != 'R')
{
str[l] = 'R';
tres -= l, tres += n - l - 1;
}
else if (r > mid - (n % 2 == 0) && str[r] != 'L')
{
str[r] = 'L';
tres -= n - r - 1, tres += r;
}
ans.emplace_back(tres);
}
for (LL &x : ans)
cout << x << ' ';
for (int i = 0; i < n - ans.size(); i++)
cout << tres << ' ';
cout << '\n';
}
return 0;
}D-sol2
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
cin >> T; // scanf("%d", &T);
while (T--)
{
int n;
cin >> n;
string s;
cin >> s;
vector<LL> ans(n + 1), dx(n);
for (int i = 0; i < n; i++)
{
if (s[i] == 'L')
ans[0] += i, dx[i] = (n - i - 1) - i;
else
ans[0] += n - i - 1, dx[i] = i - (n - i - 1);
}
sort(all(dx), greater<int>());
for (int i = 1; i <= n; i++)
ans[i] = ans[i - 1] + max(dx[i - 1], 0LL);
for (int i = 1; i <= n; i++)
cout << ans[i] << " \n"[i == n];
}
return 0;
}E
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1010;
int n, q;
LL f[N][N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
cin >> T; // scanf("%d", &T);
while (T--)
{
memset(f, 0, sizeof f);
cin >> n >> q;
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
f[x + 1][y + 1] += x * y;
}
for (int i = 0; i <= 1001; i++)
for (int j = 0; j <= 1001; j++)
f[i][j] += f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
while (q--)
{
int h1, w1, h2, w2;
cin >> h1 >> w1 >> h2 >> w2;
cout << f[h2][w2] - f[h2][w1 + 1] - f[h1 + 1][w2] + f[h1 + 1][w1 + 1] << '\n';
}
}
return 0;
}F
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int dxy[4][2] = {
{0, 1},
{1, 0},
{0, -1},
{-1, 0},
};
char g[55][55];
bool vis[55][55];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("i.txt", "r", stdin);
// freopen("o.txt", "w", stdout);
int T;
cin >> T; // scanf("%d", &T);
while (T--)
{
memset(vis, 0, sizeof vis);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> g[i];
bool flag = false;
auto check = [&](int x, int y)
{
set<PII> s;
for (int i = 0; i < 4; i++)
{
int j = (i + 1) % 4;
int x1 = x + dxy[i][0], y1 = y + dxy[i][1];
int x2 = x + dxy[j][0], y2 = y + dxy[j][1];
if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m)
continue;
if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m)
continue;
if (g[x1][y1] == '*' && !vis[x1][y1] && g[x2][y2] == '*' && !vis[x2][y2])
{
vis[x][y] = vis[x1][y1] = vis[x2][y2] = true;
s.insert({x, y});
s.insert({x1, y1});
s.insert({x2, y2});
break;
}
}
for (auto &p : s)
{
for (int i = -1; i <= 1; i++)
for (int j = -1; j <= 1; j++)
{
if (!i && !j)
continue;
int x = p.first + i, y = p.second + j;
if (x < 0 || x >= n || y < 0 || y >= m)
continue;
if (g[x][y] == '*' && s.find({x, y}) == s.end())
return false;
}
}
return true;
};
for (int i = 0; i < n; i++)
{
if (flag)
break;
for (int j = 0; j < m; j++)
if (g[i][j] == '*' && !vis[i][j] && !check(i, j))
{
flag = true;
break;
}
}
for (int i = 0; i < n; i++)
{
if (flag)
break;
for (int j = 0; j < m; j++)
if (g[i][j] == '*' && !vis[i][j])
{
flag = true;
break;
}
}
if (flag)
cout << "NO\n";
else
cout << "YES\n";
}
return 0;
}腾讯云开发者
