@darkproject 2016-10-10T04:26:33.000000Z 字数 5950 阅读 1430

A - Lucky Division

英勇无敌的萌新

分析：
列举4与7组合处理
代码如下：

#include<stdio.h>
int main()
{
    int num;
    scanf("%d", &num);
    if (num % 4 == 0 || num % 7 == 0 || num % 47 == 0 || num % 74 == 0 || num % 474 == 0 || num % 477 == 0 || num % 447 == 0 || num % 744 == 0 || num % 774 == 0 || num % 747 == 0)
    {
        printf("YES");
    }
    else
        printf("NO");
    return 0;
}

B - Lucky Substring

分析：
寻找幸运数字4,7根据字典顺序，在一段输入中判断4与7个数，若个数相同则输出4，其余由谁多谁输出
代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char str[55];
    scanf("%s", &str);
    int count4=0, count7=0;
    for (int i = 0; str[i] != '\0'; i++)
    {
        if (str[i] == '4')
            count4++;
        if (str[i] == '7')
            count7++;
    }
    if (count4 == 0 && count7 == 0)
    {
        cout << "-1\n";
    }
    else if (count4 >= count7)
        cout << "4\n";
    else if (count4 < count7)
        cout << "7\n";
    return 0;
}

C - The number of positions

分析：
n个人的队伍，一个人去站队前面至少a人后面至多b人，问有多少种站队方法。可以通过确立前面至少的a人后，判断n-前面人数是否满足于后面必须有的b人，即n-i<=b
代码如下：

#include<stdio.h>
int main()
{
    int n, a, b;
    int count = 0;
    scanf("%d%d%d", &n, &a, &b);
    for (int i = a + 1; i <= n; ++i)
        if (n - i <= b)
            count++;
    printf("%d", count);
    return 0;
}

D - Permutations

萌萌哒灵梦
分析：
n行k位正整数，允许有前导零，求解所有序列中最大值与最小值的最小可能。（变换第一个某2个数据位置后，其余数据都要按这个顺序进行变换）这道题呢萌新没有做出来，不过在国庆这段时间参考了一些代码，这题可以通过求出k!的排列然后判断。大部分都是通过搜索完所有序列进行判断。这里我曾听到果巨巨说过next_permutation这个函数，看了下题目觉得应该是用在这里（噗，记得自己写的时候写了要上百行啦，看了下别人风格最后优化可以很短），利用此函数可以很大程度上减少代码量。

ps:这个函数是求给定数组不按升序排列的最小字典序列，可以遍历完所有可能的序列直到无法找到下一个序列返回false。
参考函数：
template<class BidirectionalIterator> bool next_permutation( BidirectionalIterator _First, BidirectionalIterator _Last );
代码如下：

#include<bits/stdc++.h>
using namespace std;
char str[10][9];
int change[10];
int main()
{
    int n, k, result = 10000000000;
    int ma,mi;
    cin >> n >> k;
    for (int i = 0; i < k; ++i)
        change[i] = i;
    for (int i = 0; i < n; ++i)
        cin>>str[i];
    do 
    {
        ma = -99999999, mi = 99999999;
        for (int i = 0; i < n; ++i)
        {
            int num = 0;
            for (int j = 0; j < k; ++j)
            {
                num = num * 10 + str[i][change[j]] - '0';
            }
            ma = max(ma, num);
            mi = min(mi, num);
        }
        result = min(ma - mi, result);
    } while (next_permutation(change, change + k));
    cout << result << endl;
    return 0;
}

E - Wasted Time

666
分析：
这题大致就是一个好像非常叼的人给别人签名，求他浪费在签名上的时间，他签名速度为每秒50毫米。n代表签名所需的点的坐标个数，k代表他签了多少张签名。这里只要用2点间公式求出最短距离乘以k张纸最后除于他的速度可以得出正确答案。
ps:不要忘记规范精度
代码如下：

#include<iostream>
#include <iomanip>
#include<cmath>
using namespace std;
int main()
{
    int n, k;
    int x[105], y[105];
    double result = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n-1; ++i)
        result += sqrt(pow(x[i] - x[i + 1], 2) + pow(y[i] - y[i + 1], 2));
    cout <<fixed<< setprecision(9) << result*k/50 <<  endl;
    return 0;
}

F - Canvas Frames

mxr
分析：
一个画家准备画框，数据输入给出所有木棒长度，问可以组成多少个矩形画框。这些木棒不能合成和拆分，通过循环遍历判断。
代码如下：

#include<iostream>
using namespace std;
int main()
{
    int n, count = 0;
    int a[105];
    cin>> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for(int i=0;i<n;++i)
        for(int j=i+1;j<n;++j)
            if (a[i] == a[j])
            {
                count++;
                a[j] = 999999 - j;
                break;
            }
    cout << count/2;
    return 0;
}

G - Cookies

baka9
分析：
嗯这个题意呢，大致是一对姐妹有n袋饼干，第i袋饼干装有a $_{i}$ (1 ≤ a $_{i}$ ≤ 100).为了让她们不吵架，我们要取走其中一袋饼干，然后使剩下的饼干能够让她们平分（既满足偶数，包括0）。
代码如下：

#include<iostream>
using namespace std;
int main()
{
    int n, judge = 0;
    int count = 0;
    int data[105];
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> data[i];
    for (int i = 1; i <= n; ++i)
    {
        int temp = data[i];
        data[i] = 0;
        for (int i=n; i >0; --i)
            judge += data[i];
        if (judge % 2 == 0)
            count++;
        data[i] = temp;
        judge = 0;
    }
    cout << count;
    return 0;
}

H - Students and Shoelaces

miku
分析：
不得不说，这题做法不算太难，但是题意比较难以理解。这里也是因为题意理解很久不能想通。题目主要是学生之间匹配，要保证不能存在学生只与另一个学生连接的情况，也就是学生的度不能为1。这题用图处理，学生作为点，连接带子作为边。还有比较重要的一点，关于一次操作的理解，一次操作指老师踢出所有度为1的学生，这记为一次操作。
采用二维数组记录连接关系，point数组存放学生。通过判断每次删点后（删点后，同时与他相连边也没啦）是否存在度为1的点来进行操作
代码如下：

#include<bits/stdc++.h>
using namespace std;
bool line[105][105];
int point[105];
int temp[105];
int main()
{
    //FILE *fp;
    //freopen_s(&fp,"d:\\hyx.txt", "r", stdin);
    memset(line, 0, sizeof(line));
    int n, m, a, b;
    int flag;
    int result = 0;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        point[a]++;
        point[b]++;
        line[a][b] = 1;
        line[b][a] = 1;
    }
    while (1)
    {
        flag = 0;
        int record = 1;
        for (int i = 1; i <= n; ++i)
            if (point[i] == 1)
            {
                point[i]--;
                temp[record++]=i;
                flag = 1;
            }
        if (!flag) break;
        for (int i = 1; i <record; ++i)
            for (int j = 1; j <= n; ++j)
                if (line[temp[i]][j])
                    point[j]--;
        result++;       
    }
    cout << result << endl;
    //fclose(stdin);
    return 0;
}

I - cAPS lOCK

二小姐
分析：
题意大致是输入的一段字符串（1-100）中进行大小写分别转换。
转换情况：
1. 全为大写字母
2. 首位为小写字母,其余全为大写字母
代码如下：

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    char str[105];
    int count = 0;
    cin >> str;
    int judge = strlen(str);
    for (int i = 0; str[i] != '\0'; ++i)
        if (str[i] < 'a')
            count++;
    if (count == judge)
        for (int i = 0; i < judge; ++i)
            str[i] = str[i] + 32;
    else if (count == judge - 1)
        if (str[0] >= 'a')
            for (int i = 0; i < judge; ++i)
            {
                if (str[i] >= 'a')
                    str[i] = str[i] - 32;
                else
                    str[i] = str[i] + 32;
            }
    cout << str << endl;
    return 0;
}

J - Opposites Attract

萌萌哒二小姐
分析：
求解输入数据存在多少组相反数（0自身互反），这道题很容易想到采用for循环处理，第一次进行时zz使用2个for循环O(n^2)处理最大数据10^5，导致直接T了。后来问了一个大大，建议采用c++ map关联容器记录数据次数，减少运算，一个for简单解决。
代码如下：

#include<iostream>
#include<map>
using namespace std;
map<int,int>x;
int main()
{
    int n,a;
    int t=0;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>a;
        t+=x[-a];
        x[a]++;
    }
    cout<<t;
    return 0;
}

K - The World is a Theatre

233

分析：
题意大致就是在确保男女规定人数n,m上任意组合成一个含t个人的队，有多少种组合方法。这里直接排列组合公式解决，嗯还有不要忘记考虑极限范围。
参考公式： C $\binom{m}{n}$ = $\frac{n!}{m!(n-m)!}$
代码如下：

#include<iostream>
using namespace std;
long long  com(int m, int n);
int main()
{
    int n, m, t;
    long long result = 0;
    cin >> n >> m >> t;
    for (int i = 4;i<=n; i++)
        for (int j = 1;j<=m; j++)
            if (i + j == t)
                result += com(n, i)*com(m, j);
    cout << result;
    return 0;
}
long long com(int m, int n)
{
    int i, j;
    long long sum = 1;
    for (i = m, j = 0; j<n; j++, i--)
    {
        sum = sum*i / (j + 1);
    }
    return sum;
}

M - HQ9+

huo
分析：
根据题意如果含有提示输出字符即为yes，唯一注意一点就是+不算在内。
代码如下：

#include<iostream>
using namespace std;
int main()
{
    char str[105];
    cin >> str;
    int flag = 0;
    for (int i = 0; str[i] != '\0'; ++i)
        if (str[i] == 'H' || str[i] == 'Q' || str[i] == '9')
        {
            flag = 1;
            break;
        }
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return 0;
}

N - Unary

分析：
题中提供的每一个符号对应一个二进制数据，多个符号按输入顺序组成新的一个二进制数据。最后求解这个二进制数据所转化为的十进制数据。直接通过字符串连接方法和一个转换函数解决。不要忘记取余模，否则大数据无法处理。
代码如下：(直觉告诉我应该还有更更简单的方法QAQ)

#include<iostream>
#include<string>
#include<cmath>
using namespace std;
#define M 1000003
string judge(string str,int i);
long long plan(int num[], int n);
int main()
{
    string str, strtemp;
    int num[10000];
    cin >> str;
    for (int i = 0; i != str.size(); ++i)
        strtemp += judge(str, i);
    for (int i = 0; i != strtemp.size(); ++i)
        num[i] = strtemp[strtemp.size() -i-1] - '0';
    cout <<plan(num, strtemp.size())%M<< endl;
    return 0;
}
string judge(string str,int i)
{
    if (str[i]== '>')
        return "1000";
    if (str[i] == '<')
        return "1001";
    if (str[i] == '+')
        return "1010";
    if (str[i] == '-')
        return "1011";
    if (str[i] == '.')
        return "1100";
    if (str[i] == ',')
        return "1101";
    if (str[i] == '[')
        return "1110";
    if (str[i] == ']')
        return "1111";
}
long long plan(int num[],int n)
{
    long long result = 0;
    long long ji= 1;
    for (int i = 0; i < n; ++i)
    {
        result = (result + num[i] * ji)%M;
        ji =ji* 2%M;
    }
    return result;
}