A. lz的吃饭问题
思路
比较 和
的大小后输出即可。
复杂度
时间复杂度 ,空间复杂度
代码实现
// Problem: lz的吃饭问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/A
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 5, M = 17;
void solve()
{
int a[4];
for (int i = 0; i < 4; i++) {
cin >> a[i];
}
if (a[0] * a[1] < a[2] * a[3]) {
cout << "lz";
} else {
cout << "gzy";
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
B. lz的数字问题
思路
把数字分割成小数点前后的两部分,如果小数点后部分长度小于 ,则补
补到长度为
。
先对整数部分进行比较,如果不相同则输出 ,否则比较小数点部分的前
位,如果存在不同输出
,不然就是
。
复杂度
时间复杂度 ,空间复杂度
代码实现
// Problem: lz的数字问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 5, M = 17;
void solve()
{
vector<array<string, 2>> all;
for (int i = 0; i < 2; i++) {
string s;
cin >> s;
int op = 0;
array<string, 2> ar = { "", "" };
for (int i = 0; i < s.size(); i++) {
if (s[i] == '.')
op++;
else {
ar[op] += s[i];
}
}
all.push_back(ar);
}
if (all[0][0] != all[1][0]) {
cout << "NO\n";
} else {
for (int i = 0; i < 2; i++) {
while (all[i][1].size() < 6)
all[i][1] += '0';
}
int flag = 1;
for (int i = 0; i < 6; i++) {
if (all[0][1][i] != all[1][1][i]) {
flag = 0;
break;
}
}
cout << (flag ? "YES" : "NO");
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
C. lz的蛋挞问题
思路
符合条件的蛋挞为以下三种情况之一:
???(这三个中存在x,不同时都为.)
...
...
???(对称情况)
x.x
xxx
.x
xx
xx
x.
(单独的一个点)
..x
x.x
x..
x.x
(对角为x)
复杂度
时间复杂度 ,空间复杂度
代码实现
// Problem: lz的蛋挞问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e4 + 5, M = 17;
int n;
string s[2];
void solve()
{
cin >> n;
for (int i = 0; i < 2; i++) {
cin >> s[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 2; j++) {
if (s[j][i] == 'x')
continue;
if ((i <= 0 || s[j][i - 1] == 'x') && (i + 1 >= n || s[j][i + 1] == 'x') && (s[j ^ 1][i] == 'x')) {
ans++;
} else if (i > 0 && s[j][i - 1] == '.' && s[j ^ 1][i - 1] == 'x' && s[j ^ 1][i] == '.')
ans++;
else if (i > 0 && s[j][i - 1] == '.' && i + 1 < n && s[j][i + 1] == '.' && (s[j ^ 1][i] == 'x' || s[j ^ 1][i - 1] == 'x' || s[j ^ 1][i + 1] == 'x'))
ans++;
else if (i + 1 < n && s[j][i + 1] == '.' && s[j ^ 1][i + 1] == 'x' && s[j ^ 1][i] == '.')
ans++;
}
}
cout << ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
D. lz的染色问题
思路
如果观察了 ,
,则
都需要修改成同一种颜色,可以把需要修改为同种颜色的点相连,相连之后会构成多个联通块,同一个块内的点都要修改为同一种颜色。
对于一个联通块,要使得修改数量最少,修改成联通块内颜色最多的哪种颜色是最优的。
复杂度
时间复杂度 ,空间复杂度
代码实现
// Problem: lz的染色问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 17;
int n, m;
int a[N];
int p[N], sz[N];
unordered_map<int, int> h[N];
// h[i] 为祖先节点为i的颜色集合,同时记录了联通块颜色的对应点数
int find(int x)
{
return x == p[x] ? x : p[x] = find(p[x]);
}
void merge(int x, int y)
{
x = find(x), y = find(y);
if (x != y) {
p[x] = y, sz[y] += sz[x];
}
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
p[i] = i, sz[i] = 1;
}
while (m--) {
int x, y;
cin >> x >> y;
merge(x, y);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
h[find(i)][a[i]]++;
}
for (int i = 1; i <= n; i++) {
if (p[i] == i) {
int ma = 0;
for (auto it : h[i]) {
ma = max(ma, it.second);
}
ans += sz[i] - ma;
// 修改成最多的哪一种颜色,原先如果为最多的哪一种颜色则不需要修改
}
}
cout << ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
E. lz的括号问题
思路
先进行括号匹配,同时对于每个左括号记录下与它匹配的右括号下标,如果匹配时有无法匹配的右括号,或者最后剩下未匹配的左括号,则是无解,输出 。
对于一个括号,它无法在包含它的括号之前被删除,但是可以在被它包含的括号之前删除,以及与它并列的括号之前删除。
串 :(()(()))
序号:12234431
上面这一串括号中,括号 包含了括号
,因此括号
无法在括号
之前删除,但是括号
可以在与它并列的括号
之前删除,括号
可以在被它包含的括号
之前删除。
抽象化一些,就是一对括号 (
分别为左右括号的下标)。
如果最近的包含它的括号为 ,那么区间
中
的并集所涉及到的括号,都可以安排在区间
内的括号之前删除。
如果并集的长度为
,在
内的括号之前删除的括号对数量就包含了
对,可以用差分的技巧,把这个数量加到
这个区间上去。
对于 这对括号,区间
之间的括号可以安排在这对括号之前删除,对应的括号对数量为
,可以加到
这个点上,最后答案都统计在左括号的位置。
复杂度
时间复杂度 ,空间复杂度
代码实现
// Problem: lz的括号问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, M = 17;
int n;
string s;
int to[N], ans[N];
int check()
{
stack<int> st;
for (int i = 0; i < 2 * n; i++) {
char c = s[i];
if (c == '(') {
st.push(i);
} else {
if (!st.size())
return 0;
int j = st.top();
st.pop();
to[i] = j, to[j] = i;
}
}
return st.size() == 0;
}
void dfs(int l, int r)
{
int len = r - l + 1;
vector<array<int, 2>> all;
for (int i = l; i <= r; i++) {
if (s[i] == '(') {
int j = to[i];
int cur = j - i + 1;
ans[i] += (len - cur) / 2;
ans[j + 1] -= (len - cur) / 2;
// len - cur 为 [l,r] 中除 [i,j] 外的长度
ans[i] += (cur - 2) / 2;
ans[i + 1] -= (cur - 2) / 2;
// cur-2 为 [i+1,j-1] 的长度
if (i + 1 != j)
dfs(i + 1, j - 1);
i = j;
// 下标i跳到当前右括号位置j,j+1为下一对并列括号的左括号位置
}
}
}
void solve()
{
cin >> n >> s;
if (!check()) {
cout << "-1";
return;
}
dfs(0, 2 * n - 1);
for (int i = 0; i < 2 * n; i++) {
if (i)
ans[i] += ans[i - 1];
if (s[i] == '(')
cout << ans[i] << ' ';
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}
F. lz的序列问题
思路
令 为
,
为
,
即为
的美丽值。
可以发现, 可以通过子区间
计算得到,即
,
。
当把区间 都修改为
时,
,
,本质首项为
,公比为
,长度为
的等比数列的求和。
将上面的计算方式应用于线段树的维护上,这样就可以在 的复杂度进行修改和查询。
注意计算结果要对 取模,需要使用快速幂求逆元。
复杂度
时间复杂度 ,空间复杂度
代码实现
// Problem: lz的序列问题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95937/F
// Memory Limit: 512 MB
// Time Limit: 6000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5, mod = 1e9 + 7;
int n, q;
int ar[N];
struct node {
int l, r, add, v[2];
} tr[4 * N];
inline int qmi(int a, int b)
{
int res = 1;
while (b) {
if (b & 1)
res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
inline int inv(int x)
{
return qmi(x, mod - 2);
}
void pushup(node& root, node& left, node& right)
{
root.v[0] = left.v[0] * right.v[0] % mod;
root.v[1] = (left.v[1] + (left.v[0] * right.v[1] % mod)) % mod;
}
void pushup(int u)
{
pushup(tr[u], tr[u * 2], tr[u * 2 + 1]);
}
void pushdown(int u)
{
if (tr[u].add) {
auto &root = tr[u], &left = tr[u * 2], &right = tr[u * 2 + 1];
int x = tr[u].add;
int ln = left.r - left.l + 1;
int rn = right.r - right.l + 1;
left.v[0] = qmi(x, ln);
right.v[0] = qmi(x, rn);
if (x == 1) {
left.v[1] = ln, right.v[1] = rn;
} else {
left.v[1] = (qmi(x, ln) + mod - 1) % mod * x % mod * inv(x - 1) % mod;
right.v[1] = (qmi(x, rn) + mod - 1) % mod * x % mod * inv(x - 1) % mod;
}
left.add = right.add = x;
root.add = 0;
}
}
void build(int u, int l, int r)
{
tr[u].l = l, tr[u].r = r;
if (l != r) {
int mid = (l + r) >> 1;
build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
pushup(u);
} else {
tr[u].v[0] = tr[u].v[1] = ar[l];
}
}
void modify(int u, int l, int r, int x)
{
if (l <= tr[u].l && tr[u].r <= r) {
int un = tr[u].r - tr[u].l + 1;
tr[u].add = x;
tr[u].v[0] = qmi(x, un);
if (x == 1) {
tr[u].v[1] = un;
} else {
tr[u].v[1] = (qmi(x, un) + mod - 1) % mod * x % mod * inv(x - 1) % mod;
}
return;
}
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
if (l <= mid)
modify(u * 2, l, r, x);
if (r > mid)
modify(u * 2 + 1, l, r, x);
pushup(u);
}
node query(int u, int l, int r)
{
if (l <= tr[u].l && tr[u].r <= r) {
return tr[u];
}
int mid = (tr[u].l + tr[u].r) >> 1;
pushdown(u);
if (r <= mid) {
pushup(u);
return query(u * 2, l, r);
}
if (l > mid) {
pushup(u);
return query(u * 2 + 1, l, r);
}
pushup(u);
node vl = query(u * 2, l, r);
node vr = query(u * 2 + 1, l, r);
node res;
pushup(res, vl, vr);
return res;
}
void solve()
{
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> ar[i];
}
build(1, 1, n);
while (q--) {
int op, a, b;
cin >> op >> a >> b;
if (op == 1) {
int x;
cin >> x;
modify(1, a, b, x);
} else {
node ans = query(1, a, b);
cout << ans.v[1] << '\n';
}
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
}