首页
关于
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 821 (Div. 2)
A.Consecutive Sum算法本质思维题目大意给长度n的数组a[],下标对于k同余的元素为同一组,同一组的元素可以任意调换位置。任意次操作后,选择长度为k的连续子数组,输出最大化其元素和。思路推演显然是每个组出一个元素,每组出最大的元素即可。B.Rule of League算法本质思维题目大意一队列原有n个人,id1~n顺序占位(1号占队头)。头的两个人会决斗,输掉的人出队,赢家仍站在队头。比赛进行n-1次直到最后剩下一个人。给定n x y,规定同一个id的人只允许赢x或y场决斗,检测是否存在如此情景,若存在输出每场胜者id,反之输出-1。思路推演手动模拟一下会发现,对于第一场比赛,1号胜利则2号直接出局——2号赢0场。所以x y中必须有一个等于0、一个大于0(n>1的情况下)。设x=0假设第一场1号必输,则2号连赢y场后必须输掉比赛,换2+y上场连赢y场,以此类推,n-1必须能整除y。即得到答案。C.Parity Shuffle Sorting算法本质思维题目大意给长度n的数组a[],最多进行n次以下操作:选择一对l r,如果a[l]+a[r]为奇数,则a[r]=a[l];反之a[l]=a[r]使得a[]单调不减。输出操作的l r。思路推演既然跟奇偶性有关,则考虑一下4种情况。若两者都是奇数或者偶数,其操作后两者奇偶性不变。这下我们就通过奇偶性来分成两条线,这两条线可以分别处理,思考如何整合到一起。此时就需要思考,奇数+偶数的情况,会a[r]=a[l]。所以若a[1]是奇数,则我们将所以的奇数向最右的奇数看齐,然后再将所有的偶数向a[1]看齐。D2.Zero-One (Hard Version)算法本质思维、dp题目大意(改)有长度n的01字符串,有2种操作方式,将其变成一个全0字符串:x元:选择两个相邻字符反转y元:选择两个不相邻字符反转最小化成本。(或者输出-1)n:[1, 5e3]思路推演显然,奇数个1会导致失败。显然操作2更为灵活,如果x>=y的情况下,有且仅有2个连续1相邻的这种情况,可能用操作1,否则都会使用操作2。于是可以单独讨论x>=y的情况,这部分比较简单不详述。实际上easy版本也提醒了我们:单独讨论x>=y的情况到了这个地步,要么贪心、要么dp。(也有可能是没见过的神奇数据结构、图论之类的)贪心的话,思考一段时间,发现找不到角度贪,所以思考一下dp。显然dp应该用二维区间dp。思考一会就发现:对于l rint val_ll = dp[l][l+1] + dp[l+2][r]; // 左边2个+右边 int val_rr = dp[l][r-2] + dp[r-1][r]; // 左边+右边2个 int val_lr = dp[l+1][r-1] + y; // 左右各给1个 dp[l][r] = min(val_ll, min(val_rr, val_lr));即得,思路很顺。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int dp[maxn][maxn]; inline void solve() { //init int x, y; string s1, s2; vector<int> v; cin>>n>>x>>y>>s1>>s2; s1 = " " + s1; s2 = " " + s2; s = s1; for (int i=1; i<=n; i++) { if (s1[i] == s2[i]) s[i] = '0'; else { s[i] = '1'; v.push_back(i); } } //cal 特殊情况判断 int ans; if (v.size()%2==1) { cout<<-1<<endl; return; } if (x>=y) { if (v.size()==2 && v[0]+1==v[1]) ans = min(x, 2*y); else ans = v.size()/2*y; cout<<ans<<endl; return; } //cal 2 n = v.size(); for (int i=1; i<=n-1; i++) dp[i][i+1] = min(x*(v[i]-v[i-1]), y); // 注意v是零下标 for (int len=4; len<=n; len+=2) { for (int l=1, r=len; r<=n; l++, r++) { int val_ll = dp[l][l+1] + dp[l+2][r]; // 左边2个+右边 int val_rr = dp[l][r-2] + dp[r-1][r]; // 左边+右边2个 int val_lr = dp[l+1][r-1] + y; // 左右各给1个 dp[l][r] = min(val_ll, min(val_rr, val_lr)); } } ans = dp[1][n]; cout<<ans<<endl; return; }
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 816 (Div. 2)
A.Crossmarket算法本质思维题目大意有一个n*m的地图,小蓝在(1,1)目标(n,m),小红在(n,1)目标(1,m),每走一步花费一秒。小红走过的路径会留下空间之力,小蓝在任意具备空间之力的格子,可以花费一秒的代价,去到任意具备空间之力的格子。小红先走,到终点后小蓝再出发。输出最小化其所用时间。思路推演小红所用时间固定n+m-2,对于小蓝,有3种走法:直接走,不使用空间之力使用空间之力在y轴方向传送使用空间之力在x轴方向传送三种情况都计算,然后取小输出即可。B.Beautiful Array算法本质思维题目大意对于长度为n的数组,定义魅力值为:元素/k之和。(除法取下限)现在需要你构造一个长度为n、魅力值为b、元素和为s的数组a[]。(若不可能输出-1)思路推演显然,若保证数组魅力值为b,其元素和范围:[bk, bk+n*(k-1)]将bk随便放到某个下标去,然后将s-bk平均分配到n个元素内即可。C.Monoblock算法本质思维题目大意给定长度n的数组a[]。定义a[l, r]的魅力值:可以拆分数组的连续相同数字的最小块数不懂的看一下题目中的样例解释定义a[]的帅气值:所有区间魅力值之和接下来有q次询问,每次询问会改变某元素的值(之后永久有效),需要输出当前a[]的帅气值。思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round #840 (Div. 2)
E.Partial Sorting算法本质分类讨论思维、容斥(一点点)题目大意给出n、mod,列出长度为3n的所有排列,每个排列都有自己的价值x——最少经过x次操作后使得排列为[1~3n]的形式。下面是可以对排列进行的2种操作:前排:递增sort前2n个元素后排:递增sort后2n个元素求所有排列价值之和(取余mod)。思路推演-1首先可以拿出的一个结论是,任何排列经过3次操作可以恢复。既然只有3次操作,显然是一个分类讨论+组合数的题目。分类讨论的重点就在于,该如何分类讨论,这里通常有2个方法:贴近答案分类讨论每个排列只有4种价值,则按照不同价值分类贴近数据本身的结构分类讨论可以看到,每个排列分为了3个大区间,思考排列的特殊结构不论哪种分类方法,最后都疏通同归,但是思考的难易程度会有所不同。同时注意,这题给的复杂度宽裕,支持在分类讨论中O(n)的暴力。固定思维想着组合数问题需要O(1)解决,是没做出来的原因之一。思路推演-2这里选择贴近答案分类讨论,同时在分类的时候,发现先用小于等于处理较好。价值==0只有一种可能。价值<=1意味着只需要一次前排or后排就可以搞定,这分别对应2种情况:[2n+1, 3n]的数字已就位且[1, 2n]数字任意排序[1, n]的数字已就位且[n+1, 3n]的数字任意排序同时这两种情况有交叉的地方fac[2n] + fac[2n] - fac[n]价值<=2这里可以反向思考一下,价值为3的情况是什么——存在最小的n个数在[2n+1, 3n]且存在最大的n个数在[1, n]思索片刻可知,操作必然是前排+后排或者后排+前排,这里也对应2种情况:最小的n个数只在[1, 2n]最大的n个数只在[n+1, 3n]这里注意理解一下同时这两种情况也存在交叉的地方。思考最小的n个数只在[1, 2n]有多少种情况:[1,2n]选择n个位置,然后全排列:C(2n, n)*fac[n]剩下位置全排列:fac[2n]思考交叉部分的情况:细细一琢磨,发现情况有点多,但是我们可以接受O(n)的暴力。于是设最小的n个数,在[1,n]中有n-x个数,在[n+1,2n]中有x个数。[1,n]中选n-x个位置给最小的n个数:C(n, n-x)[n+1,2n]中选x个位置给最小的n个数:C(n, x)[n+1,3n]中剩下2n-x个位置留给最大的n个数选择:C(2n-x, n)最小、中、大的n个数分别自我全排列:fac[n] * fac[n] * fac[n]枚举x ~ [0,n]价值<=3全排列:fac[3n]ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 组合数板子未给出 inline void solve() { //init cin>>n>>mod; init_c(); //cal vector <int> v(4, 0); //v[x]表示价值<=x的方案数 v[0] = 1; v[1] = fac[2*n] + fac[2*n] - fac[n]; v[1] %= mod; v[2] = C(2*n, n) * fac[n] %mod * fac[2*n] * 2 %mod; int n3 = fac[n] * fac[n] %mod * fac[n] %mod; for (int x=0; x<=n; x++) //减去容斥 { v[2] -= C(n, n-x) * C(n, x) %mod * C(2*n-x, n) %mod * n3 %mod; v[2] = (v[2]%mod + mod) %mod; } v[3] = fac[3*n]; //cal v[3] -= v[2]; v[3] = (v[3]%mod + mod) %mod; v[2] -= v[1]; v[2] = (v[2]%mod + mod) %mod; v[1] -= v[0]; v[1] = (v[1]%mod + mod) %mod; ans = 0; for (int i=0; i<=3; i++) { ans += i*v[i]; ans %= mod; } //out cout<<ans<<endl; return; }F.Wonderful Jump算法本质思维、dp思路推演-1整个题目看上去,很明显的线性dp,同时也很明显的发现复杂度不够,作为2900的题目,肯定是需要在某些地方做出改进的。然后观察不同寻常的地方:元素范围[1,n]成本公式:min*(j-i)^2^目标非常明确,通过这2个不同寻常的条件,改进dp方式,从而满足复杂度。同时注意有平方,复杂度可能为n^1.5^,或者nlog~2~n。元素范围暂时看不出什么花样来,那就算看成本公式。通过成本公式可以推出2个性质:性质1:对于i --> j,如果存在i<k<j && a[k]<a[i] && a[k]<a[j],则i-->k-->j 优于 i-->k这个性质相当不错,这意味我们简化了模型,只用讨论最小值在两端的情况当前的性质1作为定性讨论的,其实可以深挖定量,但是定量出来的公式未知数多,没有明确的关系。性质2: 成本公式是抛物线上升的,如果每次走一格,则成本是线性上升的,当i j相差过大时,每次走一格的成本较低对于性质1来说,可以简化我们讨论的情况,但是对于最小值在两端的情况,依然没有什么好的方法去解决。对于性质2来说,就比较有用了,因为在最朴素的n^2^算法中,我们需要对前面所有的元素都遍历一次。但性质2给我们提供了一个新的思路,或许我们可以找到i j相差过大的阈值,然后减少遍历的次数。对于i-->j (i<=k<=j),设a[k]为其最小值,设A为a[i~j]的平均值i-->j(直达)的成本是:a[k]*(j-i)*(j-i)i-->j(步步走)的成本是:A*(j-i)发现当j-i > A/a[k]时,则直达的成本>步步走的成本,这并不意味我们会选择步步走,而是说,那部分i j的直达可以不用讨论了,肯定不是最优解。但是同时,我们并不确定A a[k]的范围,没有一个较大的意义,所以我们在这里必须强制规定,假设a[k]>=根号n。为什么这里假设的是根号n而非log~2~n之类的:1.根号n的复杂度是ok的2.后面可能会用到一些除法翻转,这里数设置小了,可能下一步的算法复杂度更大了3.先随便假设一下,大了小了后面看着调整当保证了a[k]>=根号n,考虑最坏的情况(A==n),则可以推出:当i j差超过了sqrt(n)时,则直达一定不是最优解。这表明了,当a[k]>=根号n,算法复杂度被降低为了n^1.5^。思路推演-2随后我们需要考虑a[k]<根号n的情况。(a[k]是指是a[i~j]的最小值)兜兜转转找了一会,并没有发现什么不错的公式,那没办法了,只有老实用性质1分类讨论一下。如果最右边的元素是最小值(a[j]是最小值 && a[j]<根号n)那这就好办了,既然又要保证a[j]是最小值,又要保证a[j]<根号n。我们让i从j-1遍历到1,暴力i j,但是因为上面2个条件的限制,我们的总体复杂度为n^1.5^。这里理解逻辑的话可以配合代码一起看。讲一下为什么复杂度为n^1.5^:当a[j]>=根号n时不会处理当a[j]<根号n时,对于多个同样的值(值指a[j]),其总体复杂度为n,一共最多有根号n个不同值,所以复杂度为n^1.5^如果最左边的元素是最小值(a[i]是最小值 && a[i]<根号n)这里我们把这些最小值用一个栈存起来,并且保证是递增的。(单调栈)代码思路我们固定j,移动i,每次i j变化的时候,就只会存在上述3种情况:a[k]>=根号n让i从j-1开始向后暴力遍历根号n个数即可。同时在这里,其实并不需要真的去判断a[k]>=根号n,可以直接计算,也不会增加复杂度的。a[j]是最小值 && a[j]<根号n注:这里必须保证a[j]<根号n当固定好j时,移动i时,前几个数可能会高于a[j]形成这种情况。不过一旦遇到某个元素<=a[j]则会打破这种情况,进入下一个情况else这个else情况,全部都可以转化为a[i]是最小值 && a[i]<根号n。对于固定的j来说,只需要和单调栈中存放的下标一一暴力历遍即可。这里也没有什么硬性要求,可以直接计算,不会增加复杂度。ac核心代码-思路1头文件、宏定义、快读模板、常见变量、常见变量等略。 int dp[maxn]; inline void solve() { //init cin>>n; rep(i,1,n) cin>>ar[i]; mem(dp, 0x3f); m = sqrt(n); //根号n vector <int> v; //单调栈 //cal dp[1] = 0; v.push_back(1); //第一位特殊处理 for (int j=2; j<=n; j++) { //case 1 //a[k]>=根号n int mi = ar[j]; //mi表示区间[i, j]中的最小值 for (int i=j-1; i>=max((int)1, j-m); i--) { mi = min(mi, ar[i]); dp[j] = min(dp[j], dp[i] + mi*(j-i)*(j-i)); } //case 2 //a[j]是最小值 && a[j]<根号n if (ar[j]<=m) //这里必须有条件,不然复杂度会炸 { for (int i=j-1; i>=1 && ar[i]>ar[j]; i--) dp[j] = min(dp[j], dp[i] + ar[j]*(j-i)*(j-i)); } //case 3 //其他情况-->转化为`a[i]是最小值 && a[i]<根号n` for (int i:v) dp[j] = min(dp[j], dp[i] + ar[i]*(j-i)*(j-i)); //维护一下单调栈 if (ar[j]<=m) { while (!v.empty() && ar[v.back()]>=ar[j]) //当前点的值更小,就删去之前的 v.pop_back(); v.push_back(j); } } //out for (int i=1; i<=n; i++) cout<<dp[i]<<" \n"[i==n]; return; }
2024年08月26日
2 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round #840 (Div. 2)
D.Valid Bitonic Permutations算法本质dp、思维题目大意生产一个长度为n的排列,且要求这个排列为单峰形式(先上后下——峰值不在边缘)并且会明确规定排列的某2个下标对应的值,求数目。思路推演-1看了部分题解,才发现有dp的解题方式。dp方法的核心在于,是否能构建一个具有一定传递性的的意义。以dp[l][r]=x,表示在下标[l, r]中(共r-l+1个位置),有从n、n-1、n-2...n-r+l这r-l+1个数,其能构成合格的单峰数目为x上面这句话比较重要,需要完全理解。所以当我们考虑,dp[l][r]扩展到dp[l-1][r]时可以发现,我们实际上是把多加的一个数字放于最左边。同理,扩展到dp[l][r+1]时可以发现,我们实际上是把多加的一个数字放在最右边。思考单峰排列的构造,我们也是会先讲n放于中间,然后在左右两边添加较小值。而这个dp的思考方式即如此,同时配合固定下标,可以完成其对下标的要求。由此,也可以知道,dp的起点应该从dp[i][i]=1,同时发现单峰不允许峰值在边缘,所以dp[1][1]=dp[n][n]=0。同时在转移的过程中,需要注意的是得满足确定的2个下标+值这个条件,只需要在每次转移的过程中,检查一下是否满足,要是不满足就放弃这个转移即可。ac核心代码-思路1头文件、宏定义、快读模板、常见变量、常见变量等略。 int dp[105][105]; int p1, p2, v1, v2; bool check(int pos, int val) //检查pos位置放val值可行否 { if (pos==p1 && val!=v1) return 0; if (pos==p2 && val!=v2) return 0; return 1; } inline void solve() { //init mem(dp, 0); cin>>n>>p1>>p2>>v1>>v2; for (int i=2; i<=n-1; i++) if (check(i, n)) dp[i][i]=1; //cal for (int len=2; len<=n; len++) { for (int l=1; l+len-1<=n; l++) { int r=l+len-1; //可以看作dp[l+1][r]加了一个数在左边 if (check(l, n-len+1)) dp[l][r] += dp[l+1][r]; //可以看作d[l][r-1]加了一个数在右边 if (check(r, n-len+1)) dp[l][r] += dp[l][r-1]; dp[l][r] %= mod; } } //out ans = dp[1][n]; cout<<ans<<endl; return; }思路推演-2这里的思路推演请结合代码、图片(暂懒得画)一起看。目前的条件有:单峰形式、确定的2个下标+值。这两个条件能创造出的情景就相对有限,所以第一时间想到的是分类组合数。这里的分类组合数也有2个解法,一是O(n^2^)每次枚举n出现的位置,这样的组合数也相对好写,下面这个题解中的D组合数方法就是这样写的:Codeforces Round #840 (Div. 2) and Enigma 2022 - Cybros LNMIIT A~E还有一个究极分类讨论方法,预处理组合数O(nlog~2~n),每次O(n),下面讲解:首先我们讨论分类的情况,可以发现的是,这个线性模型对称,所以我们可以保证确定的2个值,在左边的一定更小。这里l r表示2个确定值的下标,vl vr表示2个确定值的值:int l, r, vl, vr; //l r为下标,vl vr为值 cin>>n>>l>>r>>vl>>vr; if (vl > vr) //等价替换,保证左边的值一定小于右边 { l = n-l+1; r = n-r+1; swap(l, r); swap(vl, vr); }加上单峰曲线,这样就可以分为2种情况:右值恰好为n(特殊情况)右值不为n如果右值不为n,我们则需要讨论n出现的位置可能:l r n:峰值n出现r的右边l n r:峰值n出现在l r的中间同时,我们也找到这个模型的一些公有变量。以下标为横轴,我们可以分为3个位置:小于l、l r之间、大于r。不同位置所拥有的位置个数,分别命名为:l_wei m_wei r_wei。以值大小为纵轴,我们也可以分为3种大小的值:小于vl、vl vr之间、大于vr。不同大小的值的个数,分别命名为:l_val m_val r_val。固定2个确实位置+值这个条件我们已经做到了,接下来的构造中,需要保证确定是单峰这个条件。右值恰好为n(特殊情况)(vr==n)当r==n时,这个时候不是单峰,则ans=0。如果r!=n的话,我们以横轴为基准,先填充左边的下标,然后填充中间的,剩下的在右边摆好即可:ans = C(l_val, l_wei) * C(m_val, m_wei)右值不为n(vr!=n)这里有2个可能:l r n:峰值n出现r的右边还是先填充左边、再填充中间:C(l_val, l_wei) * C(m_val, m_wei)值大于vr的那些数(共r_val个),会自动填充在右边的,考虑他们的结构问题,可知结构个数:qpow(2, r_val-1)同时想一想,这种情况可能导致非单峰的出现,在某个特点情况下,可能会导致n被放于最右边,那个时候需要结构个数-1l n r:峰值n出现在l r的中间先填充左边、再把值大于vr的那些数(共r_val个)强制填入中间,并考虑结构个数,最后把中间剩下的部分填满最后最后剩下的数字填充右边即可。这样就搞定了所有情况了。ac核心代码-思路2头文件、宏定义、快读模板、常见变量、常见变量等略。 //注:qpow默认对mod取模! //组合数板子 int fac[maxn],inv[maxn]; //fac[x]代表x!,inv[x]代表x的逆元 void init_c(int max_num=maxn-2) { max_num = min(max_num, mod-1); //大于等于mod的情况用lucas定理 inv[0]=fac[0]=1; for(int i=1;i<=max_num;i++) fac[i]=fac[i-1]*i%mod; inv[max_num]=qpow(fac[max_num], mod-2, mod); for(int i=max_num-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod; } int C(int a,int b) //C(下,上) { if(a<b) return 0; if (a<0 || b<0) return 0; if(a>=mod || b>=mod) return C(a%mod, b%mod)*C(a/mod, b/mod)%mod; //lucas定理,处理mod较小情况 return fac[a]*inv[b]%mod*inv[a-b]%mod; } inline void solve() { //init int l, r, vl, vr; //l r为下标,vl vr为值 cin>>n>>l>>r>>vl>>vr; if (vl > vr) //等价替换,保证左边的值一定小于右边 { l = n-l+1; r = n-r+1; swap(l, r); swap(vl, vr); } //cal int l_wei=l-1; //左边的位置个数 int m_wei=r-l-1; //中间的 int r_wei=n-r; //右边的 int l_val=vl-1; //小值:小于vl的值个数 int m_val=vr-vl-1; //中值:大于vl、小于vr的值个数 int r_val=n-vr; //大值:大于vr的值个数,含n //特殊情况 //r处放n if (vr==n) { // cout<<"特殊情况"<<endl; int d=1; d *= C(l_val, l_wei); //选一些小数去左边位置 d %= mod; d *= C(m_val, m_wei); //选一些中数去中间位置 d %= mod; ans = d; if (r==n) ans=0; } else //普遍情况 { //cal 1 //n在r右边情况 int d1=1; d1 *= C(l_val, l_wei); //选一些小数去左边位置 d1 %= mod; d1 *= C(m_val, m_wei); //选一些中数去中间位置 d1 %= mod; if (r_wei == r_val) d1 *= qpow(2, r_val-1)-1; //防止n靠在最右边的情况 else d1 *= qpow(2, r_val-1); //中间部分的选择情况 d1 %= mod; //cal 2 //n在l r中间的情况 int d2=1; d2 *= C(l_val, l_wei); //选一些小数去左边位置 d2 %= mod; d2 *= qpow(2, r_val-1); //中间先放最大的那些数 d2 %= mod; d2 *= C(m_val, m_wei-r_val); //选一些合格的数字来填充中间剩下的位置 d2 %= mod; ans = d1+d2; } //out ans %= mod; cout<<ans<<endl; return; }
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Educational Codeforces Round 135 (Rated for Div. 2)
C. Digital Logarithm算法本质思维(贪心)思路推演显然,为了达到最小操作数的目的,要在数大的时候尽量都给抵消了,实在不行才操作:如果a[]和b[]中有重复元素,则移动到一边不变(也可以看作相互抵消了)。然后我们选择具有部分特征的元素进行操作,然后再比较,一直重复这个过程直到完全抵消。通过手动模拟,抓住了一个简单的性质,给数字划分等级。一级:{1} 二级:{2~9} 三级:{10~1e9-1}可以看到,每次对一个数字操作,其都会变成低一级中的对应数字。我们先对a[] b[]中等级为三级的元素,存在相等情况就抵消。剩余的三级元素则全部进行操作,变为二级元素,然后再检查能否抵消,最后不行的变为一级元素——一定相同可抵消了。这个代码实际上就会有2个操作:相互抵消,可以选择map或者双指针(queue)的方式对更高一级的元素进行操作,随意即可——暴力复杂度也可以承受的在代码写出框架后会发现,好像完全没有必要分为多个阶段的操作,我们可以使用priority_queue<int>来排序剩下的元素,然后选择a[]剩下的元素中最大ai和b[]剩下的元素中最大bi,如果两者相等,则抵消;若不等则选择较大值操作。这样的话,实质是把上面的2个操作合并在一起了,但代码中两者可以同时进行——类似于也被我叫做“边输入边计算”的东西。代码思路priority_queue <int> qa, qb放a[]和b[]的元素。同时取出qa.top()和qb.top(),相等则抵消,不等则取大者操作。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int suan(int x) //返回x的长度 { return log10(x)+1; } inline void solve() { // init cin>>n; priority_queue <int> qa, qb; rep(i,1,n) { int a; cin>>a; qa.push(a); } rep(i,1,n) { int b; cin>>b; qb.push(b); } //cal 2 int cnt=0; while(!qa.empty()) { int a=qa.top(), b=qb.top(); if (a==b) //相等——抵消 { qa.pop(); qb.pop(); } else if (a>b) //不等——取大的操作 { qa.pop(); qa.push( suan(a) ); cnt++; } else { qb.pop(); qb.push( suan(b) ); cnt++; } } //out ans = cnt; cout<<ans<<endl; return; }D. Letter Picking算法本质dp、思维(博弈论)思路推演思维题,特别还是博弈论,就一定得从小规律找起,推导到全局。部分简单的手动模拟: bb 平局 ab alice赢 ba alice赢 abba 平局 abcd alice赢可以看到,当长度大于2时,就没有一个相对简单的规律了。但是这道题有很明显的博弈论的意味,博弈论的精髓就在于,俩人各走一步为一个回合,以回合为单位推进转换——这里就和dp的状态转移对应上了,所以博弈论sg组合数的解决方法是用dp的方式呈现的。同时,通过大量的模拟,我们发现好像并没有bob赢的情况,猜测bob可能最多平局,于是开始推理。定理1:若只剩下2个不同的字符,则一定是alice赢。 定理2:若字符串是由一对一对组成的(aabbbbcc),那一定是平局。 bob能赢的唯一途径:所以最好能让bob在某次选择中先占得先机,最后剩下2个一样的字符,类似于——bacc,让alice选择b,bob选择a。 基于此,alice可以选择优先破坏成对的字符,使得最后剩下2个不一样的字符,这波坏了bob赢的途径。 所以,bob一定不会赢。推出bob一定不会赢,可以很好的简化代码逻辑。我们现在可以简单的定义,bob一心想着平局,alice一心想着不平局。因为只能从左边or右边拿字符,这个博弈论的可能性很低,将会比较好做。假设原字符串为abxxxxcd(xxxx表示偶数个未知字符)(橘色线条代表alice可以走的,蓝色线条代表bob可以走的)若abxxxxcd为平局,有两个可能:中间的bxxxxc为平局 && a==dxxxxcd平局 && a==b && abxxxx平局 && c==d其他则都是alice赢。上面这推理,其实也就是dp里的状态转移方程。若不推出bob的情况,也是可以做的,只是说逻辑会相对复杂。代码思路dp,从底层开始推理。维护cun[][]cun[l][r]=v表示[l,r],v=0表示未知,还需要自己去求,v=1表示这个点alice会赢,v=2表示会平局。然后用对长度为2的字符串节,对cun[][]初始化。接着长度依次增加2,通过状态转移方程计算。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int cun[maxn][maxn]; //cun[l][r]=v表示[l,r],v=0表示未知,还需要自己去求,v=1表示这个点alice会赢,v=2表示会平局,v=3表示bob会赢 inline void solve() { // init scanf("%s", ch+1); n = strlen(ch+1); // cal for (int i=1; i<=n-1; i++) //初始化 cun[i][i+1] = 1 + (ch[i]==ch[i+1]); for (int len=4; len<=n; len+=2) { for (int l=1; l+len-1<=n; l++) { int r = l+len-1; //状态转移方程(逻辑) if (cun[l+1][r-1]==2 && ch[l]==ch[r]) cun[l][r]=2; else if (cun[l][r-2]==2 && cun[l+2][r]==2 && ch[l]==ch[l+1] && ch[r]==ch[r-1]) cun[l][r]=2; else cun[l][r]=1; } } //out flag = cun[1][n]==1; if (flag) cout<<"Alice"<<endl; else cout<<"Draw"<<endl; return; }题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。题目算法本质思路推演代码思路ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
1 阅读
0 评论
0 点赞
1
...
15
16
17
18