Day1 CF847 div3 vp A-E

川长思鸟来 2024-03-27 10:50 85阅读 0赞

[Dashboard - Codeforces Round \#847 (Div. 3) - Codeforces][Dashboard - Codeforces Round _847 _Div. 3_ - Codeforces]

**感觉想试试隔一天vp一场div3/4，那就试试吧**

**本来想把F补完再写的，但是感觉有点晚了，那就将就一下吧，F有缘单独补，嘻**

**今晚浅浅vp了一下，一鼓作气地打出了newbie水平，乐**

![22d97f17aae1e716826bb8dc4f31f617.png][]

**龟速签到，只能说不愧是我，以后签到还是靠队友算了**

**D题还写了个模拟，爆T，鉴定为低能，其实只需要算算贡献就好了**

A. Polycarp and the Day of Pi

模拟

题意：

给定一个字符串，问和圆周率的最长匹配是多长

思路：

模拟就好了

通过这个签到，让我认识到C++里pi咋写的：

const double pi = acos(-1.0);

应该就我不知道了吧

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e2+10;
    string s;
    string s2="3141592653589793238462643383279";
    void solve(){
        s.clear();
        cin>>s;
        int ansi=0;
        for(int i=0;i<=30;i++){
            if(s[i]!=s2[i]){
                ansi=i;
                break;
            }
        }
        cout<<ansi<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

B. Taisia and Dice

纯构造

题意：

给定n,s,r，n是数列长度，s是所有数之和，r是除了最大值的所有数之和，让你构造一个这样的数列

思路：

这样就相当于把最大值告诉你了，然后让你构造剩下的n-1个数

构造，那就让它特殊化

第一个放最大值，然后后面让它平均分配

（感觉这种构造不是平均分配就是集中在一处）

那我选择平均分配，即把r平均分配到n-1个地方

那显然不一定能平均分配，就让它下取整然后分配剩下的1就好了

这种写法值得一学，感觉很妙！

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e2+10;
    int n,s,r;
    void solve(){
        cin>>n>>s>>r;
        vector<int> v(n+1);
        v[0]=s-r;
        int x=r%(n-1),k=r/(n-1);
        for(int i=1;i<n;i++){
            if(i<=x) v[i]=k+1;
            else v[i]=k;
        }
        for(int i=0;i<n;i++) cout<<v[i]<<" \n"[i==n-1];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

C. Premutation

（拓扑排序板子题）

题意：

一个长度为 n 的排列，将 n个这样的排列每个去掉一位然后打乱。根据打乱后的排列求出原排列。

思路：

纯纯拓扑排序板子题，本来不敢写，结果看到数据范围这么小就试着写了一发，一交真的过了，乐，有种abc的美

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10,mxe=1e6+10;
    struct ty{
        int to,next;
    }edge[mxe<<1];
    vector<int> ans;
    queue<int> q;
    int n,x,tot=0;
    int head[mxn],in[mxn];
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void init(){
        ans.clear();
        tot=0;
        for(int i=0;i<=n;i++){
            in[i]=0;
            head[i]=-1;
        }
    }
    void topsort(){
        for(int i=1;i<=n;i++){
            if(!in[i]) q.push(i);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            ans.push_back(u);
            for(int i=head[u];~i;i=edge[i].next){
                in[edge[i].to]--;
                if(!in[edge[i].to]){
                    q.push(edge[i].to);
                }
            }
        }
    }
    void solve(){
        cin>>n;
        init();
        for(int i=1;i<=n;i++){
            vector<int> v;
            v.push_back(0);
            map<pair<int,int>,int > mp;
            for(int j=1;j<=n-1;j++) cin>>x,v.push_back(x);
            for(int j=1;j<=n-1;j++){
                for(int k=j+1;k<=n-1;k++){
                    if(!mp.count({v[k],v[j]})) add(v[k],v[j]),in[v[j]]++,mp[{v[k],v[j]}]++;
                }
            }
        }
        topsort();
        reverse(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++) cout<<ans[i]<<" \n"[i==ans.size()-1];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

D. Matryoshkas

贪心（直接计算贡献！）

题意：

给定一个集合，将该集合分成若干个由连续正整数组成的集合，求分成集合的数量的最小值。

思路：

这道题，一开始看起来很神秘啊，感觉就是要不贪心要不dp，div3D怎么可能dp，那肯定就是贪了

然后想了很久这怎么贪，肯定就是每次取最长连续的然后拿走，问要拿几次

然后难道是暴力吗，然后我就真的写了发暴力：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10,mxe=1e6+10;
    map<int,int> mp;
    int n;
    int a[mxn];
    void solve(){
        mp.clear();
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
        int cnt=n,ans=0;
        while(cnt>=1){
            ans++;
            int ansi;
            auto it=mp.begin();
            while(it!=mp.end()){
                if(it->second!=0){
                    ansi=it->first;
                    break;
                }
                it++;
            }
            for(int i=ansi;;i++){
                if(mp[i]>=1) mp[i]--,cnt--;
                else break;
            }
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

然后果不其然T15了，好死捏

其实这个暴力，我写了好久，就是对map用法不熟悉

通过这道题可以学学怎么用map！

其实这道题就是直接计算贡献，完全不需要模拟

![c230d4da7cbeaf4fa8ccd5c228e710b7.png][]

据说这里用umap会被hack，我的评价是狗都不用

**在考虑贪心的时候，直接计算贡献就好了！**

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10,mxe=1e6+10;
    int n;
    void solve(){
        cin>>n;
        vector<int> v(n+1);
        map<int,int> mp;
        for(int i=1;i<=n;i++) cin>>v[i],mp[v[i]]++;
        int last_x=-1,last_y=-1;
        int ans=0;
        for(auto [x,y]:mp){
            if(x!=last_x+1) last_y=0;
            ans+=max(0ll,y-last_y);
            last_x=x;
            last_y=y;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

E. Vlad and a Pair of Numbers

bitmask+构造

题意：

![69b36be4e5b6b63c2ce74a586d2626ee.png][]

思路：

喜闻乐见的bitmask+构造

bitmask嘛，那就去考虑二进制位

因为是在二进制位里构造，那么特殊一点，把所有异或的其中那个1挪到a，这样对答案没影响

然后去考虑限制条件

二进制里相加会进位，然后/2就是右移1位

因为两者相等，那么在a=1,b=0这一对右边，一定是a=1,b=1，这样才满足

为什么呢，这样右边相加后**进两位**，1就会跑到a=1,b=0这一对的左边了，然后/2右移一下，就刚好相等了

这个其实观察样例也能得出来

不存在的情况就是，x有相邻的1或第0位是1，这个看样例也能得出来

bitmask的样例很重要！要记得观察！

然后就能构造出来了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10,mxe=1e6+10;
    int x;
    void solve(){
        int a=0,b=0;
        cin>>x;
        if(x&1){
            cout<<-1<<'\n';
            return;
        }
        for(int j=30;j>=0;j--){
            if(((x>>j)&1)==1 && ((x>>(j-1))&1)==1){
                cout<<-1<<'\n';
                return;
            } 
        }
        for(int j=30;j>=0;j--){
            if((x>>j)&1){
                a|=(1<<j);
                a|=(1<<(j-1));
                b|=(1<<(j-1));
            }
        }
        cout<<a<<" "<<b<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Dashboard - Codeforces Round _847 _Div. 3_ - Codeforces]: https://codeforces.com/contest/1790
[22d97f17aae1e716826bb8dc4f31f617.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/172b61849f614ea28c34e7b797c5c10b.png
[c230d4da7cbeaf4fa8ccd5c228e710b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/87bf92ca2c164fc3b354318dc4e9ba2f.png
[69b36be4e5b6b63c2ce74a586d2626ee.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1a033537161e49439336b1c49b67526e.png