9
5
2015
0

BestCoder Round #54 (div.2)

获得成就:坑死队友

Problem1-A problem of sorting

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
给出一张许多人的年龄和生日表。你需要从年轻到年老输出人们的名字。(没有人年龄相同)
输入描述
第一行包含一个正整数T(T5)T(T \leq 5),表示数据组数。
对于每组数据,第一行包含一个正整数n(1n100)n(1 \leq n \leq 100),表示人数,接下来n行,每行包含一个姓名和生日年份(1900-2015),
用一个空格隔开。姓名长度大于0且不大于100。注意姓名中只包含字母,数字和空格。
输出描述
对于每组数据,输出nnn行姓名。
输入样例
2
1
FancyCoder 1996
2
FancyCoder 1996
xyz111 1997
输出样例
FancyCoder
xyz111
FancyCoder

排序签到题。。是的。就是这题我坑死了@Pluto_Rabbit

窝2X得把名字末尾的空格全都去掉了。。然而其实数据中只要去掉一个。。

窝觉得窝要被打死了。。

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

#define gch getchar
#define mp make_pair

typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;

char C_get;
void read(int &x)
{
    for (x = 0, C_get = gch();(C_get<'0' || C_get>'9') && C_get != '-'&&C_get != '+';C_get = gch());
    if (C_get == '-'){for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 - C_get + '0';}
    else{if (C_get == '+')C_get = gch();for (;C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 + C_get - '0';}
}

void read(long long &x)
{
    for (x = 0, C_get = gch();(C_get<'0' || C_get>'9') && C_get != '-'&&C_get != '+';C_get = gch());
    if (C_get == '-'){for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 - C_get + '0';}
    else{if (C_get == '+')C_get = gch();for (;C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 + C_get - '0';}
}

void read(double &x)
{
    for (x = 0, C_get = gch();(C_get<'0' || C_get>'9') && C_get != '-'&&C_get != '+';C_get = gch());
    if (C_get == '-'){for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 - C_get + '0';
    if (C_get == '.')
        {double n = 1;for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())n /= 10, x = x - (C_get + '0')*n;}}
    else{if (C_get == '+')C_get = gch();for (;C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 + C_get - '0';
    if (C_get == '.'){double n = 1;for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())n /= 10, x = x + (C_get - '0')*n;}}
}
void read(char x) { x = gch(); }

int T,n;
pair <int, string>a[110];
int tot;

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        getline(cin, a[0].second);
        for (int i = 1;i <= n;++i)
        {
            getline(cin,a[i].second);
            a[i].first = 0;
            tot=1;
            while(a[i].second[a[i].second.length()-1]>='0' && a[i].second[a[i].second.length()-1]<='9')
            {
                a[i].first+=a[i].second[a[i].second.length()-1]*tot;
                tot*=10;
                a[i].second.erase(a[i].second.length()-1);
            }
            if (a[i].second[a[i].second.length() - 1] == ' ')a[i].second.erase(a[i].second.length() - 1);//比赛时候这里的if是while  QAQ
        }
        sort(a + 1, a + n + 1);
        for (int i = n;i >= 1;--i)cout << a[i].second <<endl;
    }
    return 0;
}

Problem2-The Factor

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
有一个数列,FancyCoder沉迷于研究这个数列的乘积相关问题,但是它们的乘积往往非常大。
幸运的是,FancyCoder只需要找到这个巨大乘积的最小的满足如下规则的因子:这个因子包含大于两个因子(包括它本身;比如,4有3个因子,
因此它是满足这个要求的一个数)。你需要找到这个数字并输出它。但是我们知道,对于某些数可能没有这样的因子;在这样的情况下,请输出-1.
输入描述
输入文件的第一行有一个正整数T (1T15)T \ (1 \le T \le 15),表示数据组数。

接下去有TTT组数据,每组数据的第一行有一个正整数n (1n100)n \ (1 \le n \le 100).

第二行有nnn个正整数a1,,an (1a1,,an2×109)a_1, \ldots, a_n \ (1 \le a_1, \ldots ,a_n \le 2\times 10^9), 表示这个数列。
输出描述
输出TTTTTT个数表示每次询问的答案。
输入样例
2
3
1 2 3
5
6 6 6 6 6
输出样例
6
4

这题分解一下质因数。。

然而窝在最后乘法的时候小小用了long long = int*int; 原来以为没问题。。然后就死了

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

#define gch getchar
#define mp make_pair

typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;

char C_get;
void read(int &x)
{
    for (x = 0, C_get = gch();(C_get<'0' || C_get>'9') && C_get != '-'&&C_get != '+';C_get = gch());
    if (C_get == '-'){for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 - C_get + '0';}
    else{if (C_get == '+')C_get = gch();for (;C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 + C_get - '0';}
}

void read(long long &x)
{
    for (x = 0, C_get = gch();(C_get<'0' || C_get>'9') && C_get != '-'&&C_get != '+';C_get = gch());
    if (C_get == '-'){for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 - C_get + '0';}
    else{if (C_get == '+')C_get = gch();for (;C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 + C_get - '0';}
}

void read(double &x)
{
    for (x = 0, C_get = gch();(C_get<'0' || C_get>'9') && C_get != '-'&&C_get != '+';C_get = gch());
    if (C_get == '-'){for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 - C_get + '0';
    if (C_get == '.')
        {double n = 1;for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())n /= 10, x = x - (C_get + '0')*n;}}
    else{if (C_get == '+')C_get = gch();for (;C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 + C_get - '0';
    if (C_get == '.'){double n = 1;for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())n /= 10, x = x + (C_get - '0')*n;}}
}
void read(char x) { x = gch(); }

int T, n, tot;
int list[10010];
bool check[100010];
int a[110];
int fen[50010], nf;

int main()
{
    memset(check, 0, sizeof(check));
    {
        tot = 0;
        int N=100000;
        for (int i = 2;i <= N;++i)
        {
            if (!check[i])list[++tot] = i;
            for (int j = 1;j <= tot;++j)
            {
                if (i*list[j] > N)break;
                check[i*list[j]] = 1;
                if (i%list[j] == 0)break;
            }
        }
    }

    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1;i <= n;++i)
        {
            scanf("%d", &a[i]);
            if (a[i] == 1){--n;--i;}
        }
        nf = 0;
        for (int i = 1;i <= n;++i)
        {
            for (int j = 1;j <= tot && a[i] >= list[j] && a[i] > 1;++j)
            {
                while (a[i] % list[j] == 0)
                {
                    fen[++nf] = list[j];
                    a[i] /= list[j];
                }
            }
            if (a[i] > 1)fen[++nf] = a[i];
        }
        if (nf < 2)
        {
            puts("-1");
            continue;
        }
        sort(fen + 1, fen + 1 + nf);
        ll ans;
        ans =(ll) fen[1] * fen[2];//比赛时这里没有"(ll)"
        printf("%I64d\n", ans);
    }
    return 0;
}

就这样。。上面两题报废了。。。QAQ

Problem3-Geometric Progression

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
判断一个数列是否为等比数列。

在数学中,等比数列,是一个数列,这个数列中的第一项之后的每一项是前一项乘上一个固定的非零实数(我们称之为公比)。
比如,数列 2, 6, 18, 54, ... 是一个公比为3的等比数列。 类似的,10,5,2.5,1.25,...是一个公比为0.5的等比数列。
等比数列的一般形式是:
a,ar,ar2,ar3,ar4,...
其中r!=0,r为公比,a是首项(a可以是任何实数)
输入描述
第一行一个整数T,表示数据组数。T20
对于每一个组,第一行一个整数n(1n100)n(1 \leq n \leq 100),接下来第二行nnn个数允许前导零的非负整数AiA_iAi,表示数列。保证AiA_i位数100 \leq 100
输出描述
对于每一个组,输出Yes或者No。
输入样例
4
1
0
3
1 1 1
3
1 4 2
5
16 8 4 2 1
输出样例
Yes
Yes
No
Yes

这题高精度模板贴了。。鸣谢@Scarlet的模板

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

const int MAXN = 1001;

struct HugeInt {
    int len, s[MAXN];
    HugeInt() {
        memset(s, 0, sizeof(s));
        len = 1;
    }
    HugeInt(int num) {
        *this = num;
    }
    HugeInt(const char *num) {
        *this = num;
    }
    HugeInt operator = (const int num) {
        char s[MAXN];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }
    HugeInt operator = (const char *num) {
        for (int i = 0; num[i] == '0'; num++);
        len = strlen(num);
        for (int i = 0; i < len; i++) s[i] = num[len - i - 1] - '0';
        return *this;
    }
    HugeInt operator + (const HugeInt &b) const {
        HugeInt c;
        c.len = 0;
        for (int i = 0, g = 0; g || i < max(len, b.len); i++) {
            int x = g;
            if (i < len) x += s[i];
            if (i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    HugeInt operator += (const HugeInt &b) {
        *this = *this + b;
        return *this;
    }
    void clean() {
        while (len > 1 && !s[len - 1]) len--;
    }
    HugeInt operator * (const HugeInt &b) {
        HugeInt c;
        c.len = len + b.len;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < b.len; j++) {
                c.s[i + j] += s[i] * b.s[j];
            }
        }
        for (int i = 0; i < c.len; i++) {
            c.s[i + 1] += c.s[i] / 10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }
    HugeInt operator *= (const HugeInt &b) {
        *this = *this * b;
        return *this;
    }
    HugeInt operator - (const HugeInt &b) {
        HugeInt c;
        c.len = 0;

        for (int i = 0, g = 0; i < len; i++) {
            int x = s[i] - g;
            if (i < b.len) x -= b.s[i];
            if (x >= 0) g = 0;
            else {
                g = 1;
                x += 10;
            }
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }
    HugeInt operator -= (const HugeInt &b) {
        *this = *this - b;
        return *this;
    }
    HugeInt operator / (const HugeInt &b) {
        HugeInt c, f = 0;
        for (int i = len - 1; i >= 0; i--) {
            f = f * 10;
            f.s[0] = s[i];
            while (f >= b) {
                f -= b;
                c.s[i]++;
            }
        }
        c.len = len;
        c.clean();
        return c;
    }
    HugeInt operator /= (const HugeInt &b) {
        *this = *this / b;
        return *this;
    }
    HugeInt operator % (const HugeInt &b) {
        HugeInt r = *this / b;
        r = *this - r * b;
        return r;
    }
    HugeInt operator %= (const HugeInt &b) {
        *this = *this % b;
        return *this;
    }
    bool operator < (const HugeInt &b) {
        if (len != b.len) return len < b.len;
        for (int i = len - 1; i >= 0; i--) {
            if (s[i] != b.s[i]) return s[i] < b.s[i];
        }
        return false;
    }
    bool operator > (const HugeInt &b) {
        if (len != b.len) return len > b.len;
        for (int i = len - 1; i >= 0; i--) {
            if (s[i] != b.s[i]) return s[i] > b.s[i];
        }
        return false;
    }
    bool operator == (const HugeInt &b) {
        return !(*this > b) && !(*this < b);
    }
    bool operator != (const HugeInt &b) {
        return !(*this == b);
    }
    bool operator <= (const HugeInt &b) {
        return *this < b || *this == b;
    }
    bool operator >= (const HugeInt &b) {
        return *this > b || *this == b;
    }
    string str() const {
        string res = "";
        for (int i = 0; i < len; i++) res = char(s[i] + '0') + res;
        return res;
    }
    HugeInt inc(int v = 1) {
        *this += v;
        return *this;
    }
    HugeInt dec(int v = 1) {
        *this -= v;
        return *this;
    }
};

istream& operator >> (istream &in, HugeInt &x) {
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream& operator << (ostream &out, const HugeInt &x) {
    out << x.str();
    return out;
}

HugeInt X[110];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        HugeInt a, b, c, x;
        int n;
        scanf("%d", &n);
        if (n == 1)
        {
            cin >> a;
            puts("Yes");
            continue;
        }
        if (n == 2)
        {
            cin >> a >> b;
            if (a == 0 && b != 0 || a != 0 && b == 0)puts("No");
            else puts("Yes");
            continue;
        }
        for (int i = 1;i <= n;i++)
        {
            cin >> X[i];
            X[i].clean();
        }
        int v = 1;
        for (int i = 1;i <= n;i++)
            if (X[i] != 0) v = 0;
        if (v) { puts("Yes");continue; }
        int w = 1;
        for (int i = 2;i<n;i++)
            if (X[i - 1] * X[i + 1] != X[i] * X[i] || X[i] == 0)
            {
                puts("No");
                w = 0;
                break;
            }
        if (w) puts("Yes");
    }
    return 0;
}

Problem4-Reflect

Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
从镜面材质的圆上一点发出一道光线反射NN次后首次回到起点。
问本质不同的发射的方案数。

输入描述
第一行一个整数T,表示数据组数。T10
对于每一个组,共一行,包含一个整数,表示正整数N(1N106)N(1 \leq N \leq 10^{6})
输出描述
对于每一个组,输出共一行,包含一个整数,表示答案。
输入样例
1
4
输出样例
4

这题听说直接求(N+1)的欧拉函数。。

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

#define gch getchar
#define mp make_pair

typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;

char C_get;
void read(int &x)
{
    for (x = 0, C_get = gch();(C_get<'0' || C_get>'9') && C_get != '-'&&C_get != '+';C_get = gch());
    if (C_get == '-'){for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 - C_get + '0';}
    else{if (C_get == '+')C_get = gch();for (;C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 + C_get - '0';}
}

void read(long long &x)
{
    for (x = 0, C_get = gch();(C_get<'0' || C_get>'9') && C_get != '-'&&C_get != '+';C_get = gch());
    if (C_get == '-'){for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 - C_get + '0';}
    else{if (C_get == '+')C_get = gch();for (;C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 + C_get - '0';}
}

void read(double &x)
{
    for (x = 0, C_get = gch();(C_get<'0' || C_get>'9') && C_get != '-'&&C_get != '+';C_get = gch());
    if (C_get == '-'){for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 - C_get + '0';
    if (C_get == '.')
        {double n = 1;for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())n /= 10, x = x - (C_get + '0')*n;}}
    else{if (C_get == '+')C_get = gch();for (;C_get >= '0'&&C_get <= '9';C_get = gch())x = x * 10 + C_get - '0';
    if (C_get == '.'){double n = 1;for (C_get = gch();C_get >= '0'&&C_get <= '9';C_get = gch())n /= 10, x = x + (C_get - '0')*n;}}
}
void read(char x) { x = gch(); }

int T, n;

int eular(int n)
{
    int ret = 1, i;
    for (i = 2;i*i <= n;i++)
    {
        if (n%i == 0)
        {
            n /= i, ret *= i - 1;
            while (n%i == 0)
                n /= i, ret *= i;
        }
    }
    if (n>1)ret *= n - 1;
    return ret;
}


int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        printf("%d\n", eular(n + 1));
    }
    return 0;
}

赛后总结:我的贡献值是负数。。

Category: 程序 | Tags: | Read Count: 221

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com