2023河南省赛vp题解
目录
A题：
B题
C题
D题
E题
F题
G题
H题
I题
J题
K题
L题
A题：
1.思路：考虑暴力枚举和双hash，可以在O(n)做完。
2.代码实现：
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define mp make_pair
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
const ull bas = 133331;
const ll mod1 = 1000000033;
const ll mod2 = 1000000103;
typedef pair<int,int> hashv;
hashv pw[N],s1[N],s2[N];
hashv operator + (hashv a,hashv b)
{int c1 = a.fi + b.fi,c2 = a.se + b.se;if(c1 >= mod1) c1 -= mod1;if(c2 >= mod2) c2 -= mod2;return mp(c1,c2);
}
hashv operator - (hashv a,hashv b)
{int c1 = a.fi - b.fi,c2 = a.se - b.se;if(c1 < 0) c1 += mod1;if(c2 < 0) c2 += mod2;return mp(c1,c2);
}
hashv operator * (hashv a,hashv b)
{int c1 = (ll)a.fi * b.fi % mod1,c2 = (ll) a.se * b.se % mod2;return mp(c1,c2);
}
void init(string s)
{int n = sz(s);string t = s;reverse(all(t));t = " " + t;s = " " + s;hashv base = mp(10331,100313);pw[0] = mp(1,1);rep(i,1,n) {pw[i] = pw[i - 1] * base;s1[i] = s1[i - 1] * base + mp(s[i],s[i]);s2[i] = s2[i - 1] * base + mp(t[i],t[i]);
// pw[i] = pw[i - 1] * bas;}
}
hashv get1(int l,int r)
{return s1[r] - s1[l - 1] * pw[r - l + 1];
}
hashv get2(int l,int r)
{return s2[r] - s2[l - 1] * pw[r - l + 1];
}
void solve(){string s;cin >> s;init(s);int n = sz(s);s = " " + s;vector<int> vis(26);rep(i,1,n - 1) {if(vis[s[i] - 'a']) break;vis[s[i] - 'a'] = true; int len = n - i;if(get1(i + 1,n) == get2(1,len)) {cout << "HE" << endl;return;}}cout << "NaN" << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;cin >> T;while(T --) solve();
}B题
1.思路：暴力枚举+ST表，暴力枚举是调和级数的复杂度。
2.代码实现：
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define mp make_pair
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
#include <functional>
#include <numeric>namespace OY {template <typename _Tp, typename _Maximum>class STTable {std::vector<std::vector<_Tp>> m_sub;_Maximum m_maxi;int m_length;_Tp m_defaultValue;void _check() {// assert(m_maxi(m_defaultValue, m_defaultValue) == m_defaultValue);}public:STTable(int __n = 0, _Maximum __maxi = std::max<_Tp>, _Tp __defaultValue = _Tp()) : m_maxi(__maxi), m_defaultValue(__defaultValue) {_check();resize(__n);}template <typename _Iterator>STTable(_Iterator __first, _Iterator __last, _Maximum __maxi = std::max<_Tp>, _Tp __defaultValue = _Tp()) : m_maxi(__maxi), m_defaultValue(__defaultValue) {_check();reset(__first, __last);}void resize(int __n) {if (!__n) return;m_length = __n;int d = 32 - (m_length > 1 ? __builtin_clz(m_length - 1) : 32);m_sub.resize(d);m_sub[0].assign(__n, m_defaultValue);for (int i = 1; i < d; i++) {m_sub[i].clear();m_sub[i].reserve(m_length - (1 << i) + 1);for (int j = 0; j <= m_length - (1 << i); j++)m_sub[i].push_back(m_maxi(m_sub[i - 1][j], m_sub[i - 1][j + (1 << i - 1)]));}}template <typename _Iterator>void reset(_Iterator __first, _Iterator __last) {m_length = __last - __first;int d = 32 - (m_length > 1 ? __builtin_clz(m_length - 1) : 32);m_sub.resize(d);m_sub[0].assign(__first, __last);for (int i = 1; i < d; i++) {m_sub[i].clear();m_sub[i].reserve(m_length - (1 << i) + 1);for (int j = 0; j <= m_length - (1 << i); j++)m_sub[i].push_back(m_maxi(m_sub[i - 1][j], m_sub[i - 1][j + (1 << i - 1)]));}}void update(int __i, _Tp __val) {m_sub[0][__i] = __val;for (int i = 1; i < m_sub.size(); i++)for (int j = std::max(0, __i - (1 << i) + 1), end = std::min(__i, int(m_sub[i].size() - 1)); j <= end; j++)m_sub[i][j] = m_maxi(m_sub[i - 1][j], m_sub[i - 1][j + (1 << i - 1)]);}_Tp query(int __i) const {return m_sub[0][__i];}_Tp query(int __left, int __right) const {if (__left == __right) return m_sub[0][__left];int d = 31 - __builtin_clz(__right - __left);return m_maxi(m_sub[d][__left], m_sub[d][__right - (1 << d) + 1]);}_Tp queryAll() const {return query(0, m_length - 1);}};template <typename _Tp = int>STTable(int = 0, const _Tp &(*)(const _Tp &, const _Tp &) = std::max<_Tp>, _Tp = _Tp()) -> STTable<_Tp, const _Tp &(*)(const _Tp &, const _Tp &)>;template <typename _Tp = int>STTable(int, _Tp (*)(_Tp, _Tp), _Tp = _Tp()) -> STTable<_Tp, _Tp (*)(_Tp, _Tp)>;template <typename _Maximum, typename _Tp = std::decay_t<typename decltype(std::mem_fn(&_Maximum::operator()))::result_type>>STTable(int, _Maximum, _Tp = _Tp()) -> STTable<_Tp, _Maximum>;template <typename _Iterator, typename _Maximum, typename _Tp = typename std::iterator_traits<_Iterator>::value_type>STTable(_Iterator, _Iterator, _Maximum, _Tp = _Tp()) -> STTable<_Tp, _Maximum>;template <typename _Iterator, typename _Tp = typename std::iterator_traits<_Iterator>::value_type>STTable(_Iterator, _Iterator, const _Tp &(*)(const _Tp &, const _Tp &) = std::max<_Tp>, _Tp = _Tp()) -> STTable<_Tp, const _Tp &(*)(const _Tp &, const _Tp &)>;template <typename _Iterator, typename _Tp = typename std::iterator_traits<_Iterator>::value_type>STTable(_Iterator, _Iterator, _Tp (*)(_Tp, _Tp), _Tp = _Tp()) -> STTable<_Tp, _Tp (*)(_Tp, _Tp)>;
}
int n;
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T> inline bool read(T &x) {x = 0; char c = nc(); bool f(0);while (c < '0' || c > '9') { if (c == EOF) return false; f = c == '-', c = nc(); }while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = nc(); if (f) x = -x; return true;
}
int a[N];
void solve(){read(n);rep(i,0,n-1) read(a[i]);auto mymax = [](int x, int y) {return x > y ? x : y;};OY::STTable st_max(a , a + n, mymax);OY::STTable st_min(a , a + n, std::min);int ans = 1;for(int i = 1;i < n;i ++) {bool ok = true;for(int j = i;j <= n;j += i) {if(j == n) break;int nxt = min(j + i,n);int v1 = st_max.query(j - i,j - 1);int v2 = st_min.query(j,nxt - 1);if(v1 > v2) {ok = false;break;}}if(ok) ans ++;}cout << ans << endl;
}
int main()
{ios::sync_with_stdio(false);cout.tie(0);int T = 1;
// cin >> T;while(T --) solve();
}C题
1.思路：考虑验证这个序列，如果出现两个相同的连续超过40的串，那么就认为这个串不随机就行了，错误率就是，实现就是直接kmp搞一下next数组找个最大的看是否大于等于40即可。
2.代码实现：
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
int a[N],nxt[N];
void get_next(string s)
{int i = 0,j = -1;nxt[0] = -1;int n = s.size();while(i < n) {if(j == -1 || s[i] == s[j]) {i++, j++;nxt[i] = j;}else j = nxt[j];}
}
void solve(){string s,t;s = "";while(cin >> t) s += t; get_next(s);int n = sz(s);int mx = 0;for(int i = 1;i <= n;i ++) mx = max(mx,nxt[i]);if(mx >= 40) cout << "NO" << endl;else cout << "YES" << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;
// cin >> T;while(T --) solve();
}D题 不会
E题
1.思路：考虑dp[i][j][k]表示第i行第j列修改了k个问号的最大值是多少，因为数组内存开不了这么大，因此我们考虑优化空间，我们发现这一行的状态只跟这一行和上一行有关，因此可以滚动dp优化空间。
2.代码实现：
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define mp make_pair
using namespace std;
using ll = long long;
const int N = 501;
int n;
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T> inline bool read(T &x) {x = 0; char c = nc(); bool f(0);while (c < '0' || c > '9') { if (c == EOF) return false; f = c == '-', c = nc(); }while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = nc(); if (f) x = -x; return true;
}
int a[N];
string s[N];
void solve(){int m,x;cin >> n >> m >> x;rep(i,1,n) {cin >> s[i];s[i] = " " + s[i];}vector<vector<int>> odp(m + 1,vector<int>(x + 1));odp[1][0] = (s[1][1] == '1');if(s[1][1] == '?' && x >= 1) odp[1][1] = 1;rep(j,1,m) {rep(k,0,x) {int v = s[1][j] == '1';odp[j][k] = max(odp[j - 1][k] + v,odp[j][k]);if(s[1][j] == '?' && k + 1 <= x) odp[j][k + 1] = max(odp[j - 1][k] + 1,odp[j][k + 1]);}}rep(i,2,n) {vector<vector<int>> ndp(m + 1,vector<int>(x + 1));rep(j,1,m) {vector<int> dp(x + 1,0);rep(k,0,x) {int v = s[i][j] == '1';dp[k] = max(ndp[j - 1][k] + v,dp[k]);if(s[i][j] == '?' && k + 1 <= x) dp[k + 1] = max(dp[k + 1],ndp[j - 1][k] + 1);ndp[j][k] = max(ndp[j][k],odp[j][k] + v);if(s[i][j] == '?' && k + 1 <= x) ndp[j][k + 1] = max(ndp[j][k + 1],odp[j][k] + 1);}rep(k,0,x) ndp[j][k] = max(ndp[j][k],dp[k]);}swap(ndp,odp);}int ans = 0;rep(i,0,x) ans = max(ans,odp[m][i]);cout << ans << '\n';
}
int main()
{ios::sync_with_stdio(false);cout.tie(0),cin.tie(0);int T = 1;cin >> T;while(T --) solve();
}F题
1.思路：因为是任意i，j相差取min和max，因此考虑直接排序选k个中最大和最小的一直取min就是答案，考虑用multiset维护即可。
2.代码实现
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define mp make_pair
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
int n;
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T> inline bool read(T &x) {x = 0; char c = nc(); bool f(0);while (c < '0' || c > '9') { if (c == EOF) return false; f = c == '-', c = nc(); }while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = nc(); if (f) x = -x; return true;
}
int a[N];
void solve(){int n,k;cin >> n >> k;rep(i,1,n) cin >> a[i];sort(a + 1,a + 1 + n);multiset<int> mt;ll ans = 2e18;rep(i,1,n) {if(i > 1) mt.insert(a[i] - a[i - 1]);if(i > k) mt.erase(mt.find(a[i - k + 1] - a[i - k]));if(i >= k) {int mx = a[i] - a[i - k + 1];int mi = *mt.begin();
// cout << i << ',' << mi << ',' << mx << endl;ans = min(ans,1ll * mi * mx);}}cout << ans << endl;
}
int main()
{ios::sync_with_stdio(false);cout.tie(0),cin.tie(0);int T = 1;
// cin >> T;while(T --) solve();
}G题
1.思路：模拟题，考虑特判1的情况就可以了。
2.代码实现：
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define mp make_pair
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
int n;
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T> inline bool read(T &x) {x = 0; char c = nc(); bool f(0);while (c < '0' || c > '9') { if (c == EOF) return false; f = c == '-', c = nc(); }while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = nc(); if (f) x = -x; return true;
}
int a[N];
string ans[14];
string num[15][100];
string unum[12][100];
void init2()
{unum[0][1] = ".....";unum[0][2] = "00000";unum[0][3] = "0...0";unum[0][4] = "0...0";unum[0][5] = "0...0";unum[0][6] = "00000";unum[0][7] = ".....";unum[0][8] = ".....";unum[0][9] = ".....";unum[0][10] = ".....";unum[1][1] = ".....";unum[1][2] = "....1";unum[1][3] = "....1";unum[1][4] = "....1";unum[1][5] = "....1";unum[1][6] = "....1";unum[1][7] = ".....";unum[1][8] = ".....";unum[1][9] = ".....";unum[1][10] = ".....";unum[2][1] = ".....";unum[2][2] = "22222";unum[2][3] = "....2";unum[2][4] = "22222";unum[2][5] = "2....";unum[2][6] = "22222";unum[2][7] = ".....";unum[2][8] = ".....";unum[2][9] = ".....";unum[2][10] = ".....";unum[3][1] = ".....";unum[3][2] = "33333";unum[3][3] = "....3";unum[3][4] = "33333";unum[3][5] = "....3";unum[3][6] = "33333";unum[3][7] = ".....";unum[3][8] = ".....";unum[3][9] = ".....";unum[3][10] = ".....";unum[4][1] = ".....";unum[4][2] = "4...4";unum[4][3] = "4...4";unum[4][4] = "44444";unum[4][5] = "....4";unum[4][6] = "....4";unum[4][7] = ".....";unum[4][8] = ".....";unum[4][9] = ".....";unum[4][10] = ".....";unum[5][1] = ".....";unum[5][2] = "55555";unum[5][3] = "5....";unum[5][4] = "55555";unum[5][5] = "....5";unum[5][6] = "55555";unum[5][7] = ".....";unum[5][8] = ".....";unum[5][9] = ".....";unum[5][10] = ".....";unum[6][1] = ".....";unum[6][2] = "66666";unum[6][3] = "6....";unum[6][4] = "66666";unum[6][5] = "6...6";unum[6][6] = "66666";unum[6][7] = ".....";unum[6][8] = ".....";unum[6][9] = ".....";unum[6][10] = ".....";unum[7][1] = ".....";unum[7][2] = "77777";unum[7][3] = "....7";unum[7][4] = "....7";unum[7][5] = "....7";unum[7][6] = "....7";unum[7][7] = ".....";unum[7][8] = ".....";unum[7][9] = ".....";unum[7][10] = ".....";unum[8][1] = ".....";unum[8][2] = "88888";unum[8][3] = "8...8";unum[8][4] = "88888";unum[8][5] = "8...8";unum[8][6] = "88888";unum[8][7] = ".....";unum[8][8] = ".....";unum[8][9] = ".....";unum[8][10] = ".....";unum[9][1] = ".....";unum[9][2] = "99999";unum[9][3] = "9...9";unum[9][4] = "99999";unum[9][5] = "....9";unum[9][6] = "99999";unum[9][7] = ".....";unum[9][8] = ".....";unum[9][9] = ".....";unum[9][10] = ".....";
}
//处理下面的数字
void init()
{num[0][1] = ".......";num[0][2] = ".......";num[0][3] = "0000000";num[0][4] = "0.....0";num[0][5] = "0.....0";num[0][6] = "0.....0";num[0][7] = "0.....0";num[0][8] = "0.....0";num[0][9] = "0000000";num[0][10] = ".......";num[1][1] = ".......";num[1][2] = ".......";num[1][3] = "......1";num[1][4] = "......1";num[1][5] = "......1";num[1][6] = "......1";num[1][7] = "......1";num[1][8] = "......1";num[1][9] = "......1";num[1][10] = ".......";num[2][1] = ".......";num[2][2] = ".......";num[2][3] = "2222222";num[2][4] = "......2";num[2][5] = "......2";num[2][6] = "2222222";num[2][7] = "2......";num[2][8] = "2......";num[2][9] = "2222222";num[2][10] = ".......";num[3][1] = ".......";num[3][2] = ".......";num[3][3] = "3333333";num[3][4] = "......3";num[3][5] = "......3";num[3][6] = "3333333";num[3][7] = "......3";num[3][8] = "......3";num[3][9] = "3333333";num[3][10] = ".......";num[4][1] = ".......";num[4][2] = ".......";num[4][3] = "4.....4";num[4][4] = "4.....4";num[4][5] = "4.....4";num[4][6] = "4444444";num[4][7] = "......4";num[4][8] = "......4";num[4][9] = "......4";num[4][10] = ".......";num[5][1] = ".......";num[5][2] = ".......";num[5][3] = "5555555";num[5][4] = "5......";num[5][5] = "5......";num[5][6] = "5555555";num[5][7] = "......5";num[5][8] = "......5";num[5][9] = "5555555";num[5][10] = ".......";num[6][1] = ".......";num[6][2] = ".......";num[6][3] = "6666666";num[6][4] = "6......";num[6][5] = "6......";num[6][6] = "6666666";num[6][7] = "6.....6";num[6][8] = "6.....6";num[6][9] = "6666666";num[6][10] = ".......";num[7][1] = ".......";num[7][2] = ".......";num[7][3] = "7777777";num[7][4] = "......7";num[7][5] = "......7";num[7][6] = "......7";num[7][7] = "......7";num[7][8] = "......7";num[7][9] = "......7";num[7][10] = ".......";num[8][1] = ".......";num[8][2] = ".......";num[8][3] = "8888888";num[8][4] = "8.....8";num[8][5] = "8.....8";num[8][6] = "8888888";num[8][7] = "8.....8";num[8][8] = "8.....8";num[8][9] = "8888888";num[8][10] = ".......";num[9][1] = ".......";num[9][2] = ".......";num[9][3] = "9999999";num[9][4] = "9.....9";num[9][5] = "9.....9";num[9][6] = "9999999";num[9][7] = "......9";num[9][8] = "......9";num[9][9] = "9999999";num[9][10] = ".......";//Inum[10][1] = ".......";num[10][2] = ".......";num[10][3] = "IIIIIII";num[10][4] = "...I...";num[10][5] = "...I...";num[10][6] = "...I...";num[10][7] = "...I...";num[10][8] = "...I...";num[10][9] = "IIIIIII";num[10][10] = ".......";//Nnum[11][1] = ".......";num[11][2] = ".......";num[11][3] = "N.....N";num[11][4] = "NN....N";num[11][5] = "N.N...N";num[11][6] = "N..N..N";num[11][7] = "N...N.N";num[11][8] = "N....NN";num[11][9] = "N.....N";num[11][10] = ".......";//Fnum[12][1] = ".......";num[12][2] = ".......";num[12][3] = "FFFFFFF";num[12][4] = "F......";num[12][5] = "F......";num[12][6] = "FFFFFFF";num[12][7] = "F......";num[12][8] = "F......";num[12][9] = "F......";num[12][10] = ".......";//=num[13][1] = ".......";num[13][2] = ".......";num[13][3] = ".......";num[13][4] = ".......";num[13][5] = "=======";num[13][6] = ".......";num[13][7] = "=======";num[13][8] = ".......";num[13][9] = ".......";num[13][10] = ".......";}
void add1(int idx)
{rep(i,1,10) ans[i] += '.';rep(i,1,10) ans[i] += num[idx][i];
}
void add2(int idx)
{rep(i,1,10) ans[i] += '.';rep(i,1,10) ans[i] += unum[idx][i];
}
void dispose1(ll x)
{vector<int> nums;while(x) {nums.pb(x % 10);x /= 10;}reverse(all(nums));for(int i = 0;i < sz(nums);i ++) add1(nums[i]);
}
void dispose2(ll x)
{vector<int> nums;while(x) {nums.pb(x % 10);x /= 10;}reverse(all(nums));for(int i = 0;i < sz(nums);i ++) add2(nums[i]);add1(13);
}
void dispose3(ll x,bool lim)
{if(lim) {add1(10);add1(11);add1(12);}else dispose1(x);
}
void dispose4()
{rep(i,1,10) ans[i] += '.';
}
void solve(){rep(i,1,10) ans[i].clear();string s;ll x = 0,y = 0;cin >> s;int vis = 0;for(int i = 0;i < sz(s);i ++) {if(s[i] == '^' || s[i] == '{' || s[i] == '}') {vis ++;continue;}if(vis == 0) x = x * 10 + s[i] - '0';else y = y * 10 + s[i] - '0';}bool lim = false;dispose1(x);dispose2(y);ll tv = 1;rep(i,1,y) {if(x == 1) break;if((__int128)tv * x > 1e18) {lim = true;break;}tv *= x;}dispose3(tv,lim);dispose4();rep(i,1,10) cout << ans[i] << '\n';
}
int main()
{ios::sync_with_stdio(false);cout.tie(0),cin.tie(0);init();init2();int T = 1;cin >> T;while(T --) solve();
}H题
1.思路：找的规律
2.代码实现：
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define mp make_pair
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
int n;
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T> inline bool read(T &x) {x = 0; char c = nc(); bool f(0);while (c < '0' || c > '9') { if (c == EOF) return false; f = c == '-', c = nc(); }while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = nc(); if (f) x = -x; return true;
}
int a[N];
void solve(){int n,k;cin >> n >> k;cout << n - min(2 * n,k - 1) / 2 << ' ' << n + (min(2 * n,k - 1) + 1) / 2 << endl;
}
int main()
{ios::sync_with_stdio(false);cout.tie(0),cin.tie(0);int T = 1;cin >> T;while(T --) solve();
}I题
1.思路：考虑x序列和y序列的特殊性，我们容易手搓出来最多每个格子只会被cover两次，因此我们考虑用扫描线处理这个问题，考虑答案求解，我们可以反着求答案用总数减去非纯色矩阵即可。考虑非纯色矩阵的构成，说明这个矩阵中有点被覆盖了，我们直接减去被矩形边覆盖的点数，问题转变为我们直接减去交点数即可，因此用树状数组维护一下单点修改区间查询即可。
2.代码实现：
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define endl '\n'
using namespace std;
using ll = long long;
const int N = 1e6 + 10;
pii a[N];
template <typename T>
struct Fenwick {const int n;std::vector<T> a;Fenwick (int n) : n(n), a(n + 1) {}void add(int pos, int x) {for (int i = pos; i <= n; i += i & -i) {a[i] += x;}}T query(int x) {T res = 0;for (int i = x; i; i -= i & -i) {res += a[i];}return res;}T query(int l, int r) {if (l == 0 || l > r) {return 0;}return query(r) - query(l - 1);}
};
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T> inline bool read(T &x) {x = 0; char c = nc(); bool f(0);while (c < '0' || c > '9') { if (c == EOF) return false; f = c == '-', c = nc(); }while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = nc(); if (f) x = -x; return true;
}
void solve(){int n;read(n);rep(i,1,n) {int x1,y1,x2,y2;read(x1),read(y1);read(x2),read(y2);a[y1] = {x1,x2};a[y2] = {-x1,-x2};}Fenwick<int> fen(2 * n);ll ans = 0;rep(i,1,2*n) {int L = a[i].fi,R = a[i].se;if(L < 0) {L = -L,R = -R;fen.add(L,-1);fen.add(R,-1);}else {fen.add(L,1);fen.add(R,1);}ans = ans + 2 * n - (R - L + 1) - fen.query(2 * n) + fen.query(L,R);}cout << ans << endl;
}
int main()
{int T = 1;
// cin >> T;while(T --) solve();
}J题 不会
K题
1.思路：考虑2为质数这个特性，我们尽可能把数差为2的构造，发现无论计数情况和偶数情况我们都能够剩下2和n-1这两个数，对于2这个数我们可以插入到4和6中间，n-1这个数我们可以插入到n-3和n-5中间去。小于10的话写个dfs就行了。
2.代码实现：
#include<bits/stdc++.h>
#define sz(x) (int) x.size()
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define pii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define mp make_pair
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
inline char nc() {static char buf[1000000], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T> inline bool read(T &x) {x = 0; char c = nc(); bool f(0);while (c < '0' || c > '9') { if (c == EOF) return false; f = c == '-', c = nc(); }while (c >= '0' && c <= '9') x = x * 10 + (c ^ 48), c = nc(); if (f) x = -x; return true;
}
struct Primes {bitset <N> st;int cnt,primes[N],idx[N],n;Primes(int n = N - 1) {this->n = n;init(n);}void init(int n) {st[0] = st[1] = 1;for(int i = 2;i <= n;i ++) {if(!st[i]) {primes[++ cnt] = i;idx[i] = cnt;}for(int j = 1;primes[j] <= n / i;j ++) {st.flip(primes[j] * i);if(i % primes[j] == 0) break;}}}//判断x是否是质数 bool isPrime(int x) {assert(x <= n);return !st[x];}//求解x在质数表是第几个 bool atIndex(int x) {assert(!st[x]);assert(x <= n);return idx[x];}
}pr(1e5);
int n,vis[11],ans[N];
inline void dfs(int f)
{if(f == n + 1) {if(pr.isPrime(abs(ans[f - 1] - ans[1]))) {rep(i,1,n) cout << ans[i] << ' ';exit(0);}return ;}rep(i,1,n) {if(!vis[i]) {if(f > 1 && !pr.isPrime(abs(i - ans[f - 1]))) continue;vis[i] = true;ans[f] = i;dfs(f + 1);vis[i] = false;}}
}
void solve(){cin >> n;//10! = 40320*9*10if(n <= 10) {dfs(1);cout << -1 << endl;return;}if(n & 1) {int cnt = 0;for(int i = 1;i <= n;i += 2) ans[++ cnt] = i;for(int i = n - 3;i >= 4;i -= 2) ans[++ cnt] = i;//剩下n-1和2int ok1 = false,ok2 = false;rep(i,1,cnt - 1) {bool same = false;if(!ok1 && pr.isPrime(abs(n - 1 - ans[i])) && pr.isPrime(abs(n - 1 - ans[i + 1]))) {ok1 = i;same = true;}if(!same && !ok2 && pr.isPrime(abs(2 - ans[i])) && pr.isPrime(abs(2 - ans[i + 1]))) {ok2 = i;}}bool same = false;if(!ok1 && pr.isPrime(abs(n - 1 - ans[cnt])) && pr.isPrime(abs(n - 1 - ans[1]))) {ok2 = n;same = true;}if(!same && !ok2 && pr.isPrime(abs(2 - ans[cnt])) && pr.isPrime(abs(2 - ans[1]))) {ok2 = n;}assert(ok1 != ok2);rep(i,1,cnt) {cout << ans[i] << ' ';if(i == ok1) cout << n - 1 << ' ';if(i == ok2) cout << 2 << ' ';}cout << endl;}else {int cnt = 0;for(int i = 1;i <= n - 3;i += 2) ans[++ cnt] = i;for(int i = n;i >= 4;i -= 2) ans[++ cnt] = i;//剩下n-1和2int ok1 = false,ok2 = false;rep(i,1,cnt - 1) {bool same = false;if(!ok1 && pr.isPrime(abs(n - 1 - ans[i])) && pr.isPrime(abs(n - 1 - ans[i + 1]))) {ok1 = i;same = true;}if(!same && !ok2 && pr.isPrime(abs(2 - ans[i])) && pr.isPrime(abs(2 - ans[i + 1]))) {ok2 = i;}}bool same = false;if(!ok1 && pr.isPrime(abs(n - 1 - ans[cnt])) && pr.isPrime(abs(n - 1 - ans[1]))) {ok2 = n;same = true;}if(!same && !ok2 && pr.isPrime(abs(2 - ans[cnt])) && pr.isPrime(abs(2 - ans[1]))) {ok2 = n;}assert(ok1 != ok2);rep(i,1,cnt) {cout << ans[i] << ' ';if(i == ok1) cout << n - 1 << ' ';if(i == ok2) cout << 2 << ' ';}cout << endl;}
}
int main()
{ios::sync_with_stdio(false);cout.tie(0),cin.tie(0);int T = 1;
// cin >> T;while(T --) solve();
}L题 不会
相关文章：
2023河南省赛vp题解
目录 A题： B题 C题 D题 E题 F题 G题 H题 I题 J题 K题 L题 A题： 1.思路：考虑暴力枚举和双hash，可以在O(n)做完。 2.代码实现： #include<bits/stdc.h> #define sz(x) (int) x.size() #define rep(i,z,…...
港科夜闻｜香港科大与香港资管通有限公司签署校企合作备忘录,成立校企合作基金促科研成果落地...
关注并星标 每周阅读港科夜闻 建立新视野 开启新思维 1、香港科大与香港资管通有限公司签署校企合作备忘录，成立校企合作基金促科研成果落地。“港科资管通领航基金”28日在香港成立，将致力于推动高校科研成果转化，助力香港国际创科中心建设。…...
Neo4j 笔记
启动命令 neo4j console Cypher句法由四个不同的部分组成， 每一部分都有一个特殊的规则： start——查找图形中的起始节点。 match——匹配图形模式， 可以定位感兴趣数据的子图形。 where——基于某些标准过滤数据。 return——返回感兴趣的…...
数据库基础应用——概念模型
1、实体(Entity) 客观存在并可相互区别的事物称为实体。实体可以是人、物、对象、概念、事物本身、事物之间的联系。（例如一名员工、一个部门、一辆汽车等等。） 2、属性(Attributre) 实体所具有的每个特性称为属性。（例如：员工由员…...
【学姐面试宝典】前端基础篇Ⅴ——JS深浅拷贝、箭头函数、事件监听等
前言 博主主页👉🏻蜡笔雏田学代码 专栏链接👉🏻【前端面试专栏】 今天继续学习前端面试题相关的知识！ 感兴趣的小伙伴一起来看看吧~🤞 文章目录 什么是事件监听事件委托以及冒泡原理介绍一下 promise&#…...
最新研究，GPT-4暴露了缺点！无法完全理解语言歧义！
夕小瑶科技说 原创作者 |智商掉了一地、Python自然语言推理（Natural Language Inference，NLI）是自然语言处理中一项重要任务，其目标是根据给定的前提和假设，来判断假设是否可以从前提中推断出来。然而，由于…...
商业数据挖掘-第一章-数据探索式分析-1
数据探索最基本的步骤之一是获取对数据的基本描述，通过获取对数据的基本描述从而获得对数据的基本感觉。下面的一些方法用于帮助我们认识数据。 我们使用波士顿房价预测的数据集进行实验 DataFrame.describe()：查看数据的基本分布，具体是对每列数据进行统计，统计值包含频…...
MybatisPlus是否防止SQL注入？
问 如果我希望使用mybatisplus同时也进行防SQL注入操作，应该怎么处理？ 答 如果你想在使用 MyBatis-Plus 进行数据库操作的同时也进行防 SQL 注入处理，可以采用以下两种方式： 使用 #{} 占位符：在 QueryWrapper 或 Up…...
5月第1周榜单丨飞瓜数据B站UP主排行榜（哔哩哔哩平台）发布！
飞瓜轻数发布2023年5月1日-5月7日飞瓜数据UP主排行榜（B站平台），通过充电数、涨粉数、成长指数三个维度来体现UP主账号成长的情况，为用户提供B站号综合价值的数据参考，根据UP主成长情况用户能够快速找到运营能力强的B站…...
数据的插入删除和更新
在之前我们就已经学过了数据的插入，在这里再进行一点内容的补充： 在insert语句中，value子句中参数的顺序与表中各个列的顺序是一一对应的。 mysql> insert into first_table(second_column, first_column) values(aaa, 1); Query OK, 1 r…...
C# byte[] 与 int 类型互转
本文讲述在C#中,怎样使用 BitConverter 类将字节数组转换为 int 然后又转换回字节数组的过程。 为什么需要这样呢？这是因为，比如说,在从网络读取字节之后，可能需要将字节转换为内置数据类型。 除了示例中的 ToInt32(Byte[], Int32) 方法之外…...
MySQL---多表联合查询（上）（多表关系、外键约束、学生成绩多表关系、交叉连接查询）
1. 多表关系 MySQL多表之间的关系可以概括为： 一对一： 比如：一个学生只有一张身份证；一张身份证只能对应一学生。 实现原则：在任一表中添加唯一外键，指向另一方主键，确保一对一关系。 一般一对…...
【iOS】—— RunLoop线程常驻和线程保活
文章目录 没有线程常驻会怎么样？ 线程常驻线程保活 没有线程常驻会怎么样？ 我们一般写一个子线程，子线程执行完分配的任务后就会自动销毁，比如下面这个情况： 我们先重写一下NSThread里面的dealloc方法，打印…...
Springcloud--docker快速入门
认识docker docker相关操作 1.初识Docker 1.1.什么是Docker 微服务虽然具备各种各样的优势，但服务的拆分通用给部署带来了很大的麻烦。 分布式系统中，依赖的组件非常多，不同组件之间部署时往往会产生一些冲突。在数百上千台服务中重复部署…...
基于AT89C51单片机的电子计数器设计与仿真
点击链接获取Keil源码与Project Backups仿真图： https://download.csdn.net/download/qq_64505944/87770826 源码获取 主要内容： 设计一个电子计时器，数码管初始显示值为“00”，每隔1s电子秒表加1；秒计数到60时清0&a…...
IT程序员如何面对35岁大龄问题？我从公司老板的角度聊聊
很多从事IT行业的人一想到35岁就很焦虑，担心自己被公司裁员后找不到工作。同时还有家庭责任加身，担心中年失业后晚年生活。作为一位公司老板，我想从我的角度谈一下这个问题。 首先，我本质上不介意我的员工年龄，无论是…...
【计算机专业漫谈】【计算机系统基础学习笔记】W2-2-2 模运算系统和补码表示
利用空档期时间学习一下计算机系统基础，以前对这些知识只停留在应试层面，今天终于能详细理解一下了。参考课程为南京大学袁春风老师的计算机系统基础MOOC，参考书籍也是袁老师的教材，这是我的听课自查资料整理后的笔记 补码表示法…...
vue概述
vue2和vue3的区别 vue2和vue3区别 NOvue2vue31 optinos Api写法 比较分散 Compostiton Api 代码集 2重写数序双向绑定通过Object.defineProperty（）实现 基于Proxy实现 对数组有了更好的支持 3Fragments 1，在template中只能一个div 2…...
SpringCloud-OpenFeign案例实战
关于Spring Cloud Open Feign的介绍可以参考这两篇博客 OpenFeign服务接口调用 使用Feign作为服务消费者 本博客参考gitee开源项目代码，结合自己的理解，记录下微服务场景下的使用。Talk is cheap. Show me the code！ 一、项目结构 这里使用…...
ACM - 数学 - 提高（还没学多少）
ACM - 数学 练习题 一、数论1、分解质因数 ：AcWing 197. 阶乘分解2、求约数个数（1）AcWing 1294. 樱花 （求 n！约数个数之和）（2）AcWing 198. 反素数 （求 1 ~ N 中约数最多的…...
JavaScript class和继承的原理
（对于不屈不挠的人来说，没有失败这回事。——俾斯麦） class 相关链接 MDN链接 有关类的详细描述 关于构造函数，原型和原型链的说明 类的概述 类是用于创建对象的模板。他们用代码封装数据以处理该数据。JS 中的类建立在原型上…...
Playwright-python 自动化测试【Anaconda】环境配置
第一步：Anaconda的安装 安装Anaconda的好处，比prenv网速快，并且拥有独立的python环境，再也不用烦恼用哪个python好了。 Anaconda的下载页参见官网下载，Linux、Mac、Windows均支持。 https://mirrors.tuna.tsinghua.ed…...
攻防世界-web-simple js
题目描述：小宁发现了一个网页，但却一直输不对密码。(Flag格式为 Cyberpeace{xxxxxxxxx} ) 打开链接： 然后我们会发现不管我们输入什么密码，发现是都是这样的报错 1. 先用bp抓包看看，可以抓到这样的一串js脚本 看不懂…...
【SpringCloud】初始微服务
目录 一、单体架构 1、概念 2、优点 3、缺点 二、分布式架构 1、概念 2、优点 3、缺点 三、微服务 1、概念 2、优点 3、缺点 四、微服务技术对比 五、SpringCloud 六、服务拆分 1、注意事项 2、服务远程调用 一、单体架构 1、概念 业务的所有功能都集中到一个…...
均摊时间复杂度
均摊时间复杂度，它对应的分析方法，摊还分析（或者叫平摊分析） 均摊时间复杂度应用的场景比它更加特殊、更加有限 // array表示一个长度为n的数组// 代码中的array.length就等于nint[] array new int[n];int count 0;void insert…...
夏驰和徐策的解决数学问题思路——反证法
反证法是一种证明方法，它的基本思路是通过假设某个结论不成立，然后构造出一个矛盾的情况来推导出原先假设的结论是成立的。 具体来说，反证法一般包含以下步骤： 1. 假设所要证明的命题不成立。 2. 通过这个假设，构造…...
面向开发人员的 ChatGPT 提示词教程 - ChatGPT Prompt Engineering for Developers
面向开发人员的 ChatGPT 提示词教程 - ChatGPT Prompt Engineering for Developers 1. 指南(原文: Guidelines)1-1. 提示的指南(原文: Guidelines for Prompting)1-2. 配置1-3. 提示语原则(原文: Prompting Principles)原则 1: 写出清晰而具体的指示(原文: Write clear and spe…...
虹科方案|使用 HK-TRUENAS支持媒体和娱乐工作流程-1
一、摘要 开发和交付能够随时随地触及受众的媒体内容变得越来越重要和复杂。 在当今高度互联、娱乐驱动的世界中，媒体和娱乐 (M&E) 公司需要保持竞争力才能取得成功。 这些组织需要制作各种不同格式的信息和娱乐内容，以便在移动设备、台式机、工作站…...
DDR5内存彻底白菜价，国外大厂却整出了比着火更离谱的骚操作
今年的 PC 硬件市场，似乎出现了明显两极分化现象。 一边是 N、A 两家新显卡价格高高在上，摆明了不坑穷人。 另一边固态硬盘、内存条又在疯狂互卷不断杀价。 四五百元的 2TB SSD，二百元的 16G 内存条早已见怪不怪。 要说面世多年的 PCIe 3.0…...
Linux网络——Shell编程之函数
Linux网络——Shell编程之函数 一、概述二、定义函数的格式1.格式一2.格式二 三、函数的查看和删除1.查看 declare2.删除 declare 四、函数的返回值1.return 返回值2.echo 返回值 五、函数的参数传入与变量范围1.函数的传参2.函数变量的作用范围 六、函数的应用1.阶乘2.递归目录…...