2024.9.13 CF1863 VP
A：\(n\) 个人一定都看了帖子当且仅当某时刻在线人数达 \(n\) 人。否则，若 \(a+s中'+'的个数 \ge n\)，则 \(n\) 个人有可能都看了帖子，否则不可能。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, a, q;
string s;
void solve()
{
cin >> n >> a >> q >> s, s = ' ' + s;
if(a == n)
{
cout << "YES" << endl;
return;
}
int nw = a, cnt = a;
for(int i=1;i<=q;i++)
{
if(s[i] == '+')
{
nw++;
cnt++;
}
else
{
nw--;
}
if(nw == n)
{
cout << "YES" << endl;
return;
}
}
if(cnt >= n)
{
cout << "MAYBE" << endl;
}
else
{
cout << "NO" << endl;
}
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}
B：结论：设 \(1\sim n\) 的排列 \(p'\) 满足 \(p'_{p_i}=i\)。则：\(Ans = \sum_{i=1}^{n-1}[p'_i>p'_{i+1}]\)。
证明：对于 \(1\le i<n\)，若 \(p'_i>p'_{i+1}\)，即 \(p\) 中 \(i\) 出现在 \(i+1\) 之后，则必须有一次操作选择 \(x = i+1\) 因为只有这一种选择可以交换 \(i,i+1\) 的相对位置。反之，若 \(p'_i<p'_{i+1}\)，则一定没必要做 \(i+1\) 操作。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, p[100005], revp[100005];
void solve()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> p[i];
revp[p[i]] = i;
}
int ans = 0;
for(int i=1;i<n;i++)
{
ans += (revp[i] > revp[i + 1]);
}
cout << ans << endl;
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}
C：简单模拟样例可知，每次操作相当于把 \(a_1\sim a_{n-1}\) 向后移一位，然后将 \(a_1\) 变为原数组的 \(\operatorname{mex}\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, k, a[100005], ans[100005];
void solve()
{
cin >> n >> k;
int d = 0;
for(int i=1;i<=n;i++)
{
cin >> a[i];
d ^= (a[i] ^ i);
}
k %= (n + 1);
if(k)
{
ans[k] = d;
}
for(int i=1;i<=n;i++)
{
ans[(i + k - 1) % (n + 1) + 1] = a[i];
}
for(int i=1;i<=n;i++)
{
cout << ans[i] << ' ';
}
cout << endl;
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}
D：
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, m;
char a[505][505], ans[505][505];
void solve()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin >> a[i][j];
ans[i][j] = '.';
}
}
bool lst = 0;
for(int i=1;i<n;i++)
{
bool fg = lst;
for(int j=1;j<=m;j++)
{
if(a[i][j] == 'U')
{
if(fg)
{
ans[i][j] = 'W';
ans[i + 1][j] = 'B';
}
else
{
ans[i][j] = 'B';
ans[i + 1][j] = 'W';
}
fg ^= 1;
}
}
if(fg)
{
cout << -1 << endl;
return;
}
lst = fg;
}
lst = 0;
for(int i=1;i<m;i++)
{
bool fg = lst;
for(int j=1;j<=n;j++)
{
if(a[j][i] == 'L')
{
if(fg)
{
ans[j][i] = 'W';
ans[j][i + 1] = 'B';
}
else
{
ans[j][i] = 'B';
ans[j][i + 1] = 'W';
}
fg ^= 1;
}
}
if(fg)
{
cout << -1 << endl;
return;
}
lst = fg;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout << ans[i][j];
}
cout << endl;
}
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}
E：
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define psbk push_back
#define fst first
#define scd second
#define umap unordered_map
#define pqueue priority_queue
#define vc vector
#define endl '\n'
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
constexpr int inf = 0x3f3f3f3f;
int n, m, k, h[200005], mnt[200005], ind[200005];
vc<int> e[200005];
multiset<int> st;
bool cmp(int x, int y)
{
return h[x] < h[y];
}
void srh(int x, int v)
{
if(mnt[x] >= v)
{
return;
}
st.erase(st.find(mnt[x]));
mnt[x] += (v - mnt[x] + k - 1) / k * k;
st.insert(mnt[x]);
for(int i : e[x])
{
srh(i, mnt[x]);
}
}
void solve()
{
cin >> n >> m >> k;
for(int i=1;i<=n;i++)
{
cin >> h[i];
mnt[i] = h[i];
e[i] = vc<int>();
ind[i] = 0;
}
for(int i=1;i<=m;i++)
{
int u, v;
cin >> u >> v;
e[u].psbk(v);
ind[v]++;
}
vc<int> ind0;
for(int i=1;i<=n;i++)
{
if(!ind[i])
{
ind0.psbk(i);
}
}
sort(all(ind0), cmp);
st = multiset<int>();
for(int i=1;i<=n;i++)
{
st.insert(mnt[i]);
for(int j : e[i])
{
if(mnt[j] < mnt[i])
{
mnt[j] += (mnt[i] - mnt[j] + k - 1) / k * k;
}
}
}
int ans = *st.rbegin() - *st.begin();
for(int i : ind0)
{
srh(i, mnt[i] + k);
ans = min(ans, *st.rbegin() - *st.begin());
}
cout << ans << endl;
}
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt;
cin >> tt;
while(tt--)
{
solve();
}
return 0;
}