头像

Amazing168




离线:5小时前



Amazing168
6小时前
# include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        int c,cnt=0;
        scanf("%d",&c);
        for(int i=c;i>0;i-=i&-i) cnt++;
        printf("%d ",cnt);
    }
    return 0;
}


活动打卡代码 AcWing 2816. 判断子序列

Amazing168
6小时前
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;

int n,m;
int a[N],b[N];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++) scanf("%d",&b[i]);
    int i=0,j=0;
    while(i<n&&j<m){
        if(a[i]==b[j]) i++;
        j++;
    }
    if(i==n) printf("Yes\n");
    else printf("No\n");
    return 0;
}



Amazing168
6小时前
# include<iostream>
using namespace std;

const int N=1e5+10;

int n,m,x;

int a[N],b[N];

int main(){
    scanf("%d%d%d",&n,&m,&x);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++) scanf("%d",&b[i]);
    for(int i=0,j=m-1;i<n;i++){
        while(j>=0&&a[i]+b[j]>x) j--;
        if(j>=0&&a[i]+b[j]==x) cout<<i<<" "<<j<<endl;
    }
    return 0;
}



/*
 * @Author: Horizon 
 * @Date: 2020-11-28 21:36:23 
 * @Last Modified by: Horizon
 * @Last Modified time: 2020-12-01 15:53:11
 */
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N=1e5+5;
int n,m;
int primes[N], cnt;
bool st[N];   

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >>n;
    get_primes(N);
    if(n<=2)
        cout <<1<<endl;
    else 
        cout <<2<<endl;

    for(int i=2;i<=n+1;i++)
    {
        if(st[i])
            cout <<2<<" ";
        else 
            cout <<1<<" ";
    }


    return 0;
}


活动打卡代码 AcWing 1292. 哥德巴赫猜想

/*
 * @Author: Horizon 
 * @Date: 2020-11-28 17:10:01 
 * @Last Modified by: Horizon
 * @Last Modified time: 2020-11-28 17:27:32
 */
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 1000006;
int n,m;
int primes[N], cnt; 
bool st[N];         

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    get_primes(N);

    while(cin >>n)
    {
        if(n==0) return 0;
        int prime1,prime2;
        for(int i=0;i<=N;i++)
        {
            prime1=primes[i];
            prime2=n-prime1;
            if(!st[prime2])
                break;
        }
        cout <<n<<" = "<<prime1<<" + "<<prime2<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 346. 走廊泼水节

/*
 * @Author: Horizon 
 * @Date: 2020-11-27 22:40:59 
 * @Last Modified by: Horizon
 * @Last Modified time: 2020-11-27 23:13:19
 */
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N=1e8,M=6004;
int n,m;
struct Edge
{
    int a,b,w;
    bool operator < (Edge &s) const{
        return w<s.w;
    }
}edge[M];
int p[M],Size[M];

int find(int x) 
{
    if(p[x]!=x)
        p[x]=find(p[x]);
    return p[x];
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >>t;
    while(t--)
    {
        cin >>n;

        for(int i=1;i<n;i++)
        {
            int a,b,w;
            cin >>a>>b>>w;
            edge[i]={a,b,w};
        }
        for(int i=1;i<=n;i++)
            p[i]=i,Size[i]=1;
        sort(edge+1,edge+n);

        int ans=0;
        for(int i=1;i<n;i++)
        {
            int a=edge[i].a;
            int b=edge[i].b;
            int ww=edge[i].w;
            int pa=find(a),pb=find(b);
            if(pa!=pb)
            {
                ans+=(Size[pa]*Size[pb]-1)*(ww+1);
                Size[pa]+=Size[pb];
                p[pb]=pa;
            }
        }
        cout <<ans<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 1145. 北极通讯网络

#include<bits/stdc++.h>
using namespace std;

const int N=505*505;
int n,k;
pair<int,int> q[N];
int cnt;
int ans;
double ww[1000006];
int p[N];
int num=1;

struct Edge
{
    int a,b;
    double w;
    bool operator <(Edge &s)const
    {
        return w<s.w;
    }
}edge[N];

int Find(int x)
{
    if(x!=p[x])
        p[x]=Find(p[x]);
    return p[x];
}

void kruskal()
{
    for(int i=1;i<=n;i++)
        p[i]=i;
    for(int i=0;i<cnt;i++)
    {
        int aa=edge[i].a,bb=edge[i].b;
        double ws=edge[i].w;
        int pa=Find(aa),pb=Find(bb);
        if(pa!=pb)
        {
            p[pa]=pb;
            ww[num++]=ws;
        }
        if(num==n) return ;
    }
}

int main()
{
    cin >>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin >>q[i].first>>q[i].second;
    }

    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int x1=q[i].first,y1=q[i].second,x2=q[j].first,y2=q[j].second;
            double dist=pow((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1),0.5);

            //cout <<dist<<endl;

            edge[cnt].a=i;
            edge[cnt].b=j;
            edge[cnt].w=dist;
            cnt++;
        }
    }

    sort(edge,edge+cnt);

    kruskal();

    if(k==0||k==1)
        k=0;
    else
        k-=1;

    //cout <<cnt<<endl;
    //cout <<k<<" "<<num-1<<endl;
    for(int i=num-1;i>=1;i--)
    {
        if(!k) printf("%.2f",ww[i]);
        k--;
    }



    return 0;
}



活动打卡代码 AcWing 1146. 新的开始

//同样多个起点,最短路和最小生成树,都会用到超级源点
#include<bits/stdc++.h>

using namespace std;

const int N=304;
int n;
int g[N][N];
int dis[N];
bool st[N];
int res;

void prim()
{
    memset(dis,0x3f3f3f3f,sizeof(dis));
    for(int i=0;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n+1;j++)
        {
            if(!st[j]&&(t==-1||dis[j]<dis[t]))
                t=j;
        }
        //cout <<dis[t]<<endl;
        if(i) res+=dis[t];
        st[t]=true;
        for(int j=1;j<=n+1;j++)
        {
            dis[j]=min(dis[j],g[t][j]);
        }
    }
}

int main()
{
    cin >>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin >>x;
        g[n+1][i]=x;
        g[i][n+1]=x;
    }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin >>g[i][j];

    for(int i=1;i<=n+1;i++)
        g[i][i]=0x3f3f3f3f;

    /*for(int i=1;i<=n+1;i++)
    {
        for(int j=1;j<=n+1;j++)
            cout <<g[i][j]<<" ";
        cout <<endl;
    }*/

    prim();

    cout <<res<<endl;
}


活动打卡代码 AcWing 1123. 铲雪车

#include<bits/stdc++.h>

using namespace std;

int sx,sy;
double a,b,c,d;
int main()
{
    double sum=0;
    cin >>sx>>sy;
    while(cin >>a>>b>>c>>d)
    {
        double dis=pow((c-a)*(c-a)+(d-b)*(d-b),0.5);
        //cout <<dis<<endl;
        sum+=dis;
    }
    sum=sum*2;
    double time=sum*60/20000;
    //cout <<time<<endl;
    int time_2=time+0.5;
    //cout <<time_2<<endl;

    int hour=time_2/60;
    int mi=time_2-hour*60;

    printf("%d:%.2d",hour,mi);;
    puts("");
}


活动打卡代码 AcWing 1117. 单词接龙

/*
 * @Author: Horizon 
 * @Date: 2020-11-24 20:51:28 
 * @Last Modified by: Horizon
 * @Last Modified time: 2020-11-24 22:32:23
 */
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n,m;
string dr[22];
char s;
int cnt[22];
int ans=-1;

void dfs(string s,int len)
{
    //cout <<s<<" "<<len<<endl;

    ans=max(ans,len);
    //cout <<ans<<endl;

    for(int i=0;i<n;i++)
    {
        int j=min(s.size(),dr[i].size())-1;
        for(;j>=1;j--)
        {
            int l1=s.size();
            if(((s.substr(l1-j,j))==(dr[i].substr(0,j)))&&cnt[i]<2)
            {
                //cout <<i<<"->"<<cnt[i]<<endl;
                //cout <<s.substr(l1-j,j)<<" "<<dr[i].substr(0,j)<<endl;

                int l2=dr[i].size();
                string ss=s+dr[i].substr(j);
                len+=(l2-j);
                cnt[i]++;
                dfs(ss,len);
                len-=(l2-j);
                cnt[i]--;
            }
        }
    }

    return ;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >>n;
    for(int i=0;i<n;i++)
        cin >>dr[i];

    cin >>s;

    for(int i=0;i<n;i++)
    {
        memset(cnt,0,sizeof(cnt));
        if(dr[i][0]==s)
        {
            cnt[i]=1;
            dfs(dr[i],dr[i].size());
        }
    }

    cout <<ans<<endl;

    return 0;
}