周末训练

A（lightOJ 1022）

题目大意

给你一个正方形和一个正方形内接圆，告诉你圆的半径，求出指定阴影范围的面积大小。

解题思路

由于已知圆的半径，直接算出圆和正方形的面积，然后相减，就可得出答案。

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const double pi=2*acos(0.0);
int T,casee;
double r;
int main()
{
    casee=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lf",&r);
        double s=r*r*2*2;
        double m=pi*r*r;
        double ans=s-m;
        printf("Case %d: %.2lf\n",++casee,ans);
    }
    return 0;
}

B(lightOJ 1023)

题目大意

给你两个数N和K，让你输出N个字母的K次全排列。

解题思路

直接使用STL函数输出全排列字符串就行了。

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int T,n,k;
char a[30];
int main()
{
    int casee=0;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        if(n<5)
        {
            int p=1;
            for(int i=1; i<=n; i++)
                p*=i;
            k=min(k,p);
        }
        for(int i=0; i<n; i++)
        {
            a[i]=i+'A';
        }
        printf("Case %d:\n",++casee);
        do
        {
            for(int i=0; i<n; i++)
                printf("%c",a[i]);
            printf("\n");
            k--;
        }
        while(next_permutation(a,a+n)&&k);
    }
    return 0;
}

C (lightOJ 1024)
题目大意

给你一个n，然后求这n个数的最小公倍数，每个数的大小为1~1e4。

解题思路

因为数字太多，每个数字也不小，所以如果直接求最小公倍数的话会炸long long，因此需要一种高精度的计算方式。通过观察可以知道，这些数的最小公倍数是他们的质因数以最大出现次数为幂的乘积。
例如样例2：
    4
    5 6 30 60
    5 : 5 
    6 : 2*3
    30 : 2*3*5
    60 : 2^2*3*5
所以最小公倍数为2^2*3*5（因为2出现次数最多为两次，其他两个为一次）

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e6+5;
int n,T,num,k=0;
int cnt[maxn],ans[maxn];
int f(int x)
{
    int mark=0;
    for(int i=2; i<=sqrt(x); i++)
    {
        mark=0;
        while(x%i==0)
        {
            mark++;
            x/=i;
        }
        cnt[i]=max(cnt[i],mark);
    }
    if(x>1)
        cnt[x]=max(cnt[x],1);
}
void Mul(int a[], int t)
{
    for(int i=0; i<1000; i++)
        a[i] = a[i]*t;
    for(int i=0; i<1000; i++)
    {
        a[i+1] += a[i]/10000;
        a[i] = a[i]%10000;
    }
}
void put(int a[])
{
    int i=1000;
    while(i>=0 && a[i]==0)
        i--;
    printf("%d", a[i--]);
    while(i>=0)
        printf("%04d", a[i--]);
    printf("\n");
}
int main()
{
    int casee=0;
    scanf("%d", &T);
    while(T--)
    {
        memset(cnt, 0, sizeof(cnt));
        memset(ans, 0, sizeof(ans));
        scanf("%d", &n);
        for(int i=0; i<n; i++)
        {
            scanf("%d", &num);
            f(num);
        }
        ans[0] = 1;
        for(int i=0; i<=10000; i++)
        {
            if(!cnt[i])
                continue;
            int t = 1;
            for(int j=0; j<cnt[i]; j++)
                t *= i;
            Mul(ans, t);
        }
        printf("Case %d: ", ++casee);
        put(ans);
    }
    return 0;
}