首页
关于
Search
1
Codeforces Round 930 (Div. 2)
14 阅读
2
Codeforces Round 931 (Div. 2)
9 阅读
3
测试页面
6 阅读
4
Codeforces Round 922 (Div. 2)
6 阅读
5
Codeforces Round 926 (Div. 2)
6 阅读
默认分类
codeforces
登录
Search
算法小何
累计撰写
87
篇文章
累计收到
1
条评论
首页
栏目
默认分类
codeforces
页面
关于
搜索到
86
篇与
的结果
2024-08-26
Codeforces Round #832 (Div. 2)
D. Yet Another Problem算法本质思维题目大意给定一个长度为n的数组arr[],下面给出m此询问,每次询问给出l r。需要回答,对于arr[l~r],我们可以最少进行多少次操作,使得其元素全部为0(无法输出-1)。一次操作定义:选定arr[l~r]内连续的奇数个元素,设x为这些元素异或运算,然后将在arr[]这奇数个元素全部赋为x。思路推演梳理思路,显然我们需要找到一个可以通用的、死板的方法来方便解题。在各种猜测、尝试后,第一个问题映入脑海:某个元素变为0,是否会存在中间过程,还是说一步到位。如果是存在中间步骤,则肯定是会对下一次操作有利的。通过这个点,我们可以很快推出:元素变为0是一步到位的。思维部分最难想到的地方就是这一步了,当推出这个结论后,无数多个结论就蜂拥而至:元素总个数为奇数时,是会被化为奇数个操作搞定的——>奇数个操作,可以直接融合为1次操作元素总个数为奇数时,如果能被操作,是被1次或者2次操作搞定的……进一步分类:元素个数为奇数: 元素和为0(元素全部为0)次数为:0 元素异或运算值不等于0:-1 元素异或运算值等于0:1 元素个数为偶数: 元素和为0(元素全部为0)次数为:0 元素异或运算值不等于0:-1 元素异或运算值等于0: { 若能划分出2个连续的奇数块,且这两个连续的奇数块都必须异或和为0,则:1 或 2 (若其中一个奇数块全为0则选择1) 若无法满足上述要求:-1 }接下来就需要查询复杂度:重点在于,如何O(log~2~n)查询到是否存在这样的奇数块呢?继续推理:若第一个奇数块异或为0,且整体异或为0,则第二个奇数块异或也为0。怎么判断是否存在一个以l为下标的奇数块异或为0呢:异或性质!设xsum[y]表示arr[1~y]的元素异或值设i表示第一个奇数块的末尾下标,若存在i使得xsum[i] == xsum[l-1] && i-l+1为奇数,则说明arr[l~i]元素异或值为0,即第一个奇数块!ac核心代码记得关流!头文件、宏定义、快读模板、常见变量、常见变量等略。 int sum[maxn], xsum[maxn]; //sum[]前缀和,xsum[]异或前缀 int gsum(int l, int r) { return sum[r] - sum[l-1]; } int gxsum(int l, int r) { return xsum[r] ^ xsum[l-1]; } map<int, vector<int>> mp1, mp2; //mp1用来存放奇数下标的异或前缀和,mp2存偶数 //mp[异或前缀]里放的是下标集合 inline void solve() { //init cin>>n>>m; rep(i,1,n) cin>>ar[i]; rep(i,1,n) { sum[i] = sum[i-1] + ar[i]; //搞定前缀和、异或前缀和 xsum[i] = xsum[i-1] ^ ar[i]; } for (int i=0; i<=n; i++) { if (i%2==1) mp1[xsum[i]].push_back(i); //奇数下标的异或前缀和 else mp2[xsum[i]].push_back(i); //偶数下标的异或前缀和 } //cal while (m--) { int l, r, len; cin>>l>>r; len = r-l+1; //长度 //cal if (gsum(l, r)==0) //全是0的情况,不需要出手 ans=0; else if (gxsum(l, r)!=0) //如果异或和不为0,直接G ans=-1; else if (len%2==1) //奇数,不全为0,且可以操作得到0,则只需要一次操作 ans=1; else if (ar[l]==0 || ar[r]==0) //偶数区间的特殊情况,可以看作一个奇数区间 ans=1; else //偶数,不全为0,也许可以操作得到0,还需要进一步判断 { vector <int> *pv; //奇数下标的异或前缀和 if (l%2==1) pv=&mp1[xsum[l-1]]; //奇数下标 else pv=&mp2[xsum[l-1]]; //偶数下标 auto it = lower_bound((*pv).begin(), (*pv).end(), l); //找到第一个大于l的下标 if (it!=(*pv).end() && *it<=r) //如果存在,且小于等于r,说明可以操作得到0 ans=2; else ans=-1; } //out cout<<ans<<endl; } return; }
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round #822 (Div. 2)
C. Removing Smallest Multiples算法本质思维(贪心)思路推演对于每个缺失的值,我们肯定是希望它用尽可能小的因数来去掉。但是举例12,12的因数2。要想12用因数2来去掉,就需要保证2、4、6、8、10、12都是缺失的。显然,如果我们先找值,再找值的因数,选取最小的,这样复杂度是一定过不了的。所以得先找因数。历遍每个因数,我们寻找其能达到的值,一旦这个某个值并非丢失,则继续。这样复杂度大约是O(nlog~2~n)ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 char ch2[maxn]; inline void solve() { cin>>n; scanf("%s", ch+1); //ch[]来表示值是否缺失 rep(i,1,n) ch2[i]=ch[i]; //ch2[]来表示值是否已经被填充,避免重复 ans=0; for (int i=1; i<=n; i++) { for (int pos=i; pos<=n; pos+=i) { if (ch[pos]=='1') break; //遇到不缺失的值了 if (ch2[pos]=='0') //填充 { ch2[pos]='1'; ans+=i; } } } cout<<ans<<endl; return; }D. Slime Escape算法本质思维思路推演这道题跟多校的一个题,思路和模型都很类似,算是那个题的简单版本。题目稍加推理可知,走出去的方法可以归纳为:先走x方向,再走y方向,……,吸纳足够的能量,然后向另一方向冲出去。关键就在于,每次走的时候,应该走到什么地方停下。基础操作围绕核心的点——能量,只要能保证能量收益是正的即可。所以我们假装向某个方向前进,设定走到停下来的条件:收益是大于等于0(那就真的走过去)整体能量为负(那就换个方向)触边(说明成功走出去了)同时,再加一个触发机制——要是连续左右没有更新则表明不能走通。ac核心代码PS:代码看起来多,主要是有大循环里有左右两个方向的代码,重复了许多。头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>n>>k; rep(i,1,n) cin>>arr[i]; //cal int l=k-1, r=k+1; //l r表示边界,表示还没走到的地方 ans=arr[k]; flag=0; while (1) { //cal1 计算向左走 int da=ans; //模拟整体能量值——要是能走,就赋值,不能就不动 int yuan_l = l; //记录原来的l位置 int cnt=0; //cnt表示连续不更新的次数,要是cnt==2说明走不通 while (1) //向左边挖洞 { if (da>ans && arr[l]<0) break; //整体收益大于等于0 if (l==0) break; //触碰到边界 if (da+arr[l]<0) break; //保证整体能量大于等于0 da += arr[l]; l--; } if (l==0 || r==n+1) //先判断是否走出来 { flag=1; break; } if (da>=ans) //有收益,则走 ans=da; else //负收益,不走 l=yuan_l; if (yuan_l != l) cnt++; //说明没有更新 //cal 2 计算向右走 da=ans; int yuan_r = r; while (1) //向右边挖洞 { if (da>ans && arr[r]<0) break; //整体收益大于等于0 if (r==n+1) break; //触碰到边界 if (da+arr[r]<0) break; //保证整体能量大于等于0 da += arr[r]; r++; } if (l==0 || r==n+1) //先判断是否走出来 { flag=1; break; } if (da>=ans) ans=da; else r=yuan_r; if (yuan_r != r) cnt++; //计算是否走不通 if (cnt==0) //说明左右目前都走不通,那就算了呗 break; } //out if (flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; return; }E. Rectangular Congruence算法本质思维、(一点)数学思路推演这种题目好像被称之为构造题,叫做数学题也可以吧。不管叫做什么名称,存在这样明确的数学条件(素数、方阵、算式),就一定需要使用数学方法推导出结论,来帮助更好地用代码去解决。a(x,x)+a(y,y) != a(x,y)+a(y,x) --> a(x,x)-a(y,x) != a(x,y)-a(y,y)第二个式子明显有强烈的视觉规律——这4个点,两列,每列的上点减下点的差,不允许相等。(结合方阵中只有主对角线有确定值,可以推断出整个方阵的规律只有相对差值有关系)这个时候,就很容易想到一个思路:各列相邻两点的差值分别固定0 1 2 ... n-1。用具体的数据验证一下,果然是可行的。再结合式子简单分析,发现也是可行的。思路回顾数学题实际推出式子后就十分简单了。作为编程题,大多时候所谓的数学题也不会是枯燥单纯的证明,比如此题是与图形方阵结合,还有的题与位运算结合。也许一些条件、式子看起来毫无章法,但是对其演化,尝尝能得到不错的结果。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void mo(int &x) //方便取余 { x %= n; if (x < 0) x += n; } int mp[maxn][maxn]; inline void solve() { //init cin>>n; rep(i,1,n) cin>>mp[i][i]; //cal for (int c=1; c<=n; c++) //c:列下标 { int add=c-1; //每列的相邻相差值 for (int r=c-1; r>=1; r--) //向上填充 { mp[r][c] = mp[r+1][c]-add; mo(mp[r][c]); } for (int r=c+1; r<=n; r++) //向下填充 { mp[r][c] = mp[r-1][c]+add; mo(mp[r][c]); } } //out rep(i,1,n) { rep(j,1,n) cout<<mp[i][j]<<" "; cout<<endl; } return; }题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round #819 (Div. 1 + Div. 2)
D. Edge Split算法本质思维思路推演找规律,要从小规律开找,然后推广。自己拿张纸,任意画个小图,然后其中的边变化颜色:比如全涂红、随机涂等等。就会发现了规律:涂边时,相同颜色边不成环收益 > 成环收益。多试几个图,再根据这个规律总结数学公式,会发现果真如此。题目表示,边数m最多为n+2。所以选择首先先弄一棵树出来,数全为红色,剩下的为蓝色。现在唯一需要担心的是,蓝色部分最多有3条边,可能构成环,那得替换一条边,那应该怎么样替换才能使得替换后大家都没有环呢?又拿出一张纸,开始画图,自己动手……然后发现,替换任意一蓝边都是可行的。随机找一条边,设其中的两个点为u v,红边的选择必须是u v到其最近公共组先的路径上的边。因为这题的性质,特别是只找路径中一个边即可,所以并不用搞一套最近公共组先模板,设u v两点其中深度更大的点是v,那红边设定位v--fu[v]即可。注意,因为最后的输出结构,所以需要记录所有边的下标。代码思路建树,同时维护dep[]、fu[]ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round #818 (Div. 2)
A. Madoka and Strange Thoughts算法本质思维思路推演这个题值得注意的一个点就是,在考虑2个数的gcd()、lcm()类似的函数时,可以把这两个数设为ak和bk,保证gcd(a, b)==1。如果使用这个思路,则这个题能够秒解出来。按照题目的要求则把式子化简为:a*b<=3,那就只有数种情况。比如当n=10时,我们把k分为三段。第一段是k为1~3。a b则有5种情况:1 1、1 2、2 1、1 3、3 1。第二段是k为4~5。a b若取3则会超出n,所以只有3种情况:1 1、1 2、2 1。第三段是k为6~10。a b若取2、3则会超出n,所以只有1种情况:1 1。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 ans = 5*(n/3) + 3*(n/2-n/3) + 1*(n-n/2);B. Madoka and Underground Competitions算法本质思维、模拟思路推演最基础的性质就是,同一行、列X之间的距离为k。所以最能第一时间想到的方法是,通过(r, c)把周围必须填的点填上,同时记录哪些行和列已经被填写。然后找到没有填写的行和列,一行+一列为一组,这组把中间交叉的点填上,然后把周围的点天上,记录填写上的行和列。数学上可以证明,不会有重合的部分。但是这样做显得有点过头。题目只会给出一个固定的点,实际完全没有必要采用这样的饱和式攻击。看样例1的第三个情况,就很容发现一种填法,那就是斜着填写。这种填写方法只是正确答案中的一种,但是足够覆盖题目的要求了。(如果题目会给出多个点,这个方法就不能行了)以斜着填写思路为主,稍加思索可知:对于(r, c),我们先把这一列所有应该填写的点找出来(包括(r,c)),放入集合s,然后集合s里的点,都固定向斜着填写(4个斜着的方向都行),直到再次回来这一列停止。思路回顾简单的一个通过性质写模拟的题目,这种就要留心观察,是否能有一个更加简洁的式子。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int mp[maxn][maxn]; int k, sx, sy; void dfs(int x, int y) { if (x>n) x-=n; if (x<1) x+=n; if (y>n) y-=n; if (y<1) y+=n; if (y==sy) return; mp[x][y]=1; dfs(x+1, y+1); } inline void solve() { // init cin>>n>>k>>sx>>sy; mem(mp, 0); //cal vector <int> row; for (int xx=(sx-1)%k+1; xx<=n; xx+=k) { row.push_back(xx); //记录这一列都应该填写的点的行坐标 mp[xx][sy]=1; } for (int x:row) dfs(x+1, sy+1); //out rep(i,1,n) { rep(j,1,n) { if (mp[i][j]==1) cout<<"X"; else cout<<"."; } cout<<endl; } return; }C. Madoka and Formal Statement算法本质思维思路推演典型的找题目规律(本质)的题目。性质1:存在b[i]<a[i]则无解。性质1是题目中已经给出,更重要的是另一个初始条件:若a[i]<=a[i+1],则可以a[i]++。可知:在a[i]<=a[i+1]的情况下,最多可以使得a[i]=a[i+1]+1。同时会发现,这个条件,是相邻2个数的关系。于是我们先缩小范围,研究不同情况下a[i] a[i+1] b[i] b[i+1]能否有解。根据条件,我们简单得分为4种情况:a[i] <= a[i+1]+1 && b[i] <= b[i+1]+1a[i] <= a[i+1]+1 && b[i] > b[i+1]+1a[i] > a[i+1]+1 && b[i] <= b[i+1]+1a[i] > a[i+1]+1 && b[i] > b[i+1]+1经过简单思考,发现如果存在b[i]-b[i+1]>=2,则必须保证a[i]==b[i],否则无解。(性质2)2个元素的关系推理出来了,接着看扩大范围。发现性质相互补充,无缝连接。思路回顾这类题,已经把”找规律“写在脸上了,过程就是通过初始的条件,推出一些规律。但是具体要怎么推,就需要逻辑和思维。代码思路先检查是否存在b[i]<a[i]的情况(性质1)。若存在,无解。再看,如果出现了这样的情况b[i]-b[i+1]>=2,是否能保证a[i]==b[i]。(性质2)若不能做到,无解。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn]; inline void solve() { // init cin>>n; rep(i,1,n) cin>>a[i]; rep(i,1,n) cin>>b[i]; //cal flag=1; rep(i,1,n) if (a[i]>b[i]) flag=0; //性质1 if (!flag) { cout<<"NO"<<endl; return; } //cal 2 b[n+1] = b[1]; for (int i=1; i<=n; i++) //性质2 { if (b[i]-b[i+1] >= 2) //有沟壑 { if (b[i] != a[i]) flag=0; } } //out if (flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; return; }D. Madoka and The Corruption Scheme算法本质思维、思维(二进制)、一点博弈论思路推演此题最大的提示地方在于:有pow(2,n)个选手,n最大范围1e5。这个数据范围,稍微脑子一转就明白,必须得向二进制方向思考,这是大前提。随后我们简化初始条件,Madoka可以随意变化选手初始位置和每场比赛的胜负边,这里其中有2个“随意”,但实际要做到任意更变,只需要1个“随意”就好了。于是我们改成:每场比赛初始设置永远是左边获胜,Madoka可以随意变化选手初始位置。同时对赞助商的行为简化:希望使得最后胜者编号最大。此时,单纯根据文本推到比较困难,于是举一个例子。n=3,k=0~7。可以很明显的想到,如果要推选任意一个选手为胜者,其付出的代价等价于n。所以n=3 k>=3时,赞助商就可以推编号最大的选手获胜,作特殊处理。接下来思考n=3, k=0~2。以下图为例,红色代表胜利。当k=0时,只能采纳pos=1的点。此时Madoka肯定在pos=1的地方放上编号为1的选手。当k=1时,通过改变胜负边,能采纳pos=1、2、3、5的点。Madoka肯定会在这4个点,放上编号为1~4的选手,最后赞助商肯定会选择编号为4的选手。当k=2时,能采纳pos=1~7的点。Madoka同上操作,赞助商会选择编号为15的选手。接下来就是更简单的事了,根据目前发现的东西,找出规律。(思考类似这样的问题:问什么pos=1点在k=0的时候都能被采纳,而pos=3的店只能在k>=1被采纳?)很明显,一个点的位置是否能被采纳跟原本设定的胜利路径有关系。我们用0表示红色代表胜利的线,1表示黑色代表失败的线,从上往下表示。其二进制表示中,有多少个1则代表其胜利所需要的代价。我们要找的就是:长度为n的二进制数,条件:拥有数字1数目小于等于k,符合条件的二进制数有多少个。代码思路组合数相加。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 //组合数板子略 int C(int a,int b); //C(下,上) inline void solve() { // init init_c(); cin>>n>>m; //m代替题目中的k //cal if (m>=n) ans = qpow(2, n, mod); else { ans=0; rep(i, 0, m) { ans += C(n, i); ans %= mod; } } //out cout<<ans<<endl; return; }
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round #816 (Div. 2)
C. Min-Max Array Transformation算法本质思维思路推演a[] + d[] = b[],独立的求d[i]的最值。可以看作对某个a[i]找出可以选择的b[j]。因为一定有解,所以至少会有一个解是,每个a[i]对应的就是b[i],这种对应解先称之为标准解。既然让我们求最值,说明一定是存在一些情况,对b[]的选择起到限制作用。先看最小值,明面上的限制:b[j]>=a[i],思考,如果采用简单的贪心去做,是否可能导致最后无解。经过简单的推算可知,方法:先对特定的a[i]对应尽量小的b[i],对于有解一定是正面作用。所以最小值就搞定了。再看最大值,如果考虑贪心,明面上甚至没有限制条件了。当然题目不可能这么简单,所以自己造样例来找到暗地里的限制。自造样例1: a[]:2 5 6 b[]:4 8 9这里可以看出,a[1]只能对应b[1]的,完全不符合我们说的贪心,究其原因是因为b[1]太小,只有标准解的对应。这样的逻辑关系该如何表示呢?自造样例2: a[]:2 5 9 b[]:4 8 9在自造样例2中,就只有标准解这唯一方法了。通过这2个样例,敏锐地可以察觉到,a[1]之所以不能选择b[2]、b[3],是因为a[2]、a[3]的最低对应已经把b[2]、b[3]给用完了。可以看到,当我们思考a[1]能对应的最大b[j]时,需要考虑a[2]、a[3],这明显是需要从后往前遍历来获取信息。逻辑方面,我们把a[i]的最低对应的b[j]的j记录出现次数,用cnt[]来存放。以自造样例1为例,cnt[]的情况如下:cnt[]:1 2 0 cnt[i]=x表示:b[i]被对应了x次。最开始设mm=b[n],mm表示当前a[i]能取到对应的最大b[i]的值。然后我们从右往左遍历,当下标为i时,取cnt[i+1 ~ n]的和,如果和等于n-i,说明a[i+1 ~ n]通过最低对应,已经用完了b[i+1 ~ n],当前的a[i]的最大对应为b[i],更新mm=b[i],更新cnt[]。同时也可以结合题目性质做出一些改进,比如会发现,要想满足cnt[i+1 ~ n]的和==n-i,其实等同于当前的a[i]最低对应值为b[i]。代码思路因为求最小值(最低对应值)是不需要额外信息的,所以整体从右往左遍历,最小、大值一起求解。设mm=b[n],从右往左遍历,用二分求得a[i]最低对应值b[j],b[j]-a[i]记录到答案最小值。mm-a[i]记录到答案最大值,若j等于i,更新mm=b[i-1],ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn]; int da[maxn][2]; //da[][0、1]分别记录最小、大值 inline void solve() { // init cin>>n; rep(i,1,n) cin>>a[i]; rep(i,1,n) cin>>b[i]; //cal int mm=b[n]; for (int i=n; i>=1; i--) { int pos = lower_bound(b+1, b+1+n, a[i])-b; //找到a[i]的最低对应b[pos] da[i][0] = b[pos]-a[i]; da[i][1] = mm-a[i]; if (pos==i) mm=b[i-1]; } //out rep(i,1,n) cout<<da[i][0]<<" "; cout<<endl; rep(i,1,n) cout<<da[i][1]<<" "; cout<<endl; return; }D. Maximum AND算法本质思维(贪心)思路推演最开始可能会误以为是数学题,整个题的运算就是异或、和,通过改变部分数字的位置,寻求最大值。但是朝这个方向思考了一会,没有找到规律和式子。所以转向了另一个比较明显的方向,求多个数字位运算和的最大值。很明显,把数字以二进制展开,肯定优先保证最高位为1。至于优先保证的方法,可以通过调整b[]中元素位置来实现。这个思路其实相对简单,甚至担心有假,用数据推算了一下复杂度,发现是有可能的,于是继续思考。若要使得答案二进制x位为1,则c[]所有元素二进制x位都得为1,则需要所有的相对应的a[i]、b[i]二进制x位必须一个为0、一个为1。这个实现挺简单的,我们只需要统计他们的二进制x位出现的次数就好了。形象的,我们调整a[] b[]中元素位置:把a[]中二进制x位为1的统统放到左边,二进制x位为0的放到右边。b[]则为0的放到左边,为1的放到右边。若能对齐(a[]中元素二进制x位为1的数目 == b[]中元素二进制x位为0的数目),则说明二进制x位可以对齐。但是发现一个问题,我们可能在对齐x位时,打乱了x+?位的布置。于是为了贯彻贪心思想,从高位开始遍历,一旦对齐了x位,就需要对原数组采取分块的思想,分成2组。之后要想答案y位为1,就需要所有组都能对齐。可以看到,代码将会由2部分组成:分块思想+对齐思想。对齐思想十分简单,只需要历遍一次元素即可。那么分块思想该如何实现:朴素的想法当然是用分块实现。参考分块那章的思想。把是一组的元素放在一起,为一个分块,同时记录每个分块的左右边界。运算时,如果所有分块都能对齐。则对每个分块进行再分块——使用deque先记录元素,然后重新赋值元素,更改原分块的信息、创建一个新的块。整体过程虽然有些繁琐,但是思路十分清晰,复杂度也是可行的。另外一个想法则更为巧妙,分到一组的元素有什么特点:他们在ans(答案值)为1的二进制位上,一定是一致的。表现为ans&a[i] == ans&a[j],则a[i]与a[j]一定是一组的。(b[]同理)所以我们可以建立2个map<int, int> mapa, mapb,分别记录ans&a[i]的个数——即mapa[ ans&a[i] ]++,mapb同理。这个操作实质上是记录每个组的,面对当前x位的0、1数目。a[]中ans&a[i]一组所对应的是b[]中的ans&a[i]^ans。这也就意味,如果:mpa[ a[i]&ans ] == mpb[ a[i]&ans^ans ]就说明这个组是可对齐的。第二个想法整体更巧妙,代码采用第二个想法。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], b[maxn]; inline void solve() { // init cin>>n; rep(i,1,n) cin>>a[i]; rep(i,1,n) cin>>b[i]; //cal ans=0; int shu=qpow(2, 30); //小优化,虽然实际没有用 for (int j=30; j>=0; j--) { ans += shu; unordered_map <int, int> mpa, mpb; //记录不同组的0、1个数 rep(i,1,n) mpa[ a[i]&ans ]++; rep(i,1,n) mpb[ b[i]&ans ]++; flag=1; for (int i=1; i<=n; i++) { if (mpa[ a[i]&ans ] != mpb[ a[i]&ans^ans ]) //^ans是全部对应,^shu是当前位对应 { flag=0; break; } } if (!flag) ans-=shu; shu /= 2; } //out cout<<ans<<endl; return; }可以注意到的是,每个组的对齐检测可能存在多次检测(位运算),这也是为什么第二个想法用时相对较长的原因。不过实际上2个方法的最坏复杂度是一致的。E. Prefix Function Queries算法本质dp(字符串kmp)考察对kmp算法里的nxt[]理解是否深刻。思路推演首先看到这个题会觉得很奇怪,kmp算法的复杂度是O(n),题面上只是简单的更换了最后部分的数据。但马上就会联想到,虽然kmp算法复杂度为O(n),但是那种平摊复杂度。以aaaab举例,在计算nxt[]数组时,很明显为0 1 2 3 0,但是在计算字母b也就是nxt[4]时,其用时显著高于其他元素,单次计算达到了O(n),但是平摊综合来看(数学推导),整体复杂度任然为O(n)。所以题目中,如果我们采取正常的kmp算法,其最坏复杂度约为O(n*q),肯定无法通过。这里面,最重要的是降低查询的复杂度,必须做到O(1)或者O(log~2~n)查询。到这里也就明白了,题目要求我们根据条件对kmp求nxt[]进行优化。至于如何优化,就从复杂度过高的情况说起。复杂度最高的情况就是类似aaa...aaab,求nxt[n]时,需要一点一点向前动。最好能整个一步到位或者倍增实现,两个想法的复杂度分别对应O(1)和O(log~2~n)。至于倍增,没有什么说法,此题中没有单调性,字符串里的字母没有特殊意义(比如大小)、单纯表示两者不同或相同。再看一步到位,相对可行,于是朝这个方向继续思考。为了适应不同的字符串t,所以肯定是需要对26个字母的情况都作出维护。维护数组qf[][],qf[x][y]=z表示当nxt[]回溯下标为x且当前字符为y时,直接回溯到正确下标z——这样就可以省去中间的许多步骤,降低复杂度。通过仔细思考、研究,发现维护qf[][]可行。(具体实现看代码思路、代码)思路回顾想到基础的做法——发现难点(基础做法复杂度过大)——找到导致复杂度过大的情况,根据题目优化。这道题整体简单,是因为题目的意义会引导向kmp算法方向去想,最后去针对性优化kmp。代码思路核心就是如何维护qf[][],这个维护的过程就是dp(其实kmp也可以看作dp)。维护的核心就在于找到状态转移方程。转移方程:nxt[i] = qf[ nxt[i-1] ][ ch[i] ] //使用qf[][]一步到位 qf[i-1][ ch[i] ] = i //显而易见,回溯到上一个点,且当下字符为ch[i]时,最终回溯下标一定为i qf[i-1][ 其他字母 ] = qf[ nxt[i-1] ][ ch[i] ] //若当前的还没更新,直接找到上一个点ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int last[maxn], qf[maxn][30], q; //qf[x][y]=z:回找下标为x,字符为y的情况,可以直接查找到下标z去 char ch2[100]; inline void solve() { //init scanf("%s", ch+1); n = strlen(ch+1); cin>>q; //构造时间回溯功能——last[]和它的升级版:qf[][] last[1]=0; qf[0][ ch[1]-'a' ] = 1; //qf[x][y]=z:回找下标为x,字符为y的情况,可以直接查找到下标z去,不用依次查找浪费时间 for (int i=2; i<=n; i++) { last[i] = qf[ last[i-1] ][ ch[i]-'a' ]; //使用qf[][]一步到位 for (int j='a'; j<='z'; j++) //状态转移方程 { if (ch[i] == j) qf[i-1][j-'a'] = i; //回溯到上一个点,且当下字符为ch[i]时,最终回溯下标一定为i else qf[i-1][j-'a'] = qf[ last[i-1] ][j-'a']; //若当前的还没更新,直接找到上一个点 } } //cal while (q--) { // init scanf("%s", ch2+1); m = strlen(ch2+1); for (int i=1; i<=m; i++) //衔接到ch上 ch[n+i] = ch2[i]; //cal for (int i=n+1; i<=n+m; i++) { last[i] = qf[ last[i-1] ][ ch[i]-'a' ]; //同上 for (int j='a'; j<='z'; j++) { if (ch[i] == j) qf[i-1][j-'a'] = i; //同上 else qf[i-1][j-'a'] = qf[ last[i-1] ][j-'a']; //同上 } } //out rep(i, n+1, n+m) cout<<last[i]<<" "; cout<<endl; } return; }
2024年08月26日
2 阅读
0 评论
0 点赞
1
...
16
17
18