CF刷题记录

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

cf969

c题

• 题目描述:
  给定整数数组，和整数a,b(可相等)，可以任意选择数组元素，进行加减a或b的操作，该操作任意次。输出数组最大值与最小值差的最小值。
• 题解
  首先±a,b等价于加减gcd(a,b),设为d。且可以确定最后的数组极差不会大于d,故将数组元素先取MODd,然后将数组升序排序，得到的数组设为c。
  考虑每个元素都可能作为最小值，首先令$c_1$为最小值，则极差为$c_{n-1}-c_1$,然后从$c_2$开始遍历数组，当$c_i$为最小值，那么最大值为$c_{i-1}+d$,极差为$c_{i-1}+d-c_i$,然后更新最小值。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n,a,b;
int gcd(int a,int b){return b==0 ? a : (gcd(b,a%b));
}
int c[N];
int main() {ios::sync_with_stdio(0);cin.tie(0);int t;cin >> t;while (t--) {cin>>n>>a>>b;int d=gcd(a,b);for(int i=0;i<n;i++){cin>>c[i];c[i]%=d;}sort(c,c+n);int ans=c[n-1]-c[0];for(int i=1;i<n;i++){ans=min(ans,c[i-1]+d-c[i]);}cout<<ans<<'\n';}return 0;
}

d题

• 题目描述：
  一颗树，每个节点是1或0或?(表示未确定)，对于一个叶子节点，从根节点到叶子节点形成01串，若01的数量和10的数量不同，则计一分，否则不计分。周sir和和他的小跟班玩游戏，每个人轮流将?确定为0或1，周sir需要得分越高越好，而小跟班希望越小越好，两个人都很聪明，周sir先手，输出最后的得分。
• 题解
  我们发现一个01串是否几分只与根节点和叶子节点的值有关（若两者相同，怎不计分，反之计分），故有多种情况讨论
  我们定义几个数据，方便说明：cnt0:值为0的叶子数，cnt1:值为1的叶子数，cnt2：值为？的叶子数，cnt3:值为？的非根非叶子数。
  1.根节点确定。假设为1，那么答案为cnt0+(cnt2+1)/2
  2.根节点为？。若cnt0>cnt1，则周sir第一步令根节点为1。之后依次确定根节点，则答案为cnt0+cnt2/2，反之就不赘述了
  3.根节点为？且cnt0==cnt1,此时先确定根节点是不明智的选择，周sir只能用cnt3来拖延时间，若cnt3为奇数，则是轮到小跟班确定根节点，那么答案为cnt0+(cnt2+1)/2;若cnt3为偶，答案为cnt0+cnt2/2;

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2;
int n,a,b;
string s;
int cnt[N];
int main() {ios::sync_with_stdio(0);cin.tie(0);int t;cin >> t;while (t--) {memset(cnt,0,sizeof cnt);cin>>n;for(int i=1;i<n;i++){cin>>a>>b;cnt[a]++,cnt[b]++;}cin>>s;int cnt0=0,cnt1=0,cnt2=0,cnt3=0;for(int i=1;i<n;i++){if(cnt[i+1]==1){if(s[i]=='1'){cnt1++;}else if(s[i]=='0'){cnt0++;}}if(s[i]=='?'){if(cnt[i+1]==1)cnt2++;else cnt3++;}}if(s[0]!='?'){if(s[0]=='1'){cout<<cnt0+(cnt2+1)/2<<'\n';}else{cout<<cnt1+(cnt2+1)/2<<'\n';}}else{if(cnt1>cnt0){cout<<cnt1+cnt2/2<<'\n';}else if(cnt1<cnt0){cout<<cnt0+cnt2/2<<'\n';}else{if(cnt3&1){cout<<cnt1+(cnt2+1)/2<<'\n';}else{cout<<cnt1+cnt2/2<<'\n';}}}}return 0;
}

e题

放弃，题解都看不懂

f题

放弃

cf967

c题

交互题

• 题目描述：
  告诉你树有n个节点，允许你询问15n次最多，每次询问格式为"? a b",系统返回给你使d(x,a)-d(x,b)的最小的x,若有多个，返回d(x,a)最小的那个。最后输出n-1条边，以!开头。
• 题解
  树的每一个节点都可以是根，所以不妨设1节点为根，遍历i从2~n,在1和i之间二分直到，中点等于起点，就得到了i的父节点。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+2;
int n,ans;
int a[N];
int b[N];
int now=0;
int main() {int t;cin >> t;while (t--) {now=0;cin>>n;for(int i=2;i<=n;i++){cout<<"? "<<1<<' '<<i<<'\n';cin>>ans;int u=1,v=i;while(ans!=u){u=ans;cout<<"? "<<u<<' '<<i<<'\n';cin>>ans;}a[now]=u;b[now]=v;now++;}cout<<"! ";for(int i=0;i<now;i++){cout<<a[i]<<" "<<b[i]<<" ";}cout<<'\n';}return 0;
}

d题

不敢恭维

cf965

b题

1000分的题卡住了，蚌埠住了

• 题目描述
  给你一个由1~n的数字组成的排列a，请输出另一种排列p，使
  $a_i+...a_j==p_i+...+p_j$的区间数量最少。
• 题解
  其实就是将a全体循环向右移动一位。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 2;
int n,a[N];
int main(){int t;cin>>t;while(t--){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cout<<a[n]<<' ';for(int i=1;i<n;i++)cout<<a[i]<<' ';cout<<'\n';}return 0;
}

c题

• 题目描述
  给定整数n,k，数组a,b。你可以使$b_i$为1的$a_i$增加，总共增加的大小不能大于k。求max($a_i$+f($a_i$)),其中f($a_i$)为将$a_i$去掉后的数组a’的中位数。
• 题解
  根据贪心思想，$a_i$一定会选择最大的数（可能是最大的$b_i$为0的数，也可能是最大的$b_i$为1的数）;
  分两种情况讨论，若$b_i$为1，那么将k全加在$a_i$上最佳。然后排序求个中位数。较为轻松。
  若$b_i$为0，那么k就要分配给剩下的数，使得中位数最大化，我们考虑二分思想，从而得到最大化的中位数。
  最后取两种情况的max。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 2;
ll n,k,ans,cnt;
struct node{ll da,b;
}a[N];
bool cmp(node a,node b){if(a.b==b.b)return a.da>b.da;return a.b<b.b;
}
bool check(ll x){int sum=0;for(int i=2;i<=cnt;i++){if(a[i].da>=x)sum++;}ll k1=k;for(int i=cnt+1;i<=n;i++){if(a[i].da>=x){sum++;}else if(a[i].b && k1>=x-a[i].da){sum++;k1-=x-a[i].da;}}return sum>=(n+1)/2;
}
int main(){int t;cin>>t;while(t--){cin>>n>>k;ans=0;cnt=0;for(int i=1;i<=n;i++)cin>>a[i].da;for(int i=1;i<=n;i++){cin>>a[i].b;if(a[i].b==0)cnt++;}sort(a+1,a+n+1,cmp);if(cnt){ll l=0,r=INT_MAX;while(l+1<r){ll mid=(r+l)>>1;if(check(mid))l=mid;else r=mid;}ans=max(ans,a[1].da+l);}if(cnt!=n){swap(a[cnt+1],a[n]);sort(a+1,a+n,[](node x,node y){return x.da<y.da;});ans=max(ans,a[n].da+k+a[n/2].da);}cout<<ans<<'\n';}return 0;
}

d题

• 题目描述
  两只牛，一只叫Bessie，一只叫Elsie，有n个岛，编号为1~n，有n-1条主桥（且为单向桥)，即i—(i+1)，（1<=i<=n-1）。
  还有m条跳跃桥（同为单向桥）。
  Bessie只能走主桥，Elsie两种桥都能走，两个人比谁先到n号岛。Bessie先走，Elsie起点为1号岛。
  当一只牛从i岛去j岛，i岛坍塌。
  输出Bessie起点分别在1,2,…n-1号岛，能否胜利，能输出1，否输出0；

• 题解
  dp
  dp[i]的Elsie的路线可以分为两种：
  1.路线的倒数第二个岛为i-1，枚举从i-1岛出发的跳跃桥。
  2.路线的倒数第二个岛不为i-1,这种情况的最优解为dp[i-1]-1；
  若dp[i]>0，代表Bessie会输

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 2;
int n,m;
int mem[N];//记录Elsie不受阻碍到达各点的最短时间
int dp[N];//记录B牛的起点为i时Elsie能够最多领先的时间
int u,v;
int main(){int t;cin>>t;while(t--){cin>>n>>m;vector<vector<int>>a1(n+1);//后面连接的alternative桥vector<vector<int>>a2(n+1);//前面连接的~~~for(int i=1;i<=m;i++){cin>>u>>v;a1[u].push_back(v);a2[v].push_back(u);}mem[1]=0;for(int i=2;i<=n;i++){mem[i]=mem[i-1]+1;for(auto x:a2[i]){mem[i]=min(mem[i],mem[x]+1);}}dp[1]=-1;cout<<"1";for(int i=2;i<=n-1;i++){dp[i]=dp[i-1]-1;for(auto x:a1[i-1]){dp[i]=max(dp[i],x-i-mem[i-1]-1);}if(dp[i]>0)cout<<"0";else cout<<"1";}cout<<"\n";}return 0;
}

cf963

c题

• 题目描述
  n个房间，$a_i$表示第i个房间灯亮的时间，之后k秒后灯灭，再k秒后灯亮，如此进行下去；
  输出n个房间同时亮的最早时刻，若没有，输出-1；
• 题解
  我们发现n个房间的状态具有周期性，为2k;
  故我们对$a_i$取mod(2k)，模数一样的可看作相同房间，并进行中心化：将最晚开始亮的房间的模数调整到k，方便后续操作,将调整后的数组，记录为b。
  我们考虑最晚开始亮的房间，例如$a_1$，那么我们只需要考察$a_1$到$a_1+k$这个时间段是否有同时亮的情况，我们发现同时亮的充分必要条件为$max(b_i)-min(b_i)$<k。且最早时刻为$a_i+max(b_i)-k$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 2;
ll n,k;
ll m=0;//最晚的房间
ll a[N];
ll b1,b2;//b1:最小mod值，最大mod值
int main() {int t;cin >> t;while (t--) {m=0;cin>>n>>k;b1=k+1,b2=-1;ll nn=2*k;for(int i=1;i<=n;i++){cin>>a[i];m=max(m,a[i]);}ll tmp=k-m%nn;//中心化for(int i=1;i<=n;i++){ll x=(a[i]%nn+tmp+nn)%nn;b1=min(b1,x);b2=max(b2,x);}if(b2-b1<k){cout<<m+b2-k<<'\n';}else{cout<<"-1\n";}}
}

d题

• 题目描述
  给定长度为n的整数数组a,给定k。若a的长度大于k,则选择数组中k个连续的数删去，直到a的长度不大于k停止删除。
  返回所有可能性中最终数组的中位数的最大值。
• 题解
  设最终a的长度为tmp。
  考虑二分
  每次判断最终数组大于等于（或小于）mid的数量的最大值是否大于等于tmp/2+1(或小于(tmp+1)/2)。若是,l=mid;否则，r=mid；
  dp数组
  dp[i]代表从初始数组为$a_1$~$a_i$的最终数组……
  dp2[i]有些许不同，它要求最终数组长度严格小于k。

两种思路：

求<x的数量

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 2;
int n,k;
ll dp[N],dp2[N];
int a[N];
int ans;
int rem(int a, int b) {if (a % b == 0)return b;return a % b;
}
bool check(int x){for (int i = 0; i <= n; i++)dp[i] = 0;for (int i = 1; i <= k; i++)dp[i] = dp[i - 1] + (a[i] < x);for (int i = 1; i <= k - 1; i++)dp2[i] = dp2[i - 1] + (a[i] < x);for (int i = k; i <= n; i++) {dp2[i] = dp2[i - 1] + (a[i] < x);dp2[i] = min(dp2[i], dp2[i - k]);}for (int i = k + 1; i <= n; i++) {dp[i] = dp2[i - 1] + (a[i] < x);dp[i] = min(dp[i], dp[i - k]);}//dp[n]个<x的，rem(n,k)-dp[n]个>=x的 return (rem(n, k) + 1) / 2 > dp[n];
}
int main(){int t;cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];if(n<=k){sort(a+1,a+n+1);cout<<a[(n+1)/2]<<'\n';continue;}// check(7);int l=1,r=1000000001;while(l+1<r){int mid=(r+l)>>1;if(check(mid))l=mid;else r=mid;}cout<<l<<'\n';}return 0;
}

求>=x的数量

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 2;
int n,k;
ll dp[N],dp2[N];
int a[N];
int ans;
bool check(int x){for(int i=1;i<=k;i++){dp[i]=dp[i-1]+(a[i]>=x);dp2[i]=dp[i];}dp2[k]=0;for(int i=k+1;i<=n;i++){if(i%k==0){dp2[i]=dp2[i-k];continue;}dp2[i]=max(dp2[i-1]+(a[i]>=x),dp2[i-k]);}for(int i=k+1;i<=n;i++){dp[i]=max(dp2[i-1]+(a[i]>=x),dp[i-k]);}int tmp=n%k;if(tmp==0)tmp=k;return dp[n]>=((tmp)/2+1);
}
int main(){ios::sync_with_stdio(0);cin.tie(0);int t;cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];if(n<=k){sort(a+1,a+n+1);cout<<a[(n+1)/2]<<'\n';continue;}int l=1,r=INT_MAX;while(l+1<r){int mid=(r+l)>>1;if(check(mid))l=mid;else r=mid;}cout<<l<<'\n';}return 0;
}