西安理工大学2024年程序设计校赛（校外同步赛）_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
A：签到篇.上
void solve(){
string s;
cin >> s;
if(s == "A" || s == "B" || s == "C") cout << "YES\n";
else cout << "NO\n";
}
B：签到篇.中
typedef tuple<string, string, string> tss;
void solve(){
map<tss, string> v;
v[{"Vertebrates", "Bird", "Carnivores"}] = "Eagle";
v[{"Vertebrates", "Bird", "Haunted Den"}] = "Pigeons";
v[{"Vertebrates", "Mamifero", "Haunted Den"}] = "People";
v[{"Vertebrates", "Mamifero", "Herbivorous"}] = "Cow";
v[{"Invertebrates", "Insect", "Blood Devouring"}] = "Fleas";
v[{"Invertebrates", "Insect", "Herbivorous"}] = "Caterpillar";
v[{"Invertebrates", "Wrinkle", "Blood Devouring"}] = "Leeches";
v[{"Invertebrates", "Wrinkle", "Haunted Den"}] = "Worms";
string s1, s2, s3;
getline(cin, s1);
getline(cin, s2);
getline(cin, s3);
cout << v[{s1, s2, s3}];
}
C：签到篇.下
void solve(){
string x, y, z;
cin >> x >> y >> z;
if(x == y && y == z && z == x) cout << "=";
else cout << ">";
}
D：坐标游戏
思路：博弈问题，如果后手一直把先手维持在 y = x 上面，假设 s 是小于 sqrt(d * d / 2 * k * k) 的最小整数，如果此时先手任然能走出一步，也就是 (s * s * k * k) + (s * k + s) * (s * k + s) <= d * d 那么先手必胜，否则的话就是后手获胜
void solve(){
ll d, k;
cin >> d >> k;
ll s = sqrt(d * d / (2 * k * k));
if(s * s * k * k + (s * k + k) * (s * k + k) <= d * d) cout << "Parry\n";
else cout << "Mercedes\n";
}
F：数对
思路：每次加入⌊m/a[i]⌋，树状数组维护，修改也就是减去原贡献，加上新的贡献即可
struct BIT{
ll n;
vector<ll> tr;
ll lowbit(ll x){
return x & (-x);
}
BIT(int _n) : n(_n), tr(n + 10) {}
void build(ll n, vector<ll> & arr){
for(int i = 1; i <= n; i ++){
ll fa = i + lowbit(i);
tr[i] += arr[i];
if(fa <= n) tr[fa] += arr[i];
}
}
void add(ll x, ll y){
for(ll pos = x; pos < n; pos += lowbit(pos)){
tr[pos] += y;
}
}
ll query(ll x){
ll res = 0;
for(ll pos = x; pos; pos -= lowbit(pos)){
res += tr[pos];
}
return res;
}
ll query(ll l, ll r){
return query(r) - query(l - 1);
}
};
void solve(){
ll n, q, m;
cin >> n >> q >> m;
vector<ll> a(n + 1);
BIT bit(1000010);
for(ll i = 1; i <= n; i ++) cin >> a[i];
// sort(a.begin() + 1, a.end());
ll ans = 0;
for(int i = 1; i <= n; i ++){
bit.add(a[i], 1);
ll num = m / a[i];
ans += bit.query(num);
}
while(q --){
ll op, p, x;
cin >> op;
if(op == 1){
cin >> p >> x;
ll num = a[p];
ans -= bit.query(m / num);
bit.add(num, -1);
bit.add(x, 1);
ans += bit.query(m / x);
a[p] = x;
}
else{
cout << ans << '\n';
}
}
}
G：数字查询
思路：暴力搜索
int p(string s, int p) {
//s[]为顺序存储的p进制字符串
int x = 0;
for (int i = 0; i < s.size(); i++) {
x *= p;
if (s[i] >= 'A' && s[i] <= 'Z') x += (s[i] - 'A' + 10);
else x += (s[i] - '0');
}
return x;
}
void solve(){
int n, ans = 0;
cin >> n;
int n1 = n;
vector<int> a;
set<int> st;
while(n){
a.push_back(n % 10);
n /= 10;
}
int len = a.size();
auto dfs =[&](auto && dfs, int u, string s) -> void{
if(u == 0){
for(int i = 0; i <= 9; i ++){
char c = '0';
c += i;
string s1 = s + c;
dfs(dfs, u + 1, s1);
}
}
else{
if(s.size() == len + 1){
ll num = p(s, 10);
if(num <= n1){
st.insert(num);
}
return;
}
if(s.size() >= 2 && s.size() <= len){
ll num = p(s, 10);
if(num <= n1){
st.insert(num);
};
}
char c1 = s.back();
if(c1 - 2 >= '0'){
string s1 = s;
char c2 = c1 - 2;
s1 += c2;
dfs(dfs, u + 1, s1);
}
if(c1 + 2 <= '9'){
string s1 = s;
char c2 = c1 + 2;
s1 += c2;
dfs(dfs, u + 1, s1);
}
}
};
string s = "";
dfs(dfs, 0, s);
for(auto v : st){
if(v >= 10 && v <= n1) ans ++;
}
cout << ans << '\n';
}
H：听歌
思路：赛时写了一个很麻烦的ST表套单调栈，正解应该是二分答案，二分最小值，把所有小于mid的全部加上这个区间最大值的绝对值，如果还是小于mid，返回false，详细看代码
赛时代码：
struct ST{
int n, q;
vector<vector<int>> f;
ST(int _n) : n(_n), f(25, vector<int>(n + 1, 0)) {}
void init(vector<int> & a){
for(int i = 1; i <= n; i ++) f[0][i] = a[i];
for(int j = 1; j <= 20; j ++){
for(int i = 1; i + (1 << j) - 1 <= n; i ++){
f[j][i] = min(f[j - 1][i], f[j - 1][i + (1ll << (j - 1))]);
}
}
}
int query(int l, int r){
int len = __lg(r - l + 1);
return min(f[len][l], f[len][r - (1 << len) + 1]);
}
};
void solve(){
int n;
cin >> n;
vector<PII> a(n + 1);
for(int i = 1; i <= n; i ++) cin >> a[i].first >> a[i].second;
sort(a.begin() + 1, a.end());
vector<int> b(n + 1);
for(int i = 1; i <= n; i ++) b[i] = a[i].second;
ST st(n);
st.init(b);
vector<int> nxt(n + 1, -1), pre(n + 1, -1);
stack<int> stk;
for(int i = 1; i <= n; i ++){
if(stk.size() == 0 || b[i] < b[stk.top()]) stk.push(i);
else{
while(stk.size() && b[i] > b[stk.top()]){
int x = stk.top();
stk.pop();
nxt[x] = i;
}
stk.push(i);
}
}
while(stk.size()) stk.pop();
for(int i = n; i >= 1; i --){
if(stk.size() == 0 || b[i] < b[stk.top()]) stk.push(i);
else{
while(stk.size() && b[i] > b[stk.top()]){
int x = stk.top();
stk.pop();
pre[x] = i;
}
stk.push(i);
}
}
int ans = -INF;
for(int i = 1; i <= n; i ++){
int l = pre[i], r = nxt[i];
if(l == -1) l = 1;
else l = l + 1;
if(r == -1) r = n;
else r = r - 1;
int res = st.query(l, r) + abs(b[i]);
if(l > 1) res = min(res, st.query(1, l - 1));
if(r < n) res = min(res, st.query(r + 1, n));
// cout << l << ' ' << r << '\n';
ans = max(ans, res);
}
cout << ans << '\n';
}
正解：
void solve(){
int n;
cin >> n;
vector<PII> v(n);
for(auto & [x, y] : v) cin >> x >> y;
sort(v.begin(), v.end());
int l = -1000000000, r = 0;
auto check =[&] (int mid) -> bool{
int l = -1, r = - 1;
for(int i = 0; i < n; i ++){
if(v[i].second < mid){
if(l == -1) l = i;
r = i;
}
}
if(l == -1) return true;
int ma = -1e9;
for(int i = l; i <= r; i ++){
ma = max(ma, v[i].second);
}
for(int i = l; i <= r; i ++){
if(v[i].second - ma < mid) return false;
}
return true;
};
while(l < r){
ll mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
}
I：哲学问题
思路：看奇数个数：
1：奇数数量为1，先手必胜；
2：奇数的数量为偶数，先拿到只剩下一个奇数，后手永远无法消除这个奇数，然后下一轮先手必胜；
3：奇数数量为0，后手必胜
void solve(){
ll n;
cin >> n;
int jis = 0, ous = 0;
for(int i = 1; i <= n; i ++){
ll x;
cin >> x;
if(x & 1) jis ++;
else ous ++;
}
if(jis != 0) cout << "halo\n";
else cout << "parry\n";
}
J：魔方
思路：恶心大模拟，没啥思路，干就完了
#include<bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
int lowbit(int x) {return x & (- x);};
const int N = 200010, mod = 998244353;
const int Mod = 1e9 + 7, INF = 0x3f3f3f3f;
char mf[30][20];
void init(int x, int y, char c){
for(int i = x; i <= x + 2; i ++){
for(int j = y; j <= y + 2; j ++){
mf[i][j] = c;
}
}
}
int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
void s1(int x, int y){
string s;
for(int i = 0; i < 8; i ++) s += mf[x + dx[i]][y + dy[i]];
for(int i = 0; i < 8; i ++){
mf[x + dx[(i + 2) % 8]][y + dy[(i + 2) % 8]] = s[i];
}
}
void l(){
s1(5, 2);
string s;
for(int i = 10; i <= 12; i ++) s += mf[i][4];
for(int i = 1; i <= 9; i ++) s += mf[i][4];
for(int i = 1; i <= 12; i ++) mf[i][4] = s[i - 1];
}
void r(){
s1(5, 8);
string s;
for(int i = 4; i <= 12; i ++) s += mf[i][6];
for(int i = 1; i <= 3; i ++) s += mf[i][6];
for(int i = 1; i <= 12; i ++) mf[i][6] = s[i - 1];
}
void u(){
s1(2, 5);
string s;
for(int i = 4; i <= 9; i ++) s += mf[4][i];
for(int i = 6; i >= 4; i --) s += mf[12][i];
swap(mf[4][1], mf[12][6]);
swap(mf[4][2], mf[12][5]);
swap(mf[4][3], mf[12][4]);
for(int i = 1; i <= 9; i ++) mf[4][i] = s[i - 1];
}
void f(){
s1(5, 5);
string s;
for(int i = 4; i <= 6; i ++) s += mf[3][i];
for(int i = 4; i <= 6; i ++) s += mf[i][7];
for(int i = 6; i >= 4; i --) s += mf[7][i];
for(int i = 6; i >= 4; i --) s += mf[i][3];
int idx = 0;
for(int i = 4; i <= 6; i ++) mf[i][7] = s[idx ++];
for(int i = 6; i >= 4; i --) mf[7][i] = s[idx ++];
for(int i = 6; i >= 4; i --) mf[i][3] = s[idx ++];
for(int i = 4; i <= 6; i ++) mf[3][i] = s[idx ++];
}
void d(){
s1(8, 5);
string s;
for(int i = 6; i >= 4; i --) s += mf[10][i];
for(int i = 1; i <= 6; i ++) s += mf[6][i];
swap(mf[6][7], mf[10][6]);
swap(mf[6][8], mf[10][5]);
swap(mf[6][9], mf[10][4]);
for(int i = 1; i <= 9; i ++) mf[6][i] = s[i - 1];
}
void b(){
s1(11, 5);
string s;
for(int i = 4; i <= 6; i ++) s += mf[1][i];
for(int i = 4; i <= 6; i ++) s += mf[i][9];
for(int i = 6; i >= 4; i --) s += mf[9][i];
for(int i = 6; i >= 4; i --) s += mf[i][1];
int idx = 0;
for(int i = 6; i >= 4; i --) mf[i][1] = s[idx ++];
for(int i = 4; i <= 6; i ++) mf[1][i] = s[idx ++];
for(int i = 4; i <= 6; i ++) mf[i][9] = s[idx ++];
for(int i = 6; i >= 4; i --) mf[9][i] = s[idx ++];
}
void solve(){
for(int i = 1; i <= 12; i ++){
for(int j = 1; j <= 9; j ++){
mf[i][j] = ' ';
}
}
init(1, 4, 'y');
init(4, 1, 'o');
init(4, 4, 'b');
init(4, 7, 'r');
init(7, 4, 'w');
init(10, 4, 'g');
string s;
cin >> s;
int idx = 0;
for(auto c : s){
if(c == 'L') l();
if(c == 'R') r();
if(c == 'U') u();
if(c == 'F') f();
if(c == 'D') d();
if(c == 'B') b();
}
for(int i = 1; i <= 12; i ++){
for(int j = 1; j <= 9; j ++){
cout << mf[i][j];
}
cout << '\n';
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
while(t --){
solve();
}
return 0;
}
L：kids 们的字符串游戏
思路：模拟
void solve(){
int n, m;
cin >> n >> m;
string s;
cin >> s;
vector<pair<char, int>> v;
int flag = 1;
for(int i = 1; i <= m; i ++){
int op, p;
char c;
cin >> op;
if(op == 1) flag = (flag + 1) % 2;
else{
cin >> p >> c;
if(p == 1){
if(flag == 1) v.push_back({c, 1});
else v.push_back({c, 0});
}
else{
if(flag == 1) v.push_back({c, 0});
else v.push_back({c, 1});
}
}
}
deque<char> q;
for(auto c : s) q.push_back(c);
for(auto [x, y] : v){
if(y == 1) q.push_front(x);
else q.push_back(x);
}
if(flag == 1){
while(q.size()){
cout << q.front();
q.pop_front();
}
}
else{
while(q.size()){
cout << q.back();
q.pop_back();
}
}
}
M：数学问题
思路：处理出在端点处的坐标
bool cmp(PII & a1, PII & a2){
if(a1.first != a2.first) return a1.first < a2.first;
else return a1.second > a2.second;
}
struct BIT{
int n;
vector<ll> a;
BIT(int _n) : n(_n + 3), a(n + 1) {}
int lowbit(int x) {return x & (- x);};
void add(int x, int y){
for(int pos = x; pos < n; pos += lowbit(pos)){
a[pos] += y;
}
}
ll query(int x){
ll res = 0;
for(int pos = x; pos; pos -= lowbit(pos)){
res += a[pos];
}
return res;
}
};
void solve(){
ll n, l, r;
cin >> n >> l >> r;
vector<PII> v(n + 1);
vector<ll> a;
for(int i = 1; i <= n; i ++){
ll k, b;
cin >> k >> b;
ll l1 = l * k + b, r1 = r * k + b;
v[i] = pair(l1, r1);
a.push_back(r1);
a.push_back(r1 - 1);
}
sort(v.begin() + 1, v.end(), cmp);
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
cout << a.size() << '\n';
map<ll, ll> mp;
for(int i = 0; i < a.size(); i ++) mp[a[i]] = i + 1;
BIT bit(a.size() + 10);
ll ans = 0;
for(int i = 1; i <= n; i ++){
ans += bit.query(a.size() + 1) - bit.query(mp[v[i].second - 1]);
bit.add(mp[v[i].second], 1);
}
cout << ans << '\n';
}
O：完美区间
思路：字符串哈希+暴力模拟
struct Hash{
const ll p = 998244353;
const ll base = 131;
int n;
vector<ll> a, c;
Hash(int _n) : n(_n), a(n + 10), c(n + 10) {}
void build(int n, string & arr){
c[0] = 1;
ll res = 0;
for(int i = 1; i <= n; i ++){
res = (res * base + arr[i - 1]) % p;
c[i] = c[i - 1] * base % p;
a[i] = res;
}
}
ll query(ll l, ll r){
ll ans = (a[r] - a[l - 1] * c[r - l + 1] % p + p) % p;
return ans;
}
};
void solve(){
ll n;
cin >> n;
vector<ll> a(n + 2), b(n + 1);
string s;
for(int i = 1; i <= n; i ++){
string s1;
cin >> s1;
a[i] = s.size();
s += s1;
for(auto c : s1){
if(c != '0' && c != '1' && c != '8' && c != '6' && c != '9') b[i] = -1;
}
}
ll len = s.size();
a[n + 1] = len;
Hash h1(len);
h1.build(len, s);
for(auto & c : s){
if(c == '6') c = '9';
else if(c == '9') c = '6';
}
reverse(s.begin(), s.end());
Hash h2(len);
h2.build(len, s);
ll ans = 0;
for(int i = 1; i <= n; i ++){
if(b[i] != -1){
for(int j = i; j <= n; j ++){
if(b[j] != -1){
ll l = a[i], r = a[j + 1] - 1;
ll l1 = len - r - 1, r1 = len - l - 1;
auto hashnum1 = h1.query(l + 1, r + 1);
auto hashnum2 = h2.query(l1 + 1, r1 + 1);
if(hashnum1 == hashnum2){
ans = max(ans, 1ll * (j - i + 1));
}
}
else{
break;
}
}
}
}
cout << ans << '\n';
}
标签：mf,理工大学,int,ll,stk,2024,vector,校赛,void From： https://www.cnblogs.com/RosmontisL/p/18113447