头像

infancy

acwing


访客:6631

离线:18小时前



infancy
9天前
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    long long a,b,q;
    cin>>a>>b>>q;
    long long res=1%q;
    while(b)
    {
        if(b&1) res=res*a%q;
        a=a*a%q;
        b>>=1;
    }
    cout<<res;
    return 0;
}



infancy
9天前

迭代版

#include<iostream>
using namespace std;
#define ull unsigned long long
ull quick_pow(ull a,ull b,ull p)
{
    ull result=1%p;
    a=a%p;
    while(b)
    {
        if(b&1) result=result*a%p;
        a=a*a%p;
        b>>=1;
    }
    return result;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,p;
        cin.tie(0);
        ios::sync_with_stdio(false);
        cin>>a>>b>>p;
        cout<<quick_pow(a,b,p)<<endl;
    }
    return 0;
}

递归版

#include<iostream>
using namespace std;
#define ull unsigned long long
ull quick_pow(ull a,ull b,ull p)
{
    if(b==0) return 1;
    a%=p;
    ull res=quick_pow(a,b>>1,p);
    if(b&1) return res*res%p*a%p;
    return res*res%p;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,p;
        cin.tie(0);
        ios::sync_with_stdio(false);
        cin>>a>>b>>p;
        cout<<quick_pow(a,b,p)<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 846. 树的重心

infancy
9天前
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],idx,m=M,n;
bool st[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int i)
{
    st[i]=true;
    int siz=0,sum=0;
    for(int j=h[i];j!=-1;j=ne[j])
    {
        if(!st[e[j]]) 
        {
            int x=dfs(e[j]);
            siz=max(siz,x);
            sum+=x;
        }
    }
    siz=max(siz,n-sum-1);
    m=min(siz,m);
    return sum+1;
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    dfs(1);
    cout<<m;
    return 0;
}


活动打卡代码 AcWing 844. 走迷宫

infancy
11天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
const int N=110;
int p[N][N],d[N][N];
int bfs()
{
    memset(d,-1,sizeof d);
    int x[4]={-1,0,1,0},y[4]={0,1,0,-1};
    queue<pair<int,int>> q;
    d[1][1]=0;
    q.push({1,1});
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=1;i<=4;i++)
        {
            int dx=t.first+x[i-1],dy=t.second+y[i-1];
            if(dx>=1 && dx<=n && dy>=1 && dy<=m && d[dx][dy]==-1 && p[dx][dy]==0)
            { 
                d[dx][dy]=d[t.first][t.second]+1;
                q.push({dx,dy});
            }
        }
    }
    return d[n][m];
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>p[i][j];
    cout<<bfs();
    return 0;
}



infancy
11天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
const int N=110;
int p[N][N],d[N][N];
int bfs()
{
    memset(d,-1,sizeof d);
    int x[4]={-1,0,1,0},y[4]={0,1,0,-1};
    queue<pair<int,int>> q;
    d[1][1]=0;
    q.push({1,1});
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=1;i<=4;i++)
        {
            int dx=t.first+x[i-1],dy=t.second+y[i-1];
            if(dx>=1 && dx<=n && dy>=1 && dy<=m && d[dx][dy]==-1 && p[dx][dy]==0)
            { 
                d[dx][dy]=d[t.first][t.second]+1;
                q.push({dx,dy});
            }
        }
    }
    return d[n][m];
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>p[i][j];
    cout<<bfs();
    return 0;
}


活动打卡代码 AcWing 843. n-皇后问题

infancy
11天前
#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
        return;
    }

    for (int i = 0; i < n; i ++ )
        if (!col[i] && !dg[u + i] && !udg[n - u + i])
        {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            g[i][j] = '.';

    dfs(0);

    return 0;
}




活动打卡代码 AcWing 842. 排列数字

infancy
12天前
#include<iostream>
using namespace std;
const int N=10;
int f[N],nn;
bool flag[N];
void dfs(int n)
{
    if(n==nn){
        for(int i=0;i<nn;i++) cout<<f[i]<<' ';
        cout<<endl;
        return ;
    }
    else
    {
        for(int i=1;i<=nn;i++)
        {
            if(!flag[i]) 
            {
                f[n]=i,flag[i]=true;
            dfs(n+1);
            flag[i]=false;
            }
        }
    }
}
int main()
{
    cin>>nn;
    dfs(0);
    return 0;
}


活动打卡代码 AcWing 841. 字符串哈希

infancy
13天前
#include<iostream>
using namespace std;
const int N=1e5+10;
char word[N],P=131;//p=13331
unsigned long long h[N],p[N];//h[N]哈希函数 p[N]=P的n次方
unsigned long long query(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    int n,m;
    cin>>n>>m;
    cin>>word+1;
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        h[i]=h[i-1]*P+word[i];
        p[i]=p[i-1]*P;
    }
    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(query(l1,r1)==query(l2,r2)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}



infancy
13天前
#include<iostream>
using namespace std;
const int N=1e5+10;
char word[N],P=131;//p=13331
unsigned long long h[N],p[N];//h[N]哈希函数 p[N]=P的n次方
unsigned long long query(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    int n,m;
    cin>>n>>m;
    cin>>word+1;
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        h[i]=h[i-1]*P+word[i];
        p[i]=p[i-1]*P;
    }
    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(query(l1,r1)==query(l2,r2)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}



infancy
13天前

1.拉链法

#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+3;
int h[N],v[N],ne[N],idx;
void insert(int x)
{
    int k=(x%N+N)%N;
    v[idx]=x;
    ne[idx]=h[k];
    h[k]=idx++;
}
bool find(int x)
{
    int k=(x%N+N)%N;
    int i=h[k];
    while(i!=-1 && v[i]!=x) i=ne[i];
    if(v[i]==x) return true;
    return false;
}
int main()
{
   int n;
   memset(h,-1,sizeof h);
   cin>>n;
   while(n--)
   {
       char op;
       int x;
       cin>>op;
       cin>>x;
       if(op=='I') insert(x);
       else
       {
           if(find(x)) cout<<"Yes"<<endl;
           else cout<<"No"<<endl;
       }
   }
   return 0;
}

2.开放寻址法

#include<iostream>
#include<cstring>
using namespace std;
const int N=2e5+3;
int h[N],flag=0x3f3f3f3f;
int find(int x)
{
    int k=(x%N+N)%N;
    while(h[k]!=flag && h[k]!=x)
    {
        k++;
        if(k==N) k=1;
    }
    return k;
}
int main()
{
   int n;
   memset(h,0x3f,sizeof h);
   cin>>n;
   while(n--)
   {
       char op;
       int x;
       cin>>op;
       cin>>x;
       if(op=='I') h[find(x)]=x;
       else
       {
           if(h[find(x)]==x) cout<<"Yes"<<endl;
           else cout<<"No"<<endl;
       }
   }
   return 0;
}