首页
关于
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 930 (Div. 2)
Bitwise Operation Wizard算法本质思维题目大意存在长度n的排列p(0开始),现在需要找到下标i j,使得p[i]^p[j]的值最大。玩家至多可以进行3n轮以下询问:询问每次需要给出a b c d四个整数,会返回p[a] | p[b]于p[c] | p[d]的大小关系:小于、等于、大于思路推演4个整数的询问比较少见,变数比较多,所以我们反向思考——怎样的两个数异或值最大。举个例子,若n=14,异或最大值就是>=n的最小2的幂值,即16,显然较大的值是比较容易得到16的。如果我们使用a a b b的询问,显然n轮就可以得到谁是最大值p。接下来需要找到另外一个恰好的值:所有与p或是16的下标的最小值。这个讲起来比较玄学,但是没法,这种题就是不断发散思维一直碰撞ac核心代码下面代码对询问次数进行了一些压缩,属于没必要的优化。头文件、宏定义、快读模板、常见变量、常见变量等略。 char ask(int a, int b, int c, int d) { cout<<"? "<<a<<" "<<b<<" "<<c<<" "<<d<<endl; char ans; cin>>ans; return ans; } int getmax(const vector<int> &v) { int p = v[0]; for (int i=1; i<v.size(); i++) { if (ask(p, p, v[i], v[i]) == '<') p = v[i]; } return p; } int getmin(const vector<int> &v) { int p = v[0]; for (int i=1; i<v.size(); i++) { if (ask(p, p, v[i], v[i]) == '>') p = v[i]; } return p; } inline void solve() { cin>>n; vector<int> v(n); iota(v.begin(), v.end(), 0); int maxp = getmax(v); int last=(maxp==0?1:0); v.clear(); v.push_back(last); for (int i=last+1; i<n; i++) { if (i==maxp) continue; char c=ask(maxp, last, maxp, i); if (c=='<') last=i, v.clear(), v.push_back(last); else if (c=='=') v.push_back(i); } int q = getmin(v); cout<<"! "<<maxp<<" "<<q<<endl; return; }Pinball算法本质思维、数据结构题目大意给定由>和<组成的长度n字符串。如果小人现在处于>上,就会花费1秒向右移动一格,同时>会反转为<。现在请给出小人初始在1~n的情况,花费多少时间会掉出字符串。思路推演模拟一下,这个游戏实际很简单,可以改成这样:(初始时)小人左侧的>看作一个墙,<看作空地小人右侧的<看作一个墙,>看作空地小人脚下的字符表示初始行动方向小人遇到墙,会将墙撞碎(变为空地),然后向反方向行走我们想要知道小人多久出去,先得知道从哪边出去。需要判断一下小人左侧和右侧的墙的数目(使用前缀和),根据小人的初始方向就可以确定。这个时候我们可以得到2个值:撞碎左边墙的数目、撞碎右边墙的数目。现在需要计算撞碎这些墙所需要的时间。这个的解决方法有很多,我们可以维护一个花费时间的前缀和,然后使用数目前缀和+二分来确定位置,确定位置后使用时间前缀和得到时间。ac核心代码代码写的比较复杂,还没有优化就不放了。头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
14 阅读
1 评论
0 点赞
2024-08-26
Codeforces Round 931 (Div. 2)
Find a Mine算法本质思维题目大意矩阵地图中,有2颗地雷(坐标未知),玩家可以进行至多3次探测:制定一个坐标返回2颗地雷与坐标的曼哈顿值的较小值最后输出某颗地雷的坐标。思路推演矩阵中的曼哈顿值很有趣,如果在中间部分放置,其地雷可能存在的地方是一个正菱形。显然,如果我们在角落进行探测,可能的范围会缩小。进一步可以发现,如果在两个对角进行探测,则可以锁定两个地雷所在的斜线,在任意选一个位置探测即可。经验这类题其实比较典型,既然是3个操作,2个地雷,其过程很有可能是,通过前1-2次操作,可以获得两颗地雷的部分信息(两者的信息量是一致的),然后使用最后的操作获取某个地雷的所有信息。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int ask(int x, int y) { cout<<"? "<<x<<" "<<y<<endl; return in(); } bool ck(int x, int y) { if (x<1 || x>n || y<1 || y>m) return 0; return 1; } inline void solve() { cin>>n>>m; int d1=ask(1, 1), d2=ask(n, m), d3=ask(n, 1); set<pair<int,int>> cod; if ((d1+d3-n+1)%2==0) // 说明左侧上下有交点 { int rt = (d1+d3-n+1)/2; int y = rt + 1; int x = d1 - rt + 1; if (ck(x, y)) cod.insert({x, y}); } if ((d2+d3-m+1)%2==0) { int up = (d2+d3-m+1)/2; int x = n - up; int y = d3 - up + 1; if (ck(x, y)) cod.insert({x, y}); } if (cod.size()==2) { auto [x, y] = *cod.begin(); int dis = ask(x, y); if (dis) cod.erase({x, y}); else { cod.clear(); cod.insert({x, y}); } } auto [x, y] = *cod.begin(); cout<<"! "<<x<<" "<<y<<endl; return; }XOR Break --- Solo Version算法本质思维题目大意给定初始值x和目标值y,需要玩家进行至多63回合,最终使得x==y值:(以下2个操作记作1回合)将x分解成2个值a b,需要保证:a^b == xa < xb < x然后选择将a或者b赋值给x输出转换过程1 < y < x < 1e18思路推演既然我们最后会选择a或b进行赋值,这明显告诉我们,不用管另一个值,只需要保证其合法即可。为了之后方便叙述,我们这里强制保证a < b模拟一下分解过程,发现一个很不错的性质:若x的二进制位高的某几位1并非单独b的话,之后的所有二进制位都可以任意分配这个性质特别好,如果y是比较小的情况的话,我们可以先构建a为y的超集,然后再得到y。我们进行了更多的模拟,发现如果y的最高位不超过初始x的次高位(从高往低,第2个出现1的位),则可以如此构建。如果x仅有1位,显然不可行例如:(左边是高位) x = 101000 y = 000101 我们构建 a = y 如果y在x的次高位上没有值,则a=y+x次高位 a = 001101 b = x^a 同时这样会保证:b<x 且 a是y的超集接着我们考虑其他情况,如果y的最高位介于x的最高位和次高位之间,可以证明这样没有解。如果y的最高位同x的最高位一致,又因为保证了y<x——所以我们可以直接使得b=y, a=x^b,一步到位。63次操作属于障眼法ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int get_top(int x) { while (x > lowbit(x)) x-=lowbit(x); return x; } inline void solve() { int a, b, c; cin>>a>>b; int tar=b; c = a^b; if (get_top(a) == get_top(b)) { cout<<1<<endl; cout<<a<<" "<<b<<endl; return; } flag = 1; int val = a; val -= get_top(val); val = get_top(val); // 获取次高位的值 if (b >= val*2) // 如果介于高位和次高位之间,无解 { cout<<"-1"<<endl; return; } else if ((b&val)==0) // 有解,开始制造超集 b+=val, c-=val; if (b==tar) // 有可能超集刚好相等,所以一步到位 { cout<<1<<endl; cout<<a<<" "<<b<<endl; } else // 使用超集作为中间值 { cout<<2<<endl; cout<<a<<" "<<b<<" "<<tar<<endl; } return; }XOR Break --- Game Version算法本质思维、简单博弈题目大意(小改)玩家和系统进行博弈游戏,两者轮流执行以下操作:从a b两个值中选择一个作为x将x分解成2个值a b,需要保证:a^b == xa < xb < x如果无法分解,记作当前玩家输掉游戏初始系统给定的a b保证a==b(但是游戏过程中不一定会相等了)。玩家可以选择先手或者后手,需要在63回合内击败对手(自己行动才记作一个回合)。输出游戏过程。思路推演我们考虑,如果x值的二进制位仅有一个1,则显然无法分解,会失败。所有有两个1就是必胜态。但是当继续推理时,情况就十分复杂了——因为对手有2个选择。博弈论的一部分,需要我们观察到更加内核本质的变化,从而逼迫对手一直处于必败态。奇偶是一个比较常思考的方向,考虑到异或的特殊性,我们可以一直让对手的x处于由奇数个1组成,而我们的x由偶数个1组成。稍加模拟,发现可行。接下来我们需要在63回合获胜,就需要防止对手一直拖回合。考虑到单个1无法分解,于是对于x,我们可以把最高位的1作为a,剩余的值作为b,对手就会被迫选择b,这样每回合至少都减少了一个高位1,63回合绰绰有余。这题2400,不理解,从过题人数结合难度来看,大概2100-2200吧。因为当时标2400,思考简单博弈的时候,还自我否定,想着2400怎么可能一个简单博弈出来了。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int get_top(int x) { while (x > lowbit(x)) x-=lowbit(x); return x; } int get_num(int x) { int res=0; while (x) x-=lowbit(x), res++; return res; } void send(int x) { int a=get_top(x); int b=x-a; cout<<a<<" "<<b<<endl; } int recceive() { int a, b; cin>>a>>b; return (get_num(a)%2==0 ? a : b); } inline void solve() { int x; cin>>x; if (get_num(x)%2) cout<<"second"<<endl; else { cout<<"first"<<endl; send(x); } while (1) { x = recceive(); if (x==0) break; send(x); } return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
9 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 926 (Div. 2)
Sasha and the Casino算法本质思维题目大意玩家初始有a个硬币,可以选择进行任意回合游戏,每回合游戏规则如下:玩家选择y个硬币作为门票主办方直接决定玩家的胜负,如果玩家胜利会获得ky个硬币,反之什么得不到同时也有一条对主办方的限制:无法使得玩家连续失败x+1次。已知k x a,询问玩家是否可以赢得$100^{100^{100}}$个硬币。思路推演联想到“倍投法”。显然这个游戏规则十分适合倍投,因为在x+1回合里必然有胜利。但不同的是,玩家胜利获得的硬币数是ky而不一定是2y。这引导我们深入一些思考倍投的内涵。显然我们以每次胜利作为一个阶段,我们仅需保证每个阶段都不亏钱即可——保证每次的收益都可以覆盖之前的损失,同时保证投的钱最少即可。检查复杂度,可行。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { int k, x, a; cin>>k>>x>>a; int pre=0; flag = 1; for (int i=1; i<=x+1; i++) { int y = (pre + k-2) / (k-1); y += (pre % (k-1) == 0); pre += y; if (pre > a) { flag = 0; break; } } cout<<(flag?"YES":"NO")<<endl; return; }Sasha and a Walk in the City算法本质思维、dp题目大意给定树结构,节点初始全白,玩家可以给任意节点涂黑,如果涂色后树结构满足任意一条简单路径上黑点数目<=2则称之为美丽。输出玩家可以创造的美丽树结构数目。思路推演很显然的树形dp题目,所以从树形dp的角度去思考,可以缩小方法。如果要记录中途点u状态,我们仅能记录点u到其子树的任意一条简单路径上的最多黑点数目。构建dp[u][i]表示:点u到其子树的任意一条简单路径上的最多黑点数目为i个的方法数。dp[u][0]显然只能为1。dp[u][1],考虑两种情况:u是黑色和u非黑色。dp[u][2],考虑两种情况:u是黑色和u非黑色。具体的公式看代码ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 void dfs(int u, int fr, vector<vector<int>> &g, vector<int> &dp1, vector<int> &dp2) { for (int v:g[u]) { if (v==fr) continue; dfs(v, u, g, dp1, dp2); dp1[u] = dp1[u] * (dp1[v]+1) % mod; dp2[u] += dp1[v] + dp2[v]; dp2[u] %= mod; } } inline void solve() { cin>>n; vector<vector<int>> g(n+5); vector<int> dp1(n+5, 1), dp2(n+5); for (int i=1; i<n; i++) { int u, v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0, g, dp1, dp2); int ans = 1 + dp1[1] + dp2[1]; ans %= mod; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
6 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 924 (Div. 2)
Lonely Mountain Dungeons算法本质思维、数学、三分题目大意给定整数b x,有n种士兵,c[]表示每种士兵的数目。玩家需要将所有士兵分成k支队伍:(k由玩家指定)分成k支队伍花费(k-1)*x若某2个士兵属于同兵种且不在同一支队伍,则收益b输出最大收益。思路推演首先想到的就是,士兵如何分队才能收益最大。显然每种士兵之间互不打扰,然后就是没有任意同种士兵同一队伍,这肯定可以收益最大,但是同理我们需要付出更多的成本。但是这是一种思考方式,我们可以假设最初得到所有士兵的收益,若有同种士兵同队就扣去收益,这样计算显然更方便。退而求其次,我们考虑对于一种士兵,有a个分配到k个队伍中。隐约觉得平摊分是最合理的,我们可以来证明。证:若存在a个同种士兵面对k支队伍,尽可能平摊分配是最优解。 平摊分配的意思是: a%k 支队伍有 a/k+1 人 k-a%k 支队伍有 a/k 人 我们使用反证法: 对于任意一种非平摊分配法,都可以视作在平摊仅执行任意次以下操作: * 选择2支队伍,其人数分别是a b,保证a>=b,将其人数更改为a+1 b-1 接下来我们证明,执行这个操作会导致收益降低或不变 对于任意一支有c同种人数的队伍,其收益会降低:f(c)=c(c-1)/2 所以实际上就是证明 f(a)+f(b) <= f(a+1)+f(b-1) 自行计算即可,实际上最后发现是必定小于的,没有等于情况我们可以得到公式:$f(x)=\frac{x*(x-1)}{2}$$sum = \sum_{i=1}^nf(c_i)*b$$cost(k) = (k-1)*x + b*( (k-c_i\%k)*f(c_i/k) + (c_i\%k)*(c_i/k+1) )$$ans(k) = sum - cost(k)$注意公式中的除法表示向下整除所以我们实际上是需要找到一个k来最小化ans。其中sum的值是固定的,观察cost(k),这个函数由2部分组成,一部分是递增的线性函数,另一部分是递减双曲线函数的平方。显然这可以使用三分搞定。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn]; int f(int x) { if (x<=0) return 0; return x*(x-1)/2; } int g(int k, int b, int x) // 注意这个计算的是负收益 { int res = (k-1)*x; for (int i=1; i<=n; i++) res += b*( (k-a[i]%k)*f(a[i]/k) + (a[i]%k)*f(a[i]/k+1) ); return res; } int tri_search(int l,int r, int b, int x) { // 求凹函数的极小值 int f1, f2; while(l < r) { int lp = l + (r - l) / 3; int rp = r - (r - l) / 3; f1 = g(lp, b, x), f2 = g(rp, b, x); if(f1 <= f2) r = rp - 1; else l = lp + 1; } //查找的是极小值 return min(f1,f2); //查找的是极小值对应的下标 return f1<f2?l:r; } inline void solve() { int b, x; cin>>n>>b>>x; for (int i=1; i<=n; i++) cin>>a[i]; sort(a+1, a+1+n); int cost = tri_search(1, a[n], b, x); int ans=0; for (int i=1; i<=n; i++) ans += f(a[i])*b; ans -= cost; cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
4 阅读
0 评论
0 点赞
2024-08-26
Codeforces Round 922 (Div. 2)
Blocking Elements算法本质思维、二分、dp题目大意(改)给定长度n数组a[],玩家可以选择任意个元素涂成黑色:res1值为将所有黑色元素值之和2个相近黑色元素之间的元素(不含黑色元素)为一组,剩余的若干组,其中元素和最大值计为res2值输出最小化的max(res1, res2)值。n <= 1e5思路推演通常来说,这样的“最小化最大值”和“最大化最小值”的题目,我们可以首先尝试一下二分思路,其可以在增加log复杂度情况下多提供一个条件。当我们获取到当前回合的上限值时,有2个目标:每组元素和 < 上限值选择元素和 < 上限值用贪心的思路去想的话,会发现情景十分复杂,很难获取最优解。所以转变思路使用dp去处理。dp条件十分明显,dp[x]=y可以表示对于1~x来说,x必涂黑的情况下已经涂黑元素和值为y。因为有2个目标,所以肯定是需要维护一个、力求保证另一个,这里我们选择维护每组元素和,最后检查选择元素和。可以使用优先队列来解决,代码相对简洁,不懂可以看一下代码。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int a[maxn], dp[maxn], pre[maxn]; inline void solve() { cin>>n; for (int i=1; i<=n; i++) cin>>a[i], pre[i]=pre[i-1]+a[i]; a[n+1] = 0; // 为了方便就直接使用dp[n+1],其需要保证a[n+1]为0 int l=1, r=1e13; int ans=r; while (l<=r) { int mid=(l+r)/2; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q; q.push({0, 0}); // {val, idx} for (int i=1; i<=n+1; i++) { while (q.size() && pre[i-1] - pre[q.top().second] > mid) // 保证中间 q.pop(); dp[i] = a[i] + q.top().first; q.push({dp[i], i}); } if (dp[n+1]<=mid) { r=mid-1; ans=mid; } else l=mid+1; } cout<<ans<<endl; return; }title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 title算法本质题目大意思路推演ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。
2024年08月26日
6 阅读
0 评论
0 点赞
1
2
...
18