2024.9.4 CF1534 模拟赛记录
A：当 \(n,m\) 确定后，整张表只有 \(2\) 种情况，分别检查是否符合原表。
点击查看代码
#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[55][55];
void solve()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin >> a[i][j];
}
}
for(int _=0;_<2;_++)
{
bool fg = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j] != '.' && (a[i][j] == 'R') != ((i + j) % 2 == _))
{
fg = 1;
break;
}
}
if(fg)
{
break;
}
}
if(fg)
{
continue;
}
cout << "YES" << endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout << ((i + j) % 2 == _ ? 'R' : 'W');
}
cout << endl;
}
return;
}
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：对于一次选择 \(i\) 的操作，当且仅当 \(a_i > a_{i-1}\) 且 \(a_i > a_{i+1}\) 会使丑陋值减小。于是对这些位置不断操作，直到 \(a_i=max(a_{i-1}, a_{i+1})\)。（\(a_0=a_{n+1}=0\)）
点击查看代码
#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[400005];
void solve()
{
cin >> n;
int ans = 0;
for(int i=1;i<=n;i++)
{
cin >> a[i];
ans += abs(a[i] - a[i - 1]);
}
ans += a[n];
a[n + 1] = 0;
for(int i=1;i<=n;i++)
{
if(a[i] > a[i - 1] && a[i] > a[i + 1])
{
ans -= a[i] - max(a[i - 1], a[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, b_1\sim b_n\)，再找到 \(b\) 的逆排列，即排列 \(b'\)，满足 \(b'_{b_i}=i\)。考虑一张 \(n\) 个点（编号 \(1\sim n\)）的图，对所有 \(1\le i\le n\)，连边 \((i, b'_{a_i})\)。此图由若干个环组成，每个环必须同时 换/不换，故答案为 \(2^{环的个数}\)。
点击查看代码
#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, mo = 1000000007;
int n, a[400005], b[400005], pa[400005], pb[400005];
bool vis[400005];
int qpw(int x, int y)
{
if(!y)
{
return 1;
}
int tmp = qpw(x, y / 2);
return tmp * tmp % mo * (y % 2 ? x : 1) % mo;
}
void solve()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
pa[a[i]] = i;
vis[i] = 0;
}
for(int i=1;i<=n;i++)
{
cin >> b[i];
pb[b[i]] = i;
}
int cnt = 0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
vis[i] = 1;
for(int j=pb[a[i]];j-i;j=pb[a[j]])
{
vis[j] = 1;
}
cnt++;
}
}
cout << qpw(2, cnt) << 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：先查询 \(1\)，将 \(2\sim n\) 根据到 \(1\) 距离的奇偶性分为两个集合（树一定是二分图！！），然后查询较小集合中的所有数，即可得知所有边。最差步数为 $1 + \left \lfloor \dfrac{n-1}{2} \right \rfloor = \left \lfloor \dfrac{n+1}{2} \right \rfloor = \left \lceil \dfrac{n}{2} \right \rceil $。
Trick：图论构造题，很多与二分图相关，特别是看到 \(\dfrac{n}{2}\) 时。
点击查看代码
#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 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, d[2005];
vc<int> v[2];
vc<pii> ans;
signed main()
{
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
cin >> n;
cout << "? 1" << endl;
for(int i=1;i<=n;i++)
{
cin >> d[i];
if(i != 1)
{
v[d[i] % 2].psbk(i);
}
}
if(v[0].size() < v[1].size())
{
for(int i=1;i<=n;i++)
{
if(d[i] == 1)
{
ans.psbk({1, i});
}
}
for(int i : v[0])
{
cout << "? " << i << endl;
for(int j=1;j<=n;j++)
{
cin >> d[j];
if(d[j] == 1)
{
ans.psbk({i, j});
}
}
}
}
else
{
for(int i : v[1])
{
cout << "? " << i << endl;
for(int j=1;j<=n;j++)
{
cin >> d[j];
if(d[j] == 1)
{
ans.psbk({i, j});
}
}
}
}
cout << '!' << endl;
for(pii i : ans)
{
cout << i.fst << ' ' << i.scd << endl;
}
return 0;
}