Codeforces Round 967(Div.2)
A.Make All Equal
1.题面分析
废话这么多,说白了就是求总数减去最多出现数的个数的值。
2.解法
直接用桶装一下,然后扫一遍维护最大值。
3.code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+520;
int t,n,sum[N];
int main()
{
cin>>t;
while(t--)
{
memset(sum,0,sizeof(sum));
int ans=-1;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
sum[x]++;
}
for(int i=1;i<=200;i++) ans=max(ans,sum[i]);
cout<<n-ans<<endl;
}
return 0;
}
B.Generate Permutation
1.题面分析
又是典型的复杂题面+构造,样例也看不出来什么,此时就该想到找规律大法。
2.解法
简单枚举一下小数,可以发现n为偶数结果为-1,n为奇数时构造的序列可以形成规律性。
例子:
n=7
序列:1 3 5 7 6 4 2
3.code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+520;
int t,n;
int main()
{
cin>>t;
while(t--)
{
cin>>n;
if(n%2==0) {cout<<-1<<endl;continue;}
else
{
for(int i=1;i<=n;i+=2){cout<<i<<" ";}
for(int i=n-1;i>0;i-=2){cout<<i<<" ";}
cout<<endl;
}
}
return 0;
}
C.Guess The Tree Permutation
1.题面分析
一秒发现交互题
,询问返回的为\(a\)和\(b\)之间路径的中点。
2.解法
通过一步步拓展连接部分建树。设两个集合分别为\(A\)和\(B\),在\(B\)不为空的情况下,任意选择\(a \in A\)和\(b \in B\)。设\(P\)为\(a\)和\(b\)之间的路径,然后二分查找一下\(i\)中的第一个\(P_i \in B\)。最终,让\((P_{i-1}, P_i)\)成为树的一条边即可。
3.code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+520;
int query(int a,int b)
{
cout<<"? "<<a+1<<" "<<b+1<<endl;
cout<<endl;
int x;cin>>x;
return x-1;
}
void solve()
{
int n;cin>>n;
vector<int>in(n,0),s;
for(int i=1;i<n;++i)s.push_back(i);
in[0]=1;
vector<pair<int,int> >q;
while(!s.empty())
{
int u=s.back();s.pop_back();
if(in[u]) continue;
int l=0,r=u;
while(1)
{
int v=query(l,r);
if(v==l)
{
in[r]=1;
q.push_back({l,r});
break;
}
if(in[v]) l=v;
else r=v;
}
s.push_back(u);
}
cout<<"! ";
for(auto [x,y]:q) cout<<x+1<<" "<<y+1<<" ";
cout<<endl;
}
int main()
{
int t;cin>>t;
while(t--) solve();
return 0;
}
蟹不动了
总结
- 在比赛过程中,前面的题写的太慢,下次需要将前两题控制在半小时内。
- 需要学会新题型的写法,尝试新题型。
完结收工!!!!!
看完点赞,养成习惯
\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)
标签:back,967,int,Codeforces,long,cin,while,Downarrow,Round From: https://www.cnblogs.com/qc0817/p/18377027