Beatcoder#39+#41+#42

HDU5211

思路：

倒着更新每个数的约数，更新完要把自己加上，以及1的情况？

//#include <bits/stdc++.h>

#include<iostream>

#include<map>

#include<cstdio>

#include<queue>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

//找最近倍数

const int N=1e4+10;

map<int,int>mp;

void solve(int n,int id)

{

    int q=sqrt(n);

    if(n==1)

        return;

    mp[1]=id;

    for(int i=2;i<=q;++i)

        if(n%i==0)

        {

            mp[i]=id;

            mp[n/i]=id;

        }

}

int x[N];

int main()

{

    int n;

    while(~scanf("%d",&n))

    {

        int ans=0;

        mp.clear();

        for(int i=1;i<=n;i++)

            scanf("%d",&x[i]);

        for(int i=n;i>=1;i--)

        {

            solve(x[i],i);

            ans+=mp[x[i]];

            mp[x[i]]=i;

        }

        printf("%d\n",ans);

    }

    return 0;

}

HDU5228

注意本身牌可随意变换顺序= =、

//#include <bits/stdc++.h>

#include<iostream>

#include<map>

#include<cstdio>

#include<queue>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

char str[5];

int a[5][13];

int b[5][13];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        memset(a,0,sizeof(a));

        for(int i=0; i<5; i++)

        {

            scanf("%s",str);

            int len=strlen(str);

            if(len==3)

                a[str[0]-'A'][(str[2]-'0')+(str[1]-'0')*10]=1;

            else

                a[str[0]-'A'][(str[1]-'0')]=1;

        }

        int ans=4;

        for(int i=0; i<4; i++)

            for(int j=1; j<=10; j++)

            {

                int num=0,k=j;

                if(j==10)

                {

                    b[num][0]=i;b[num++][1]=k;k++;

                    b[num][0]=i;b[num++][1]=k;k++;

                    b[num][0]=i;b[num++][1]=k;k++;

                    b[num][0]=i;b[num++][1]=k;k++;

                    b[num][0]=i;b[num++][1]=1;

                }

                else

                {

                    b[num][0]=i;b[num++][1]=k;k++;

                    b[num][0]=i;b[num++][1]=k;k++;

                    b[num][0]=i;b[num++][1]=k;k++;

                    b[num][0]=i;b[num++][1]=k;k++;

                    b[num][0]=i;b[num++][1]=k;

                }

                int sum=0;

                for(k=0; k<5; k++)

                    if(a[b[k][0]][b[k][1]]==1)

                        sum++;

                ans=min(ans,5-sum);

            }

        printf("%d\n",ans);

    }

    return 0;

}

HDU5229

先手赢的话有两种：字符串相同或者字符串两个相加为奇数。

因为字符串相同的话，一定是偶数，所以只要找偶数的相同就好了，也就是说只要找相同就好了

先手赢的贡献=奇数长字符串个数*偶数长字符串个数 + 相同组合数

这里我用的是Trie树处理。

//#include <bits/stdc++.h>

#include<iostream>

#include<cstdio>

#include<queue>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int N=20000+10;

struct Trie{

    int num;

    Trie *next[26];

};

Trie q[N*10],*root;

int tol,ans,n;

char s[200010];

Trie* Creat()

{

    Trie *p=&q[tol++];

    for(int i=0;i<26;i++)

        p->next[i]=NULL;

    p->num=0;

    return p;

}

int INS()

{

    int len=strlen(s);

    Trie* p=root;

    for(int i=0;i<len;i++)

    {

        int index=s[i]-'a';

        if(p->next[index]==NULL)

            p->next[index]=Creat();

        p=p->next[index];

    }

    p->num++;

    return p->num;

}

int gcd(int x, int y)

{

    if (x%y) return gcd(y, x%y);

    return y;

}  

int main()

{

    int T;

    scanf("%d",&T);

    while(T--){

        int len,even=0,odd=0;

        scanf("%d",&n);

        tol=ans=0;

        root=Creat();

        for(int i=0;i<n;i++)

        {

            scanf("%s",s);

            int temp=INS();

            if(temp>2)

            {

            	ans-=(temp-1)*(temp-2)/2;

            	ans+=(temp-1)*temp/2;

			}

			else if(temp==2)

				ans+=temp*(temp-1)/2;

            len=strlen(s);

            if(len%2)

                odd++;

            else

                even++;

        }

        ans+=odd*even;

        int pp=ans;

        int qq=n*(n-1)/2;

        int g=gcd(qq,pp);

        if(pp==0)

			puts("0/1");

		else

        	printf("%d/%d\n",pp/g,qq/g);

    }

    return 0;

}

HDU5232

水题；

//#include <bits/stdc++.h>

#include<iostream>

#include<map>

#include<cstdio>

#include<queue>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int N=1e6+10;

int a[105][105],ans;

int main()

{

    int n;

	while (scanf("%d",&n)!=EOF)

    {

        ans=n*2;

        for (int i=1;i<=n;i++)

            for (int j=1;j<=n;j++)

                scanf("%d",&a[i][j]);

        for (int i=1;i<n;i++)

            for (int j=i+1;j<=n;j++)

                if (a[i][j]) ans+=2;

        printf("%d\n",ans);

  }

}

HDU5233

思路：

这道题可以二分，也能用map嵌套一个queue（很有可能mle），这里给出一个好的思想：预留；

对鸟每个位置的高度加一个预留位置，从最后往前枚举预处理一下，然后每次取完更新位置。

//#include <bits/stdc++.h>

#include<iostream>

#include<map>

#include<cstdio>

#include<queue>

#include<string.h>

#include<algorithm>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int N=1e6+10;

struct asd{

    int id;

    int next;

};

asd q[N];

map<int,int>mp;

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

int main()

{

    while(~scanf("%d%d",&n,&m)){

        mp.clear();

        num=0;

        for(int i=1;i<=n;i++)

            scanf("%d",&a[i]);

        for(int i=n;i>=1;i--)

        {

            q[++num].id=i;

            q[num].next=mp[a[i]];

            mp[a[i]]=num;

        }

        for(int i=1;i<=m;i++){

            int x,temp;

            scanf("%d",&x);

            temp=mp[x];

            if(!temp)

                puts("-1");

            else

                printf("%d\n",q[temp].id);

            mp[x]=q[temp].next;

        }

    }

    return 0;

}

巴特西