SCNU ACM 2016新生赛初赛 解题报告

时间：2024-08-04 17:32:56

新生初赛题目、解题思路、参考代码一览

1001. 无聊的日常

Problem Description

两位小朋友小A和小B无聊时玩了个游戏，在限定时间内说出一排数字，那边说出的数大就赢，你的工作是帮他们统计他们获胜的次数。

Input

第一行是一个T，代表游戏的次数T（T≤1000）。每组两个整数p，y（1≤p≤\(10^{100}\)，1≤y≤\(10^{100}\)），分别表示两位小朋友说出的数字。

Output

输出两个数，A和B获胜的次数。后面没有换行，仅此一题

Sample Input

2

11 22

22 11

Sample Output

1 1

解题思路

  • 签到题，但是要上天的出题人给的数据不对，造成了大量的WA。后来我点进去一看数据长度不对，放到python里len一下，数据竟然有70多位，才让大佬改成了\(10^{100}\)。
  • 很简单，比较两个数字的大小并统计次数就好了。但是数字非常大，你需要用一个字符串存储。
  • 字符串大数比较，先比较长度，长度相同再从最高位向低位比较每一位的大小（直至不等）。
  • 应当注意，既然没说相等的情况，当然不应该把相等的情况也算进去。
  • 时间复杂度：O(N)，常数为3以上。
  • 空间复杂度：O(N)

参考代码

  • ?:的语法是gnu c/c++独有，a ?: c等价于a ? (a) : c
#include <stdio.h>

#include <string.h>

int main() {

    int T, resP = 0, resY = 0, temp;

    char p[99]={0}, y[99]={0};

    scanf("%d", &T);

    while (T--) {

        scanf("%s%s", p, y);

        temp = (int) strlen(p) - (int) strlen(y) ?: strcmp(p, y);

        if (temp > 0)       ++resP;

        else if (temp < 0)  ++resY;

    }

    printf("%d %d", resP, resY);

    return 0;

}

### 1002. 写个编译器

Problem Description

写一个编译器，支持下列语言之一：

C语言 https://en.wikipedia.org/wiki/C_(language)

保证只有main函数

只使用int char main printf关键字，除字符串外只有" ( ) + - * = , 数字 字母 { } ; 空格 换行 的出现，且没有undefined behavior

保证没有判断、循环、递归

如

int main() {

char t;

t = 70;

printf ("%cello", t+=2);

}

Python语言 https://en.wikipedia.org/wiki/Python_(programming_language)

只使用print end关键字，除字符串外只有" ( ) + - * = , 数字 字母 空格 换行 的出现

保证没有判断、循环、递归

如

print (1, 4, end="+11=25")

"输出14+11=25，后面没有换行"

print (1, 4, "+11=25")

"输出14+11=25，后面有换行"

"没有print语句的表达式不会被输出"

JScript https://en.wikipedia.org/wiki/JScript

只使用WScript.Echo WScript.StdOut.Write关键字，除字符串外只有" ( ) + - * = , 数字 字母 ; 空格 . 的出现（JScript的换行比较麻烦，暂且避开）

保证没有判断、循环、递归，所有变量为数字或字符串

如

x=3;WScript.Echo(x+6);WScript.Stdout.Write("1\n2");

Text语言 http://esolangs.org/wiki/Text

除字符串外只有" ( ) + - * 数字 字母 空格 换行 , { }

保证没有循环、递归

如

Output Character H

Let t Be 3

Output String ell

If t-2 Positive {

Output Character With Ansii 111

}

If t-4 Positive {

Output Character With Ansii 10

}

BrainFuck http://esolangs.org/wiki/Brainfuck

保证只有> < + - . [ ]

每个位置可以储存0-255的数字，超过将会绕回

保证执行次数小于100 000

Input

依次输入几种语言的代码，两种语言之间以==========（10个等号）分割。保证所有代码可以正常编译执行

Output

选择一种进行编译并输出运行结果。

Sample Input

int main() {

  char t;

  t = 70;

  printf ("%cello", t+=2);

}

==========

print (1, 4, end="+11=25")

"输出14+11=25，后面没有换行"

print (1, 4, "+11=25")

"输出14+11=25，后面有换行"

"没有print语句的表达式不会被输出"

==========

x=3;WScript.Echo(x+6);WScript.Stdout.Write("1\n2");

==========

Output Character H

Let t Be 3

Output String ell

If t-2 Positive {

  Output Character With Ansii 111

}

If t-4 Positive {

  Output Character With Ansii 10

}

==========

+++++[>++++++++<-]>.

Sample Output

Hello

解题思路

  • 又是大佬的神作，看看就好。
  • 向真的写了BrainFuck的巨巨们Orz一个。
  • 注意倒数第二种语言Text，输出就是源代码本身。
  • 时间复杂度：O(N)，常数大概在1～3
  • 空间复杂度：O(N)

参考代码

#include <stdio.h>

#include <string.h>

char code[(int) (3e7)], *result = code;

int main() {

    fread(code, 1, (int) (3e7), stdin);

    for (int i = 0; i < 3; ++i)

        result = strstr(result, "\n==========\n") + 12;

    *strstr(result, "\n==========\n") = 0;

    printf("%s", result);

    return 0;

}

### 1003. 手机密码

Problem Description

某天CZJ在玩辣鸡游戏，玩着玩着发现手机被hack了，重启之后发现界面上出现了一个数字和一个密码框。

CZJ试了半天发现，当输入的正整数满足以下条件时,界面上不会弹出可恶的错误:

  1. 它的二进制形式中1的数量和显示数字的（二进制中1数量）相同；
  2. 十进制大于显示的数字；
  3. 在所有可行答案中最小。

可悲的是又跳出一个数字。CZJ算了几个之后觉得好麻烦，你可以帮他算一下吗？

Input

第一行是一个T，代表数据的组数T（T≤100001）。接下来是T行，每行有一个数字N，表示显示的数字（1≤n≤1000000000）。

Output

针对每一个数字输出对应密码。

Sample Input

2

1

5

Sample Output

2

6

Hint

1的二进制表达为1，2的二进制表达为10，5的是101，6的是110

解题思路

  • 首先只考虑第一个条件。统计数字N的二进制表示中，“1”的数量C。然后输出一个数X，使得X的二进制表示是由C个连续的“1”构成。
  • 再考虑第二个条件，要求输出的X要比N大。那就从右边找极值，从右到左扫描N的二进制，先扫过一段连续的“0”，再扫过一段连续的“1”，之后再第一次扫描到“0”时停止。如N=92（0101 1100）。把这一位0置为1，下一位1置为0（为了保证“1”的个数不变），像这样：X=108（0110 1100）。这样输出X的确要比原数N大。
  • 最后考虑第三个条件，在所有可行方案中最小。我们再次考察X=108（0110 1100），由于X=108具有N=88所没有的更高位的“1”，所以X一定比N大，而不论后面低位的数字如何变化。于是重排X=99（0110 0011），也就是将比变换位低位的1全部移到右边去。
  • 时间复杂度：O(d)=O(logN)
  • 空间复杂度：O(1)

参考代码1

  • __builtin_ctz函数是gnu c/c++独有，用于计算从右起第一个“1”之后的“0”的个数，参数为0时是ub；
  • 也可以用__builtin_ffs函数找到从右起第一个“1”的位置；
  • 然而这些函数看看就好，记得可以用，还是推荐自己算。
#include <stdio.h>

int main() {

    int T, N, a, b, t;

    scanf("%d", &T);

    while (T--) {

        scanf("%d", &N);

        t = a = N & -N;

        do a <<= 1; while (a & N);

        b = (N & (~(-a))) >> (__builtin_ctz(t) + 1);

        N = N & -a ^ a ^ b;

        printf("%d\n", N);

    }

    return 0;

}

参考代码2

#include <stdio.h>

int main() {

    int T, N, a, b;

    scanf("%d", &T);

    while (T--) {

        scanf("%d", &N);

        a = 0, b = 0;

        while (!(N & 1)) N >>= 1, ++a;

        while (N & 1) N >>= 1, ++b;

        printf("%d\n", ((N | 1) << (a + b)) & (~((1 << (a + b)) - 1)) | ((1 << (b - 1)) - 1));

    }

    return 0;

}

### 1004. Zyj大逃亡

Problem Description

Zyj打比赛时又没做出题来，还写崩了一道题，他的队友们和SCNU的大佬们都跑来追杀他啦！Zyj在逃亡过程中和大佬们一起穿越到了LOL世界中。大佬们启动了“疾走”技能，很快就把Zyj围堵到了一个包围圈中。

Zyj拥有一个被动技能，当不向敌人走动时能获得飞一般的速度，从而逃出包围圈。已知包围圈的半径为\(R\)，可以设Zyj所在位置为原点O，大佬们都恰好站在圆上一点，并知道每位大佬的坐标位置为\(P_i(x_i, y_i)\)。显然每位大佬之间都隔着一段圆弧，Zyj可以且仅可以从长度\(L \geqslant \frac12 R\)的圆弧的中点逃出以保证他的被动技能生效。若不存在这样的圆弧（即长度都太短）则Zyj无路可逃。

注意，如果Zyj的可选最长圆弧不唯一，即使长度足够，也认为Zyj无论走哪个方向都不背向敌人，Zyj还是无路可逃。

Input

第一行只有一个正整数\(T\)（\(T \leqslant 1000\)），代表了\(T\)个情形。

接下来有\(T\)组输入，每组输入中包含两个正整数\(N\)（\(N>3\)）和\(R\)（\(0<R<1000\)），分别代表包围圈的半径和追杀Zyj的大佬数量。接下来\(N\)行每行有\(2\)个数字，分别代表\(N\)个大佬的坐标\((x_i, y_i)\)，保证所有的\(x_i^2+y_i^2=R^2\)成立，提供数据的精度保证7位有效小数（舍入后）。保证数据读得完。

Output

对于每个Zyj逃亡的情形，如果Zyj能逃出来，则输出Zyj可逃离的最长圆弧的中点的坐标（保证答案唯一，且保留4位小数）；如果Zyj无路可逃，请输出"Zyj has been slain"（不包括双引号）。

Sample Input

2

4 25

0 25

-25 0

-0 -25

25 -0

4 25

0 25

0 -25

20 15

20 -15

Sample Output

Zyj has been slain

-25.0000 0.0000

解题思路

  • 我出的题。题目有修改，“如果Zyj的可选最长圆弧不唯一”原本的描述是“如果Zyj能选择的所有圆弧都等长”，但是多事的oyk说看不懂，结果改了描述后好像变难了。我的代码仍然是“所有等长”的版本，如果要判“最长不唯一”，要另开数组标记一下浮点数。
  • 如果用笛卡尔坐标系，不是不能做，挺难的。考虑极坐标系，由于坐标都在圆上，长度均等于R。每个大佬的直角坐标对应极坐标角度angle，对angle进行排序，两两相减得到每段圆弧所对圆心角theta，遍历一遍这个theta，最后有答案就除以2再转直角坐标。
  • 注意由于是个圆，还要算上第一个和最后一个坐标之间的圆弧。
  • 正确姿势做法：极角排序。
  • 奇怪的错误点：
    1. 完全不会测试浮点数，判断相等时有精度问题；
    2. 完全不会比较浮点数，判断大小时比较错误。
  • 时间复杂度：O(NlogN)

参考代码

  • C语言在stdlib.h里有个qsort排序函数
  • C++在algorithm中（STL）有个std::sort排序函数
  • 不要干手写冒泡排序这种奇怪的事情，手写快排也不要
  • 浮点数由于精度误差，不能直接比较相等，要设置一个较小的允许误差，小于这个误差可认为等于0
#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

//做自己出的题WA了是一种怎样的体验？Zyj的回答，获得0个赞同。

const double PI = acos(-1.);

int angleCount;

double angleArray[10000];

void init() {

    angleCount = 0;

    memset(angleArray, 0x0, sizeof(angleArray));

}

int N, R;

void read() {

    double x, y;

    scanf("%d%d", &N, &R);

    for (int i = 0; i < N; ++i) {

        scanf("%lf%lf", &x, &y);

        angleArray[angleCount++] = atan2(y, x);

    }

}

int fcmp(double a, double b) {

    /*if (fabs(a - b) <= 1e-7)*/

    if (fabs(a - b) / fabs(a) <= 1e-7 ||

        fabs(a - b) / fabs(b) <= 1e-7)

        return 0;

    if (a < b) return -1;

    /*if (a > b)*/ return 1;

}

int compareDouble(const void *a, const void *b) {

    return fcmp(*(double *) a, *(double *) b);

}

void work() {

    qsort(angleArray, (size_t) angleCount, sizeof(double), compareDouble);

    angleArray[angleCount++] = angleArray[0] + 2. * PI;

    int isNotSame = 0;

    int rangeUpperIdx = 1;

    double maxRange = angleArray[rangeUpperIdx] - angleArray[rangeUpperIdx - 1];

    for (int i = 2; i < angleCount; ++i) {

        double temp = angleArray[i] - angleArray[i - 1];

        int cmpJudge = fcmp(temp, maxRange);

        if (cmpJudge) ++isNotSame;

        if (cmpJudge > 0) {

            maxRange = temp;

            rangeUpperIdx = i;

        }

    }

    if (isNotSame && fcmp(maxRange, 0.5) > 0) {

        double theta = (angleArray[rangeUpperIdx] + angleArray[rangeUpperIdx - 1]) / 2.;

        printf("%.4f %.4f\n", R * cos(theta), R * sin(theta));

    } else {

        printf("Zyj has been slain\n");

    }

}

int main() {

    int T;

    scanf("%d", &T);

    while (T--) {

        init();

        read();

        work();

    }

    return 0;

}

### 1005. Czj数数

Problem Description

自从Czj上了初中，已经不再满足于从1数到100了，他打算来个高难度的挑战。

设a1=1，a2=11，有数列ai，任意1<i≤n，元素ai−1与其自身的最后一位数字组成了新的数字X（如233将会变成2333），而ai是X的最大质因子。由于Czj很懒，数到2333就觉得无聊而跑去写gc了。现在请你帮他完成这未竟的事业。

Input

第一行是一个正整数T（T<100），代表接下来有T次询问。

接下来的T行，每一行输入一个正整数i（1≤i≤104）。

Output

对于每次询问，你应该求出数组中的第i个元素ai，并以"Case #t: ai"的格式单独输出一行，不包括双引号。其中#t代表询问的编号。

Sample Input

3

5

6

7

Sample Output

Case #1: 23

Case #2: 233

Case #3: 2333

解题思路

  • 还是本菜鸡出的题。
  • 遇事不决打个表。如果你打了表，你就会发现生活的美好——这里面原来是有循环节的。从第5个数开始，到第30个数，是一个循环节。
  • 一般这种一眼看过去是递推，又没找到公式，干脆想都不要想直接打表出来，找有没有循环节，没有循环节再找规律。
  • 怎么找一个数的最大质因子呢？不需要素数筛，试除法就行。当然你开心的话，可以上Eratothenes筛或欧拉筛打素数表。试除法打素数表是会超时的。当然这里用到的素数还不大于100。
  • 时间复杂度：O(1)或O(\(M\sqrt{N}\))或O(\(M\log \log N\))，M=??

求最大质因子

/**

 * find out the largest prime factor of given num.

 */

int largestFactorOf(int num) {

    int iterateNumber = num;

    int q = (int) sqrt(num) + 1;

    int iterateFactor = 2;

    while (iterateFactor <= q) {

        while (iterateNumber % iterateFactor == 0)

            iterateNumber /= iterateFactor;

        if (iterateNumber == 1)

            break;

        ++iterateFactor;

    }

    return iterateNumber == 1 ? iterateFactor : iterateNumber;

}

参考代码

#include <stdio.h>

/**

 * http://oeis.org/A195201

 * Description: for a(1) = 1, a(n) is the largest prime factor of

 * the number which is made up from a(n-1) and its last digit.

 * Input: T, and T lines of any n.

 * Output: a(n) for every n.

 * */

const int fixedSection[4] = {

        1, 11, 37, 29

};

const int cycleSection[26] = {

        23, 233, 2333, 23333, 661, 601, 6011, 6679,

        997, 907, 313, 241, 2411, 47, 53, 41, 137,

        17, 59, 599, 857, 953, 9533, 13619, 19457, 821

};

int T, n;

void read() {

    scanf("%d", &n);

}

void work(int caseCount) {

    printf("Case #%d: %d\n", caseCount, n <= 4 ? fixedSection[n - 1] : cycleSection[(n - 5) % 26]);

}

int main() {

    scanf("%d", &T);

    for (int i = 1; i <= T; ++i) {

        read();

        work(i);

    }

    return 0;

}

### 1006. 飞来飞去的Zyj

Problem Description

Zyj在接电路板。他给出了要连接的线的列表，并按顺序进行连接。但是他不绕线，如果两个点连成的线段不与任何画线相交，就在上面把线画出来，否则就直接上飞线（即这根线不画在电路板上，而是在空中连接）。问，Zyj一共飞了几条线？

注意，如果其中一条线经过另一条线的端点，视为相交；但如果两条线在端点上相接，视为不相交。部分重叠视为相交，除非在端点上相接

Input

第一行T为数据组数（小于100）

每组数据的第一行n为连线数量（小于100），后面紧跟着n行(x1,y1)-(x2,y2)表示端点坐标。坐标值的绝对值小于100.

Output

对每组数据，输出Case #d: q，其中d为数据编号，q为飞线数量。

Sample Input

2

7

(1,2)-(4,2)

(4,2)-(4,1)

(4,1)-(2,1)

(2,1)-(2,4)

(2,4)-(3,4)

(3,4)-(3,3)

(1,3)-(3,3)

4

(1,1)-(7,1)

(2,1)-(2,2)

(3,1)-(4,1)

(6,1)-(7,1)

Sample Output

Case #1: 1

Case #2: 2

样例解释：

4  ┎┐   


3 ─╂┘   


2 ─╂─┐  


1  ┗─┘  


 １２３４




2  ┃    


1 ─┸────────  


 　  ━━　 ──（这行和上一行是叠在一起的）


 １２３４５６７ 


其中粗线表示飞线

解题思路

  • 讲真，这题我也不会做。反正又是大佬的神作。
  • 后来搜了下，线段判交是有技巧的，常用的是向量积；也可以直接解析几何解方程。这里用了随便一搜能搜出来的快速排斥+跨立试验。
  • 需要注意的是1.按顺序连接；2.重叠相交；3.端点连接强制不相交；4.应当标记飞过的线。
  • 时间复杂度：O(\(N^2\))

参考代码（因为我不会做，直接用C++了）

#include <stdio.h>

#include <string.h>

#include <algorithm>

using std::max;

using std::min;

inline int feq(const double &a, const double &b) {

    return fabs(a - b) < 1e-7;

}

inline int fneq(const double &a, const double &b) {

    return !feq(a, b);

}

inline int fgeq(const double &a, const double &b) {

    return feq(a, b) || a > b;

}

struct Point {

    double x, y;

    Point() {}

    Point(double x, double y) : x(x), y(y) {}

    int operator!=(const Point &p) const {

        return fneq(x, p.x) || fneq(y, p.y);

    }

};

struct Line {

    double x, y;

    Line() {}

    Line(const Point &P0, const Point &P1) : x(P1.x - P0.x), y(P1.y - P0.y) {}

    double operator^(const Line &l) const {

        return x * l.y - y * l.x;

    }

};

typedef Point Segment[2];

inline int quickReject(Segment &A, Segment &B) {

    return max(A[0].x, A[1].x) >= min(B[0].x, B[1].x) &&

           max(A[0].y, A[1].y) >= min(B[0].y, B[1].y) &&

           max(B[0].x, B[1].x) >= min(A[0].x, A[1].x) &&

           max(B[0].y, B[1].y) >= min(A[0].y, A[1].y);

}

inline int quickCross(Segment &A, Segment &B) {

    return (Line(B[0], A[0]) ^ Line(B[0], B[1])) * (Line(B[0], B[1]) ^ Line(B[0], A[1])) >= 0 &&

           (Line(A[0], B[0]) ^ Line(A[0], A[1])) * (Line(A[0], A[1]) ^ Line(A[0], B[1])) >= 0;

}

int flown[101];

Segment seg[101];

int main() {

    int T, N;

    scanf("%d", &T);

    for (int cse = 1; cse <= T; ++cse) {

        int res = 0;

        memset(flown, 0x0, sizeof(flown));

        scanf("%d%*c", &N);

        for (int i = 0; i < N; ++i) {

            scanf("%*c%lf%*c%lf%*c%*c%*c%lf%*c%lf%*c%*c", &seg[i][0].x, &seg[i][0].y, &seg[i][1].x, &seg[i][1].y);

            for (int j = 0; j < i; ++j)

                if (quickReject(seg[j], seg[i]) && quickCross(seg[j], seg[i]) &&

                    seg[j][0] != seg[i][0] && seg[j][0] != seg[i][1] &&

                    seg[j][1] != seg[i][0] && seg[j][1] != seg[i][1] && !flown[j]) {

                    flown[i] = 1;

                    ++res;

                    break;

                }

        }

        printf("Case #%d: %d\n", cse, res);

    }

    return 0;

}

### 1007. 灌水

Problem Description

CZJ和L2M在车上闲着没事拿了个水杯灌水，规定杯子的体积P和每次可以倒进杯子的水的最大体积Y，两个人轮流向杯子灌整数体积的水，最后灌满杯子的人获胜。

CZJ看起来很想赢的样子，L2M宽宏大量的给了先手。但是CZJ这么菜，你能教下CZJ起手要灌多少才能必胜吗？

Input

第一行是一个T，代表数据的组数T（T≤20000）。每组两个整数p，y（1≤p≤10000000，1≤y≤10000000）。

Output

对于每组数据输出CZJ起手灌水的数量，如果CZJ赢不了，打出GG。

Sample Input

2

3 1

2 1

Sample Output

1

GG

解题思路

  • 首先这是一个入门级博弈问题。不知道博弈的也没关系，如果你有耐心，在纸上演算一下6以内的情况，就会发现规律。
  • 这个问题是巴什博奕先手赢。我们总考虑P>V，否则先手必胜的。
  • 我们先找一个先手必败态：P=Y+1。无论先手怎么倒水，总不能倒满，而后手总能把杯子倒满，所以这种情况先手必败。
  • 在其他情况下，能不能想办法把这个必败态转移给对手呢？考虑只有两局，第一局先手先倒M的水，后手和第二局先手总共倒N=P-M的水，并且要保证第二局先手胜。
  • 我们发现这相当于只有一局——不管先手倒多少体积为M的水，就当水杯体积是P-M好了，这样原本的后手等价成为了新的先手。如果剩下的体积刚好N=Y+1，那么原本的后手就陷入了先手必败困局。
  • 如果除去一开始倒的M水，每一局都总共倒Y+1的水呢？因为Y<Y+1<2Y，新的先手永远最多只能倒1<=Z<=Y的水，而新的后手总能控制局面的变化，即他能倒Y+1-Z<=Y的水。控制每次两人总共倒Y+1的水，就赢了。
  • 为什么一定是Y+1，不能是+2、+3吗？因为再多的话，先手就不是必败了，先手总能取一个较小值使得后面剩下Y+1。
  • 所以一开始要抢先倒P%(Y+1)的水，后面总共倒的水体积是(Y+1)的倍数。

参考代码

#include <stdio.h>

int main() {

    int p, y;

    scanf("%d", &p);

    while (~scanf("%d%d", &p, &y))

        (p %= (y + 1)) ? printf("%d\n",p) : puts("GG");

    return 0;

}

### 1008. 和

Problem Description

输入几个数字，求和。

Input

每行一个样例，由正整数组成，空格分开

Output

对每个样例，输出和。保证结果小于\(10^9\)

Sample Input

1 1

1 2

Sample Output

2

3

解题思路

  • 签到题，注意题面的“几个数字”。
  • 用EOF判输入结束。可以用一个小char判断换行。

参考代码

#include <stdio.h>

int main() {

    int res, a, c;

    while (~scanf("%d", &res)) {

        while (scanf("%c", &c), c != '\n') {

            scanf("%d", &a);

            res += a;

        }

        printf("%d\n", res);

    }

    return 0;

}

### 1009. 开饭

Problem Description

CZJ的舍友请CZJ吃饭，作为舍友CZJ是不会放过吃穷舍友的机会，但自己身体又不好，不能吃太多也不能吃太少。假设每样食物都有一个饱腹度和价值，请你帮他算下刚好吃饱的情况下最多可以吃他舍友多少钱。

Input

第一行是一个T，代表数据的组数T（T≤100001）。每组两个整数p，y（1≤p≤1000，1≤y≤100），分别表示食物的数量和CZJ的饱腹度。

然后p个数\(Q_{p_i}\)表示第\(p_i\)个食物的价值，之后p个数\(M_{p_i}\)表示吃第\(p_i\)个食物得到的饱腹度。（1≤\(Q_{p_i}\)≤10000，1≤\(M_{p_i}\)≤1000）。

Output

对于每一个样例输出CZJ能吃下的最大价值。

Sample Input

1

5 100

11 6 7 5 6

40 50 60 20 30

Sample Output

18

解题思路

  • 0-1背包问题求最大值。入门级dp。
  • 对于这题有很多人过没有意外。只要你搜一下什么叫“动态规划”或者“dp”，把0-1背包的递推往这一套，就A了。
  • 推荐学习资料：“背包九讲”、“动态规划32讲”。

参考代码

#include <stdio.h>

#include <string.h>

#define MAXN 1010

int C[MAXN], W[MAXN], dp[MAXN];

void init() {

    memset(C, 0x0, sizeof(C));

    memset(W, 0x0, sizeof(W));

    // dp数组初始值要足够小。这里一个int是0x80808080

    memset(dp, 0x80, sizeof(dp));

    dp[0] = 0;

}

void getMax(int &a, int b) {

    if (a < b) a = b;

}

int N, V;

void read() {

    scanf("%d%d", &N, &V);

    for (int i = 0; i < N; ++i) scanf("%d", W + i);

    for (int i = 0; i < N; ++i) scanf("%d", C + i);

}

void work() {

    for (int i = 0; i < N; ++i)

        for (int v = V; v >= C[i]; --v)

            getMax(dp[v], dp[v - C[i]] + W[i]);

    printf("%d\n", dp[V]);

}

int main() {

    int T;

    scanf("%d", &T);

    while (T--) {

        init();

        read();

        work();

    }

    return 0;

}

### 1010. Zyj消极比赛

Problem Description

ACM比赛剩下最后10分钟，其他人都已经收拾好东西准备走人，Zyj才从睡梦中醒来。Zyj可以看到所有其他人的过题情况，他希望得到的名次在a到b之间，问有几种可选择的方案？（假设其他人的提交时间即使加上罚时也早于Zyj的提交，毕竟剩下10分钟了都）

Input

第一行为T(0<T<100)，代表有T组数据。

每组数据中第一行为两个数字m n a b，由空格隔开，代表这次比赛有m道题(由于字母数量的限制，0<m<27)，n个其他人，Zyj希望得到的名次x满足a<x<b (-1<n,a,b<1000)

下面n行为每个人每道题的通过情况，1为已通过，0为未通过

Output

对每个样例，输出Case #k: ans，其中k为样例编号，ans为方案数量。

Sample Input

2

26 1 0 2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

26 1 0 2

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0

（Case #1是25个1 1个0，#2是1个0 24个1 1个0）

Sample Output

Case #1: 1

Case #2: 27

Hint

样例解释：

Case #1中Zyj必须AK(全部题都做出来)才可以得到大于0小于2的名次，即第1名。不要怕他做不完，那可是Zyj

Case #2中Zyj可以AK，也可以任意选一道不做

ACM排名规则见http://scnuacm2015.sinaapp.com/php/presentation.php

解题思路

  • 对于这种题我只能无语。
  • 这里有个隐含条件，因为Zyj是最后做题，罚时爆炸，所以无论他做多少题，都是同题数的最后一名。
  • 然后累加出每个人过题的数量，进而统计过0≤x≤m题的人数，从最高名次到最低名根据Zyj想要的名次去求组合数就好。
  • 一些错误点：
    1. 没有处理好边界，对于不可能存在/达到的排名，计算结果不为0；
    2. 同题数计算排名时没有考虑zyj是最后做题；
    3. 没有加上当有人过0题时，zyj拿最后一名也可以过0题的1种情况；
    4. 并列排名不顺延，比如1题的最后一名可能是x，那么0题的并列排名是x+1而不是n；
    5. 有没看懂题的，把过题总数直接作为排名（也是没考虑过题时间会影响排名）；
    6. 还有一些奇怪的错误..不会算组合数or阶乘..有的没考虑除0..有的没考虑计算过程不整除..有的..我也不知道。
  • 时间复杂度：\(O(m*m)\)或\(O(m+m*m)\)（公式法预处理）或\(O(m+m)\)（预处理阶乘及其逆元）

参考代码1

#include <stdio.h>

#include <string.h>

/*

 * count[k] 记录了过了k题的人数

 */

int m, n, a, b;

int count[27];

void init() {

    memset(count, 0x0, sizeof(count));

}

void read() {

    scanf("%d%d%d%d", &m, &n, &a, &b);

    for (int i = 0; i < n; ++i) {

        int acc = 0, temp;

        for (int j = 0; j < m; ++j) {

            scanf("%d", &temp);

            acc += temp;

        }

        // 实际上count[0]没有利用价值

        ++count[acc];

    }

}

// 求组合数 - 魔幻除法（可以想想为什么能整除）

int C(int n, int x) {

    int res = 1;

    if (n - x > x) x = n - x;

    n -= x;

    for (int i = 1; i <= n; i++)

        res = res * (x + i) / i;

    return res;

}

int work() {

    int res = 0, rank = 1;

    for (int i = m; i > 0; --i) {

        // zyj 做i题能拿的名次

        rank += count[i];

        if (a < rank && rank < b)

            res += C(m, i);

    }

    // 就算做0题，zyj也是拿同做1题一样的排名

    if (a < rank && rank < b)

        res += 1;

    return res;

}

int main() {

    int T;

    scanf("%d", &T);

    for (int cse = 1; cse <= T; ++cse) {

        init();

        read();

        printf("Case #%d: %d\n", cse, work());

    }

    return 0;

}

参考代码2

#include <stdio.h>

#include <string.h>

/*

 * count[k] 记录了过了k题的人数

 */

int m, n, a, b;

int count[27];

void init() {

    memset(count, 0x0, sizeof(count));

}

void read() {

    scanf("%d%d%d%d", &m, &n, &a, &b);

    for (int i = 0; i < n; ++i) {

        int acc = 0, temp;

        for (int j = 0; j < m; ++j) {

            scanf("%d", &temp);

            acc += temp;

        }

        // 实际上count[0]没有利用价值

        ++count[acc];

    }

}

// 求组合数 - 公式预处理法

int C[27][27];

const int MOD = 1000000007;

void pre() {

    C[0][0] = C[1][0] = C[1][1] = 1;

    // 公式 C(n,x) = C(n-1,x-1) + C(n-1,x)

    for(int n = 2; n <= 26; n++) {

        C[n][0] = C[n][n] = 1;

        for(int x = 1; x < n; x++)

            C[n][x] = (C[n-1][x-1] + C[n-1][x]) % MOD;

    }

}

int work() {

    int res = 0, rank = 1;

    for (int i = m; i > 0; --i) {

        // zyj 做i题能拿的名次

        rank += count[i];

        if (a < rank && rank < b)

            res += C[m][i];

    }

    // 就算做0题，zyj也是拿同做1题一样的排名

    if (a < rank && rank < b)

        res += 1;

    return res;

}

int main() {

    pre();

    int T;

    scanf("%d", &T);

    for (int cse = 1; cse <= T; ++cse) {

        init();

        read();

        printf("Case #%d: %d\n", cse, work());

    }

    return 0;

}

### 1011. Oyk剪纸

Problem Description

Oyk要把一张矩形纸剪成N张一样的矩形不留剩余，使用的方法为

1.从一个方向剪若干（可能为0）刀

2.从与其垂直的方向再剪若干刀

那么他至少要剪几刀？

Input

多（少于1000）组样例，每行一个数字N（大于0小于1亿）。

Output

对每个样例，输出一行结果。

Sample Input

4

5

60

Sample Output

2

4

14

Hint

解释：

┌┬┐┌┬┬┬┬┐  


├┼┤└┴┴┴┴┘  


└┴┘

解题思路

  • 首先剪的方向只能是与纸边平行或垂直。斜着剪会产生剩余，而且也产生负收益（浪费了剪的次数）。
  • 于是问题分解成了\(N=x * \frac{N}{x}\)，\(r=(x-1)+(\frac{N}{x}-1)\)，要让\(r\)尽可能小。不记得什么不等式了。
  • 直接任性求导，\(r'=1-\frac{N}{x^2}=0\)，在\(x=\sqrt{N}\)处\(r\)取得最小值。但注意x要是整数（不可能剪半刀）。
  • 时间复杂度：O(\(\sqrt{N}\))，最坏情况由N是素数产生。

参考代码

#include <stdio.h>

#include <math.h>

int main() {

    int N, q;

    while (~scanf("%d", &N)) {

        q = (int) sqrt(N);

        for (; q > 1; --q)

            if (N % q == 0) break;

        printf("%d\n", q + N / q - 2);

    }

    return 0;

}

出题及解题总结

我出的两题

  • 1004、1005都是我出的题。设计是一简单一难的。
  • 1004极角排序我想对新生来说还是挺难想到并做出的，事实上我出数据都快出成傻逼了；
  • 1005循环节打表可能我太高估新生水平了(?)，因为我并没有出1e9的数据去卡素数表，而且数据范围设置非常小，试除法也不至于TLE，基本上是随意过的。理想情况是再不济一堆WA或TLE吧，结果伤心的发现没人做（逃）。

整体情况总结

  1. 首先看统计数据，1001的WA接近500，这里Czj应该背锅，题面数据范围与实际不符。还有一个不输出回车的坑爹设定，强行卡题意，WA得惨不忍睹，严重打击了部分同学信心。
  2. 统计数据还有第二个明显峰度在1003的OLE上。因为我看不到提交代码，没法分析。
    • 有可能是hdoj的OLE是这么判的：输出超过标准答案即判OLE。如果是这样，很多OLE应当划到WA里面。
    • 但是也有反映将C++的输出换成C语言的输出即可通过。这应当是hdoj的锅了。
  3. 还有两个WA小高峰位于1003、1008。
    • 1003的确是很多同学根本没接触到位运算的知识。
    • 而1008也是强行卡题意，给的样例不规范，还不如只给一个。另外也有很多同学并不知道EOF判输入结束。
  4. 从所有题目通过率来看，
    • 1001、1003、1005、1007、1008、1011是正常水平在七天时间内能做出的。
    • 1009尽管是入门级dp，但也涉及了算法，虚高是因为生源有部分接触过OI，以及的确简单，能间接搜到答案。
  5. 从难度上看，
    • 1002爆冷是正常，原因大家都懂。
    • 1004的确算是较难的了，之后改题面应该称得上全场最难。
    • 1006爆冷正常，因为我也不会做（逃），好吧是因为涉及了计算几何，不应该出现在新生赛中。
    • 1010爆冷是意料之外，也是情理之中，这种卡题意挖坑的题必须找出题人背锅。
  6. 1001、1008是两个签到题。预计决赛名额定在解出两题以上。
  7. 我校出题质量一年比一年差，迟早要完。

历届新生赛&别人的新生赛

  1. 华南师大2014新生赛：http://3.scnuacm2015.sinaapp.com/?p=38
  2. 广工2016新生决赛网络同步赛重现：http://gdutcode.sinaapp.com/contest.php?cid=1051
  3. ....

建议、意见、吐槽

欢迎在下方评论区提出问题，12月内我都会回复and更新。

本文基于SCNU ACM 2016新生赛初赛 解题报告知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布，欢迎引用、转载或演绎，但是必须保留本文的署名BlackStorm以及本文链接http://www.cnblogs.com/BlackStorm/p/SCNUCPC_2016_For_Freshman_Preliminary_Solution.html，且未经许可不能用于商业目的。如有疑问或授权协商请与我联系。

相关文章