首页 > 其他分享 >Codeforces 983 A-E

Codeforces 983 A-E

时间:2024-11-09 14:41:04浏览次数:1  
标签:分数 frac 进制 983 Codeforces 题目 oplus 有限小数

题解

A

难度:黄
算法标签:数学、进制
题目翻译:给定进制 \(b\) 和分数 \(\frac{p}{q}\),求这个分数在 \(b\) 进制下是否是有限小数。
题目分析:
首先将分数化简(不用说了)。接下来有命题:若 \(/frac{1}{q}\) 为有限小数,则 \(/frac{p}{q}\) 必然为有限小数。且逆命题、否命题成立。证明略。
不难看出,若 \(b\) 包含 \(q\) 中的所有质因数,则该分数为有限小数,否则为循环小数。但暴力分解质因数的复杂度为 \(O(\sqrt{n})\) 无法通过这道题。因此考虑优化。这里可以使用 q /= GCD(p, b) 代替。

B

难度:蓝
算法标签:动态规划
题目翻译:
在一个长度为 \(m\) 的数组 \(b\) 中定义函数 \(f\):

\[f(b) = \begin{cases} b[1] & \quad \text{if } m = 1 \\ f(b[1] \oplus b[2],b[2] \oplus b[3],\dots,b[m-1] \oplus b[m]) & \quad \text{otherwise,} \end{cases} \]

例如:

\[\begin{aligned} f(1,2,4,8)& = f(1\oplus2,2\oplus4,4\oplus8) \\ &=f(3,6,12)\\&=f(3\oplus6,6\oplus12)\\&=f(5,10)\\&=f(5\oplus10)\\&=f(15)\\&=15 \end{aligned} \]

现在,有一个长度为 \(n\) 的序列 \(a\),给了 \(q\) 组询问,请计算 \(a_l, a_{l+1}, \ldots, a_r\) 的所有连续子序列 \(\{b\}\) 中,\(f(b)\) 的最大值为多少。

题目分析:\(O(n^2)\) 预处理 \(f\) 每一层的值,然后递推,用 \(d[i][j]\) 表示以 \(i\) 为起点长度为 \(j\) 的最大值,然后 \(O(1)\) 查询。直接做就做完了。

C

难度:紫(未完)

标签:分数,frac,进制,983,Codeforces,题目,oplus,有限小数
From: https://www.cnblogs.com/chenaknoip/p/18536434

相关文章

  • Educational Codeforces Round 159 (Rated for Div. 2) - VP记录
    Preface重点策略:\[\large\textbf{\underline{先写简单好写的算法,再逐步修改优化}}\]十分有效,百试百灵,屡试不爽。A.BinaryImbalance当有相邻两字符不相等时,就可以不断向中间插入0。所以输出NO当且字符串全为1。点击查看代码#include<cstdio>usingnamespacestd;......
  • Codeforces 909 A-F
    CF909题解题目链接ABCDEF难度:红黄绿蓝绿紫题解A题目翻译:给定两个字符串,求字典序最小的“两字符串非空前缀拼接形成的字符串”。算法标签:贪心题目分析:字典序最小,即从左往右依次比较字符,直到一方不剩字符或两字符不同。因此想到贪心。由于前缀非空,因此在前一字......
  • Codeforces Global Round 27
    Preface这场其实是上周六VP的,但因为后面连着好几天组队训练就一直没补题,拖到今天才补这场VP的时候写了A~E,F感觉会了但是急着吃饭就跑了,今天写了下F发现贼好写写完就过了,亏麻了A.Sliding签到,手玩下式子即可#include<cstdio>#include<iostream>#defineintlonglon......
  • Codeforces Round 982 (Div. 2)(A~C)
    对dp还不是特别熟练只做到了C(还是太菜了),开始前刚好各种事情来了,vp晚了10多分钟开才始做题,喜提排名(不是)3000+,后面有时间就尽量把dp补掉A.RectangleArrangement你需要在一个无限的方格网格上涂色,所有格子最初都是白色的。为了完成这项任务,你有\(n\)个印章。每个印章是一个......
  • Educational Codeforces Round 161 (Rated for Div. 2) - VP记录
    Preface先被A题硬控\(20\)分钟,有点不爽。又看到E题AC的人比D题多而去嗑E题去了,结果D题反而是我更能做的。将问题排序:根据你所需付出的努力,将能够最快解决的问题排在前面。(答题的次序为:以前做过的,容易的,不熟悉的,难的)——李博杰《骗分导论》\(\rmP_{114}\)所以......
  • Codeforces Round 983 (Div. 2) 10.31 ABC题解
    CodeforcesRound983(Div.2)10.31题解A.Circuit数学(math)贪心(greedy)模拟(implementation)题意:有\(n\)盏灯,对应\(2\astn\)个开关,即每盏灯对应两个开关,开关打开或者关闭用\(1\)和\(0\)表示。给出\(2\astn\)个开关的状态,需要求解出可能开灯的最小数量和最大数量。......
  • Educational Codeforces Round 171 (Rated for Div. 2) 题解
    A.PerpendicularSegments显然构造一个\(k\timesk\)的左下角是原点的正方形即可。voidslv(){ intx,y,k;Read(x,y,k); intmn=min(x,y); if(mn*mn*2>=k*k) Write(0,'',0,'',mn,'',mn,'\n'), Write(0,......
  • Codeforces Round 984 div3 个人题解(A~F)
    CodeforcesRound984div3个人题解(A~F)Dashboard-CodeforcesRound984(Div.3)-Codeforces火车头#define_CRT_SECURE_NO_WARNINGS1#include<algorithm>#include<array>#include<bitset>#include<cassert>#include<cmath>#in......
  • Codeforces Round 983 (Div. 2) 题解
    CodeforcesRound983(Div.2)题解CodeforcesRound983(Div.2)Problem-A-Codeforces解题思路考虑贪心,每个灯连两个开关,即两个开的灯可以关闭一盏灯,则灯数最多则尽可能让两个开关都开的灯尽量少,灯数最少则反之#include<bits/stdc++.h>#defineendl'\n'usingnam......
  • Codeforces Round 983 (Div. 2) A~D
    链接:CodeforcesRound983(Div.2)A:Circuit大意:    n个灯,每个灯连两个开关,每个开关只连一个灯,每个灯对应的两个开关如果异或为1就亮    现给定开关状态,求灯亮的最大和最小数量思路:    求最小数量的话,将开关为1的尽量组一起,我们发现,如果开关为1的......