ABC293 vp A-G

Dear 丶 2024-03-25 22:36 74阅读 0赞

感觉vpABC比vpCF好太多了，因为至少能开到算法题....

[Tasks - AtCoder Beginner Contest 293][]

**A - Swap Odd and Even**

**模拟**

![e88820657895ec53235e857145173f60.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    string s;
    int n;
    string sub_str(int l,int r){
        return s.substr(l,r-l+1);
    }
    void solve(){
        cin>>s;
        n=s.size();
        s=" "+s;
        for(int i=1;i<=n;i+=2){
            swap(s[i],s[i+1]);
        }
        cout<<sub_str(1,n)<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**B - Call the ID Number**

**模拟**

![5417a63459ebfeb3bf1493065e741345.png][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    vector<int> v;
    map<int,int> mp;
    int n;
    int a[mxn];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            if(!mp[i]) mp[a[i]]++;
        }
        for(int i=1;i<=n;i++){
            if(!mp[i]) v.push_back(i);
        }
        cout<<v.size()<<'\n';
        for(int i=0;i<v.size();i++) cout<<v[i]<<" \n"[i==v.size()-1];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**C - Make Takahashi Happy**

**DFS**

![19990a9c579e916f61c12203b6c7bacf.png][]

思路：

直接暴力DFS

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=1e2+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    map<int,int> mp;
    int n,m,ans;
    int a[mxn][mxn];
    int dx[2]={1,0},dy[2]={0,1};
    int vis[mxn][mxn];
    bool check(int x,int y){
        return x>=1&&x<=n&&y>=1&&y<=m;
    }
    void dfs(int x,int y){
        if(x==n&&y==m){
            ans++;
            return;
        }
        for(int i=0;i<2;i++){
            int vx=x+dx[i],vy=y+dy[i];
            if(check(vx,vy)&&!vis[vx][vy]&&mp[a[vx][vy]]==0){
                vis[vx][vy]=1;
                mp[a[vx][vy]]=1;
                dfs(vx,vy);
                mp[a[vx][vy]]=0;
                vis[vx][vy]=0;
            }
        }
    }
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) cin>>a[i][j];
        }
        vis[1][1]=1;
        mp[a[1][1]]=1;
        dfs(1,1);
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**D - Tying Rope**

**并查集判环**

题意：

有n条绳子，将一些绳子的头尾连接，问你最后有多少环和多少链

![26e716d199eb8dee4a4e30c6dca3c8d9.png][]

思路：

经典并查集判环

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=2e5+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    string p1,p2;
    int n,m,u,v,x,y,cnt;
    int f[mxn];
    int find(int x){
        return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1!=f2) f[f1]=f2;
    }
    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) f[i]=i;
        for(int i=1;i<=m;i++){
            cin>>u>>p1>>v>>p2;
            if(find(u)==find(v)) x++;
            join(u,v);
        }
        for(int i=1;i<=n;i++){
            if(f[i]==i) cnt++;
        }
        cout<<x<<" "<<cnt-x<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**E - Geometric Progression**

**分治+等比数列求和**

![d401fe7fd1a9a1e3a7da4f625fcecad9.png][]

思路：

![10829f774b3da866ce599a0ff781e29c.jpeg][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=2e5+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    int a,x,m;
    int ksm(int a,int b,int mod){
        int res=1;
        while(b>0){
            if(b&1) res=(res*a)%mod;
            a=(a*a)%mod;
            b>>=1;
        }
        return res;
    }
    int sum(int x){
        if(x==1) return 1;
        if(x%2==0) return ((1+ksm(a,x/2,m))*sum(x/2)%m)%m;
        return (1+a*sum(x-1))%m;
    }
    void solve(){
        cin>>a>>x>>m;
        cout<<sum(x)%m<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**F - Zero or One**

**枚举+二分**

![19f35bc280d19efc1750ea619e900d8f.png][]

思路：

对于2~1000进制，直接去暴力check

对于更大的进制，更换枚举对象

去枚举01串，对于每一个01串，去二分刚好满足条件的进制，如果这个进制>1000，就加上贡献

Code：

// हर हर महादेव
    using namespace std;
    #include <bits/stdc++.h>
    #define int long long int
    
    const int lim = 1e3 + 5;
    const int dig = 7;
    const int N = (int) 1e18 + 50;
    const int inf = (int) 1e18 + 50;
    
    bool check(int n,int b){
        while(n){
            if(abs(n % b) > 1){
                return false;
            }
            n /= b;
        }
        return true;
    }
    
    int interpret_in_base_b(int mask,int b){
        int ans = 0;
        __int128 pw = 1;
        bool flag = false;
        for(int i = 0; i < dig; i++){
            if(1 << i & mask){
                if(flag){
                    return inf;
                }
                ans += pw;
            }
            pw *= b;
            if(pw > N){
                flag = true;
            }
        }
        return ans;
    }
    
    int binary_search_base(int n,int mask){ // value of b for which mask interpreted in base b is equal to n. Returns -1 if there is no such b
        int l = 0,r = N,ans = -1;
        while(l <= r){
            int m = (l + r) >> 1;
            if(interpret_in_base_b(mask,m) <= n){
                ans = m;
                l = m + 1;
            }
            else{
                r = m - 1;
            }
        }
        
        return interpret_in_base_b(mask,ans) == n ? ans : -1;
    }
    
    void testcase(){
        
        int n; cin >> n;
        
        // checking for b in [2,1000)
        int ans = 0;
        for(int i = 2; i < lim; i++){
            ans += check(n,i);
        }
        
        
        // bitmasking + binary search
        for(int mask = 1;mask < (1 << dig);mask++){
            int here = binary_search_base(n,mask);
            if(here >= lim){
                ans++;
            }
        }
        cout << ans << '\n';
    }
    
    int32_t main(){
        ios::sync_with_stdio(false);cin.tie(0);
        
        int tt; cin >> tt;
        
        while(tt--){
            testcase();
        }
        return 0;
    }

**G - Triple Index**

**莫队**

![200f0adcd10059a5726c656615d3811d.png][]

思路：

第一次写莫队，有点紧张

莫队利用了分块思想，把询问离线处理，然后按块的ｌ进行排序，减少指针移动次数

唯一要改的就是add和del函数

具体看代码：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    int n,m,sq,l=1,r=0,cur;
    int a[mxn],cnt[mxn],ans[mxn],block[mxn];
    struct Query{
        int l,r,id;
    }Q[mxn];
    bool cmp(Query a,Query b){
        if(block[a.l]!=block[b.l]) return a.l<b.l;
        if(block[a.l]&1) return a.r<b.r;
        return a.r>b.r;
    }
    int C3(int x){
        return x*(x-1)*(x-2)/6;
    }
    void add(int p){
        cur-=C3(cnt[a[p]]);
        cnt[a[p]]++;
        cur+=C3(cnt[a[p]]);
    }
    void del(int p){
        cur-=C3(cnt[a[p]]);
        cnt[a[p]]--;
        cur+=C3(cnt[a[p]]);
    }
    void solve(){
        cin>>n>>m;
        sq=ceil(1.*n/sqrt(m));
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++){
            cin>>Q[i].l>>Q[i].r;
            Q[i].id=i;
            block[i]=(i-1)/sq+1;
        }
        sort(Q+1,Q+1+m,cmp);
        l=1,r=0;
        for(int i=1;i<=m;i++){
            while(l>Q[i].l) add(--l);
            while(r<Q[i].r) add(++r);
            while(l<Q[i].l) del(l++);
            while(r>Q[i].r) del(r--);
            ans[Q[i].id]=cur;
        }
        for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Tasks - AtCoder Beginner Contest 293]: https://atcoder.jp/contests/abc293/tasks
[e88820657895ec53235e857145173f60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/600e213f3be4433c84db7c279bd9d541.png
[5417a63459ebfeb3bf1493065e741345.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/cb4e8f91b523431ca80b8d39d41a007e.png
[19990a9c579e916f61c12203b6c7bacf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/3f8ee75e78664cfb816fcc5cf4fe1c2b.png
[26e716d199eb8dee4a4e30c6dca3c8d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8c1e2cf684c64d63ba2ac811c8c3ce70.png
[d401fe7fd1a9a1e3a7da4f625fcecad9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/07c1c90b8d32480c9501b15296d32f0f.png
[10829f774b3da866ce599a0ff781e29c.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/cc8dd49bfa6241e79cb3dc1ebeae251b.png
[19f35bc280d19efc1750ea619e900d8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/298b298267f04995bf6287c2fbed7deb.png
[200f0adcd10059a5726c656615d3811d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/33a096deba7b4d87a40bf5e773201c7d.png