标签：2024.12 int res long nx ny 周三 define
2024.12.4 周三
给定01串，操作：选择l,r，将s[r]放到s[l]前:s[l]s[l+1]...s[r-1]s[r]->s[r]s[l]s[l+1]...s[r-1],代价为r-l+1/区间长度。
问最小代价将01串由小到大排序。
给定2行'<''>'组成的字符串，起点[1,1],可选4个方向走一步，然后必须根据所在字符走一步。
问是否可到达[2,m]。
给定n,m。n个人在排队，你在n+1的位置。操作：你在i,与前面的j交换位置，代价a[j]+b[j+1]+..+b[i-1]。
问最小代价使你排到前m。
给定n,k,a数组。i:1~n卡牌数字i的数量为a[i]。你可以购买k张任意数字的卡牌。
问排列后可构成1~n的排列的连续子数组的最大数量。
------------------------独自思考分割线------------------------
-
这次的4道题算是比较顺，Q2 Q3都是20分钟左右，Q4近一个小时，主要是在对2种答案的讨论上费了时间，最后发现殊途同归。
A1.
两点：1.发现最终必须000011111，必要操作就是将后面的0提到1之前。
2.发现最小代价就是对最近的0操作，操作次数就是前面1的个数。即对每个0:res+=pre_1+1。
A2.
这里发现bfs可做就直接bfs了，当然也有其他巧妙的做法。
A3.
两点：1.发现本质就是在1~m选一个a[i],中间的话选min(a[i],b[i])最优。
2.操作就是m+1n：选min(a[i],b[i])，m1枚举作为终点的位置,倒序枚举可简化当其不为终点时取min(a[i],b[i])。
A4.
4点：1.贪心构造出最多排列的方式：1234123412 且数量取决于最少数量牌的个数
2.二分找出贪心购买后最少数量，枚举一次找到最少数量牌的个数。
3.设最少数量为k,其个数为cnt,，发现答案就是n*(k-1)+1+n-cnt;
4.二分的时候可能爆long long，开int128。(重测了一次,l开1e12确实有问题，r需要开到1e13,long long也没问题)
------------------------代码分割线------------------------
A1.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
string s;
cin >> s;
int pre = 0, res = 0;
for (auto v : s)
if (v == '0')
{
if (pre)
res += pre + 1;
}
else
pre++;
cout << res << endl;
}
A2.
#include <bits/stdc++.h>
#define int long long //
// #define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n = 2, m;
cin >> m;
vector<string> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] = " " + a[i];
}
vector<vector<int>> vis(n + 1, vector<int>(m + 1));
auto bfs = [&]()
{
queue<pair<int, int>> q;
vis[1][1] = 1;
q.push({1, 1});
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
while (q.size())
{
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i], ny = y + dy[i];
if (nx < 1 || nx > 2 || ny < 1 || ny > m || vis[nx][ny])
continue;
vis[nx][ny] = 1;
// bug2(nx, ny);
if (a[nx][ny] == '<')
ny--;
else
ny++;
if (nx < 1 || nx > 2 || ny < 1 || ny > m || vis[nx][ny])
continue;
// bug2(nx, ny);
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
};
bfs();
cout << (vis[n][m] ? "YES" : "NO") << endl;
}
A3.
#include <bits/stdc++.h>
#define int long long //
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
cin >> T;
while (T--)
_();
return 0;
}
void _()
{
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(n + 1), pre(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
{
cin >> b[i];
pre[i] = pre[i - 1] + b[i];
}
int s = 0, cnt = 0;
for (int i = m + 1; i <= n; i++)
s += min(a[i], b[i]);
int res = 1e18;
int has = 0;
for (int i = m; i; i--)
{
res = min(res, s + a[i]);
s += min(a[i], b[i]);
}
cout << res << endl;
}
A4.
#include <bits/stdc++.h>
// #define int long long //
#define int __int128
#define endl '\n' // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
int re()
{
int s = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while ('0' <= ch && ch <= '9')
s = s * 10 + ch - 48, ch = getchar();
return s * f;
}
void wr(int s)
{
if (s < 0)
putchar('-'), s = -s;
if (s > 9)
wr(s / 10);
putchar(s % 10 + 48);
}
void wr(int s, char ch) { wr(s), putchar(ch); }
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cout << fixed << setprecision(6);
int T = 1;
T = re();
while (T--)
_();
return 0;
}
void _()
{
int n, k;
n = re(), k = re();
vector<int> a(n);
for (int &x : a)
x = re();
auto ok = [&](int x)
{
int res = 0;
for (auto v : a)
if (x > v)
res += x - v;
return res <= k;
};
int l = 0, r = 1e13;
while (r - l - 1)
{
int mid = l + r >> 1;
if (ok(mid))
l = mid;
else
r = mid;
}
int kk = k;
int cnt = 0;
for (auto v : a)
if (l >= v)
kk -= l - v, cnt++;
cnt -= kk;
// bug2(l, cnt);
int res = n * (l - 1) + 1 + n - cnt;
// if (l * n == n + k)
// bug(1);
// res = n * (l - 1) + 1;
// if (!k)
// res = n * l - n - 1;
wr(res, '\n');
}
标签：2024.12,
int,
res,
long,
nx,
ny,
周三,
define
From： https://www.cnblogs.com/jkkk/p/18588214