首页 > 其他分享 >AtCoder Beginner Contest 293

AtCoder Beginner Contest 293

时间：2023-03-14 21:33:07浏览次数：58  
标签：AtCoder Beginner int ll cin Edge pmatrix include 293

题解报告

基本的一些理解和问题都在注释中
A：Swap Odd and Even

//水题
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s;cin>>s;
    int len=s.size();
    for(int i=0;i*2<len;i++)
        swap(s[2*i],s[2*i+1]);
    cout<<s<<endl;
    return 0;
}

B：Call the ID Number

//水题
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=2e5+10;
int num[maxn];
int flag[maxn];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int N;cin>>N;
    for(int i=1;i<=N;i++)cin>>num[i];
    for(int i=1;i<=N;i++)
        if(!flag[i])flag[num[i]]=1;
    int res=0;
    for(int i=1;i<=N;i++)if(!flag[i])res++;
    cout<<res<<endl;
    for(int i=1;i<=N;i++)if(!flag[i])cout<<i<<' ';
    cout<<endl;
    return 0;
}

C：Make Takahashi Happy

//水题
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
const int maxn=15;
int W[maxn][maxn];
int dirx[2]={0,1};
int diry[2]={1,0};
unordered_map<int,int> mp;
int N,M,res;
void dfs(int x,int y)
{
    if(x==N&&y==M) {
        ++res;
    }
    else{
        for(int i=0;i<2;i++)
        {
            int fx=dirx[i]+x;
            int fy=diry[i]+y;
            if(fx<=N&&fy<=M&&!mp[W[fx][fy]])
            {
                mp[W[fx][fy]]=1;
                dfs(fx,fy);
                mp[W[fx][fy]]=0;
            }
        }
    }
    return;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>N>>M;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            cin>>W[i][j];
    mp[W[1][1]]=1;
    dfs(1,1);
    cout<<res<<endl;
    return 0;
}

D：Tying Rope
题目大意： 把一些线连接起来，找联通和环。
我使用的是建图然后暴力搜索，好像并查集也可以做

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=2e5+10;
int vis[maxn];
int vis2[maxn];//这个是里面看的。
struct edge
{
    int R,B;
}Edge[maxn];
bool dfs(int u,int dir)//第二个记录哪边不能走
{
    if(u==0)return false;
    vis[u]=1;
    vis2[u]=1;
    bool res=false;
    if(dir!=1)//蓝色的不能走 
    {
        int Dir=0;
        if(Edge[Edge[u].R].B==u) Dir=0;
        else Dir=1;
        if(vis2[Edge[u].R])return true;
        else{
            res|=dfs(Edge[u].R,Dir);
        }
    }
    if(dir!=0)//红色的不能走
    {
        int Dir=0;
        if(Edge[Edge[u].B].B==u)Dir=0;
        else Dir=1;
        if(vis2[Edge[u].B])return true;
        else{
            res|=dfs(Edge[u].B,Dir);
        }
    }
    return res;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int N,M;cin>>N>>M;
    for(int i=0;i<M;i++)
    {
        char op1,op2;
        int u,v;
        cin>>u>>op1>>v>>op2;
        if(op1=='R'){
            if(op2=='R'){
                Edge[u].R=v;
                Edge[v].R=u;
            }else{
                Edge[u].R=v;
                Edge[v].B=u;
            }
        }else{
            if(op2=='R'){
                Edge[u].B=v;
                Edge[v].R=u;
            }else{
                Edge[u].B=v;
                Edge[v].B=u;
            }
        }
    }
    int res1=0,res2=0;
    for(int i=1;i<=N;i++)
    {
        if(!vis[i])
        {
            if(dfs(i,-1))res1++;//1代表红。
            else res2++;
        }
    }
    cout<<res1<<' '<<res2<<endl;
    return 0;
}

E：Geometric Progression
题目大意： 求一个等比数列的和后取模。
等比数列有如下性质：
\(S_n=q*S_{n-1}+1\)
可以知道等比数列的前\(N\)项的和是可以通过递推式写出来的。可以考虑利用矩阵的乘法实现一步一步的递推
有如下形式：

\[\begin{pmatrix} S_{n+1}\\ 1\\ \end{pmatrix}=\begin{pmatrix} q&1\\ 0&1\\ \end{pmatrix} \begin{pmatrix} S_n\\ 1\\ \end{pmatrix}.\]

取\(S_0\)=0,则有

\[\begin{pmatrix} S_n\\ 1\\ \end{pmatrix}=\begin{pmatrix} q&1\\ 0&1\\ \end{pmatrix}^n\begin{pmatrix} 0\\ 1\\ \end{pmatrix}\]

从上面可以看出，利用矩阵的快速幂求取\(n\)次方后,获得的矩阵的右上角就是\(S_n\)。
如果这里使用等比数列的求和公式的话会有如下式子：
\(\sum_{i=0}^{n-1}q^i=\frac {q^n-1}{q-1}\),其中\(q-1\)是要用逆元来取模的，但是这道题目的模数不一定是质数，所以不一定能拿来用，所以不能用这种方法，要用矩阵快速幂。

//等比数列求和
//注意质数，这里的求乘法逆元的时候只有质数才能用来取模，不是质数就不可以。
//这道题的模数是不确定的，所以不能使用逆元。
//然后用矩阵运算的规则
//以后遇到等比数列求和且模不确定的数，就直接用矩阵快速幂。
//矩阵的快速幂适用于有递推公式的。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
void mul(ll A[2][2],ll B[2][2],int MOD)
{
    ll temp[2][2];
    memset(temp,0,sizeof(temp));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                temp[i][j]=(temp[i][j]+A[i][k]*B[k][j])%MOD;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            A[i][j]=temp[i][j];
}
int M_fpow(ll A,ll B,int MOD)
{
    ll res[2][2]{{1,0},{0,1}};
    ll M[2][2]={{A,1},{0,1}};
    while(B)
    {
        if(B&1)mul(res,M,MOD);
        B>>=1;
        mul(M,M,MOD);
    }
    return res[0][1];
}
//X次方取右上角
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll A,B,C;cin>>A>>B>>C;
    cout<<M_fpow(A,B,C)<<endl;
}

F：Zero or One
（我刚开始没读懂题目，还是看了别人的题解才懂的，菜是原罪）
这道题目居然能用二分写，终究是我写的题目少了，想都想不到。

//二分的题目，用所有可能的状态和原来的状态进行匹配
//如果是看进制的话，就可以把一个数分成好几部分来进行判断，但是又不能分很多份
//所以要先处理好一些要分成很多区间的进制，最后剩下的就是比较大的进制，然后对所有的状态进行枚举判断就行了，看看后面的状态是否能有对应的进制来满足。
//这道题主要是根据不同的区间利用不同的算法进行判断。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
bool Invalid(int bit,ll num)//先把一些小的进制枚举掉，那么就可以缩小最后需要枚举的状态的范围
{
    while(num)
    {
        if(num%bit>1)return false;
        num/=bit;
    }
    return true;
}
int check(ll bit,int state,ll num)//这里是最容易出错的地方，如果没有限制好就非常容易超出去
{
    __int128 now=0,Now_bit=1;//防止两个乘起来后很大//用__int128
    for(int i=0;i<7;i++)
    {
        if(state>>i&1)
        {
            if(Now_bit>num)return 1;//这里是联合下面一起来限制的，太大了就不行。
            now+=Now_bit;
        }
        if(now>num)return 1;
        if(Now_bit<2e18)Now_bit*=bit;//这个累乘法的是很大的比如说bit为1e18那么在只有最后一位是1的时候就有(1e18)^6非常大，要限制
    }
    if(now==num)return 0;
    else return -1;
}
bool Has_bit(int state,ll num)//利用状态去找进制，看看能不能找到
{
    ll l=1001,r=2e18;
    //二分去找，有判断的条件，有大有小
    while(l<r)
    {
        ll mid=(l+r)>>1;
        if(check(mid,state,num)!=-1)r=mid;
        else l=mid+1;
    }
    //最后还要判断下合不合法
    return check(l,state,num)==0;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--)
    {
        ll N;cin>>N;
        ll ans=0;
        for(int i=2;i<=1000;i++)if(Invalid(i,N))ans++;//先处理前一千以内的进制。
        for(int i=1;i<1<<7;i++)if(Has_bit(i,N))ans++;
        cout<<ans<<endl;
    }
    return 0;
}

最后一题好像是板子题，但是我不会，哎~~（原因还是懒得学）
学了莫队再说吧。

标签：AtCoder,Beginner,int,ll,cin,Edge,pmatrix,include,293
From： https://www.cnblogs.com/WUTONGHUA02/p/17216497.html

相关文章

  • AtCoder Beginner Contest 240 F
    ABC240F思路维护前缀和B，以及B的前缀和C，然后在每次添加连续y个x的时候，从中找出最大的\(C_i\)(用pre记录)，更新答案。有四种情况\(B\geq0,x>0\)那么新出现的\(C_i\)中......
  • atcoder ABC
    Ex-OptimalPathDecomposition题目只能给链染色，问你最短的（两点距离最大值），距离为不同颜色个数f[u],g[u]，f表示u可以和father同一个颜色，g表示不可以。转移记录三个值。......
  • ABC 293 ABCD(并查集)
    A-SwapOddandEven#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<LL,LL>PII;constLLMAXN=1e18,MINN=-1e18;constLLN=1e6......
  • ATABC293D Tying Rope
    ATABC293DTyingRope题意有\(N\)根一端涂成红色，另一端涂成蓝色的绳子，现进行\(M\)次操作，第\(i\)次操作给出两个整数\(A_i\)，\(C_i\)与两个字符\(B_i\)，\(D_i\)，表......
  • 题解 ABC293D【Tying Rope】
    颜色是不好处理的，我们不妨不区分绳子的两个端点，将每条绳子作为一个节点，每条边直接将两个节点连接起来。每个绳子的端点本质上是保证了每个点的度数不超过\(2\)，也就是说图......
  • 题解 ABC293E【Geometric Progression】
    由于模数不一定是大质数，我们不能直接套等比数列求和公式。换一种思路，数列\(\langle1,A,A^2,\cdots,A^{X-1}\rangle\)可以看做线性递推，因此设计矩阵：\[\boldsymbolT=\b......
  • 题解 ABC293F【Zero or One】
    我们可以暴力检查进制数不超过\(B\)的是否符合要求；然后对于进制数大于\(B\)的，位数不超过\(\log_BN\)，可以暴力枚举每一位的值然后二分进制数检查。代码中\(B=10^3\)......
  • 题解 ABC293G【Triple Index】
    莫队板子。类似于小B的询问，在移动指针过程中，维护每个数出现次数\(cnt_i\)，同时维护\(\sum\binom{cnt_i}{3}\)即可。取序列分块块长\(B=\frac{n}{\sqrt{m}}\)，有最优......
  • [ABC293E] Geometric Progression 题解
    [ABC293E]GeometricProgression题解神中神数论题目描述给定整数\(A,X,M\)，求\[\sum_{i=0}^{X-1}A^i\bmodM\]\(1\leA,M\le10^9\)\(1\leX\le10^......
  • AtCoder Beginner Contest 272（D,E)
    AtCoderBeginnerContest272（D,E)DD这个题最主要的是需要找出有哪些移动的距离对于题目给出的\(m\),我们的移动过程可以是\((i-ii)^2+(j-jj)^2=m\)这样的话，我们可以......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99