山东胜越石化工程建设有限公司网站,做网站容易挣钱吗,长春网站制作优势吉网传媒,如何写软文推广产品零、前言
经过七七四十九天的分别#xff0c;本期 ABC 题解又和大家见面啦#xff01;
经过七周的奋勇杀题#xff0c;我终于达成了三个小心愿#xff1a;
不吃罚时AK上金排名 100 100 100 以内 且 Rated#xff08;悲催的是#xff0c;我 ABC400 排名两位数但没Rate…零、前言
经过七七四十九天的分别本期 ABC 题解又和大家见面啦
经过七周的奋勇杀题我终于达成了三个小心愿
不吃罚时AK上金排名 100 100 100 以内 且 Rated悲催的是我 ABC400 排名两位数但没Rated 咳咳言归正传开始讲题
一、正文
第 A 题 G1
十分简单即求 K K K 小于等于 a a a 中几个数即可。
代码
#include bits/stdc.h
using namespace std;
int a[1110];
int main(){int n; cinn;for (int i1; in; i) cina[i];int k,ans0; cink;for (int i1; in; i){if (a[i]k) ans;}coutans;
} 第 B 题 Reverse Proxy
本题题意为维护 n n n 个盒子 m m m 次操作每次可以往特定一个盒子或球数量最小如有多个则取编号最小的的盒子里放一个球问每个球被放进那些盒子里了。
考虑到 n , m ≤ 100 n,m\le 100 n,m≤100 可以暴力查询球数量最小的盒子编号。
代码
#include bits/stdc.h
using namespace std;
int a[1110];
int main(){int n,q; cinnq;for (int i1; iq; i){int x; cinx;if (x!0) coutx ,a[x];else{int mn1000000000,id;for (int i1; in; i){if (a[i]mn) mna[i],idi;}coutid ; a[id];}}
} 第 C 题 Rotatable Array
题意为维护一个数组有三种操作
单点修改单点查询旋转即把第一个元素放到最后
我们发现数组长度不变旋转 n n n 次可以抵消。
假设我们的下标从 0 0 0 开始那么旋转 u u u 次的第一个元素就是 a u % n a_{u\% n} au%n。
修改、查询第 p p p 个点转化为修改、查询第 ( p ∑ i 1 i d k i ) % n (p\sum_{i1}^{id} k_i)\% n (p∑i1idki)%n 个点 i d id id 表示当前操作编号 k k k 为旋转次数。
代码
#include bits/stdc.h
using namespace std;
int a[2000010];
int main(){int n,q,st0; cinnq;for (int i1; in; i) a[i-1]i;for (int i1; iq; i){int op; cinop;if (op1){int p,s; cinps; p--;a[(pst)%n]s;}else if (op2){int p; cinp; p--;couta[(pst)%n]\n;}else{int k; cink;st(stk)%n;}}
} 第 D 题 XOR Shortest Walk
一句话题意给你 n n n 个点 m m m 条边的图求 1 1 1 到 n n n 的最小异或路径。
发现 w 2 10 1024 w2^{10}1024 w2101024可以维护 o k i , j ok_{i,j} oki,j 表示从 1 1 1 走到 i i i 是否有异或和为 j j j 的路径。
BFS 维护时间复杂度为 O ( w × ( n m ) ) O(w\times(nm)) O(w×(nm)) 可以通过本题。
代码
#include bits/stdc.h
using namespace std;
bool vis[2010][2010];
vector pairint,int vc[2010];
int main(){int n,m; cinnm;for (int i1; im; i){int u,v,w; cinuvw;vc[u].push_back({v,w});}vis[1][0]1;queue int qx,qy;qx.push(1); qy.push(0);while (qx.size()){int xqx.front(),yqy.front();qx.pop(); qy.pop();for (auto z:vc[x]){if (!vis[z.first][z.second^y]){vis[z.first][z.second^y]1;qx.push(z.first); qy.push(z.second^y);}}}for (int i0; i2000; i){if (vis[n][i]) {couti; return 0;}}cout-1;
} 第 E 题 Battles in a Row
题意有 n n n 个怪物每个怪物有两个参数 a i , b i a_i,b_i ai,bi你也有两个参数 A , B A,B A,B。你可以令你的 A A A 减去 a i a_i ai 或 B B B 减去 b i b_i bi 来杀死怪物 i i i你的 A , B A,B A,B 不能变为负数。问 依次杀死怪物你能杀死几个呢
特别提醒标黑部分本蒟蒻读错题不会做卡了 20min。
考虑二分二分一个怪物数量。对于前 m i d mid mid 个怪物我们先把默认每个怪物都用 A A A 杀然后把 b b b 作为代价 a a a 作为价值 B B B 为容量跑背包跑出最大价值 v v v发现如果 ( ∑ a ) − v ≤ A (\sum a)-v\le A (∑a)−v≤A则有解。
其实不用二分也可以但我赛时没写。
代码
#include bits/stdc.h
using namespace std;
#define N 500000
int x[N],y[N],n,a,b,dp[N];
bool check(int mid){int sum0;for (int i1; imid; i) sumx[i];memset(dp,0,sizeof(dp));for (int i1; imid; i){for (int jb; jy[i]; j--){dp[j]max(dp[j],dp[j-y[i]]x[i]);}}return sum-dp[b]a;
}
int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cinnab;for (int i1; in; i){cinx[i]y[i];}int l0,rn;while (lr-1){int mid(lr1);if (check(mid)) lmid;else rmid;}if (check(r)) coutr;else coutl;
} 第 F 题 Balanced Rectangles
一句话题意给你一个黑白网格求多少子矩阵内黑白数量相等。
首先注意到 H × W ≤ 300000 H\times W\le 300000 H×W≤300000则 H × W × min ( H , W ) ≤ 300000 × 300000 164316767 H\times W\times \min(H,W)\le 300000\times \sqrt{300000}164316767 H×W×min(H,W)≤300000×300000 164316767考虑这个时间复杂度。
首先你可以把黑设为 1 1 1白为 − 1 -1 −1跑二维前缀和那么假设 H ≤ W H\le W H≤W。
枚举 u , d u,d u,d满足 1 ≤ u ≤ d ≤ H 1\le u\le d\le H 1≤u≤d≤H然后根据前缀和我们可以求出每个紫矩阵的权值和任选两个红绿矩阵如果它们权值相等则构成一个可行答案黑。 那么请使用桶来统计答案时间复杂度为上述值。
如果 H W H W HW同理枚举两列即可。
代码
#include bits/stdc.h
using namespace std;
#define K 500000
int cnt[KKK];
string s[K];
vector int sum[K];
int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int t; cint;while (t--){int n,m; cinnm;for (int i1; in; i) cins[i],s[i] s[i];for (int i0; in; i){sum[i].clear();for (int j0; jm; j){sum[i].push_back(((i0||j0)?0:(s[i][j].?1:-1)));}}for (int i1; in; i){for (int j1; jm; j) sum[i][j]sum[i][j-1];}for (int i1; in; i){for (int j1; jm; j) sum[i][j]sum[i-1][j];}if (nm){long long ans0;for (int i1; in; i){for (int ji; jn; j){cnt[K];for (int k1; km; k){anscnt[sum[j][k]-sum[i-1][k]K];cnt[sum[j][k]-sum[i-1][k]K];}for (int k1; km; k){cnt[sum[j][k]-sum[i-1][k]K]--;}cnt[K]--;}}coutans\n;}else{long long ans0;for (int i1; im; i){for (int ji; jm; j){cnt[K];for (int k1; kn; k){anscnt[sum[k][j]-sum[k][i-1]K];cnt[sum[k][j]-sum[k][i-1]K];}for (int k1; kn; k){cnt[sum[k][j]-sum[k][i-1]K]--;}cnt[K]--;}}coutans\n;}}
} 第 G 题 Longest Chord Chain
一句话题意一个圆上有一些弦保留互不相交的一些弦再画一条弦求问它们之间最多存在多少个交点。
猜结论保留最多的弦使得它们可以分成两部分每部分都依次包含两部分无交集。
看如下图 可以粗略证明上述结论。
现在考虑如何求解首先假设 a i b i a_ib_i aibi可以交换两者接下来把 a a a 从大到小排序设 d p i dp_i dpi 为第 i i i 个弦可以连套多少个区间易得 d p i max j ∈ [ 1 , n ] j ! i , a i a j b j b i d p j 1 dp_i\max_{j\in[1,n]}^{j!i,a_ia_jb_jb_i} dp_j1 dpimaxj∈[1,n]j!i,aiajbjbidpj1可以使用树状数组优化。
接下来有了 d p dp dp 后易得答案为 max i , j ∈ [ 1 , n ] i ! j , b j a i d p i d p j \max_{i,j\in[1,n]}^{i!j,b_ja_i} dp_idp_j maxi,j∈[1,n]i!j,bjaidpidpj 和 max ( d p i ) \max(dp_i) max(dpi) 求最大值前者也用树状数组优化即可具体实现请参考代码。
代码
#include bits/stdc.h
using namespace std;
#define N 500010
int n,dp[N];
struct edg{int x,y;
}a[N];
bool cmp(edg a,edg b){return a.xb.x;
}
struct node{int c[N];void update(int id,int mx){while (idn*2){c[id]max(c[id],mx); id(id-id);}}int query(int id){int ans0;while (id0){ansmax(ans,c[id]); id-(id-id);}return ans;}
}tr,tr2;
int main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cinn;for (int i1; in; i){cina[i].xa[i].y;if (a[i].xa[i].y) swap(a[i].x,a[i].y);}sort(a1,an1,cmp);for (int i1; in; i){dp[i]tr.query(a[i].y)1;tr.update(a[i].y,dp[i]);}for (int i1; in; i){tr2.update(a[i].y,dp[i]);}int ans0;for (int i1; in; i){ansmax(ans,tr2.query(a[i].x)dp[i]);}coutans;
} 二、后记
本篇题解结束了祝愿大家能够在学习中实现一个一个小目标在突破自我中成长。
