Codeforces Round #465 (Div. 2)

Codeforces

Contests 链接：Codeforces Round #465 (Div. 2)
过题数：3
排名：1072/10985

A. Fafa and his Company

题意

有 $n$ 个人，从 $n$ 个人中选出一些人作为领导，管理其他所有人，要求每个领导管理的人数相等，问有多少种选领导的方式。

输入

输入包含一个整数 $n~(2\leq n\leq10^5)$。

输出

输出方案数。

样例

题解

相当于将 $n$ 个人平均分组，每组至少两人，问有多少种分法，暴力枚举。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
#define LL long long
int n;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        int ans = 0;
        for(int i = 2; i <= n; ++i) {
            if(n % i == 0) {
                ++ans;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Fafa and the Gates

题意

在一个平面直角坐标系内，初始 $Fafa$ 的坐标为 $(0,0)$，接着他会按照一个长度为 $n$ 的字符串的指令来走，假设当前 $Fafa$ 的位置为 $(x,y)$，字符串的第 $i$ 个字符为 'U' 时，$Fafa$ 将移动到 $(x,y+1)$，为 'R' 时移动到 $(x+1,y)$，问在移动的过程中穿过直线 $y=x$ 的次数。

输入

第一行为一个整数 $n~(1\leq n\leq10^5)$，第二行为一个长度为 $n$ 的字符串 $s$，字符串内的每个字符 $ch\in\{'U','R'\}$。

输出

输出穿过 $y=x$ 的次数。

样例

输入	输出	提示
1 U	0
6 RURUUR	1
7 URRRUUU	2	移动路线如下图：

题解

按题意模拟，每当 $x=y$ 时判断当前行走方向是否和下一步方向相同，如果相同则穿过这条直线一次。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n;
char str[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d%s", &n, str) != EOF) {
        int ans = 0;
        int x = 0, y = 0;
        for(int i = 0; i < n; ++i) {
            if(str[i] == 'U') {
                ++y;
            } else {
                ++x;
            }
            if(x == y) {
                if(str[i] == str[i + 1]) {
                    ++ans;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Fifa and Fafa

题意

在平面直角坐标系内，有一个圆心为 $(x_1,y_1)$，半径为 $R$ 的圆，还有一个点 $(x_2,y_2)$，要求在圆内找到一个圆，使得这个圆不包含点 $(x_2,y_2)$ 且面积最大。

输入

输入包含五个整数 $R,x_1,y_1,x_2,y_2~(1\leq R\leq10^5,|x_1|,|y_1|,|x_2|,|y_2|\leq10^5)$。

输出

输出满足题意的圆的圆心坐标和半径，误差在 $10^{-6}$ 内即认为答案正确，如果有多解输出任意一个。

样例

题解

如果点在圆外，就可以直接输出圆的圆心和半径，否则：
经过点 $(x_1,y_1),(x_2,y_2)$ 的直线倾斜角为 $\theta=\arctan(\frac{y_1-y_2}{x_1-x_2})$（注意 $x_1=x_2$ 的倾斜角特判为 $\frac{\pi}{2}$），则该直线与圆的交点为 $({x_3}_{12},{y_3}_{12})=(x_1\pm R\cos\theta,y_1\pm R\sin\theta)$，取使 $|({x_3}_1-x_2,{y_3}_1-y_2)|$ 与 $|({x_3}_2-x_2,{y_3}_2-y_2)|$ 大的那个点 $(x_4,y_4)$，则最终圆的圆心为 $(\frac{x_4+x_2}{2},\frac{y_4+y_2}{2})$，然后就可以算出半径。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;
#define LL long long
const double PI = acos(-1.0);
double theta;
LL R, xx1, xx2, yy1, yy2;
double lx, rx, ly, ry, ansx, ansy, ansr;
double dis(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%I64d%I64d%I64d%I64d%I64d", &R, &xx1, &yy1, &xx2, &yy2) != EOF) {
        if(dis(xx1, yy1, xx2, yy2) >= R) {
            printf("%I64d %I64d %I64d\n", xx1, yy1, R);
            continue;
        }
        if(xx1 == xx2) {
            theta = PI / 2;
        } else {
            theta = atan((double)(yy1 - yy2) / (xx1 - xx2));
        }
        lx = R * cos(theta) + xx1;
        ly = R * sin(theta) + yy1;
        rx = -R * cos(theta) + xx1;
        ry = -R * sin(theta) + yy1;
        if(dis(lx, ly, xx2, yy2) < dis(rx, ry, xx2, yy2)) {
            ansx = (xx2 + rx) / 2;
            ansy = (yy2 + ry) / 2;
            ansr = dis(rx, ry, xx2, yy2) / 2;
        } else {
            ansx = (xx2 + lx) / 2;
            ansy = (yy2 + ly) / 2;
            ansr = dis(lx, ly, xx2, yy2) / 2;
        }
        printf("%.10f %.10f %.10f\n", ansx, ansy, ansr);
    }
    return 0;
}