Codeforces Round #450(Div.2)

Codeforces

Contests 链接：Codeforces Round #450(Div.2)
过题数：3
排名：808/4629

A. Find Extra One

题意

给定平面直角坐标系上 $n$ 个点的坐标，数据保证没有点在 $OY$ 轴上，问，是否存在这样一个点 $P$，删掉 $P$ 之后，剩下的所有点，都在 $OY$ 轴的一侧。

数据范围

$2\leq n\leq105$

题解

扫一遍，记录 $OY$ 轴左边和右边的点的数量，如果其中一边的点的数量小于等于 $1$，就输出 $Yes$，否则就 $No$。

过题代码

#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 <functional>
#include <iomanip>
using namespace std;
#define LL long long
int n;
int x, y;
int cntl, cntr;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        cntl = cntr = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &x, &y);
            if(x > 0) {
                ++cntr;
            } else {
                ++cntl;
            }
        }
        if(cntl == 0 || cntl == 1) {
            printf("Yes\n");
        } else if(cntr == 0 || cntr == 1) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

B. Position in Fraction

题意

给定三个数字 $a,b,c$，求数字 $c$ 在有理数 $\frac{a}{b}$ 小数点后第几位，如果不存在，则输出 $-1$。

数据范围

$1\leq a\leq b\leq105\\0\leq c\leq9$

题解

模拟除法计算即可，根据抽屉原理， $\frac{a}{b}$，在取模的过程中，取模的次数超过 $b$，就一定会取到相同的数字，所以最多做 $b$ 次除法，就可以判断 $c$ 是否在 $\frac{a}{b}$ 的小数位中。

过题代码

#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 <functional>
#include <iomanip>
using namespace std;
#define LL long long
long long a, b, c;
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(cin >> a >> b >> c) {
        int ans = -1;
        a = a % b;
        for(int i = 1; i <= b; ++i) {
            LL tmp = a * 10 / b;
            if(tmp == c) {
                ans = i;
                break;
            }
            a = a * 10 % b;
        }
        cout << ans << endl;
    }
    return 0;
}

C. Remove Extra One

题意

给定一个 $n$ 个数字的排列，要删掉其中一个数字，使得这个排列中的 $Order$ 数最多，$Order$ 数需要满足以下条件：
对于排列 $a_1,a_2\cdots,a_k$，如果存在一下标 $i$ 对于任意的 $1\leq j<i$，都有 $a_j<a_i$，那么数字 $a_i$ 就是一个 $Order$ 数。

数据范围

$1\leq n\leq10^5\\p_1,p_2,\cdots p_n(1\leq p_i\leq n)$

题解

计算删掉每个数字 $a_i$ 后，对整个数列的 $Order$ 数的个数的贡献，如果 $a_i$ 是 $\max(a_1,a_2,\cdots,a_i)$，则删掉 $a_i$ 后，对整个数列的贡献 $-1$，如果 $a_i$ 是 $a_1,a_2,\cdots,a_j$ 中的最大值，而 $a_j$ 是其中的次大值，则删掉 $a_i$ 后，对整个数列的贡献 $+1$，最后跑一边，取贡献的最大值。

过题代码

#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 <functional>
#include <iomanip>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
int n, ans;
int num[maxn];
set<int> st;
set<int>::iterator it;
int Time[maxn];
int main() {
    #ifdef LOCAL
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
//    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        st.clear();
        memset(Time, 0, sizeof(Time));
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &num[i]);
        }
        st.insert(num[1]);
        --Time[num[1]];
        for(int i = 2; i <= n; ++i) {
            st.insert(num[i]);
            it = st.end();
            --it;
            if(*it == num[i]) {
                --Time[*it];
                continue;
            }
            --it;
            if(*it == num[i]) {
                ++it;
                ++Time[*it];
            }
        }
        int Max = Time[1];
        ans = 1;
        for(int i = 2; i <= n; ++i) {
            if(Time[i] > Max) {
                Max = Time[i];
                ans = i;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}