codeforces 50题精选训练
本章节部分参考:2020,2021 年 CF 简单题精选 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
T1:Problem - B - Codeforces
首先，很容易观察到点的一些特征:
- 都在第一象限；
- 点的分布越来越稀疏。
以样例为例：
还有无限个点没有画出来。
根据点的分布越来越稀疏的特性，能不能发现收集点的规律呢？
比如我们可以先枚举一个点 \(i\)，直接从 \((x_s, y_s)\) 出发去收集 \(\text P_i\)。
然后呢？如果往 \(\text P_0\) 的方向收集，点会非常密集；如果往 \(\text P_\infty\) 的方向收集，点就会非常稀疏。
当然，我们往 \(\text P_0\) 的方向收集！
但是，这边的点是有限的，如果全部收集完了时间还绰绰有余呢？
那就原路返回，再往 \(\text P_\infty\) 的方向收集！
有人可能会疑惑，为什么这里都原路返回了，答案还是最优呢？
首先，因为随着 \(j\) 的增大，\(x_j, y_j\) 都在增大，所以 \(\sum_{j = 1}^{i}\operatorname{dist}(\text P_{j-1}, \text P_j)\)（也就是从 \(\text P_i\) 收集到 \(\text P_0\) 的总距离）就等于 \(\operatorname{dist}(\text P_0 ,\text P_i)\)（\(\operatorname{dist}\) 表示曼哈顿距离）。
下面为了分析方便只看 \(x\) 坐标（\(\operatorname{Xdist}\) 表示 \(x\) 坐标之差）。
点最密集的时候应该是什么时候？很显然，\(a_x\) 和 \(b_x\) 都最小的时候，也就是 \(a_x = 2, b_x = 0\)。
\[ \operatorname{Xdist}(\text P_{i+1}, \text P_{i}) = (a_x \cdot x_{i} + b_x) - x_{i} = (a_x - 1)\cdot x_{i} + b_x = x_i \]
\[ \operatorname{Xdist}(\text P_{0}, \text P_{i}) = x_i - x_0 \]
\(\because x_0 \ge 1 \quad \therefore \operatorname{Xdist}(\text P_{i+1}, \text P_{i}) > \operatorname{Xdist}(\text P_{0}, \text P_{i})\)
现在 \(y\) 坐标也加进来，就可以得到 \(\operatorname{dist}(\text P_{i+1}, \text P_{i}) > \operatorname{dist}(\text P_{0}, \text P_{i})\)。
这说明什么？收集 \(\text P_0 \sim \text P_{i - 1}\) 的时间比只收集一个 \(\text P_{i + 1}\) 的时间还要少！
如果当初选择向右走，那再去收集 \(\text P_{i + 2}\) 的时候，显然 \(\operatorname{dist}(\text P_{i+1}, \text P_{i +2}) > \operatorname{dist}(\text P_{i}, \text P_{i+1})\)，那么 \(\operatorname{dist}(\text P_{i+1}, \text P_{i +2}) + \operatorname{dist}(\text P_{i}, \text P_{i+1}) > 2 \operatorname{dist}(\text P_{0}, \text P_{i})\)。说明向 \(\text P_{\infty}\) 方向收集 \(2\) 个点的时候，\(\text P_0\) 方向已经回来了，并收集了 \(i\) 个点，如果 \(i \ge 2\) 那么直接可以知道答案更优了，还剩两种情况：
- \(i=0\)，这时没什么左右之分，那不影响答案；
- \(i=1\)，直接带入算一算，\(x_1 = 2 x_0\)，\(x_2 = 4 x_0\)，那么左边加上返回的时间是 \(2 x_0\)，直接去 \(\text P_2\) 的时间也是 \(2 x_0\)，因为越往后点越稀疏，而两种方案当前耗时相同，起点不同，所以 \(\text P_0\) 方向还是更优。
还有一个小问题，就是数组开多大，因为 \(2^{64} > 10^{18}\)，所以数组开到 \(70\) 就绰绰有余了。
时间复杂度 \(\mathcal O(n^2)\)，\(n\) 是要用到的点数，算到 \(x_n > x_s, y_n > y_s, \operatorname{dist}(\text P_n, \text S) > t\) 即可。
//https://codeforces.com/contest/1292/problem/B /* 38 70 2 2 67 88 6838924170055088 456766390500883 9176106261147424 调了半天,最终还是A了 由数据范围可知道,由于数据点是以指数级增长的,所以最多有2^64>=10^16,也就是顶多64个 然后 由于数据点一共就64个,不难想到暴力枚举,我认为比较难的地方就在于如何去枚举,如果 我们真的是纯暴力的话,每个点有选或不选,那么就是2^64,肯定不行 由于数据点是指数级爆炸增长,所以说可以这样想,假设原点在某两点之间,那么我们要先把左边的遍历完再遍历右边 可以想 2^0+2^1+....2^n-1相加,他们的和 是不如 2^n大的,所以说我们走2^n这个点不如走n-1所有点 */ //3,144,565,100,727,795 //5,102,364,399,534,485 #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int res; //bool cmp(pair<int,int>a,pair<int,int>b) //{ // return a.first<b.first; //} signed main() { int x0,y0,ax,ay,bx,by,xs,ys,t,f=0,pos; cin>>x0>>y0>>ax>>ay>>bx>>by>>xs>>ys>>t; vector<pair<int,int>>point; point.push_back({x0,y0}); for(int i=1;i<=61;i++){ int x=x0*ax+bx,y=y0*ay+by; if(x<0||y<0) break; if(x0*ax+bx>=1e17||y0*ay+by>=1e17) break; point.push_back({x,y}),x0=x,y0=y; } // sort(point.begin(),point.end(),cmp); // int vis=0; // for(int i=0;i<point.size();i++) // if(point[i]==make_pair(xs,ys)) pos=i,vis++; // // cout<<pos<<endl; // for(auto i:point) cout<<i.first<<' '<<i.second<<endl; // // for(int i=pos;i<point.size();i++){ // int ans=0,nowx=xs,nowy=ys,t_=t; //// cout<<"右: "<<endl; // for(int j=pos+1;j<=i;j++){ //// cout<<t_<<endl; //// cout<<j<<' '<<point[j].first<<' '<<point[j].second<<endl; // if(point[j]==make_pair(xs,ys)) continue; // int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy)); // if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second; // else break; // } //// cout<<"左: "<<endl; // for(int j=pos;j>=0;j--){ //// cout<<t_<<endl; //// cout<<j<<' '<<point[j].first<<' '<<point[j].second<<' '<<endl; // if(point[j]==make_pair(xs,ys)) continue; // int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy)); // if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second; // } //// cout<<ans<<endl; // res=max(res,ans); // } for(int i=0;i<point.size();i++){ int t_=t,nowx=xs,nowy=ys,ans=0; for(int j=i;j>=0;j--){ int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy)); if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second; } for(int j=i+1;j<point.size();j++){ int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy)); if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second; else break; } res=max(res,ans); } // if(vis>=2) res++; cout<<res; return 0; }
T2:Problem - 1313D - Codeforces
首先注意到 \(k\) 的取值范围，可以想到要用状压。
对于数据范围 \(1 \le m \le 10^9\)，显然 \(O(m\, 2^k)\) 的时间复杂度无法接受。
可以发现，\(n\) 个序列中不同的点最多只有 \(2 \times n\) 个，所以进行离散化。
奇偶数之间的转化可以用异或实现。
对于状态 \(s\)，可以通过 `__builtin_parity()` 函数快速求得其中有奇数个还是偶数个 \(1\)，返回值为 \(1\) 则个数为奇数个，这在 DP 转移时可以用到。
\section*{预处理}
应用差分的思想，对于一个区间 \([ l_i,r_i ]\)，将其拆成 \(l_i\) 和 \(r_i+1\)，分成开始目前区间和结束目前区间两种操作。
具体实现可以用 STL： \texttt{vector<pair<int,int>>}，分别存入 \(( l_i,i )\) 和 \(( r_i+1,-i )\)，按序列中位置排序。
\section*{DP}
设 \(f_{i,j}\) 表示离散化后序列第 \(i\) 个位置的状态为 \(j\) 时，第 \(i\) 个位置及其之前的序列中最多的奇数个数，初始值为极小值。
设 \(g_{i,j}\) 表示在序列第 \(i\) 个位置时，第 \(j\) 个对其有影响的区间（没有就是 \(0\)）。
- 如果当前操作是开始某个区间
- 遍历数组 \(g_i\)，找到第一个 \(0\) 的位置 \(p\)，此时 \(g_{i,p}\) 即当前区间是第 \(p\) 个对位置 \(i\) 有影响的区间。
- 如果状态 \(j\) 的第 \(p\) 位是 \(1\)，即状态 \(j\) 下加入了当前区间，则 \(f[i][j]\) 应由 \(f[i-1][j^(1<<p)]\) 转移而来。
- 如果状态 \(j\) 的第 \(p\) 位是 \(0\)，即状态 \(j\) 下未加入当前区间，则 \(f[i][j]\) 应由 \(f[i-1][j]\) 转移而来。
- 对于开始某个区间的转移，其中都要先记录下离散化后当前位置与下一个位置之间的长度 \(len\)（最后一个位置为 \(0\)），转移时加上 \(len*__builtin_parity(j)\)，即当前状态下增加的奇数个数。
- 如果当前操作是结束某个区间
- 遍历数组 \(g_i\)，找到当前结束的区间的位置 \(p\) 并清空 \(g_{i,p}\)，具体原因可以结合前文理解。
- 如果状态 \(j\) 的第 \(p\) 位是 \(1\)，即状态 \(j\) 下依然存在当前区间，可知状态 \(j\) 不合法，所以赋极小值。
- 如果状态 \(j\) 的第 \(p\) 位是 \(0\)，即状态 \(j\) 下已不存在当前区间，则 \(f[i][j]\) 应由两个合法状态 \(f[i-1][j]\) 和 \(f[i-1][j^(1<<p)]\) 中的较大值转移而来。
因为当前状态的前一步状态可以本来就没有当前区间即 \(f[i-1][j]\)，也可以是在位置 \(i\) 时去掉了当前区间即 \(f[i-1][j^(1<<p)]\)。所以取较大值转移。
- 对于结束某个区间的转移，如果情况合法，也要在转移时加上 \(len*__builtin_parity(j)\)。
\section*{优化}
此时的空间复杂度达到了 \(O(2n2^k)\)，所以要对空间进行优化。
- 可以发现，对于开始某个区间的 DP 转移，在 \(f[i][j]\) 由 \(f[i-1][j^(1<<p)]\) 转移而来的情况下， \(j\) 一定大于 \(j^(1<<p)\)。
- 可以发现，对于结束某个区间的 DP 转移，在 \(f[i][j]\) 由 \(f[i-1][j]\) 和 \(f[i-1][j^(1<<p)]\) 中的较大值转移而来的情况下， \(j\) 一定小于 \(j^(1<<p)\)。
所以可以将数组 \(f\) 的第一维省略掉，即设 \(f_i\) 为状态为 \(i\) 时的当前位置前的奇数最大值，并对 DP 的转移略为改动：
- 如果操作是开始区间，就逆向遍历所有状态：`for(int i=(1<<k)-1;i>=0;i--)`，转移时也直接去掉第一维即可。
- 如果操作是结束区间，就正向遍历所有状态，可以类比开始区间的操作。
最后的输出值是 \(f_0\)，也就是序列离散化后最后一个位置在不受任何区间影响时的值。
时间复杂度 \(O(n\log_2n+2^k)\)，空间复杂度 \(O(2^k)\)。
完结。
/*m数据范围1-1e9,所以复杂度不能带m,如果数据范围较小,完全可以进行差分然后合并 考虑如何突破,注意到,n的范围为1-1e5,并且k最大为8,可以考虑离散化,这里的离散化可以这样做: 对于每个区间[L,R],可以把这段区间变化成[L,i]和[R+1,-i],这样做的意味是,把这些区间排序,然后 如果是正的,那就是要加,如果是负的,那就是减,一直减到遇到正的点,而加或减去的值就是两个相邻点之间的距离 这样我们就有最多2*n个点了,然后考虑,dp[i,j],i为第i位,j为状态,由于k小,显然可以用状态压缩 那么对于正的点开始: 有对于第i位j状态,对它有影响的区间为id,那么如果j状态的id位为1,那么就是 现在这个状态已经包含了id这个区间,那么有dp[i,j]=dp[i-1,j^(1<<id)]+len而来,如果id位为0,那么就是当前状态没有id区间 那么现在这个i位置的状态和i-1位置的状态是一样的,只不过是多加了一个len就是了 对于负的是一样的 考虑id位: 可以这样想: 对于每个点,它最多被8个区间所覆盖,所以我们可以分成8个区间 这道题里，每个位置都只会被最多 8 个线段覆盖，也就是说， 所有线段一定可以无重叠地放置进 8 个轨道。因此只要记录当前位置的所有轨道上是否有线段即可。 现在问题是如何把线段放进轨道里。直接扫描线过去，开一个 vis 数组记录轨道是否占用即可。 之后，第 i 条线段将拥有一个编号 id表示所在轨道的编号。 */ #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; struct node { int x,id,tag; bool operator<(const node&w) const{ if(x!=w.x) return x<w.x; else return tag<w.tag; } }; vector<node>g; int n,m,k,dp[N]; int ID[N]; bool vis[N]; bool check(int x) { return __builtin_popcount(x)%2==1; } signed main() { std::ios::sync_with_stdio(false),cin.tie(0); cin>>n>>m>>k; memset(dp,-0x3f,sizeof dp); for(int i=1;i<=n;i++){ int l,r; cin>>l>>r; g.push_back({l,i,1}),g.push_back({r+1,i,0}); } sort(g.begin(),g.end()),dp[0]=0; for(auto i:g){ if(i.tag) for(int s=0;s<8;s++){ if(!vis[s]){ vis[s]=true,ID[i.id]=s; break; } } else vis[ID[i.id]]=false; } for(int i=0;i<g.size();i++){ node now=g[i]; int id=ID[now.id]; if(now.tag) for(int s=(1<<8)-1;~s;s--){ int v=(i+1<g.size()?(g[i+1].x-g[i].x):0); if(!check(s)) v=0; if((s>>id)&1) dp[s]=dp[s^(1<<id)]+v; else dp[s]=dp[s]+v; } else for(int s=0;s<(1<<8);s++){ if(!((s>>id)&1)){ if(check(s)) dp[s]=max(dp[s],dp[s^(1<<id)])+(i+1<g.size()?(g[i+1].x-g[i].x):0); else dp[s]=max(dp[s],dp[s^(1<<id)]); } else dp[s]=-0x3f3f3f3f; } } cout<<dp[0]; return 0; }
T3:Problem - 1325D - Codeforces
设两个数为 $n$ 和 $m$，我们可以把它们分为 $3$ 部分，有 $x \oplus x \oplus y = m$。对于 $x$ 和 $x$，$x \oplus x = 0$，然后 $0 \oplus y = y$，所以此时让 $y = n$ 即可。
考虑是否有长度为 $2$ 的解，注意由于上一步，我们有 $y = n$，发现，如果有 $(x + n) \oplus x = n$ 或者 $(x \oplus x) \oplus n = n$，那么有 $(x + n) \oplus x = n$ 或 $(x \oplus x) \oplus n = n$，此时答案变成 $2$。
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; signed main() { int n,m; cin>>n>>m; int u=m-n; if(u<0||m%2!=n%2) return cout<<-1<<endl,0; if(m==0) return cout<<0<<endl,0; if(n==m) return cout<<1<<endl<<n<<endl,0; int now=u>>1; if(((now+n)^now)==n) cout<<2<<endl<<now<<' '<<now+n<<endl; else if(((now+now)^n)==n) cout<<2<<endl<<now*2<<' '<<n<<endl; else cout<<3<<endl<<now<<' '<<now<<' '<<n<<endl; return 0; }
T4:Problem - 1349B - Codeforces
对于本道题,可以发现,对于一串数组,对于长度为 $2$ 的子串,如果 $i$ 位为 $k$ , $i+1$ 位为 $k+s(s>0)$
那么肯定会有 $i$ 和 $i+1$ 合并变成 $[k,k]$ ,然后依次向后推过去就可以了
所以本题的关键是找到能变的位置,通俗的来讲,就是,只要能变一次,就能够变无数次
这里讲一下我犯的错误,只是着眼于眼前,总以为 $k$ 的时候才能变,其实如果在一个长度为 $3$ 或 $2$ 的区间里
有 $2$ 个数都大于 $k$ ,那么中位数一定大于 $k$,所以这个时候大于 $k$ 的数就出现了,一直把这个数推到 $k$ 旁边即可
我犯的错是只在 $k$ 的时候变化,并没有想到其他数的变化,导致一直 $WA$
//https://codeforces.com/problemset/problem/1349/B /* 对于本道题,可以发现,对于一串数组,对于长度为2的子串,如果i位为k,i+1位为k+s(s>0) 那么肯定会有i和i+1合并变成[k,k],然后依次向后推过去就可以了 所以本题的关键是找到能变的位置,通俗的来讲,就是,只要能变一次,就能够变无数次 这里讲一下我犯的错误,只是着眼于眼前,总以为k的时候才能变,其实如果在一个长度为3或2的区间里 有2个数都大于k,那么中位数一定大于k,所以这个时候大于k的数就出现了,一直把这个数推到k旁边即可 我犯的错是只在k的时候变化,并没有想到其他数的变化,导致一直WA */ //错误代码 #include<bits/stdc++.h> using namespace std; const int N=2e5+10; int a[N],res; bool check(int pos) { if(a[pos]<=a[pos-1]||a[pos]<=a[pos+1]) return true; if(a[pos]>=a[pos+1]&&a[pos]<=a[pos+2]) return true; if(pos>=2&&a[pos]>=a[pos-1]&&a[pos]<=a[pos-2]) return true; return false; } void solve() { int n,k; cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; a[0]=-1,a[n+1]=-1,a[n+2]=-1; if(n==1&&a[1]==k) return cout<<"Yes"<<endl,void(); for(int i=1;i<=n;i++) //只着眼于k这个数,而忘记了其他数 if(a[i]==k&&check(i)) return cout<<"Yes"<<endl,void(); cout<<"NO"<<endl; } int main() { int t; cin>>t; while(t--) solve(); } //正确代码: #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int a[N],res,n,k; bool check(int pos) { if(a[pos]>=k&&a[pos+1]>=k) return true; if(a[pos]>=k&&a[pos+2]>=k) return true; return false; } void solve() { cin>>n>>k; bool vis=false; for(int i=1;i<=n+2;i++) a[i]=0; for(int i=1;i<=n;i++){ cin>>a[i]; if(a[i]==k) vis=true; } if(n==1&&a[1]==k) return cout<<"Yes"<<endl,void(); if(!vis) return cout<<"No"<<endl,void(); for(int i=1;i<=n;i++) if(check(i)) return cout<<"Yes"<<endl,void(); cout<<"No"<<endl; } signed main() { int t; cin>>t; while(t--) solve(); }
T5:Problem - 1338B - Codeforces
题意
-----
对于每对叶子结点，保证他们之间的最短路径异或和为 $0$，求出现边权种类个数的最大 / 小值。
思路
-----
设一个度不为1的点做跟。
1. 两叶子 $ u, v$ 最短路径的异或和，也就相当于 $u, v$ 到他们根节点的异或和。因为异或具有自反性（$LCA$ 异或到根节点，根节点再异或回 $LCA$， 结果不变）。
2. 考虑最小值：如果两个叶子结点的深度和全部为偶数的话，那么答案为 $1$（异或的自反性，偶数个 $a$ 异或结果为 0）。如果出现了深度和为奇数的情况，那么要使得路径上两个节点，那么答案为 $3$（有 $b$ ^ $c$ = $a$，易证 $a, b, c$ 互不相等）。
3. 考虑最大值：将最大值初始化为边数，如果一个节点有 $k$ 个儿子为叶子结点，那么显然他们到父亲的权值必须相同。那么最大值减去 $k - 1$。
时间复杂度 $O(n)$。
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n,m,res,idx; int e[N],ne[N],h[N],in[N],dis[N]; bool vis[N],st[5]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int dfs(int u,int fa) { dis[u]=dis[fa]+1; if(in[u]==1) return vis[dis[u]]=true,1; int sum=0; for(int i=h[u];~i;i=ne[i]){ int j=e[i]; if(j!=fa) sum+=dfs(j,u); } res-=max(0,sum-1); return 0; } int main() { cin>>n; res=n-1; memset(h,-1,sizeof h); for(int i=1;i<=n-1;i++){ int u,v; cin>>u>>v; add(u,v),add(v,u),in[u]++,in[v]++; } for(int i=1;i<=n;i++) if(in[i]>1){ dfs(i,0); break; } for(int i=1;i<=n;i++) if(vis[i]) st[i&1]=true; // for(int i=1;i<=n;i++) cout<<dis[i]<<endl; if(st[1]&&st[0]) cout<<3<<' ';//注意这里,这里的dis是根节点到叶子节点的距离,只有一个为奇数一个为偶数的时候相加才是奇数,如果都为奇数那么他俩的距离是偶数 else cout<<1<<' '; cout<<res; return 0; }
T6:Problem - 1396B - Codeforces
又是道思维题，来，让我们仔细分析：
首先规定模型： $t$ 先拿然后 $hl$ 再拿，所以有一个显然的情况：
那就是如果有一堆石头比其他所有的都多，特别多，那么 $t$ 只需要一直呆在这堆石头上就行了，$hl$ 取完所有的也不够 $t$ 自己的这一堆。
然后考虑不满足这种情况的，首先：假设一种为 $4 \ 1 \ 1 \ 1 \ 1$，那么无论 $t$ 他一开始在哪，都不会赢，因为 $t$ 先手。
如果 $t$ 在 $4$，那么 $hl$ 取 $1$，又 $t$ 先手，一定是 $t$ 先取完。如果 $t$ 放弃 $4$ 跑去取 $1$ 呢？那么就变成了 $4 \ 0 \ 1 \ 1 \ 1$，$hl$ 一直守着第一堆就可以了。
如果是 $5 \ 3 \ 1 \ 1 \ 1$，自己推一下又可以发现，无论 $t$ 先手在哪个石堆，经过两次之后，会出现 $5 \ 2 \ 0 \ 1 \ 1$，此时改 $t$ 先手，$t$ 赢。
当然，情况不一定是 $5 \ 2 \ 0 \ 1 \ 1$，但是一定会出现一个很大的堆，因为我们的最大堆和其他的值差值为奇数，也就是第奇数次该 $t$ 选，
所以当出现最大堆的时候，一定是 $t$ 选。
如果某一堆比其他堆加起来还要多，那么先手必胜，可以一直选这一堆。
否则，两人不可能让某一堆比其他堆加起来还要多这种情况出现，否则自己必败，所以所有石子都会被取完，直接判断奇偶性即可。
/* 又是道思维题,来,让我们仔细分析: 首先规定模型: t先拿然后hl再拿,所以有一个显然的情况: 那就是如果有一堆石头比其他所有的都多,特别多,那么t只需要一直呆在这堆石头上就行了,hl取完所有的也不够t自己的这一堆 然后考虑不满足这种情况的,首先: 假设一种为 4 1 1 1 1,那么无论t他一开始在哪,都不会赢,因为,t先手 如果t在4,那么hl取1,又t先手,一定是t先取完,如果t放弃4跑去取1呢?那么就变成了 4 0 1 1 1,hl一直守着第一堆就可以了 如果是 5 3 1 1 1,自己推一下又可以发现,无论t先手在哪个石堆,经过两次之后,会出现 5 2 0 1 1,此时改t先手,t赢 当然,情况不一定是5 2 0 1 1,但是一定会出现一个很大的堆,因为我们的最大堆和其他的值差值为奇数,也就是第奇数次该t选 所以当出现最大堆的时候,一定是t选 */ #include<bits/stdc++.h> using namespace std; const int N=2e5+10; int a[N]; void solve() { int n; cin>>n; int sum=0,maxx=-1; for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i],maxx=max(maxx,a[i]); for(int i=1;i<=n;i++) if(a[i]>sum-a[i]) return cout<<"T"<<endl,void(); if((sum-maxx*2)%2==1) return cout<<"T"<<endl,void(); cout<<"HL"<<endl; } int main() { int t; cin>>t; while(t--) solve(); }
T7:Problem - C - Codeforces
对本题研究较多,写了三种方法:
二分法:
将所有的可能性排序全部放在一个数组里面并记录他们的归属 $id$ ,然后用一个cnt数组进行统计
二分答案,如果说在一个区间l,r内,具有r的值减去l的值符合 $mid$ 约束.并且说这个区间里面包含了n个数,那么就符合check
进行排序是因为l,r的单调性,这样才能进行区间的判断
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int a[10],b[N],n,cnt[N]; int res=1e18,cur,id; struct node { int id,v; bool operator<(const node&w)const { return v<w.v; } }c[5*N]; bool check(int u) { int num=0; memset(cnt,0,sizeof cnt); for(int l=1,r=1;r<6*n;l++){ while(r<6*n&&c[r].v-c[l].v<=u) num+=((cnt[c[r].id]++)==0),r++; if(num==n) return true; num-=((--cnt[c[l].id])==0); } return false; } void solve() { for(int i=0;i<6;i++) cin>>a[i]; cin>>n; for(int i=1;i<=n;i++){ cin>>b[i]; for(int j=0;j<6;j++) c[i+j*n].v=b[i]-a[j],c[i+j*n].id=i; } sort(c+1,c+6*n+1); int l=0,r=1e10; while(l<r){ int mid=l+r>>1; if(check(mid)) r=mid; else l=mid+1; } cout<<r<<'\n'; } signed main() { std::ios::sync_with_stdio(false),cin.tie(0); int t; t=1; while(t--) solve(); return 0; }
双指针:
与二分的check函数类似,不再赘述,这里注意一点,while循环的时候,双指针的r初始化为0然后先+再更新
这样始终保持r是正确的范围,否则r可能会在id=20是正确的,然后r++导致while结束时为21
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int a[10],b[N],n,cnt; int res=1e18,cur,id; struct node { int id,v; bool operator<(const node&w)const { return v<w.v; } }c[5*N]; map<int,int>mp; void solve() { for(int i=0;i<6;i++) cin>>a[i]; cin>>n; for(int i=1;i<=n;i++){ cin>>b[i]; for(int j=0;j<6;j++) c[i+j*n].v=b[i]-a[j],c[i+j*n].id=i; } sort(c+1,c+6*n+1); int res=1e15,num=0; for(int l=1,r=0;r<6*n;l++){ while(r<6*n&&num<n) r++,num+=((mp[c[r].id]++)==0); if(num==n) res=min(res,c[r].v-c[l].v); num-=((--mp[c[l].id])==0); } cout<<res<<endl; } signed main() { std::ios::sync_with_stdio(false),cin.tie(0); int t; t=1; while(t--) solve(); return 0; }
堆:
对于一个堆,首先将轨道值从小到大排序,然后先把所有的数都放在第一号轨道里,并且记录最大值
维护一个小根堆,我们每次都从小根堆里面取top元素,然后更新答案,然后我们把这个数放进下一个轨道,也就是pos+1
那么有个显然的性质,如果一个数已经到达最后轨道并且在top中,那么根据top性质,它最小,而后面的数都比它大,而这个数走完了所有轨道
所以此时一定是最优解
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int a[10],b[N],n,cnt; int res=1e18,cur,id; struct node { int v,id; bool operator<(const node&w)const { return v>w.v; } }c[5*N]; map<int,int>mp; priority_queue<node>que; void solve() { for(int i=1;i<=6;i++) cin>>a[i]; cin>>n; int mx=-1e15; sort(a+1,a+7),reverse(a+1,a+7); for(int i=1;i<=n;i++){ cin>>b[i]; c[i].v=b[i]-a[1],mx=max(mx,c[i].v); que.push({c[i].v,i}),mp[i]=1; } while(!que.empty()){ node now=que.top(); que.pop(); // cout<<now.v<<endl; int i=now.id; res=min(res,mx-now.v); mp[i]++; if(mp[i]>6) return cout<<res<<endl,void(); mx=max(mx,b[i]-a[mp[i]]); que.push({b[i]-a[mp[i]],i}); } cout<<res<<endl; } signed main() { std::ios::sync_with_stdio(false),cin.tie(0); int t; t=1; while(t--) solve(); return 0; }
T8:Problem - 1415D - Codeforces
本题的解法非常的巧妙,观察到,原序列不降,那么对于第 $i$ 个数字
设第 $i$ 个数字为 $x$ ,那么 $x$ 的最高位为 $1$,则有,$i-1$ 个数字关于 $x$ 的最高位也可能是 $1$ , $i+1$ 同理
如果三个连续的数最高位都是$1$,那么就有,$1 \oplus 1=0$,那么最高位抵消,我们只需异或 $i$ 和 $i+1$ 即可,$i-1$ 一定大于他们的异或,一次即可
观察到 $a_i<10^9$,所以一个数的二进制最大位数为 $30$,那么如果我们的 $n>60$,考虑最坏情况,每个位数不可能不出现大于 $3$的情况,所以当 $n>60$ 的时候,操作数一定是$1$,因为最高位为 $1$ 的数一定是相邻的
那么我们的 $n$ 最多为 $60$,直接暴力枚举即可,这样来枚举,考虑两个区间,$[i,j]$, $[j+1,k]$,如果左区间异或完之后大于右区间,那么成立,操作数为 $k-i-1$,可使用异或前缀和
//运用异或前缀和 #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int n,a[N],s[N],res=1e9; signed main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; if(n>60) return cout<<1<<endl,0; for(int i=1;i<=n;i++) s[i]=s[i-1]^a[i]; for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) for(int k=j+1;k<=n;k++) if((s[j]^s[i-1])>(s[k]^s[j])) res=min(res,k-i-1); cout<<(res==1e9?-1:res)<<endl; }
也可以直接暴力,时间复杂度一样的
//n^3方法: #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int n,a[N],s[N],res=1e9; signed main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; if(n>60) return cout<<1<<endl,0; for(int i=1;i<n;i++){ for(int j=i;j<n;j++){ int l=0,r=a[j+1],minn=a[j+1],pos=j+1; for(int k=i;k<=j;k++) l^=a[k]; for(int k=j+2;k<=n;k++){ r^=a[k]; if(r<minn) minn=r,pos=k; } if(l>minn) res=min(res,pos-i-1); } } cout<<(res==1e9?-1:res)<<endl; return 0; }
T9:Problem - E - Codeforces
对于本题,总体想法很简单,既然要求奖励是一层一层的变换的,那么不难想到肯定是要把权值大的放在前面,这样才能让他们被计算多次,得到的总奖励也就会越大,所以首先我们要先把数组从大到小排序
对于所有的正数,对答案的贡献是一定的,肯定是能选就选,如果当前我们的打完 $boss$ 的奖励变成了负数,那么我们就要考虑清零次数了,不难看出,对于一串数组来说,我们把最小的数放在最后面是对答案没有影响的
那么对于所有的对答案影响是负的数组,由于我们有 $k$ 次机会,那么可以把这组数组分成 $k+1$ 个集合,由于不一定用完 $k$ 次,所以集合可以为空,那么贪心的去想,我们要对答案的影响最小,所以最小的数一定在后面,那么次小的数呢?倒数第二个数应该是在第二组的最后面才是最优解.尽量的去缩小权值才能得到最优解,所以我们可以得出一个规律: 对于所有对答案负影响的,把他们分为 $k+1$ 组,然后前 $k+1$ 个最小的数组充当 $k+1$ 组的最后面的数,次小的从当倒数第二个,依次类推...
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10; int a[N],res,sum,n,k; signed main() { scanf("%lld %lld",&n,&k); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); int pos=n; sort(a+1,a+1+n),reverse(a+1,a+1+n); for(int i=1;i<=n;i++){ res+=sum,sum+=a[i]; if(sum<0) {pos=i;break;} } a[pos]=sum; for(int i=pos;i<=n;i++) res+=(n-i)/(k+1)*a[i]; cout<<res<<endl; return 0; }
T10:Problem - C - Codeforces
首先观察函数 $f(i)$,$f(i)$为一个数 $x$ 为 $i$ 的最小公因数,那么有可以转换一下,$f(i)=x$,则有对于 $i$ 来说, $[1,x-1]$ 均可以被 $i$ 整除,这样方向就很明确了,我们要枚举的不是 $i$,而是 $x$,对于每个数,如果他是 $1$ 和 $2$ 的倍数,那么他就对 $1$ 和 $2$ 这两个数有贡献,为 $2$,所以我们枚举 $x=1$ 和$x=2$ 的时候累加一次即可,接下来是如何计算这样一个值,该值满足以下性质: $g[i]$ 为前 $i$ 之前的最小因数,例如 $g[3]=6$ ,意味着 $6$ 可以整除前 $3$ 个数即 $1 2 3$,那么如何计算这个函数呢? 用前 $i$ 个数和当前的 $g[i]$ 求个最小公倍数即可
#include<bits/stdc++.h> #define int long long using namespace std; const int mod=1e9+7; void solve(){ int n,res=0; cin>>n; for(int x=1,i=1;x<=n;x=lcm(x,i),i++) res=(res+n/x)%mod; cout<<res<<endl; } signed main(){ int t; cin>>t; while(t--) solve(); }
T11 :Problem - 1548A - Codeforces
不愧是这套题单里面难度最小的,我说怎么我花8分钟就A了
言归正传,题意一开始并不是很清楚,看了样例解释之后才清晰,注意到,对于操作 $3$ 都是围绕这个点的所有邻边删除的,所以不必要建图,既然是最小的那个会被杀死,那么不如开个 $map$ 来储存被杀死的人,然后并且储存这个人的邻边数量,如果操作一或者操作二让 $map$ 变为 $0$ 那么就意味着,他不会被杀死,输出所有人减去应该被杀死的人即可
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; map<int,int>mp; int main() { int n,m,res=0; cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; if(mp[min(u,v)]==0) res++; mp[min(u,v)]++; } int t; cin>>t; while(t--){ int q; cin>>q; if(q==3) cout<<n-res<<endl; if(q==1){ int u,v; cin>>u>>v; if(mp[min(u,v)]==0) res++; mp[min(u,v)]++; } if(q==2){ int u,v; cin>>u>>v; mp[min(u,v)]--; if(mp[min(u,v)]==0) res--; } } return 0; }
T12:Problem - 1490F - Codeforces
最后的答案肯定是所有的数出现的次数都相同,所以我们要进行统一操作,题目还要求最小的操作次数.
这里注意,数组中只能删,不能增,那么就好办了,对于任何一个出现次数较小的数字,那么免除不了被删除的命运,通俗的来说,就是,现在
有两个数,一个出现次数为 $x$ 另一个出现次数为 $y$, 如果我们选择出现次数多的那个(设为 $y$ ),我们就要把 $x$ 全部删除,否则 把 $y$ 删到 $x$,又我们最终的答案一定是一个次数,所以说,对当前的次数进行排序,然后两个两个一组进行比较,看看哪个操作贡献最小,就进行那个操作即可,如果把较大的删除不要忘记小的次数要 $+1$
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int a[N],n; void solve() { cin>>n; map<int,int>mp,num; for(int i=1;i<=n;i++) cin>>a[i],num[a[i]]++; for(auto it:num) mp[it.second]++; int x_,y_,vis=0; for(auto it:mp){ int x=it.first,y=it.second; if(!vis) x_=x,y_=y,vis=1; else{ if((x-x_)*y>=x_*y_) res+=x_*y_,x_=x,y_=y; else res+=(x-x_)*y,y_+=y; } } cout<<res<<endl; } signed main() { int t; cin>>t; while(t--) solve(); return 0; }
T13:Problem - E - Codeforces
贪心+排序:
首先观察条件,观察到具有这样两个条件: $1: h_1<h_2 , w_1<w_2$ , $2: w_1<h_2 , h_1<w_2$,显然,第二个条件有些别扭,那么对于第二个,它的意思是自己的第二个大于别人的第一个,自己的第一个大于别人的第二个,那么如果我们把所有的 $h$ 和 $w$ 按照 $h>w$ 的放入,也就是当我们的 $w>h$ 的时候,我们就把他俩互换,这样可以消除第二个条件. 为什么这样做是对的? 因为反正我的 $h$ 和 $w$ 在比较的时候可以互换,那么为什么我不一开始就互换呢?性质是一样的,此时只剩下一个条件了,接下来就好办了,按照 $w$ 升序然后判断即可,注意这里相同的 $h$ 要特殊处理
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int n,res; struct node{ int h,w,id; bool operator<(const node&W) const{ if(h==W.h) return w<W.w; else return h<W.h; } }per[N]; void solve(){ cin>>n; for(int i=1;i<=n;i++){ int a,b; cin>>a>>b; if(a<b) swap(a,b); per[i].h=a,per[i].w=b,per[i].id=i; } sort(per+1,per+1+n); vector<int>res(n+1); int mn=1e9,pos; for(int i=1;i<=n;i++){ int cur=i; while(cur<=n&&per[i].h==per[cur].h){ if(per[cur].w>mn) res[per[cur].id]=pos; else res[per[cur].id]=-1; cur++; } if(mn>per[i].w) mn=per[i].w,pos=per[i].id; i=cur-1; } for(int i=1;i<=n;i++) cout<<res[i]<<' '; cout<<'\n'; } signed main(){ int t; cin>>t; while(t--) solve(); return 0; }
T14:Problem - 1379C - Codeforces
证：因为如果两个物品同时选多次，那么一定是两个都被选过一次，那么用 $b_i$ 更大的去替换另一个一定不劣。
基于贪心的函数递归法:
基于贪心,对于此题来说,有一个母庸置疑的思路就是,我们 $B$ 中的花朵肯定只有一组会被一直选下去,为什么是只选一组呢?其实很好证明: 把所有的 $A$ 和 $B$ 全部混合起来然后从大到小排序,倘若我们在解决的问题中碰到了某一个 $B$,此时有两种选择: 选它(分先手 $a$ 被没被买两种情况),跳过不选,因为如果我们要选这个 $B$,那么我们接下来的花朵价值都没有这个 $B$ 高,所以怎么选都不如这样大.
所以我们的 $B$ 花一定是只有一种被多次选择,而这个 $B$ 是哪个我们很难抉择,因为我们有可能碰到, $A$ 没被先手选,要先选它,但是如果先选它的话会亏损很大一部分从而导致不是正确答案,但是我们知道这样做一定是对的: 前面的全选,到这个 $B$ 之后全部选它,只是我们不知道选哪个 $B$,所以此时我们采用函数递归的方法,交给函数,我们只需要每次递归的时候返回的是 $max$ 值即可了,时间复杂度 $O(nlogn)$,瓶颈在于排序.
// LUOGU_RID: 138973828 #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; struct node{ int v,id,cur; bool operator<(const node&w) const{ return v>w.v; } }p[2*N]; int tot,num[N][2],n,m; bool vis[N]; int solvep(int now,int cnt){ int res=0; for(int i=now;i<=tot;i++){ if(cnt<=0) return res; if(p[i].cur==0) cnt--,res+=p[i].v,vis[p[i].id]=true; else{ if(vis[p[i].id]) res+=p[i].v*cnt; else{ int val=num[p[i].id][0]+(cnt-1)*p[i].v; res+=max(val,solvep(i+1,cnt)); } return res; } } return res; } void solve(){ cin>>n>>m; tot=0; for(int i=1;i<=m;i++){ cin>>num[i][0]>>num[i][1]; vis[i]=false,p[++tot]={num[i][0],i,0},p[++tot]={num[i][1],i,1}; } sort(p+1,p+1+tot); cout<<solvep(1,n)<<endl; } signed main(){ int t; cin>>t; while(t--) solve(); }
二分法:
根据前面贪心的证明: 肯定有一个 $B$ 类被选多次,所以说我们可以枚举这个 $b$,然后把大于这个 $b$ 价值的前面所有的 $a$ 都选走,关于的 $a$ 的位置可以用二分来找到,然后通过维护一个前缀和方便实现计入 $a$ 价值,时间复杂度 $O(nlogn)$
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; struct node{ int a,b; bool operator<(const node&w)const{ return a>w.a; } }p[N]; int n,m,sum[N]; void solve(){ cin>>n>>m; for(int i=1;i<=m;i++) cin>>p[i].a>>p[i].b; sort(p+1,p+1+m); for(int i=1;i<=m;i++) sum[i]=sum[i-1]+p[i].a; int res=0; for(int i=1;i<=m;i++){ int l=0,r=m; //注意l要为0: while(l<r){ int mid=(l+r+1)>>1; if(p[mid].a>=p[i].b) l=mid; else r=mid-1; } if(r>=n) res=max(res,sum[n]); else if(r>=i) res=max(res,sum[r]+(n-r)*p[i].b); else res=max(res,sum[r]+p[i].a+(n-r-1)*p[i].b); } cout<<res<<endl; } signed main(){ int t;cin>>t; while(t--) solve(); }
T15:Problem - B - Codeforces
该题比较有弯,首先思考,如果不存在商人的话,我们的基本思路就是每隔 $d$ 个然后吃一个饼干,但是如果碰到商人的话,我们就要重新计数. 首先把没去除商人的情况算出来,具体就是用 $s$ 数组存储商人的位置,然后 $s_0$ 为 $-d+1$,这里解释一下为什么是 $-d+1$,因为我们要统一下计算方式,也就是说从开始到第一个商人所消耗的所有饼干应该是: $(s_1-1-1)/d+1$,这里的 $1$ 是刚开始什么都没有必须吃的 ,然后其中的 $s_1-1-1$ 两次减一,第一次是因为刚开始的第一个距离不算,然后第二次是因为到达第 $s_i$ 处的距离也不算,然后 $s_n+1$段也要特别处理一下即可,这样就算出来不除掉商人的总消耗量,然后计算处理掉商人的情况,对于每个商人,他对答案的贡献无非就是从他的上一个商人开始到他的下一个商人结束的这段情况,所以枚举每个商人,然后把这段特殊情况减去,加上如果没有他应该吃掉的饼干数,然后再加遇到商人吃的数量 $m-1$ ,在循环中更新最小值和答案即可.
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int n,m,t,d; void solve(){ cin>>n>>m>>d; vector<int>s(m+2); for(int i=1;i<=m;i++) cin>>s[i]; s[0]=-d+1,s[m+1]=n+1; int sum=0,res=n+1,cnt=1; for(int i=1;i<=m+1;i++) sum+=(s[i]-s[i-1]-1)/d; for(int i=1;i<=m;i++){ int ans=sum; ans-=(s[i]-s[i-1]-1)/d,ans-=(s[i+1]-s[i]-1)/d,ans+=(s[i+1]-s[i-1]-1)/d; ans+=m-1; if(ans<res) res=ans,cnt=1; else if(res==ans) cnt++; } cout<<res<<' '<<cnt<<endl; } signed main(){ cin>>t; while(t--) solve(); }
T16:Problem - A - Codeforces
#include<bits/stdc++.h> #define int long long signed main(){ int n,m,k,l,res; std::cin>>n>>m>>k>>l; if(m>n||n-k<l) return std::cout<<-1,0; res=((k+l)%m)==0?(k+l)/m:((k+l)/m)+1; std::cout<<(res*m>n?-1:res); }
T17:Problem - 804B - Codeforces
#include<bits/stdc++.h> #define int long long using namespace std; const int mod=1e9+7; signed main(){ string s; cin>>s; int res=0,cur=0; for(int i=s.size()-1;i>=0;i--){ if(s[i]=='b') cur=(cur+1)%mod; else res=(res+cur)%mod,cur=(cur*2)%mod; } cout<<res; }
T18:Problem - 1491C - Codeforces
贪心的去想,对于每一张床,我们都需要把他变成1,那么我们从一个必须跳的地方开始一定是最优的,因为如果我们从其它床开始能跳到这个地方的,显然前面那个床更优,所以从左向右第一个非 $1$ 的床是起点,然后记录差分,计算出每个床的贡献,如果当前的跳过次数 $h$ 小于当前的值的话,那么就意味着在某次之后要从这个床为起点,更新答案然后记录差分,对于已经变成 $1$ 的,那么他前面的那个床也会有次数贡献,不要忘记更新记录
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int a[N],c[N]; void solve(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i],c[i]=0; int h=0,res=0; for(int i=1;i<=n;i++){ h+=c[i]; if(h>a[i]-1){ c[i+1]+=h-a[i]+1,c[i+2]-=h-a[i]+1; c[i+2]++,c[min(n+1,i+a[i]+1)]--; } else res+=a[i]-1-h,c[i+2]++,c[min(n+1,i+a[i]+1)]--; } cout<<res<<endl; } signed main(){ int t; cin>>t; while(t--) solve(); return 0; }
T19:Problem - 1490G - Codeforces
寒假告一段落,我的寒假还有仅存的 $20$ 多天,在保持作业的基础下也是又重新开始了我的50题精选系列,回到本题:
对于这种无限长的序列来说,我的第一想法是,算出它的圈数,也就是加上一圈之后我能增加多少,然后整除取余数即可,但是很快意识到不对劲,你会发现如果到 $x-1$ 圈之后,前 $i$ 个数的前缀和要比一圈的大很多,所以我们要时刻记录一圈中的区间最大值,接下来就是二分圈数,用 $mx$ 数组记录到某个点的时候区间的最大值,如果当前二分的圈数 $s$ 有: $s*sum[n]+mx[n] >= q$ 的话,那么很明显我们就只进行了 $s$ 圈,剩下的在 $1$ 圈里找即可,这里注意一些特判情况,具体看代码:
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int n,m,a[N],mx[N],sum[N]; bool check(int u,int q){ return u*sum[n]+mx[n]>=q; } void solve(){ cin>>n>>m; mx[0]=-1e18; for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=sum[i-1]+a[i],mx[i]=max(mx[i-1],sum[i]); } vector<int>res; while(m--){ int q; cin>>q; if(mx[n]>=q) res.push_back((lower_bound(mx+1,mx+1+n,q)-mx-1)); else if(sum[n]<=0) res.push_back(-1); else{ int l=0,r=1e9; while(l<r){ int mid=l+r>>1; if(check(mid,q)) r=mid; else l=mid+1; } res.push_back(r*n+(lower_bound(mx+1,mx+1+n,q-sum[n]*r)-mx)-1); } } for(auto x: res) cout<<x<<' '; cout<<endl; } signed main(){ int t; cin>>t; while(t--) solve(); }
T20: Problem - 1470A - Codeforces
这里题目简化了,给定的 $c$ 数组是递增的,那么我们只需要对 $A$ 进行排序,然后倒序求即可,利用 $Min$ 函数计算当前应该是送钱好还是买礼物更好
如果 $c$ 数组不是递增的,可以开一个 $mn$ 数组记录时刻的区间最小值,然后利用此进行判断即可
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e6+10; int n,m,a[N],c[N],res; bool cmp(int x,int y){ return x>y; } void solve(){ cin>>n>>m; res=0; for(int i=1;i<=n;i++) scanf("%d", &a[i]); for(int i=1;i<=m;i++) scanf("%d", &c[i]); sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) res+=min(c[min(m,i)],c[a[i]]); cout<<res<<endl; } signed main(){ int t; cin>>t; while(t--) solve(); }
T21:Problem - C - Codeforces
由于 $n$ 的最大上限为 $1e19$, 故很明显暴力不可以,考虑二进制,试想一下二进制的最低位,由于 $0-n$ 中,其一定是奇偶奇偶的变化,也就是最低位为 $0->1->0$ 的变化,这样算做一次贡献,那么用这个思想考虑倒数第二位,倒数第二位为: $0->0->1->1->0->0$ 的变化,也就是两次贡献加一,依次类推即可
#include <bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10,mod=1e9+7; string s; int n,t,a[N],f[N],res,num,ans,m,k; bool vis[N]; void solve() { cin>>n; int res=0; while(n>0) res+=n,n>>=1; cout<<res<<endl; } signed main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>t; while(t--){ solve(); } return 0; }