Skip to content

Latest commit

 

History

History
323 lines (293 loc) · 8.33 KB

第四届福建省大学生程序设计竞赛.md

File metadata and controls

323 lines (293 loc) · 8.33 KB

第四届福建省大学生程序设计竞赛

A.Forever 0.5

FZU 2140 题意：
给你一个数n，让你找出n个点，满足一下关系： 任意两点的距离不大于1.0
所有点到原点的距离不大于1.0
恰好有N对点的距离为1.0
由这些点构成的n边形的面积不小于0.5
由这些点构成的n边形的面积不大于0.75

思路：由于所有点到原点距离为1，那么首先想到的是圆。
假设输入的点为1或者2，构不成多边形。
当n==3时，例如图A，O，B三点（前三条符合要求），△AOB是一个等边三角形，面积为0.216506，不符合要求 当n>=4时，把另一个点设置在C点，AB=OB=OC=1， 四边形ACBO的面积为0.5，符合要求，那么剩下的点都放在C处即可，因为题目没有要求说不能在一处

#include<cstdio>  
#include<queue>  
#include<cstring>  
#include<math.h>  
#include<algorithm>  
using namespace std;  
const int maxn = 35;  
int T, n;  
  
int main() {  
    scanf("%d", &T);  
    for (int cas = 1; cas <= T; cas++) {  
        scanf("%d", &n);  
        if (n <= 3) printf("No\n");  
        else {  
            printf("Yes\n");  
            printf("%.6lf %.6lf\n", 0.0, 0.0);  
            printf("%.6lf %.6lf\n", -0.5, sqrt(3.0) / 2);  
            printf("%.6lf %.6lf\n", 0.5, sqrt(3.0) / 2);  
            for (int i = 4; i <= n; i++) {  
                printf("%.6lf %.6lf\n", 0.0, 1.0);  
            }  
        }  
    }  
    return 0;  
}

G.Easy Game

FZU - 2146
题意：判断输入字符串的个数

思路：输入字符数组，然后strlen()，求长度取余判断奇偶

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int main()
{
    string a;
    int T;
    cin >> T;

    for(int i=1; i<=T; i++)
    {
        cin >> a;
        {
            printf("Case %d: ", i);
            int len = a.size();
            if(len % 2 == 0)
            {
                cout << "Even";
            }
            else{
                cout << "Odd";
            }
            cout << endl;
        }
    }
    return 0;
}

H.A-B Game

FZU - 2147
题意：
给出一个数字A和B，要求A经过变化成为A`，A`<=B，计算出最小需要多少次变化
变化的公式是A-(A%x)，x是[1,A-1]之间的任意值

思路：需要变化的最少，那么每次减去的数字要最大，最大的时候正是x=A/2+1的时候，公式是自己推的
例如8，8/3=5，7，7/3=4，可以看出。

#include<cstdio>
#include<iostream>
#include<cstring>
typedef long long ll;
using namespace std;

int main()
{
    int T;
    ll a,b;
    ll time;
    cin >> T;
    for(int i=1; i<=T; i++){
        time = 0;
        cin >> a >> b;
        while(a > b){
            a = a/2 + 1;
            time++;
        }
        printf("Case %d: ", i);
        cout << time << endl;
    }
    return 0;
}

I.Moon Game

FZU - 2148 题意：给出n个点，判断出一共有多少个凸包

思路：凸包不好计算，转化为凹包计算，首先枚举出四个点，分别以其中的三个点为三角形计算出面积
由于不知道那个点是凹点，枚举测试，如果是凹包返回false

如上图，左边是凹包，右边是凸包，凹包性质是S△BCD=S△ACD+S△ACB+S△ABD，凸包没有这个性质，那么通过这个性质可以排除凹包，剩下的就是凸包（题目说没有三点共线）

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<string.h>
#include<stdio.h>
#include<queue>
using namespace std;

const double inf=1e-6;
struct node
{
    int x;
    int y;
} num[35];
double area(node a,node b,node c) {
    return fabs(1.0*((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)))/2.0;
}
bool is_ok(node a,node b,node c,node d) {
    if(fabs(area(a,b,c)-area(a,b,d)-area(b,c,d)-area(a,c, d))<inf)
        return false;
    return true;
}
int main()
{
    int T;
    scanf("%d",&T);
    int count=1;
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            cin>>num[i].x>>num[i].y;
        int sum=0;
        for(int i=0; i<n; i++)
            for(int j=i+1; j<n; j++)
                for(int k=j+1; k<n; k++)
                    for(int p=k+1; p<n; p++)
                        if(is_ok(num[i],num[j],num[k],num[p])&&is_ok(num[i],num[p],num[k],num[j])&&is_ok(num[i],num[j],num[p],num[k])&&is_ok(num[p],num[j],num[k],num[i]))
                            sum++;
        printf("Case %d: ",count++);
        printf("%d\n",sum);
    }
    return 0;
}

K.Fire Game

FZU - 2150
题意：#代表草地，.代表空地，要求只能选择两个位置点火（火可以在时间1内向四周蔓延），输入地图，输出最短多长时间全部烧完，如果不能输出-1

思路：
通过一个结构体存储坐标，用dis[i][j]数组存储烧到i,j位置最短时间
然后使用4个for循环分别表示两处点火，进行一次bfs，bfs是两个点同时进行搜索，每次搜索除了边界，草地条件外，还要判断先前烧到此位置，和现在烧的时间哪个更短，如果短，那么更新继续，然后push新的节点
最后选出最大的数输出(dis)

#include<iostream>  
#include<cstring>  
#include<algorithm>  
#include<string>  
#include<cstdio>  
#include<queue>  
using  namespace std;  
#define inf 0x3f3f3f  
  
struct Point   
{  
    int x;  
    int y;  
};  
  
int n, m;  
char map[15][15];  
int dis[15][15];  
queue<Point> que;  
int dirx[4] = { 1, -1, 0, 0 };  
int diry[4] = { 0, 0, -1, 1 };  
  
int bfs(int x1, int y1, int x2, int y2)  
{  
    int xx, yy;  
    Point p1, p2, cur, nex;  
    memset(dis, inf, sizeof(dis));  
    p1.x = x1; p1.y = y1;  
    p2.x = x2; p2.y = y2;  
    dis[x1][y1] = 0;  
    dis[x2][y2] = 0;  
    que.push(p1);  
    que.push(p2);  
    while (!que.empty())  
    {  
        cur = que.front();  
        que.pop();  
        for (int i=0; i<4; i++)  
        {  
            xx = cur.x + dirx[i];  
            yy = cur.y + diry[i];  
            if (xx>=0 && xx<n && yy>=0 && yy<m && map[xx][yy]=='#' && dis[xx][yy]>dis[cur.x][cur.y]+1)  
            {  
                dis[xx][yy] = dis[cur.x][cur.y] + 1;  
                nex.x = xx;  
                nex.y = yy;  
                que.push(nex);  
            }  
        }  
    }  
    int maxx = 0;  
    for (int i = 0; i < n;i++)  
        for (int j = 0 ; j < m; j++)  
            if (map[i][j] == '#') {  
                maxx = max(maxx, dis[i][j]);  
            }  
    return maxx;  
}  
  
int main()  
{  
    int casen;  
    cin >> casen;   
    for (int cas = 1; cas <= casen; cas++)  
    {  
        while (!que.empty())  
            que.pop();  
        cin >> n >> m;  
  
        for (int i = 0; i < n; i++)  
            cin >> map[i];  
      
        int temp;  
        int ans = inf;  
        for (int i = 0; i < n;i++)  
            for (int j = 0; j < m;j++)  
                if (map[i][j] == '#')  
                    for (int ii = 0; ii < n;ii++)  
                         for (int jj = 0; jj < m;jj++)  
                            if (map[ii][jj] == '#') {  
                                temp = bfs(i, j, ii, jj);  
                                ans = min(ans, temp);  
                            }  
        if (ans == inf) ans = -1;
        cout << "Case " << cas << ": " << ans << endl;  
    }  
}

L. OOXX Game

FZU - 2151 题意：输入一串字符串，O和X，Fat brother和Maze，每人轮流选择一个O变为X，直到不能变为止，输出谁赢，F先

思路：如果O的个数为偶数那么Fat brother赢，奇数Maze赢

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int main()
{
    int T;
    int n,m;
    int ans = 0;
    char s;
    cin >> T;
    for(int i=1; i<=T; i++)
    {
        ans = 0;
        cin >> n >> m;
        getchar();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                s = getchar();
                if(s == 'O')
                {
                    ans++;
                }
            }
            getchar();
        }
        printf("Case %d: ", i);
        if(ans % 2 == 0){

            cout << "Fat brother";
        }
        else cout << "Maze";
        cout << endl;
    }
    return 0;
}