“玲珑杯”ACM比赛 Round #23

A -- 生是脂肪的人

Time Limit：2s Memory Limit：128MByte

Submissions：263Solved：97

DESCRIPTION

给定一个整数n，输出[(10^n)/7]的个位数。
其中 abs(n) ≤ 1e18

INPUT

第一行是一个正整数T (1 ≤ T ≤ 100)，表示数据组数。
接下来每一行一个整数n。

OUTPUT

T行，每行一个整数。

SAMPLE INPUT

SAMPLE OUTPUT

A和/7的小数一样啊，也是142857循环的，直接做，但是本来说是正数，然后有负数很不厚道啊，数据范围锅了一次

#include<bits/stdc++.h>

using namespace std;

string s="";

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        long long n;

        cin>>n;

        n--;

        if(n<)

            printf("0\n");

        else

        printf("%c\n",s[n%]);

    }

B -- 死是脂肪的鬼

Time Limit：2s Memory Limit：128MByte

Submissions：127Solved：86

DESCRIPTION

给定一个99的数独，判断该数独是否合法。
如果合法输出Yes,否则输出No。
数独当且仅当每行每列以及9个33的小方格都是1〜9的9个数才合法。

INPUT

第一行是一个正整数T (1 ≤ T ≤ 100)表示数据组数，每组数据中：一共9行，每行9个正整数。
两组数据之间没有空行。
保证输入的数独中的数都在1~9中。

OUTPUT

一共T行，每行Yes或者No。

SAMPLE INPUT

4 8 3 9 2 1 6 5 7

9 6 7 3 4 5 8 2 1

2 5 1 8 7 6 4 9 3

5 4 8 1 3 2 9 7 6

7 2 9 5 6 4 1 3 8

1 3 6 7 9 8 2 4 5

3 7 2 6 8 9 5 1 4

8 1 4 2 5 3 7 6 9

6 9 5 4 1 7 3 8 2

SAMPLE OUTPUT

Yes

B直接暴力判断

#include<bits/stdc++.h>

using namespace std;

int a[][];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int f=;

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

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

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

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

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

            {

                int b[]= {};

                for(int k=i-; k<=i; k++)

                    for(int l=j-; l<=j; l++)

                        if(a[k][l]>&&a[k][l]<)b[a[k][l]]++;

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

                    if(!b[i])f=;

            }

        printf("%s\n",f?"Yes":"No");

    }

}

C -- 你居然不吃巧克力

Time Limit：2s Memory Limit：128MByte

Submissions：131Solved：66

DESCRIPTION

给定一个正整数n，现在有n个石头，每个单独成一堆。
现在可以每次合并两堆石头，产生的能量为两堆石头个数的min。
你现在要将所有的石头合并成一堆，并且获得的能量最大。
输出这个最大值。
1 ≤ n ≤ 1e7。

INPUT

第一行是一个正整数T (1 ≤ T ≤ 10)表示数据组数，接下来T行每行一个正整数。
数据满足一个测试点中，最多只有1个n超过1e6。

OUTPUT

T行，每行一个正整数。

SAMPLE INPUT

SAMPLE OUTPUT

C太暴力了我，用的是合并

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        map<int,int>M;

        int n,a,b,c,d;

        scanf("%d",&n);

        M[]=n;

        long long ans=;

        for(;;)

        {

            a=M.begin()->first,b=M.begin()->second;

            if(b>)

            {

               ans+=b/*a;

               M[a+a]=b/;

               if(b&)M[a]=;

               else M.erase(M.begin());

            }

            else  if(b==)

            {

                if(M.size()==)break;

                else

                {

                    c=(++M.begin())->first,d=(++M.begin())->second;

                    ans+=a;

                    M[a+c]=;

                    M.erase(M.begin());

                    M[c]=d-;

                }

            }

            else M.erase(M.begin());

            if(!M.size())break;

        }

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

    }

}

蓝金爷的直接分堆

#include<bits/stdc++.h>

using namespace std;

long long ans;

void dfs(int x)

{

    if(x==)return;

    ans+=x/,dfs(x/);

    if(x&)dfs(x/+);

    else dfs(x/);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n;

        cin>>n;

        ans=;

        dfs(n);

        cout<<ans<<"\n";

    }

}

TLE的直接优先队列（1e7我电脑要2s，优化下可以1s跑完，但是OJ没那么快啊

#include<bits/stdc++.h>

using namespace std;

priority_queue<int, vector<int>, greater<int> > Q;

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        while(!Q.empty())Q.pop();

        int n;

        scanf("%d",&n);

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

            Q.push();

        long long ans=;

        while(Q.size()>=)

        {

            int a=Q.top();Q.pop();

            int b=Q.top();Q.pop();

            ans+=a;

            Q.push(a+b);

        }

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

    }

}

D -- 别不好意思，都是脂肪的人

Time Limit：2s Memory Limit：128MByte

Submissions：25Solved：20

DESCRIPTION

给定两个正整数 nn 和 kk，请求出

∑x1=0 ∑x2=0...∑xn=0 x1+x2+...+xnkx1+x2+...+xn∑x1=0 ∑x2=0...∑xn=0 x1+x2+...+xnkx1+x2+...+xn

（如果公式看不懂，请看图）

数据保证答案是一个有理数，我们假设它为 pqpq , 你只需输出它对 1e9+71e9+7 的模即可。（即 p∗q−1p∗q−1 对 1e9+71e9+7 的模数)。

INPUT

第一行一个正整数 TT 表示数据组数。
对于每组数据：
一行两个正整数，表示 nn 和 kk 。

OUTPUT

一共 TT 行，每行一个正整数，表示答案。

SAMPLE INPUT

SAMPLE OUTPUT

457031313

HINT

数据范围：
数据满足 1<=T<=1000,1<=n<=1e9,2<=k<=1e91<=T<=1000,1<=n<=1e9,2<=k<=1e9 。

妈耶，看看他们的结论还差点啊

n=1的时候

k=1

k=2 2

k=3 3/4

k=4 4/9

k=5 5/16

k=6 6/25

k=7 7/36

这个我是直接用数据暴力的啊，很明显的，拿高数硬算也是可以的

规律很明显 k / (k-1)^2

最后是ans=n*k^n/(k-1)^(n+1)，这个我没有搞出来

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MD=1e9+;

LL po(LL a, LL n)

{

    LL ans = ;

    while(n)

    {

        if(n&) ans=(ans*a)%MD;

        a=(a*a)%MD;

        n>>=;

    }

    return(ans+MD)%MD;

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        LL n,k,a,b;

        scanf("%lld%lld",&n,&k);

        a=po(k,n)*n%MD;

        b=po(k-,n+)%MD;

        LL bn=po(b,MD-);

        printf("%lld\n",(a*bn)%MD);

    }

    return ;

}

巴特西

“玲珑杯”ACM比赛 Round #23

∑x1=0 ∑x2=0...∑xn=0 x1+x2+...+xnkx1+x2+...+xn∑x1=0 ∑x2=0...∑xn=0 x1+x2+...+xnkx1+x2+...+xn

最新文章

热门文章