首页
关于
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 921 (Div. 2)
Good Trip算法本质思维、概论题目大意有n个孩子,其中有m对朋友,每对朋友有一个初始的友情值。初始分数为0,接下来会进行k轮游戏,每轮游戏会随机选择2个孩子,如果这2个孩子是朋友:这对朋友的友情值+1获得这对朋友友情值的分数如果不是朋友,则无事发生输出最后分数的期望值。(mod 1e9+7)n,m <= 1e5 k <= 2e5思路推演分数的增加首先需要发生在朋友上,所以我们可以将$\frac{n*(n-1)}{2}$种情况为了m种朋友情况和其他。我们将分数的获取分成两类,初始值友情分数和后续增加的友情分数,即这2个子问题:如果规则中,友情值不会改变如果规则中,友情值都默认为0第一个问题易于解决,简单的平均值可以搞定。对于第二个问题,这是一个比较经典情景,我们以单对朋友的视角来看,如果抽中他们x次,则收益是$\frac{x*(x-1)}{2}$,每次抽中的概论$p=\frac{2}{n(n-1)}$,一共抽k轮,则期望收益就是:$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}\frac{i*(i-1)}{2}$这是单对朋友的期望收益,我们乘以m就可以得到所有朋友的增加友情分数的期望收益了。思路推演 - 进阶实际上这道题仍然有发挥空间:$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}\frac{i*(i-1)}{2} * 2= \sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i^2 - \sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i$$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i$是二项式分布的期望$E(x)$,我们可以使用kp来O(1)计算。$\sum_{i=0}^k\C_k^ip^i(1-p)^{k-i}i^2$也可以看作是其的一种简单变形$E(x^2)$,根据概率论中的知识,使用$E(x^2) = D(x)+E(x)^2 = kp(1-p)+k^2p^2$来O(1)计算。所以实际上可以做到O(t)的复杂度(因为有多组数据),虽然在这道题上没有意义。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 912 (Div. 2)
Maximum And Queries (hard version)算法本质思维、dp题目大意给定长度n的数组a[],接下来有q轮询问(询问之间独立),每次会给出k,玩家可以至多进行k次操作:选择数组a[]某个元素使其值+1输出最大化a[]所有值的按位AND值。a[] n q <= 1e6 k <= 1e18思路推演这个题十分有意思,让我们先来发散一下思维:每次操作需要在根号级别的复杂度下输出答案,所以肯定需要离线做或者预处理AND方式的求和,让我们按位思考,且具备贪心属性(如果可以选择更大的二进制位,则选择更大的)随便拿些样例模拟一下,发现一个特征,就是如果有二进制(左侧为高位):10010、101、1,如果答案能选择的最高位暂时是二进制第三位,即100,则观察第一个和第三个数,其在二进制第三位上都是0,贪心地想,我们可以理解为其选择后的值变成了0。顺着这个思路想,如果我们已知ans的值和某个元素的值a[i],是可以计算出a[i]需要的最少操作数的:找到二进制下的最高位,满足:a[i]这一位是0,ans这一位是1,假设这是二进制的第x位(注意这里的x是1下标开始的)如果不存在,花费即是0如果存在x,设变量$mask = 2^x-1$花费是:$cost_i = (ans \& mask) - (a_i \& mask)$这是一种逆向的思维,因为已知k和a[]来直接求ans比较困难。一个比较顺畅的想法是,预处理出所有的ans即可。注意观察a[]的值,其在1e6以内,但是k很大。如果$k + \sum_{i=1}^n a_i \ge n * 2^{20}$,那就可以说明所有的a[]值都是会被利用到的,可以使用$\left \lfloor \frac{k + \sum_{i=1}^n a_i}{n} \right \rfloor $来求解。反之,则最终答案一定小于2^20^,我们仅需处理2^20^以内的所有ans值即可,接下来构建dp。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Educational Codeforces Round 157 (Rated for Div. 2)
Torn Lucky Ticket算法本质思维角度题目大意有若干由数字组成的短字符串(长度<=5),现在选择2个字符串(可以重复选择一个字符串),将其拼接得到字符串s,定义幸运s:注意不同的拼接方式算两种,但是重复选择一个字符串拼接方式只能算一种s.length()为偶数s前半部分的数字和等于后半部分数字和计算有多少种拼接方式可以组成幸运字符串。思路推演显然,我们看对于某个字符串s来说,我们希望在其身上提取出一些特征来进行匹配。如果对于字符串123,这些字符串可以和它匹配:右侧匹配:长度1、数字和为0长度3、数字和为6左侧匹配:长度1、数字和为4长度3、数字和为6但显然,我们可以写一个长度5的字符串来与其匹配。这里就发现了规律,对于幸运字符串来说,用长的字符串去找短的字符串是一个优解。我们构建一个映射(字符串长度, 字符串数字之和) --> 个数。然后匹配即可,注意同样长度需要特殊一点,别计算重复了。XOR Construction算法本质思维题目大意给定数字n,还有长度n-1的数组a[],我们需要构建一个长度n的排列p[](排列值为0~n-1),需要满足:p[i-1]^p[i] == a[i]题目保证有解。思路推演稍加模拟可以发现,每改变一个元素的值,所有元素的值都会被影响。我们可以先随意让p[1]=0,然后通过a[]求得p[]。p[]的所有元素异或某个值来满足答案。实际这个题是看题解才想到的,后面的思路是题解的既然可以改变二进制位,我们也从二进制位上观察最后的p[],其每个二进制位上的01个数是一定的。所以我们只需要检查二进制位,如果不满足就异或这一位。题目保证有解还剩下一个问题,如果这个二进制位的01数目一致,则我们如何判断是否该改。稍加模拟或者思考,即可发现改不改不影响最后的答案。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n; vector<int> v(n); for (int i=1; i<n; i++) // 给v[0]=0 { int x=in(); v[i] = x^v[i-1]; } for (int i=0, val=1; i<=30; i++, val*=2) { int cnt=0; for (int j=0; j<n; j++) cnt += (val & j) > 0; for (int j=0; j<n; j++) cnt -= (val & v[j]) > 0; if (cnt!=0) // 数目不对 { for (int j=0; j<n; j++) v[j] ^= val; } } for (int x:v) cout<<x<<" "; return; }Infinite Card Game算法本质思维题目大意A有n张卡、B有m张卡,每张卡有2个属性:攻击值和防御值。接下来有2个设定:桌面上至多存在一张卡x,如果希望使用另一张卡y击退它,必须y的攻击值严格大于x的防御值如果卡y击退了卡x,则卡x会退回给它的主人,卡y会留在桌上初始时,A会随机选择一张卡放在桌上,然后BA轮流行动,如果谁无法击退敌人的卡则算失败。现在计算A胜利、平局、失败的概论,为了方便输出将其乘以n。思路推演勇气,即是信念游戏有卡牌回收机制,这表明了每次战斗不需要留手,应该选出自己最强的卡牌:能够击败敌人的卡牌,且防御值最高(当攻击值超过敌人的防御时,攻击值就没有了意义。)我们先思考A可以胜利的情况,需要掏出防御力最强的卡牌,且对手无计可施。我们可以给这张卡牌涂上金色表示其掏出必胜。如果掏出任意一张卡牌,在对手给予回击后,我们可以掏出一张金色的卡牌,则当前卡牌为金色。这显然是图的传播方式,同时由于存在贪心思路,我们可以预处理我们每一张卡牌使用之后,对手的策略,然后检查我们是否可以使用金色卡牌。在脑海中模拟这个预处理的时候有所察觉,也许代码不需要写这么复杂。为了使得预处理,我们需要将A的卡牌防御值升序,B的卡牌攻击值升序,这有一个小结论:A的金色卡牌一定是一个后缀区间(使用防御值升序时)证:A的金色卡牌一定是一个后缀区间(使用防御值升序时) 反证法,假设存在金色卡牌不是一个后缀区间,则一定存在两张牌a b,其中a是金色卡牌,b非金色卡牌,且防御值:b>=a B用某张卡牌击退b时,A可以采取面对“B用某张卡牌击退a时”的相同策略。鉴于此,我们可以双指针搞一下即可。随后为了方便,来计算A失败的卡牌数目,则一定是B有一张强力的防御卡牌。于是我们可以同样方式求得B的金色卡牌,如果A的第一轮出的牌,B可以使用金色卡牌应对(取最大攻击值即可),则A注定失败。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 // 防御优先 bool cmp(pair<int,int> p1, pair<int, int> p2) { if (p1.second == p2.second) return p1.first < p2.first; return p1.second < p2.second; } inline void solve() { vector<pair<int,int>> v1, v2; cin>>n; v1.resize(n); for (int i=0; i<n; i++) cin>>v1[i].first; for (int i=0; i<n; i++) cin>>v1[i].second; cin>>m; v2.resize(m); for (int i=0; i<m; i++) cin>>v2[i].first; for (int i=0; i<m; i++) cin>>v2[i].second; sort(v1.begin(), v1.end(), cmp); // v1防御优先 sort(v2.begin(), v2.end()); // v2攻击优先 int hackmax = 0; // 表示目前已经确定的金色卡牌的最大攻击值 int defenmax = -1; // 对手面临当前情况会出的牌,其中的最大防御值 // 初始的-1值是为了让初始的hack > defen int p2 = v2.size()-1; int p1; for (p1=v1.size()-1; p1>=0; p1--) { while (p2>=0 && v2[p2].first>v1[p1].second) // p2这张牌可以击败p1 defenmax = max(defenmax, v2[p2].second), p2--; if (hackmax <= defenmax) // 如果打不过对面 break; hackmax = max(hackmax, v1[p1].first); } // [p1+1 ~ v1.size()-1] 为金色卡牌 int num_win = n - (p1+1); // 必胜的次数 sort(v1.begin(), v1.end()); sort(v2.begin(), v2.end(), cmp); hackmax = 0; defenmax = -1; p1 = v1.size()-1; for (p2=v2.size()-1; p2>=0; p2--) { while (p1>=0 && v1[p1].first>v2[p2].second) defenmax = max(defenmax, v1[p1].second), p1--; if (hackmax <= defenmax) break; hackmax = max(hackmax, v2[p2].first); } // [p2+1 ~ v2.size()-1] 为金色卡牌 int num_lose=0; for (auto [x, y] : v1) if (y < hackmax) num_lose++; int num_draw = n - num_win - num_lose; cout<<num_win<<" "<<num_draw<<" "<<num_lose<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
0 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 906 (Div. 2)
Doremy's Connecting Plan算法本质思维题目大意给出n个点(暂时没有边),每个点有点值,若某2个点满足以下条件则可以连接一条边:对于第i个点和第j个点,若i点和j点的连通块的所有点值 >= i * j * c(c是给定的常数)输出是否可以使得图为连通块。思路推演首先想到是同点1连接,但是似乎不一定,于是来展开证明:证明: 若有两个非1点u v,若其可以连接成功,则一定存在某个点可以与1连接成功。 使用反证法。 若两点可以连接成功,可以写出式子: a[u] + a[v] >= u*v*c 若两点不可同1连接成功,可以写出式子: a[u] + a[1] < u*c a[v] + a[1] < v*c 由于u>1 v>1,则可以得出: 所以显然 a[u] + a[v] >= u*v*c >= u*c+v*c > a[u] + a[v] + 2*a[1] 可以看出存在问题,所以得证。这说明了,我们可以优先处理同1连接的情况,而且由于其仅需要连通,所以我们仅处理同1连接的情况。每个点同1连接的难度是固定的,所以可以用一个优先队列来处理即可。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>k; vector<int> a(n+5); read(a, 1, n); int sum=a[1]; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q; for (int i=2; i<=n; i++) q.push({i*k-a[i], i}); flag = 1; while (q.size()) { auto [cha, id] = q.top(); q.pop(); if (cha>sum) // 如果钱不够 { flag=0; break; } sum += a[id]; } cout<<(flag ? "Yes" : "No")<<endl; return; }Doremy's Drying Plan (Easy Version)算法本质思维题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
1 阅读
0 评论
0 点赞
2024-08-26
Educational Codeforces Round 156 (Rated for Div. 2)
Decreasing String算法本质思维题目大意给定由小写字母组成的字符串s和正整数p。存在一个空字符串,接下来做如下操作直至s为空:res = res+s删去s的一个字符,保证其删除后尽可能字典序小输出res[p]。思路推演此题的核心是找到每次操作的本质。通过思考可以发现,在每次仅删一个字符且保证删除后字典序小,其就是删除s第一个上升序列的最后一个元素。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { string s; int p; cin>>s>>p; n=s.length(); queue<char> q; for (char c:s) q.push(c); q.push('a'-1); // 方便后续 string res; int len=n; while (res.size()==0 || res.back()<=q.front()) // res为s中上升子序列部分 res.push_back(q.front()), q.pop(); while (p > len) { p -= len; len--; res.pop_back(); while (res.size()==0 || res.back()<=q.front()) // 维护res res.push_back(q.front()), q.pop(); } while (q.size()) // 注意这里需要将所有字符都放入res res.push_back(q.front()), q.pop(); char ans = res[p-1]; cout<<ans; return; }Monocarp and the Set算法本质思维题目大意玩家可以构建长度n的排列,初始存在一个长度n-1的字符串s来表示一些规则:s[i] == '>'第i+1个元素大于前i个元素s[i] == '<'第i+1个元素小于前i个元素s[i] == '?'第i+1个元素不能处于以上两种情况接下来有m次询问,每次询问会修改s的某个字符值,每次修改后玩家需要回答符合规则的排列数目。(特别输出没有修改的合法排列数目)思路推演此题思路简单,核心在于认知,模拟过程中会发现,其规则与相对位置息息相关,从这个角度入手在模拟过程中,可以发现,在出现?之前,元素的相对位置是固定的。当第i位出现问号时,则表示已有i个元素相对位置确定,现在需要添加第i+1个元素并且符合?规则,则有i-1种填法。而且当前问好填入后,也可以视作相对位置确定。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { string s; cin>>n>>m>>s; s = " " + s; int ans=1; for (int i=2; i<=n-1; i++) if (s[i]=='?') ans *= i-1, ans%=mod; cout<<ans*(s[1]!='?')<<endl; while (m--) { int p; char c; cin>>p>>c; if (s[p]!='?' && c=='?' && p!=1) ans *= p-1, ans%=mod; else if (s[p]=='?' && c!='?' && p!=1) ans *= qpow(p-1, mod-2, mod), ans%=mod; s[p] = c; cout<<ans*(s[1]!='?')<<endl; } return; }I Wanna be the Team Leader算法本质思维、dp题目大意存在n个员工和m个项目,目标完成所有项目,玩家可以按下列规则分配员工:员工有能力值a[]项目有难度值b[]当某个项目的当前项目员工数目 * 当前项目员工中最小能力值 >= 项目难度时,项目可以完成(员工数目不可为0)员工至多去一个项目输出项目的分配情况。n <= 2e5 m <= 20思路推演通过模拟可以知道,员工的顺序无意义,可以将a[]有序排列。然后可以贪心知道,某个项目的最优解一定是选择连续的员工(a[]值相近的),这给dp做法提供了方便。再通过一些细节,可以发现贪心不可行,唯有dp。其中最核心的问题是:无法确定项目解决的顺序。但是m=20这给提供了一个思路——通过状态压缩来无视顺序dp。于是可以构建dp[x]=y表示项目状态x时最少用了a[1~y]。然后枚举当前状态处理的项目即可转移。转移需要O(1),因为对于某个项目,可能[1~4]和[2~3]两种方式都是可行的,所以需要预处理一下。(详细看代码)还有一个问题是最后需要输出状态,所以维护一下路径方便后续状态的查找。(这个也主要是代码细节)笔者赛时没出,因为把dp的复杂度想成了2^m^ * n,这里以后需要注意。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { cin>>n>>m; vector<int> a(n), b(m), rank_id(n); for (int i=0; i<n; i++) cin>>a[i], rank_id[i] = i; for (int i=0; i<m; i++) cin>>b[i]; sort(rank_id.begin(), rank_id.end(), [&](int x, int y) { return a[x] < a[y]; }); vector<vector<int>> to(m+5, vector<int>(n+5, 1e9)); // tor[i][l] = r表示对于第i个项目,如果其使用l作为开始,则最少需要到r for (int i=0; i<m; i++) { for (int l=0; l<n; l++) { int base=a[rank_id[l]]; int len=(b[i] + base - 1) / base; to[i][l] = l + len - 1; } for (int l=n-1; l>=0; l--) // 可能不会选择较小数 to[i][l] = min(to[i][l], to[i][l+1]); } vector<int> dp(1<<m, 1e9); // dp[x]=y表示项目状态x时最少用了前1~y个元素 vector<int> path(1<<m); // path[x]=y表示项目状态x时,上一次搞定的项目下标 dp[0] = -1; // 注意是0下标,所以初始值为-1 for (int i=0; i<1<<m; i++) { if (dp[i]>=n) continue; for (int j=0; j<m; j++) { if (i>>j & 1) continue; // 说明第j项目已经搞定 if (to[j][dp[i]+1] > n) continue; // 超出n了 if (dp[i | (1<<j)] > to[j][dp[i]+1]) { dp[i | (1<<j)] = to[j][dp[i]+1]; path[i | (1<<j)] = j; } } } if (dp[(1<<m) - 1] >= n) { cout<<"NO"<<endl; return; } cout<<"YES"<<endl; vector<vector<int>> ans(m); int v = (1<<m) - 1; while (v) { int id=path[v]; // 处理第id个项目 int val = (1<<id); int u = v ^ val; // u状态 --> v状态 int l=dp[u]+1, r=dp[v]; for (int i=r; i>=l; i--) // 检查第id个项目用了哪些元素 { ans[id].push_back( rank_id[i] ); if (a[rank_id[i]]*(r-i+1) >= b[id]) // 区间[l,r]对第id个项目可行,一定是某个后缀 break; } v = u; } for (auto vv:ans) { cout<<vv.size()<<" "; for (int x:vv) cout<<x+1<<" "; // 题目需要1下标,这里+1 cout<<endl; } return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
1 阅读
0 评论
0 点赞
1
2
3
...
18