头像

纳兰晚宁




在线 


活动打卡代码 AcWing 1371. 货币系统

纳兰晚宁
1小时前
#include<iostream>
#include<cstring>
#include<algorithm>

using   namespace std;

typedef long long LL;

const int N =30,M=10010;
int n,m;
LL f[M];

int main()
{
    cin>>n>>m;
    f[0]=1;
    for(int i=1;i<=n;i++)
    {
        int v;
        cin>>v;
        for(int j=v;j<=m;j++)
         f[j]=f[j]+f[j-v];
    }
    cout<<f[m]<<endl;
    return 0;
}


活动打卡代码 AcWing 1381. 阶乘

纳兰晚宁
1小时前
#include <iostream>

using namespace std;

signed main()
{
    int n, b = 1;
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        b *= i;// 递推求阶乘
        while (!(b % 10)) // 删掉后面的 0
            b /= 10;
        b %= 1000000;// 取余
    }
    cout << b % 10;
}


活动打卡代码 AcWing 1432. 棋盘挑战

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N =15;
int n;
bool col[N],dg[N*2],udg[N*2];
int path[N],ans;

void dfs(int x)
{
    if(x>n)
    {
        ans++;
        if(ans<=3)
        {
            for(int i=1;i<=n;i++)
              cout<<path[i]<<' ';
            cout<<endl;
        }
        return ;
    }

    for(int y=1;y<=n;y++)
       if(!col[y]&&!dg[x+y]&&!udg[x-y+n])
       {
           path[x]=y;
           col[y]=dg[x+y]=udg[x-y+n]=true;
           dfs(x+1);
           col[y]=dg[x+y]=udg[x-y+n]=false;
           path[x]=0;
       }
}
int main()
{
    cin>>n;
    dfs(1);
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 754. 平方矩阵 II

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N =110;
int n;
int a[N][N];

int main()
{
    while(cin>>n,n)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=i,k=1;j<=n;j++,k++)
            {
                a[i][j]=k;
                a[j][i]=k;
            }
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
               cout<<a[i][j]<<' ';
            cout<<endl;
        }

    cout<<endl;
    }
    return 0;
}



活动打卡代码 AcWing 1341. 十三号星期五

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int month[13]={0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int weekday[7];

int main()
{
    int n;
    cin>>n;

    int days=0;
    for(int year=1900;year<1900+n;year++)
    {
        for(int i=1;i<=12;i++)
        {
            weekday[(days+12)%7]++;
            days+=month[i];
            if(i==2)
            {
                if(year%100&&year%4==0||year%400==0)
                   days++;
            }
        }
    }
    for(int i=5,j=0;j<7;i=(i+1)%7,j++)
       cout<<weekday[i]<<' ';
    cout<<endl;
    return 0;
}


活动打卡代码 AcWing 785. 快速排序

#include<iostream>
#include<algorithm>

using namespace std;

const int N =100010;
int n;
int a[N];

void quick(int a[],int l,int r)
{
    if(l>=r)  return;

    int i=l-1,j=r+1,x=a[(l+r)/2];
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    quick(a,l,j);
    quick(a,j+1,r);
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
       scanf("%d",&a[i]);

       quick(a,0,n-1);

    for(int i=0;i<n;i++) cout<<a[i]<<' ';

    return 0;
}


活动打卡代码 AcWing 1532. 找硬币

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N =100010;
int n,m;
int w[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)  scanf("%d",&w[i]);
    sort(w,w+n);
    for(int i=0,j=n-1;i<j;i++)
    {
        while(i<j&&w[i]+w[j]>m)  j--;
        if(i<j&&w[i]+w[j]==m)
        {
            printf("%d %d\n",w[i],w[j]);
            return 0;
        }
    }
    puts("No Solution");
    return 0;
}


活动打卡代码 AcWing 1208. 翻硬币

#include<cstring>
#include<iostream>

using namespace std;
string a,b;
int cnt;

void turn(int u)
{
    if(a[u]=='*')  a[u]='o';
    else a[u]='*';
}
int main()
{
    cin>>a>>b;
    for(int i=0;i<a.size()-1;i++)
      if(a[i]!=b[i])
      {
          turn(i);
          turn(i+1);
          cnt++;
      }
      cout<<cnt;
      return 0;
}


活动打卡代码 AcWing 342. 道路与航线

#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N =25010,M=150010,INF=0x3f3f3f3f;
int n,mr,mp,S;
int id[N];
int h[N],e[M],ne[M],w[M],idx;
int dist[N],din[N];
vector<int> block[N];
int bcnt;
bool st[N];
queue<int> q;

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int bid)
{
    id[u]=bid,block[bid].push_back(u);

    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!id[j])
          dfs(j,bid);
    }
}

void dijkstra(int bid)
{
    priority_queue<PII,vector<PII>,greater<PII>> heap;

    for(auto u:block[bid])
      heap.push({dist[u],u});

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();

        int ver=t.y,distance=t.x;
        if(st[ver])  continue;
        st[ver]=true;

        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(id[j]!=id[ver]&&--din[id[j]]==0) q.push(id[j]);
            if(dist[j]>dist[ver]+w[i])
            {
                dist[j]=dist[ver]+w[i];
                if(id[j]==id[ver])  heap.push({dist[j],j});
            }
        }
    }
}

void topsort()
{
    memset(dist,0x3f,sizeof dist);
    dist[S]=0;
    for(int i=1;i<=bcnt;i++)  
       if(!din[i])  q.push(i);

    while(q.size())
    {
        int t=q.front();
        q.pop();
        dijkstra(t);
    }
}
int main()
{
    cin>>n>>mr>>mp>>S;
    memset(h,-1,sizeof h);

    while(mr--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    for(int i=1;i<=n;i++)
       if(!id[i])
       {
           bcnt++;
           dfs(i,bcnt);
       }
    while(mp--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        din[id[b]]++;
        add(a,b,c);
    }
    topsort();

    for(int i=1;i<=n;i++)
      if(dist[i]>INF/2)  cout<<"NO PATH"<<endl;
      else cout<<dist[i]<<endl;

    return 0;
}


活动打卡代码 AcWing 1135. 新年好

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>

using namespace std;

typedef pair<int,int> PII;

const int N =50010,M=200010,INF=0x3f3f3f3f;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int q[N],dist[6][N];
int source[6];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dijkstra(int start,int dist[])
{
    memset(dist,0x3f,N*4);
    dist[start]=0;
    memset(st,0,sizeof st);

    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,start});

    while(heap.size())
    {
        auto t=heap.top();
        heap.pop();

        int ver=t.second;
        if(st[ver])  continue;
        st[ver]=true;

        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[ver]+w[i])
            {
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
}

int dfs(int u,int start,int distance)
{
    if(u>5)  return distance;

    int res=INF;
    for(int i=1;i<=5;i++)
       if(!st[i])
       {
           int next=source[i];
           st[i]=true;
           res=min(res,dfs(u+1,i,distance+dist[start][next]));
           st[i]=false;
       }
       return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    source[0]=1;
    for(int i=1;i<=5;i++)  scanf("%d",&source[i]);

    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }
    for(int i=0;i<6;i++) dijkstra(source[i],dist[i]);

    memset(st,0,sizeof st);
    printf("%d\n",dfs(1,0,0));

    return 0;
}