域名怎么创建网站,做公司网站有用吗,做网站多少钱 佛山,动漫制作专业专升本外场最速传说（划），半小时杀到了最后两个构造。最后两题非常值得玩味。
A.小红的字符串处理
签到题。读入三个字符，输出三个字符，相邻字符之间插入点即可。复杂度\(O(1)\)。
代码：
void solve()
{string s;cin cin s;char a = s[0], b = s[1], c = s[2];cout a "." b "." c endl;
}B.小红的菊花构造
继续签到题。按照题目要求构造即可，输出每行为\(k\)和一个不为\(k\)的其他节点即可。复杂度\(O(n)\)。
代码：
void solve()
{int n, k;cin n k;for ( int i = 1; i = n; i++ ){if ( i == k ) continue;else cout k " " i endl;}
}C/D.小红的Swap
手动把玩样例，不难联想到最朴素的交换\(a\)和\(b\)数值的解决方案：给出的额外字符只是作为一个暂存位置 ，我们通过不断利用额外暂存位调整原字符串的 0 和 1 使得其最终符合目标串。
我们记录一下 \(A\) 为当前为 \(0\) 目标为\(1\)的位置下标，\(B\) 为当前为 \(1\) 目标为 \(0\) 的位置下标，不难想到用 \(A_1, B_1, A_2, B_2 \dots A_m, B_m, A_1\) 的交替模式可以修复所有错位的字符位置，而由于额外暂存位有一个非 01 字符，我们最后要做一次还原。如果不能理解，请手动模拟这个策略。不难发现对于错位数 \(m\)，这个策略最优，只需要 \(2m + 1\) 次即可。复杂度\(O(n)\)。
代码：
void solve()
{int n;cin n;string s, t;cin s t;if ( s == t ) {cout 0 endl;return ;}vector int a, b;for ( int i = 0; i n; i++ ) {if ( s[i] != t[i] ) {if ( s[i] == '0' ) a.push_back(i + 1);else b.push_back(i + 1);}}int res = a.size();cout 2 * res + 1 endl;cout a[0] endl;for ( int i = 0; i res; i++ ){cout b[i] endl;if ( i + 1 res ) cout a[i + 1] endl;}cout a[0] endl;
}E.小红的分割线
数据量很小，所以直接可以丢掉大脑放弃思考，选择劲爆的循环枚举验证法。当然如果真的很纯粹的模拟肯定要出事，这里主要用到的是向量化线段，通过叉乘公式的结果正负判断点的位置在上方、共线还是下方。枚举两个点 \(i, j\) ，然后枚举剩下的所有点\(k\) ，通过判断\((p_j−p_i)×(p_k−p_i)\) 结果为正负或者为 0 决定点在上方/下方/共线。复杂度 \(O(n^2)\)。
代码：
void solve()
{int n;cin n;vector P point ( n + 1 );for ( int i = 0; i n; i++ ) cin point[i].first point[i].second;ll res = 0;for ( int i = 0; i n; i++ ){for ( int j = i + 1; j n; j++ ){ll dx = point[j].first - point[i].first;ll dy = point[j].second - point[i].second;ll lft = 0, rgt = 0;for ( int k = 0; k n; k++ ){if ( k == i || k == j ) continue;ll mul = dx * (point[k].second - point[i].second) - dy * (point[k].first - point[i].first);if ( mul 0 ) lft++;else if ( mul 0 ) rgt++;}if ( lft == rgt ) res++;}}cout res endl;
}F.小红的网格图构造 2.0
约定：为了方便理解，我们规定 F 和 G 两题都图都是 0-based。
题目大意理解完想到前几天做到的一个签到题，核心思路还是从棋盘染色的思路开始建立。
我们先从一个在空白地图最左上角的 \(2*2\) 网格开始考虑，如果要满足题目要求，让最右下角的格子为 \(1\) 就是最“偷懒”且满足要求的方式。所以，我们先把空白图里所有奇数行奇数列的位置填充为 1，然后如果没有满足规定的数量，再去填充对角线位置。如果这样的策略还是不能满足，那我们翻转目前图中所有的 0 和 1，直到满足条件。当然如果出现全部翻转但还没有满足，即可判断不能构造。
进一步的，我们考虑一张图最少需要 $ \lfloor n / 2 \rfloor * \lfloor m / 2 \rfloor$ 个 1，最多不超过 $ n * m - \lfloor n / 2 \rfloor * \lfloor m / 2 \rfloor $ 个 1 才能进行构造。理论上如果按照第一步构造策略，应该会有最多 $ \lfloor (n * m) / 2 \rfloor $的 1。如果给定的 \(k\) 超过了这个值，那么肯定会要进行第二步甚至第三步的处理。复杂度\(O(nm)\)。
代码：
void solve()
{ll n, m, k;cin n m k;if ( ( n / 2 ) * ( m / 2 ) k || n * m - ( n / 2 ) * ( m / 2 ) k ) {cout "No" endl;return ;}cout "Yes" endl;ll tot = n * m;ll lmt = ( n / 2 ) * ( m / 2 );vectorstring mp( n, string ( m, '0' ) );ll cnt = 0;bool large = ( k tot / 2 );ll need = large ? tot - k : k;for ( int i = 0; i n; i++ ){for ( int j = 0; j m; j++ ){if ( ( i1 ) ( j1 ) ){mp[i][j] = '1';cnt++;} }}for ( int i = 0; i n cnt need; i++ ){for ( int j = 0; j m cnt need; j++ ){if ( ( i1 ) != ( j1 ) ){mp[i][j] = '1';cnt++;} }}if ( large ){for ( int i = 0; i n; i++ ){for ( int j = 0; j m; j++ ){mp[i][j] = ( mp[i][j] == '0' ? '1' : '0' );}}}for ( auto i : mp ) cout i endl;
}G.小红的网格构造 1.0
延续上个题目的思维感觉，我们同样通过行列数奇偶的方式考虑构造策略。
首先显然，如果 $ n=1 $ 或者 $ m = 1$ 时压根不会出现一个 \(2*2\) 的区域。所以对于这种最简单的情况，直接 01 交替构造，最多能产生不超过 $ \lceil n * m / 2 \rceil $ 个连通块。如果 \(k\) 比这个值大，那么直接不可能构造。
接下来考虑一般的情况。还是先尽可能少构造含 1 的连通块，我们假设 $k = \lceil n / 2 \rceil \(，\)w = \lceil m / 2 \rceil \(，\)mid = h * w $。
如果$ 1 \leq k \leq mid $，把所有偶数行置为 1，可以得到 \(h\) 个连通块。接下来，给相邻两行之间加入一个 1 使得连通块数量-1，直到得到目标数量的连通块。
如果\(h \leq k \leq mid\)，依然把所有偶数行置为 1，可以得到 \(h\) 个连通块。接下来，给同一行的奇数列位置置为 0，可以把已经有的一个连通块切分成两个，使得连通块数量+1。
如果$mid \leq k \leq \lceil n*m / 2 \rceil $，先在直接考虑棋盘染色，把偶数行偶数列的位置置为 1，然后对角线加入 1，由于对角相邻不算连通，所以最大可以有 $ \lceil n * m / 2 \rceil $ 个连通块。复杂度 \(O(nm)\).
代码：
void solve()
{i32 n, m, k;cin n m k;vv32 mp( n, v32 ( m ) );auto print = [](){cout "Yes" endl;for ( auto u : mp ) {for (auto v : u ) cout v;cout endl;}};if ( n == 1 || m == 1 ){i32 len = n * m;if ( k ( len + 1 ) / 2 ){cout "No" endl;return ;}if ( n == 1 ) for ( int i = 0; i k; i++ ) mp[0][2 * i] = 1;else for ( int j = 0; j k; j++ ) mp[2 * j][0] = 1;print();return;}i32 h = ( n + 1 ) / 2, w = ( m + 1 ) / 2;i32 mid = h * w, mx = ( n * m + 1 ) / 2;if ( k == 0 || k mx ){cout "No" endl;return ;}if ( k = h ){for ( int i = 0; i n; i += 2 ){for ( int j = 0; j m; j++ ) mp[i][j] = 1;}int need = h - k;for ( int i = 0; i need; i++ ) mp[2 * i + 1][0] = 1;}else if ( k = mid ){int rem = k, row = 0;for ( int i = 0; i n; i += 2, row++ ){i32 lft = h - row - 1;i32 c = min ( w, rem - lft );rem -= c;for ( int j = 0; j m; j++ ) mp[i][j] = 1;for ( int j = 0; j c - 1; j++ ) mp[i][2 * j + 1] = 0;}}else {for ( int i = 0; i n; i += 2 ){for ( int j = 0; j m; j += 2 ) mp[i][j] = 1;}i32 need = k - mid;for ( int i = 1; i n need; i += 2 ){for ( int j = 1; j m need; j += 2 ) mp[i][j] = 1, need--;}}print();
}头文件
// LANG: C++
// Author: Hanzhi#include bits/stdc++.husing namespace std;using i32 = int;
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;using pii = pairint, int;
using pll = pairi64, i64;#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
#define v32 vector int
#define v64 vector i64
#define vv32 vector vector i32
#define vv64 vector vector i64 const int INF = 0x3f3f3f3f;
const i64 LINF = 4e18;
const int mod7 = 1e9 + 7;
const int mod9 = 1e9 + 9;
const int modn = 998244353;const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};void solve()
{}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int T = 1;// cin T;while (T--){solve();}return 0;
} 域名怎么创建网站做公司网站有用吗
域名怎么创建网站,做公司网站有用吗,做网站多少钱 佛山,动漫制作专业专升本外场最速传说（划），半小时杀到了最后两个构造。最后两题非常值得玩味。
A.小红的字符串处理
签到题。读入三个字符，输出三个字符，相邻字符之间插入点即可。复杂度\(O(1)\)。
代码：
void solve()
{string s;cin cin s;char a = s[0], b = s[1], c = s[2];cout a "." b "." c endl;
}B.小红的菊花构造
继续签到题。按照题目要求构造即可，输出每行为\(k\)和一个不为\(k\)的其他节点即可。复杂度\(O(n)\)。
代码：
void solve()
{int n, k;cin n k;for ( int i = 1; i = n; i++ ){if ( i == k ) continue;else cout k " " i endl;}
}C/D.小红的Swap
手动把玩样例，不难联想到最朴素的交换\(a\)和\(b\)数值的解决方案：给出的额外字符只是作为一个暂存位置 ，我们通过不断利用额外暂存位调整原字符串的 0 和 1 使得其最终符合目标串。
我们记录一下 \(A\) 为当前为 \(0\) 目标为\(1\)的位置下标，\(B\) 为当前为 \(1\) 目标为 \(0\) 的位置下标，不难想到用 \(A_1, B_1, A_2, B_2 \dots A_m, B_m, A_1\) 的交替模式可以修复所有错位的字符位置，而由于额外暂存位有一个非 01 字符，我们最后要做一次还原。如果不能理解，请手动模拟这个策略。不难发现对于错位数 \(m\)，这个策略最优，只需要 \(2m + 1\) 次即可。复杂度\(O(n)\)。
代码：
void solve()
{int n;cin n;string s, t;cin s t;if ( s == t ) {cout 0 endl;return ;}vector int a, b;for ( int i = 0; i n; i++ ) {if ( s[i] != t[i] ) {if ( s[i] == '0' ) a.push_back(i + 1);else b.push_back(i + 1);}}int res = a.size();cout 2 * res + 1 endl;cout a[0] endl;for ( int i = 0; i res; i++ ){cout b[i] endl;if ( i + 1 res ) cout a[i + 1] endl;}cout a[0] endl;
}E.小红的分割线
数据量很小，所以直接可以丢掉大脑放弃思考，选择劲爆的循环枚举验证法。当然如果真的很纯粹的模拟肯定要出事，这里主要用到的是向量化线段，通过叉乘公式的结果正负判断点的位置在上方、共线还是下方。枚举两个点 \(i, j\) ，然后枚举剩下的所有点\(k\) ，通过判断\((p_j−p_i)×(p_k−p_i)\) 结果为正负或者为 0 决定点在上方/下方/共线。复杂度 \(O(n^2)\)。
代码：
void solve()
{int n;cin n;vector P point ( n + 1 );for ( int i = 0; i n; i++ ) cin point[i].first point[i].second;ll res = 0;for ( int i = 0; i n; i++ ){for ( int j = i + 1; j n; j++ ){ll dx = point[j].first - point[i].first;ll dy = point[j].second - point[i].second;ll lft = 0, rgt = 0;for ( int k = 0; k n; k++ ){if ( k == i || k == j ) continue;ll mul = dx * (point[k].second - point[i].second) - dy * (point[k].first - point[i].first);if ( mul 0 ) lft++;else if ( mul 0 ) rgt++;}if ( lft == rgt ) res++;}}cout res endl;
}F.小红的网格图构造 2.0
约定：为了方便理解，我们规定 F 和 G 两题都图都是 0-based。
题目大意理解完想到前几天做到的一个签到题，核心思路还是从棋盘染色的思路开始建立。
我们先从一个在空白地图最左上角的 \(2*2\) 网格开始考虑，如果要满足题目要求，让最右下角的格子为 \(1\) 就是最“偷懒”且满足要求的方式。所以，我们先把空白图里所有奇数行奇数列的位置填充为 1，然后如果没有满足规定的数量，再去填充对角线位置。如果这样的策略还是不能满足，那我们翻转目前图中所有的 0 和 1，直到满足条件。当然如果出现全部翻转但还没有满足，即可判断不能构造。
进一步的，我们考虑一张图最少需要 $ \lfloor n / 2 \rfloor * \lfloor m / 2 \rfloor$ 个 1，最多不超过 $ n * m - \lfloor n / 2 \rfloor * \lfloor m / 2 \rfloor $ 个 1 才能进行构造。理论上如果按照第一步构造策略，应该会有最多 $ \lfloor (n * m) / 2 \rfloor $的 1。如果给定的 \(k\) 超过了这个值，那么肯定会要进行第二步甚至第三步的处理。复杂度\(O(nm)\)。
代码：
void solve()
{ll n, m, k;cin n m k;if ( ( n / 2 ) * ( m / 2 ) k || n * m - ( n / 2 ) * ( m / 2 ) k ) {cout "No" endl;return ;}cout "Yes" endl;ll tot = n * m;ll lmt = ( n / 2 ) * ( m / 2 );vectorstring mp( n, string ( m, '0' ) );ll cnt = 0;bool large = ( k tot / 2 );ll need = large ? tot - k : k;for ( int i = 0; i n; i++ ){for ( int j = 0; j m; j++ ){if ( ( i1 ) ( j1 ) ){mp[i][j] = '1';cnt++;} }}for ( int i = 0; i n cnt need; i++ ){for ( int j = 0; j m cnt need; j++ ){if ( ( i1 ) != ( j1 ) ){mp[i][j] = '1';cnt++;} }}if ( large ){for ( int i = 0; i n; i++ ){for ( int j = 0; j m; j++ ){mp[i][j] = ( mp[i][j] == '0' ? '1' : '0' );}}}for ( auto i : mp ) cout i endl;
}G.小红的网格构造 1.0
延续上个题目的思维感觉，我们同样通过行列数奇偶的方式考虑构造策略。
首先显然，如果 $ n=1 $ 或者 $ m = 1$ 时压根不会出现一个 \(2*2\) 的区域。所以对于这种最简单的情况，直接 01 交替构造，最多能产生不超过 $ \lceil n * m / 2 \rceil $ 个连通块。如果 \(k\) 比这个值大，那么直接不可能构造。
接下来考虑一般的情况。还是先尽可能少构造含 1 的连通块，我们假设 $k = \lceil n / 2 \rceil \(，\)w = \lceil m / 2 \rceil \(，\)mid = h * w $。
如果$ 1 \leq k \leq mid $，把所有偶数行置为 1，可以得到 \(h\) 个连通块。接下来，给相邻两行之间加入一个 1 使得连通块数量-1，直到得到目标数量的连通块。
如果\(h \leq k \leq mid\)，依然把所有偶数行置为 1，可以得到 \(h\) 个连通块。接下来，给同一行的奇数列位置置为 0，可以把已经有的一个连通块切分成两个，使得连通块数量+1。
如果$mid \leq k \leq \lceil n*m / 2 \rceil $，先在直接考虑棋盘染色，把偶数行偶数列的位置置为 1，然后对角线加入 1，由于对角相邻不算连通，所以最大可以有 $ \lceil n * m / 2 \rceil $ 个连通块。复杂度 \(O(nm)\).
代码：
void solve()
{i32 n, m, k;cin n m k;vv32 mp( n, v32 ( m ) );auto print = [](){cout "Yes" endl;for ( auto u : mp ) {for (auto v : u ) cout v;cout endl;}};if ( n == 1 || m == 1 ){i32 len = n * m;if ( k ( len + 1 ) / 2 ){cout "No" endl;return ;}if ( n == 1 ) for ( int i = 0; i k; i++ ) mp[0][2 * i] = 1;else for ( int j = 0; j k; j++ ) mp[2 * j][0] = 1;print();return;}i32 h = ( n + 1 ) / 2, w = ( m + 1 ) / 2;i32 mid = h * w, mx = ( n * m + 1 ) / 2;if ( k == 0 || k mx ){cout "No" endl;return ;}if ( k = h ){for ( int i = 0; i n; i += 2 ){for ( int j = 0; j m; j++ ) mp[i][j] = 1;}int need = h - k;for ( int i = 0; i need; i++ ) mp[2 * i + 1][0] = 1;}else if ( k = mid ){int rem = k, row = 0;for ( int i = 0; i n; i += 2, row++ ){i32 lft = h - row - 1;i32 c = min ( w, rem - lft );rem -= c;for ( int j = 0; j m; j++ ) mp[i][j] = 1;for ( int j = 0; j c - 1; j++ ) mp[i][2 * j + 1] = 0;}}else {for ( int i = 0; i n; i += 2 ){for ( int j = 0; j m; j += 2 ) mp[i][j] = 1;}i32 need = k - mid;for ( int i = 1; i n need; i += 2 ){for ( int j = 1; j m need; j += 2 ) mp[i][j] = 1, need--;}}print();
}头文件
// LANG: C++
// Author: Hanzhi#include bits/stdc++.husing namespace std;using i32 = int;
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;using pii = pairint, int;
using pll = pairi64, i64;#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
#define v32 vector int
#define v64 vector i64
#define vv32 vector vector i32
#define vv64 vector vector i64 const int INF = 0x3f3f3f3f;
const i64 LINF = 4e18;
const int mod7 = 1e9 + 7;
const int mod9 = 1e9 + 9;
const int modn = 998244353;const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};void solve()
{}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int T = 1;// cin T;while (T--){solve();}return 0;
}