网站建设及维护费,营销型网站建设的标准,郑州汉狮做网站的公司,下列什么软件不能用于设计网页看不懂的英文#xff0c;题意很难理解#xff0c;这场还是有点难度的。
C需要处理#xff0c;D是不太明显的dijikstra#xff0c;E是线段树优化dp#xff0c;F是个不好想的线段树#xff0c;主席树应该也能做。
我觉得讲的很好的宝藏up主-B站视频讲解。之后会比较忙…看不懂的英文题意很难理解这场还是有点难度的。
C需要处理D是不太明显的dijikstraE是线段树优化dpF是个不好想的线段树主席树应该也能做。
我觉得讲的很好的宝藏up主-B站视频讲解。之后会比较忙一篇上万字的题解太费时间了之后的题解可能就没办法大段大段的来讲了只说重点。 A Yay!
题意
长度大于等于3的字符串里只有两种字符其中一种字符只出现了一次找到它的位置。
思路
我的思路 如果我们事先知道只出现一次的那个字符是什么就可以直接用string里内置的 find_first_of() 函数来找位置或者知道另一种字符就可以用string里内置的 find_first_not_of() 函数来找位置。
字符串第一个字符一定属于两种字符之一假设出现了一次的字符为a出现多次的字符为b。分类讨论
如果第一个字符是afind_first_of(str[0],1) 会返回 string::npos 这时第一个字符就是a如果第一个字符是bfind_first_of(str[0],1) 会返回一个合法位置这时直接 find_first_not_of(str[0],1) 就能找到a了
jiangly大佬的思路 使用string内置的 count(str[0]) 函数如果个数大于1就是b字符如果个数为1就是a字符
code
#include iostream
#include cstdio
#include cstring
using namespace std;string str;int main(){cinstr;if(str.find_first_of(str[0],1)string::npos)cout1;else coutstr.find_first_not_of(str[0])1;return 0;
}B - Which is ahead?
题意 N N N 个人排成一队每个人有个编号 P i P_i Pi。有 Q Q Q 次询问每次询问给出两个编号 A i A_i Ai 和 B i B_i Bi输出靠前的那个人的编号。
思路
对每个编号记录它在队列中的位置之后拿到编号直接查询位置。
code
#include iostream
#include cstdio
using namespace std;
const int maxn105;int n,idx[maxn],q;int main(){cinn;for(int i1,t;in;i){cint;idx[t]i;}cinq;for(int i1,a,b;iq;i){cinab;printf(%d\n,(idx[a]idx[b])?b:a);}return 0;
}C - Many Replacement
题意
给你一个长为 N N N 的小写字母组成的字符串 S S S。有 Q Q Q 次询问每次询问给出两个小写字母 c i , d i c_i,d_i ci,di 表示将字符串中所有 c i c_i ci 字符换成 d i d_i di。问最后得到的字符串是什么。
思路1
但是发现对每种字符我们只关心它最后变成了哪种字符因此用map记录一下这个字符最后变成了什么就行了也就是这个字符最后映射为什么字符。
更详细的说一开始每个字符都映射为自己每次修改把所有映射值为 c i c_i ci 的键值对改成映射为 d i d_i di最后把原字符串映射一下就行了。时间复杂度 O ( 26 ∗ q ∗ l o g ( 26 ) n ∗ l o g ( 26 ) ) O(26*q*log(26)n*log(26)) O(26∗q∗log(26)n∗log(26))
code1
#include iostream
#include cstdio
#include map
#include vector
#include cstring
using namespace std;int n,q;
string str;
mapchar,char mp;
vectorint a[30];
int c;int main(){cinnstr;for(char cha;chz;ch)mp[ch]ch;cinq;for(int i1;iq;i){char c1,c2;cinc1c2;for(char cha;chz;ch)if(mp[ch]c1)mp[ch]c2;}for(auto x:str)printf(%c,mp[x]);return 0;
}思路2
赛时丑陋的想法。
把每个字符看成一个人它一开始有把仓库钥匙仓库里的货物就是原字符串填有这个字符的所有位置。每次进行字符修改的时候就像把钥匙给了别人不用动货物。
听着挺直观的但是不好写。
code2
#include iostream
#include cstdio
#include map
#include vector
#include cstring
using namespace std;int n,q;
string str;
mapchar,int mp;
vectorint a[30];
int c;int main(){cinnstr;for(int i0;in;i){if(mp.find(str[i])mp.end())mp[str[i]]c;a[mp[str[i]]].push_back(i);}cinq;for(int i1;iq;i){char t1,t2;int n1,n2;cint1t2;if(mp.find(t1)mp.end() || t1t2)continue;if(mp.find(t2)mp.end())mp[t2]mp[t1];else {n1mp[t1];n2mp[t2];a[n2].insert(a[n2].end(),a[n1].begin(),a[n1].end());a[n1].clear();}mp.erase(t1);}for(auto x:mp){for(auto idx:a[x.second]){str[idx]x.first;}}coutstr;return 0;
}D - Square Pair
题意
给你有 N N N 个非负数的数组 A A A找到有多少对 ( i , j ) (i,j) (i,j) 满足 1 ≤ i j ≤ N 1\le ij\le N 1≤ij≤N 且 A i ∗ B j 是平方数 A_i*B_j是平方数 Ai∗Bj是平方数。
能用非负数的平方表示的非负数就是平方数。
思路
对平方数进行质因数分解它的所有质因子的次数都是偶数这样正好可以对半分如果两个数乘起来是平方数那么它们含有的一种质因子的次数的奇偶性一定相同的。我们的任务就是 l o g n logn logn 次内对一个 i i i统计前面 i − 1 i-1 i−1 个数中满足和这个数每个质因子的次数的奇偶性相同的数的个数。
因为我们只关心奇偶性所以可以把多余次数的质因数全部去掉每个奇数次数的质因数只留下一个就行了比如 108 2 ∗ 2 ∗ 3 ∗ 3 ∗ 3 1082*2*3*3*3 1082∗2∗3∗3∗3去重后得到 3 3 3。对处理后的数存入map中就可以 logn 次查询了。
不过要特判 0 0 0 的情况因为 0 0 0 可以和其他任何数产生有效的一对。如果 0 0 0 的个数有 n u m num num 个那么答案会多出 n u m ∗ ( n − 1 ) num*(n-1) num∗(n−1)不过 0 和其他 0 会重复算再减去 n u m ∗ ( n u m − 1 ) / 2 num*(num-1)/2 num∗(num−1)/2。边读数边算边特判也可以。
code
#include iostream
#include cstdio
#include map
using namespace std;
const int maxn2e55;int n;int g(int x){int ans1;for(int i2;i*ix;i){if(x%i0){int cnt0;while(x%i0)x/i,cnt;if(cnt1)ans*i;}}if(x1)ans*x;return ans;
}int main(){cinn;long long num0,ans0;mapint,long long mp;for(int i1,t,x;in;i){cint;if(t0){num;continue;}xg(t);ansmp[x];mp[x];}coutansnum*(n-1)-num*(num-1)/2endl;return 0;
} E - Last Train
题意
有 N N N 个火车站 M M M 个火车信息。第 i i i 个火车信息有六个正整数 l i , d i , k i , c i , A i , B i l_i,d_i,k_i,c_i,A_i,B_i li,di,ki,ci,Ai,Bi表示
在每个时刻 t l i , l i d i , l i 2 ∗ d i , … , l i ( k i − 1 ) ∗ d i tl_i,l_id_i,l_i2*d_i,\dots,l_i(k_i-1)*d_i tli,lidi,li2∗di,…,li(ki−1)∗di都有一列火车从车站 A i A_i Ai 出发并在时刻 t c i tc_i tci 到达车站 B i B_i Bi
问你从车站 i ( 1 ≤ i ≤ N − 1 ) i\quad (1\le i\le N-1) i(1≤i≤N−1) 出发到达车站 N N N 的最晚的出发时间是多少。
思路
乍一看不好下手不妨从终点站来看。
要出发时间最晚那么我们到达终点站也会很晚。为了在路上留出足够充裕的时间我们可以假定到达终点站坐的是最后一班车。
这样来考虑的话我们逆推得到的这些车站也可以通过尽可能晚的车次来从其他车站到达。这样逆推到我们所在的车站就得到了我们现在要出发的车站最晚可以什么时候走。而且我们一定不会回到已经经过的车站否则我们再从这个车站出发的话最晚时间就会变早。
我们每次挑出最晚时间出发的车站进行逆推把更新的车站再依次进行逆推其实就相当于在用dijkstra算法跑最短路。
详细的来说。我们一开始读入火车信息的时候反向建边然后后终点 N N N 开始跑最短路。每次取出出发时刻最晚的车站如果通过一条边也就是一班车可以到达一个点的时间变晚就加入堆。
如何算出最晚车次是哪一次假设现在所在的点的最晚时刻是 t m tm tm那么有 l ( x − 1 ) ∗ d c ≤ t m l(x-1)*dc\le tm l(x−1)∗dc≤tm x ≤ t m − l − c d 1 x\le\frac{tm-l-c}{d}1 x≤dtm−l−c1 x ⌊ t m − l − c d ⌋ 1 ( 1 ≤ x ≤ k ) x\left\lfloor\frac{tm-l-c}{d}\right\rfloor1\quad(1\le x\le k) x⌊dtm−l−c⌋1(1≤x≤k)最后只要保证 x ≥ 1 x\ge 1 x≥1然后 x x x 取 x x x 与 k k k 的较小值即可。发车时刻 l ( x − 1 ) ∗ d c l(x-1)*dc l(x−1)∗dc 就是我们从目标车站的最晚出发时刻。
code
#include iostream
#include cstdio
#include queue
#include algorithm
using namespace std;
typedef long long ll;
#define pii pairll,ll
const int maxn2e55;
const ll inf2e18;int n,m;int head[maxn],cnt;
struct edge{int v,nxt;ll l,d,k,c;
}e[maxn];
void add(int u,int v,ll l,ll d,ll k,ll c){e[cnt].vv;e[cnt].ll;e[cnt].dd;e[cnt].kk;e[cnt].cc;e[cnt].nxthead[u];head[u]cnt;
}ll dis[maxn];
bool vis[maxn];
void dijkstra(){for(ll i1;in;i)dis[i]-inf,vis[i]false;priority_queuepii h;dis[n]inf;h.push(pii(dis[n],n));while(!h.empty()){int dth.top().first,uh.top().second;h.pop();if(vis[u])continue;else vis[u]true;for(ll ihead[u],v,l,d,k,c,ti,tm;i;ie[i].nxt){ve[i].v;le[i].l;de[i].d;ke[i].k;ce[i].c;timin(k,(dis[u]-c-l)/d1);//坐哪一趟车 if(ti1)continue;tml(ti-1)*d;//发车时间if(dis[v]tm){dis[v]tm;h.push(pii(dis[v],v));} }}
}int main(){cinnm;for(ll i1,l,d,k,c,a,b;im;i){cinldkcab;add(b,a,l,d,k,c);}dijkstra();for(int i1;in;i)if(dis[i]!-inf)printf(%lld\n,dis[i]);else printf(Unreachable\n);return 0;
}F - Black Jack
题意
有一个 D D D 面骰子和两个变量 x , y x,y x,y一开始 x y 0 xy0 xy0
你可以投若干次骰子并把骰子的值加到 x x x 上。
然后庄家投若干次骰子并把骰子的值加到 y y y 上。如果某次投骰子后 y L yL yL庄家就停止投骰子。
如果 x N xN xN 则你输。如果 x y xy xy 或 y N yN yN 则你赢。两种情况都不是算你输也就是 x , y N x,yN x,yN
问你采取最大胜率的策略胜率是多少。
思路
jiangly的思路写法不太一样
当我们是某个点数的时候我们可以选择投骰子或者不投。选择哪一个取决于哪个胜率更高。而庄家的策略始终不变因此庄家投出的每种 y y y 的概率是固定的。
当我们选择投骰子时那么假设 d p [ i ] dp[i] dp[i] 是我们当前点数为 i i i 时的胜率 那么 d p [ i ] ∑ k i 1 i d d p [ k ] ∗ 1 d dp[i]\sum_{ki1}^{id}dp[k]*\frac1d dp[i]∑ki1iddp[k]∗d1 。如果我们选择不投骰子假设 f [ i ] f[i] f[i] 表示庄家投出点数为 i i i 的概率我们的胜率就是 ∑ y L x − 1 f [ i ] ∑ y n 1 l d − 1 f [ i ] \sum_{yL}^{x-1}f[i]\sum_{yn1}^{ld-1}f[i] ∑yLx−1f[i]∑yn1ld−1f[i]后者表示庄家投出了比 n n n 大的点数显然这时只要我们的点数不超过 n n n 就行。两种选择取较大值就是 d p [ i ] dp[i] dp[i] 了。 f f f 数组需要预处理当算到 f [ i ] f[i] f[i] 时我们只需要算出前 d d d 个的值这时可以边算 f f f 数组边处理一个前缀和数组这样就可以每次 O ( 1 ) O(1) O(1) 得到区间和整个预处理过程是 O ( n ) O(n) O(n) 的。不过需要注意的是庄家投骰子的策略是投到 y L yL yL 就立刻停止因此前缀和只处理到前 0 ∼ L − 1 0\sim L-1 0∼L−1 后面不再加入新 f [ i ] f[i] f[i] 值。 ∑ y n 1 l d − 1 f [ i ] \sum_{yn1}^{ld-1}f[i] ∑yn1ld−1f[i] 这个东西也可以预先直接算出来。之后为了方便处理我们再处理一个 g [ i ] g[i] g[i] 数组表示我们投出点数为 i i i 时庄家的败率也就是我们选择停手的胜率。
因为计算 d p dp dp 值时我们需要后面 d d d 位的 d p dp dp 值所以从后向前计算。
code
WA3个点精度损失严重。
#include iostream
#include cstdio
#include vector
using namespace std;
const int maxn4e55;int n,L,d;//上界为n下界为l面数为d
double f[maxn],g[maxn],s[maxn],lose;
double dp[maxn];int main(){cinnLd;s[0]f[0]1;for(int i1,l,r;in;i){lmax(0,i-d);rmin(i-1,L-1);f[i](s[r]-((l0)?s[l-1]:0))/d;//庄家投出i的概率 s[i]s[i-1]f[i];}for(int in1,l,r;iLd;i){//投出i点 lmax(0,i-d);rL-1;lose(s[r]-((l0)?s[l-1]:0))/d;}for(int i0;iL;i)f[i]0;f[0]lose;for(int i0;in;i)g[i1]g[i]f[i];//庄家败率 s[n1]0;for(int in,l,r;i0;i--){li1;rmin(id,n);dp[i]max(g[i],(s[l]-s[r1])/d);s[i]s[i1]dp[i]; }printf(%.15lf\n,dp[0]);return 0;
}由于前缀和的精度损失比较严重所以会WA掉三个点因此采用线段树维护单点修改区间和查询。
我前缀和调半天还WA三个点改成线段树还T而jiangly大佬直接一遍A了。。。
#include iostream
#include cstdio
#include vector
using namespace std;
const int maxn2e55;int n,L,d;//上界为n下界为l面数为d
double f[maxn],g[maxn],lose;
double dp[maxn];struct segement_tree{#define ls p1#define rs p1|1int n;struct Node{double val;}t[maxn2];void push_up(int p){t[p].valt[ls].valt[rs].val;}void print(int p,int l,int r){printf(%2d:[%2d,%2d] %lf\n,p,l,r,t[p].val);if(lr)return;int mid(lr)1;print(ls,l,mid);print(rs,mid1,r);}void print(){print(1,0,n);}void build(int p,int l,int r){if(lr){t[p].val0;return;}int mid(lr)1;build(ls,l,mid);build(rs,mid1,r);push_up(p);}void build(int _n){n_n;build(1,0,n);}void mdy(int p,int l,int r,int x,double val){if(lr){t[p].valval;return;}int mid(lr)1;if(xmid)mdy(ls,l,mid,x,val);else mdy(rs,mid1,r,x,val);push_up(p);}inline void mdy(int id,double val){mdy(1,0,n,id,val);}double query(int p,int l,int r,int L,int R){if(Ll rR){return t[p].val;}int mid(lr)1;double ans0;if(Lmid)ansquery(ls,l,mid,L,R);if(Rmid)ansquery(rs,mid1,r,L,R);return ans;}inline double query(int l,int r){return query(1,0,n,l,r);}#undef ls#undef rs
}tr;int main(){cinnLd;tr.build(n);f[0]1;tr.mdy(0,f[0]);for(int i1,l,r;in;i){lmax(0,i-d);rmin(i-1,L-1);f[i]tr.query(l,r)/d;//庄家投出i的概率 tr.mdy(i,f[i]);}for(int in1,l,r;iLd;i){//投出i点 lmax(0,i-d);rL-1;losetr.query(l,r)/d;}for(int i0;iL;i)f[i]0;f[0]lose;for(int i0;in;i)g[i1]g[i]f[i];//庄家败率 for(int in,l,r;i0;i--){li1;rmin(id,n);dp[i]max(g[i],(lr)?tr.query(l,r)/d:0);tr.mdy(i,dp[i]);}printf(%.15lf\n,dp[0]);return 0;
}G - Retroactive Range Chmax
题意
给你有 N N N 个正整数的数组 A A A有 Q Q Q 次操作操作有三种
输入 1 l r x 将 A l , A l 1 , … , A r A_l,A_{l1},\dots,A_{r} Al,Al1,…,Ar 的每个数 A i A_i Ai 变成 m a x { A i , x } max\{A_i,x\} max{Ai,x}。输入 2 i 将第 i i i 个操作撤销保证第 i i i 个操作是第一种操作并且之前没有被撤销过输入 3 i 查询 A i A_i Ai 的值。
思路
借鉴这位大佬
相当于记录每个点所有可能的值显然在某个时刻查询的时候我们只要给出最大的那个就行了。但是直接暴力存储每个点的可能的值既会爆空间又会爆时间。因此用线段树维护我们这里的值不需要 push_up 和 push_down 来维护查询时只需要返回到达 A i A_i Ai 时线段树路径上的最大值就行了。
code
基本相当于照抄了汗
#include iostream
#include cstdio
#include map
using namespace std;
const int maxn2e55;int n,a[maxn];
int q;struct segement_tree{#define ls p1#define rs p1|1int n;struct Node{mapint,int val;}t[maxn2];void build(int p,int l,int r){if(lr){t[p].val[a[l]];return;}int mid(lr)1;build(ls,l,mid);build(rs,mid1,r);}void build(int _n){n_n;build(1,1,n);}void mdy(int p,int l,int r,int L,int R,int d,bool x){if(Ll rR){if(x){t[p].val[d];}else {if(--t[p].val[d]0)t[p].val.erase(d);}return;}int mid(lr)1;if(Lmid)mdy(ls,l,mid,L,R,d,x);if(Rmid)mdy(rs,mid1,r,L,R,d,x);}int query(int p,int l,int r,int L,int R){if(Ll rR){return t[p].val.rbegin()-first;}int mid(lr)1,ans0;if(!t[p].val.empty())anst[p].val.rbegin()-first;if(Lmid)ansmax(ans,query(ls,l,mid,L,R));if(Rmid)ansmax(ans,query(rs,mid1,r,L,R));return ans;}#undef ls#undef rs
}tr;struct opter{int l,r,d;
}opt[maxn];int main(){int n;cinn;for(int i1;in;i)cina[i];tr.build(n);cinq;for(int i1;iq;i){int op;cinop;if(op1){cinopt[i].lopt[i].ropt[i].d;tr.mdy(1,1,n,opt[i].l,opt[i].r,opt[i].d,1);}else if(op2){cinopt[i].d;tr.mdy(1,1,n,opt[opt[i].d].l,opt[opt[i].d].r,opt[opt[i].d].d,0);}else {cinopt[i].d;couttr.query(1,1,n,opt[i].d,opt[i].d)endl;}}return 0;
}
