Codeforces Round 967 (Div. 2)(A,B,C,D)
A Make All Equal
题意
给定一个序列,每次如果a[i]<=a[i+1]则可以删除这两个的任意一个,问找出使a中所有元素相等所需的最小删除次数
思路
最小的删除次数就是保留相同数字最多的那个数的删除次数,无论如何都可以保留这个数,因为假如是3334那么可以根据3和4把4删了,假如是3332那么可以根据2和第一个3把2删了
代码
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
void solve()
{cin>>n;map<int,int>mp;int ma=0;_rep(i,1,n)cin>>m,mp[m]++,ma=max(ma,mp[m]);cout<<n-ma<<'\n';return ;
}B:Generate Permutation
题意
已知有一个排列,两个打字机,一个从1位置开始向右一个从n位置开始向左,
现在可以打字了,每次打字只能从1开始按顺序,比如现在在x位置,那么当你在x选择是否打字(假设是第一次)，如果是x位置就是1,
假设你用第一个打字机从1开始不断往右,走到后面又想在前面打字了,那么可以选择使用一个回车再把打字机重新指向1
现在问的是构造一个序列使得用第一个打字机和第二个打字机所使用的最少回车数相同,如果没有则输出-1
例如:3 1 2
那么用第一个打字机,第一个位置不打,然后第二个位置打1,第三个位置打2然后回车 然后第一个位置打3
那么用第二个打字机,第三个位置不打,然后第二个位置打1,第一个位置不打然后回车 然后第三个位置打2,第一个位置打3
思路
通过手玩可以发现偶数都不行,首先2不行然后枚举4的所有情况也不行,保险起见可以打表
然后奇数就是假设是7输出7 6 5 1 2 3 4,
代码
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
int n,m;
void solve()
{cin>>n;if(n%2==0)cout<<"-1\n";else {_pre(i,n,(n+1)/2+1)cout<<i<<" ";_rep(i,1,(n+1)/2)cout<<i<<" ";cout<<'\n';}return ;
}C:Guess The Tree
题意
交互题,只会给定一个树的大小,然后每一次都可以询问两个节点a,b,然后返回一个x,满足|d(a,x)-d(b,x)|最小，其中d为两点之间最短距离,如果有多个x满足,返回离a最近的x
要求:询问次数<=15n
思路
每次询问当然是返回a-b路径上的中间点,如果a-b(包括a,b)有偶数个点就返回满足条件的两个点中离a近的那个点
自己一开始的写法是每次询问为(1,2),(1,3),...(1,n)然后每一次询问(a,b),假设返回值不是a(代表a,b不相邻)那就递归处理(a,x),(x,b)
但是可能会这样的树1-2-3-4-5-6-7-...-1000,然后我每次询问的时候都会递归2*i-1次(i=2,3,...n)显然会超过规定询问次数,所以要经过各种优化才能过(比如,已经遍历过的点不用再递归遍历,然后已经询问过的组合(a,b)不用再询问)
最后捋了一下思路
一种稳定一点的写法就是,把这一棵树看作以1为根的有向树,虽然每个点出度不一,但是每个点只有一个父结点(除了1)
所以从这个角度出发,从1开始递归处理所有的(1,i),但是要注意一个点,那就是一次递归中遍历到的所有点其实都已经确定下来了
就比如假设是1-3-5-2-4,但是我询问的是(1,2),我在递归的过程中一定把3,5,2都标记为已确定,这样就可以避免重复查找(下一次递归(a,b)如果b是已经确定的那么就说明递归不用再继续下去了)
于是最差平均每个点询问次数也只有logn,于是可以完美解决这个题
代码
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <time.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
bool st[N];
set<PII>v;
int ask(int a,int b)
{int x;printf("? %lld %lld\n",a,b);fflush(stdout);scanf("%lld",&x);return x;
}
void deal(int a,int b)
{int x=ask(a,b);if(x==a){v.insert({a,b});st[b]=true;return;}else{if(!st[x])deal(a,x);if(!st[b])deal(x,b);}return;
}
void solve()
{
// cin>>n;sf(n);v.clear();_rep(i,1,n)st[i]=false;_rep(i,2,n)if(!st[i])deal(1,i);printf("!");for(auto i:v)printf(" %lld %lld",i.fi,i.se);printf("\n");fflush(stdout);return ;
}
signed main()
{
// IOS;int T=1;sf(T);
// cin>>T;while(T--)solve();return 0;
}D:Longest Max Min Subsequence
题意
给定一个序列,找一个最长的子序列使得子序列各个元素都不相同并且满足最后得到的这个子序列的奇数位都乘-1之后子序列的字典序最小
思路
首先这个子序列的值肯定是原序列中去重之后的所有值,那么现在就要考虑以什么顺序选这些值可以使这个子序列字典序最小
先不考虑奇数位
按照贪心的思想,假如我此时所有的元素都可以选,那么为了使字典序最小,我肯定每次优先选最小的数,这样显然就可以了,但是本题中如果先选了后面更小的数,会导致前面某个的数字没选上但是后面又再也不会出现这个数字了,这样一定是错解
所以要是每次都能找到一个区间,这个区间里面可以任意选择某个数,那我就可以轻松每次找到区间的最小值
于是构建了一个next数组,每一个位置对应自己这个数字下一个位置出现的下标,如果没有的话就指向n+1,
第一次统计答案如下图
可以发现,我从左往右找到1的时候,发现此时位置上的1是最后一次出现的了,所以我这个1是必选的,那么前面的5 2就可以任意选择选或不选,现在发现此时5 2 1中最小值为1所以选1,并且接下来前三个数不会再选了,此时的答案序列为{1}
第二次如下图
第二次右指针走到9的时候发现这个位置的9是最后一次出现的9,于是考虑7 9(9在这一轮最后必选),显然优先选最小值7,然后选9,此时的答案序列为{1,7,9}
第三次如下图:
PS:由于7已经选过所以不必考虑7
这一轮分析同上两次,这一轮先选2再选5所以此时的答案序列为{1,7,9,2,5}
第四次由于2已经选过,结束,所以最终答案为{1,7,9,2,5}
动态维护集合中的最小值我这里用了multiset,multiset从begin()开始到end()自然就是从小到大的,所以访问*s.begin()即可,并且可以支持删除某个元素
然后现在考虑奇数位置乘上-1,那么为了使字典序最小,轮到判断奇数位的时候显然要找最大值,multiset从rbegin()开始到rend()就是从大到小的,所以访问*s.rbegin()即可
multiset可以删除集合中某一个值的所有元素,这样可以避免重复选中某个数，时间复杂度O(mlogn)m为重复元素的数量
auto range=s.equal_range(now);s.erase(range.first,range.second);于是本题得解
代码
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define pp pop_back()
#define int long long
#define laile cout<<"laile"<<endl
#define lowbit(x) ((x)&(-x))
#define double long double
#define sf(x) scanf("%lld",&x)
#define sff(x,y) scanf("%lld %lld",&x,&y)
#define sd(x) scanf("%Lf",&x)
#define sdd(x,y) scanf("%Lf %Lf",&x,&y)
#define _for(i,n) for(int i=0;i<(n);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _pre(i,a,b) for(int i=(a);i>=(b);--i)
#define all(x) (x).begin(), (x).end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef unsigned long long ULL;
typedef pair<int,int>PII;
const int N=1e6+10,INF=4e18;
int n,m;
int q[N],ne[N],now[N];
bool st[N];
void solve()
{multiset<int>s;bool bl=0;cin>>n;_rep(i,1,n)cin>>q[i],now[i]=n+1,st[i]=false;_pre(i,n,1){ne[i]=now[q[i]];now[q[i]]=i;}
// _rep(i,1,n)cout<<ne[i]<<" ";
// cout<<endl;vector<int>res;int r=1,l=1;while(r<=n){while(r<=n&&(ne[r]!=n+1||st[q[r]])){if(!st[q[r]])s.insert(q[r]);r++;}if(r>n)break;s.insert(q[r]);
// cout<<"s:";
// for(auto i:s)cout<<i<<" ";
// cout<<endl;int now;if(!bl){auto t=s.rbegin();if(t!=s.rend())now=*t;}else{auto t=s.begin();if(t!=s.end())now=*t;}
// cout<<"now="<<now<<endl;res.pb(now);auto range=s.equal_range(now);s.erase(range.first,range.second);while(l<r){auto t=s.find(q[l]);if(t!=s.end())s.erase(t);if(q[l]==now)break;l++;}st[now]=true;bl=!bl;}cout<<(int)res.size()<<'\n';for(auto i:res)cout<<i<<" ";cout<<"\n";return ;
}
signed main()
{IOS;int T=1;cin>>T;while(T--)solve();return 0;
}