首页 > 其他分享 >Codeforces Round 967(Div.2)之赛后总结

Codeforces Round 967(Div.2)之赛后总结

时间:2024-08-23 20:28:33浏览次数:13  
标签:back 967 int Codeforces long cin while Downarrow Round

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;
}

蟹不动了

总结

  1. 在比赛过程中,前面的题写的太慢,下次需要将前两题控制在半小时内。
  2. 需要学会新题型的写法,尝试新题型。

完结收工!!!!!

个人主页

看完点赞,养成习惯

\(\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

相关文章

  • Codeforces Round 967 (Div. 2) ABCD
    来源:CodeforcesRound967(Div.2)做题时间:2024_08_21A.MakeAllEqual使所有元素相等的最小操作次数,就是保留最大的数字所以操作次数就是总数减去数量最多得数B.GeneratePermutation题意构造一个序列\(p\),内部元素是\([1,2,\cdots,n]\)打乱使长度为\(n\)的初始......
  • C# start thread include Thread,Task,Async/Await,BackgroundWorker,ThreadPool,Time
    usingSystem;usingSystem.Collections.Generic;usingSystem.ComponentModel;usingSystem.Linq;usingSystem.Text;usingSystem.Threading;usingSystem.Threading.Tasks;usingSystem.Windows;usingSystem.Windows.Controls;usingSystem.Windows.Data;using......
  • Solution - Codeforces 1970G3 Min-Fund Prison (Hard)
    时间\(\mathcal{O}(\frac{n\sqrt{n}\logn}{\omega})\)空间\(\mathcal{O}(\frac{n\logn}{w})\)的爆标做法。首先无解当且仅当图联通且无割边。首先考虑加边的贡献。一个比较直观的感受就是只会尽可能少的加边,即加边到整个图连通。证明考虑删掉的边。如果加多了边导致删......
  • Codeforces Round 967 (Div. 2)-D
    CodeforcesRound967(Div.2)-D这些天在留校集训……我之前空余时间在看模电,最近在玩黑猴……九月开学了估计也不能闲下来……但这个博客我还是会抽空更新的╰(°▽°)╯Problem-D-Codeforces虽然代码写得特别丑陋,但好歹是我完全想的思路——自己还de了一天bug(゜ー゜)......
  • .NetCore里使用定时任务BackgroundService
    原文链接:https://blog.csdn.net/x1234w4321/article/details/140797306namespaceXCGWebApp.TimerService{///<summary>///后台定时任务///</summary>publicclassTimerBackgroundService:BackgroundService{protectedoverrid......
  • Codeforces Round 967 (Div. 2)
    题不难。A.MakeAllEqual题意:一个圆,上面有\(n\)个数,每次可以删去相邻的两个不同数中任意一个,求至少几次使得剩下的数都一样。显然下界是出现次数最多的数且一定能取到,时间复杂度\(O(n)\)。提交记录B.GeneratePermutation题意:要求构造一个排列,使得\(x\)所在位置大......
  • CF 2001 E2 solution (967 Div.2)
    CF2001E2由于对称,所以设\(heap[u]\)为两次确定堆,且第一次弹出的是\(u\),\(heap[u,v]\)是第一次\(u\),第二次\(v\)则答案就是\(\sumheap[u]=2^{n-1}·heap[x]\)其中\(x\)任意。不妨我们考虑第一次都是从第一个叶子弹出,那么对于其他不同的第二个弹出的点,根据对称性......
  • 题解:Codeforces Round 967 (Div. 2) B [思维/构造]
    B.GeneratePermutationtimelimitpertest:1.5secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputThereisanintegersequence\(a\)oflength\(n\),whereeachelementisinitially\(-1\).Misukihastwoty......
  • Codeforces Round 966 (Div. 3)
    A.PrimaryTask#include<bits/stdc++.h>usingnamespacestd;usingvi=vector<int>;voidsolve(){strings;cin>>s;if(s.size()<=2){cout<<"NO\n";return;}if(s[0]!......
  • 题解:Codeforces Round 967 (Div. 2) [暴力/贪心]
    A.MakeAllEqualtimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouaregivenacyclicarray\(a_1,a_2,\ldots,a_n\).Youcanperformthefollowingoperationon\(a\)atmost\(n-......