华南师大 2017 年 ACM 程序设计竞赛新生初赛题解。SCNU ACM 2016初生赛决赛 解题报告。

华南师大 2017 年 ACM 程序设计竞赛新生初赛题解

华南师范大学第很大多至 ACM 程序设计竞赛新生赛(初赛)在 2017 年 11 月 20
日 – 27 日成功举行,共有 146 誉为同学中参赛(做出 1
题)。进入决赛的身份初定为做到并由此 5 题或以上,决赛时是 12 月 3
日,地点未定。

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

题解

叫你们虐了千百一体的问题与 OJ
也要命麻烦的,也想只要休息,所以你们别想了,行行好放了她,我们来拘禁题解吧。。。

A. 拒绝虐狗

A. 诡异的计数法

Problem Description

CZJ 去排队从饭的早晚看到前面有几乎对情侣秀恩爱,作为单身狗的 CZJ
表示特别不便被。
现今于有一个字符串代表 CZJ 前面的队列。你可以帮他一把把那些朋友分开吗?

Description

cgy
太喜欢质数了因为关于他计数也用用质数表示!在他看来,2(第一稍微质数)表示1,3(第二稍稍质数)表示2……可恰恰缘他的计数方法极其奇葩,所以他的数学成就非常差又拖累了外的绩点。
lxy 得知 cgy 的绩点排名后打算告诉他,可是要坐无限麻烦的 cgy
质数计数法的法门意味着。 lxy 出重金 ¥(10000000 mod 10)
请你来吗他解决这古怪的计数。

Input

第一尽是一个\(T\),代表数量的组数\(T\)(\(T\leq
100\))。
每组一个独自含大写字母的字符串\(p\)(\(1\leq
len_{p}\leq 1000\)),表示 CZJ
前面的队列,保证非会见时有发生连续三单及以上同等的字母序列

Input

输入包括多组数据,每组数据列占一尽,每一行来一个正整数 n ,表示 cgy
的绩点排名,输入到文件结尾结束( \(n \leq
100000\) ,数据组数 \(t \leq
1000000\) )。

Output

以行中相同且相互相邻之字母用“1”隔开并出口。

Output

对诺每组数据输出一个质数,为 cgy 绩点排名的质数计数法。

Sample Input

2
AABB
ABBA

Sample Input

1
2
28
13

Sample Output

A1AB1B
AB1BA

Sample Output

2
3
107
41

解题思路

  • 签到开,由于保险非见面出现3单和以上的连接相同字符,所以每次判断一下达一个字符就好;
  • 直白在线处理,时间复杂度\(O(len_{p})\)。

Hint

  1. 本场比赛是网络初赛,除了不能够抄袭袭其他运动员代码外,对其它文化以及材料的觅获取不作限制;
  2. A 题并无是无与伦比简便易行的,题目难度不照梯次,请量力而为~
  3. 倘发生其他问题请圈加说明 https://d.wps.cn/v/8pBAU

参考代码

#include <stdio.h>

int main() {
    int T;
    // 读入数据组数,并忽略本行回车
    scanf("%d%*c", &T);
    while (T--) {
        // 每次先初始化上一次读入的字符为EOF
        int readChar, lastChar = EOF;
        // 不断读入一个字符,直到回车
        while (readChar = getchar(), readChar != '\n') {
            // 如果读入的字符和上次读入字符相同,则先输出'1'分开
            if (readChar == lastChar) putchar('1');
            // 经过前面的处理后,把本次读入的字符输出
            putchar(readChar);
            // 重置上次读入的字符
            lastChar = readChar;
        }
        // 单个数据结束,输出换行
        putchar('\n');
    }
    return 0;
}

问题大意

求第 \(K\) 个质数的价值

比提交代码中发现的题目

  1. 发出选手直接提交了exe、txt文件要休是源码文件,导致编译错误;
  2. 片运动员对循环理解有差,for(i=0; i<=n; i++)是实践n+1整的,而数据只有n组,导致直接卡输入直至超时;
  3. 有的运动员误认为要读入全部数目后才会出口;实际上可以算截止一个景后再度念入下一个状况计算;
  4. 连片上一些,其中以生出有选手用开始了例如char a[105][1600];的数组。在内存限制范围外开数组没问题,但是未可知以main()等函数中开始这么好之数组;详见C/C++堆栈空间分配;
  5. 对接上某些,其中以产生一对运动员开始了大小刚好也1000底数组;实际上是针对字符串的积存理解有过错,字符串需要格外存储一个完符’\0’,因此造成越界访问内存;
  6. 起选手用了C++的string类,但心疼基本功不扎实,存在错误使用;
  7. 出选手一开始交的代码中起了“Please input …”这样的出口,导致WA;
  8. 产生选手将==写成了=(比如if(a==1)成了if(a=1)),导致循环不完直至TLE。

参考思路

得选用埃氏筛法(Sieve of Eratosthenes)、欧拉筛法(Sieve of
Euler)来举行先处理,之后便好直接出口。
注意先计算产生第 100000 只素数是 1299709 ,所以记录数组只要开始及 MaxN
,但标志数组要开到 MaxP 。
时间复杂度 \(O(NloglogN)\) 或 \(O(N)\) 。

B. Zyj 消极比赛

参考代码

标程使用了埃氏筛法:

#include <stdio.h>
#include <math.h>

int n,cnt;
int notprime[10000010];
int prime[5000010];

int main(void)
{
    for (int i=2;i<=sqrt(10000000)+1;++i)
        if (!notprime[i])
            for (int j=2*i;j<=10000000;j+=i)
                notprime[j]=1;
    for (int i=2;i<=10000000;++i)
        if (!notprime[i])
        {
            ++cnt;
            prime[cnt]=i;
        }
    while (~scanf("%d",&n))
        printf("%d\n",prime[n]);

    return 0;
}

ZYJ 的欧拉筛解:

#include <stdio.h>
#include <string.h>

const int MaxN = 1E5;
const int MaxP = 1299709;

int primes[MaxN + 1], cnt;
char isPrime[MaxP + 1];

void init() {
    memset(isPrime, 0xff, sizeof(isPrime));
    for (int i = 2; i <= MaxP; ++i) {
        if (isPrime[i]) {
            primes[++cnt] = i;
        }
        for (int j = 1; j <= cnt && i * primes[j] <= MaxP; ++j) {
            isPrime[i * primes[j]] = 0;
            if (!(i % primes[j])) {
                break;
            }
        }
    }
}

int main() {
    int N;
    init();
    while (~scanf("%d", &N)) {
        printf("%d\n", primes[N]);
    }
    return 0;
}

摸底及计院方面让的凡 cin/cout 的输入输出方法,由于某出题事故造成
cin/cout
会被卡超时,公平起见放松了数量;进而导致优化的摸索除法可以险过(过滤偶数、循环外开方、用时算),时间复杂度
\(O(N \sqrt{N})\) :

#include <stdio.h>
#include <math.h>

const int MaxN = 1E5;

int cnt = 1, primes[MaxN + 1] = {-1, 2};

int isPrime(const int& n) {
    int q = (int)sqrt(n) + 1;
    for (int i = 2; i < q; ++i) {
        if (!(n % i)) {
            return 0;
        }
    }
    return 1;
}

int getPrime(const int& n) {
    if (cnt < n) {
        for (int i = primes[cnt] + 1; cnt < n; ++i) {
            if ((n & 1) && isPrime(i)) {
                primes[++cnt] = i;
            }
        }
    }
    return primes[n];
}

int main() {
    int N;
    while (~scanf("%d", &N)) {
        printf("%d\n", getPrime(N));
    }
    return 0;
}

Problem Description

ACM 比赛剩下最后 10 分钟,其他人都已经办好东西准备撤离,Zyj
才由梦被醒来来。
Zyj 可以望有着其他人的过题情况,他愿意收获的名次在 a 到 b
之间,问出几种而选取的方案?
(假设其他人的提交时就是加上罚时为早于 Zyj 的交付,毕竟剩下 10 分钟了还)

B. 数发票

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)。
生一行也 Zyj 解决各级道题需要的秒数 \(0\leq
t_i < 999\)。
下面 n 行为每个人各道题的经情景,1 也都由此,0 为未通过。

Description

cgy 组织了某外出活动准备及院报销,学院被了他迟早之旅费报销金额。而
cgy
平时是一个分外重集公交车发票底丁,他的当下有过多张不同面值的发票,现在客想计算最少要稍微张发票可以恰好达到报销金额。
cgy
忙在整理这些发票,于是把此任务交给了伙同飞往的您,你待精心算否则就算用不交出门的交通费了。

Output

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

Input

输入第一执行是一个正整数 T
表示数据组数。接下来是差不多组数据,每组数据第一实践是正整数 n ,分别表示 cgy
有 n 种面值的发票(每种都来好多张),接下去一行来 n
个由空格隔开的正整数,表示这 n 种面值的大小,再下一行是一个正整数 x
表示报销金额(T,x<=1000; n<=100)。

Sample Input

1
4 1 0 2
300 300 300 300
0 0 0 1

Output

对每一样组数据,输出能聚集一起报销金额的尽少之发票张数,如果未克正好凑齐则输出
-1 。

Sample Output

Case #1: 6

Sample Input

2
3
1 3 5
11
2
3 5
7

Hint

样例解释:
Zyj 必须做出至少 2 题,又因每个题的解题时间吧 300 秒就 5 分钟,Zyj
也只好开尽多 2 题,
用 Zyj 做简单修出 \(C_4^2 = 6\)
种方案。

Sample Output

3
-1

解题思路

  • 初愈就书是告组合数。但是你产生没发出思了怎么能够因此求组合数的计来开也?
  • 尚记呢?初赛这道题没有指向Zyj做每题作出限制。也刚因为这样,Zyj无论做啊一样写还是相当价格的,所以于无序聚集,我们得求组合数。
  • 而是此间还类似实际情况,Zyj做每一样书写的年华还是无同等的。有或立马道题做了,剩下的写就从来不工夫做了。由于剩下的日少于,这是只求满足特定条件的子集的题目。
  • 克免可知就此枚举的方式也?
    • 选择同道题,根据剩下的时日再次摘同志题,重复下去,总能够把有情况列举出。
    • 不过若想什么,一个尺寸为\(m\)的集合,它的非空子集有 $2^m-1
      $单;
    • 一个休小心您恐怕用 \(O(2^m)\) 到甚至 \(O(m!)\)
      (姿势不对时)的复杂度把装有可行子集都枚举出来。
  • 枚举太暴力了,我们好记忆化搜索。
    • 咱俩定义一个数组 dp[i][j][t] (\(j\leq i\))来代表在共有 \(i\) 道题,Zyj睡醒后剩下 \(t\) 时间的景象下,Zyj做 \(j\) 题的方案往往。
    • 眼看,对于任意 \(1\leq i\leq
      26\), \(0\leq t\leq
      600\) (10分钟=600秒), dp[i][0][t]=1
      恒建立,均只是算1种植情形。
    • 设 c[i] 代表Zyj做第 \(i\)
      题所待的流年,显然, dp[i][i][t] =
      dp[i-1][i-1][t-c[i]];
    • 而Zyj做 \(0<j<i\)
      题时(dp[i][j][t]),不做第 \(i\) 题的方案往往为
      dp[i-1][j][t],做第 \(i\) 题并于头里的题选做 \(j-1\) 题的方案往往为
      dp[i-1][j-1][t-c[i]]。
    • 综上,我们得汲取 dp[i][j][t] = { dp[i-1][j][t] +
      dp[i-1][j-1][t-c[i]], if \(j\leq i\) }, { 0, if j > i },
      { 1, if j = 0 }。
  • 时间复杂度 \(O(300m^2)\);空间复杂度 \(O(600m^2)\),用滚动数组优化及 \(O(600m)=15600\)。

Hint

样例解释:
先是组数据中 11=5+5+1=5+3+3 ,最少要用 3 张
其次组数中任多少张都聚集不齐 7 元,输出 -1

参照代码

#include <stdio.h>
#include <string.h>

const int MaxTime = 600;
int m, n, a, b;
int dp[27][601];// dp[j][t]代表Zyj在t时间内做j题
int solveCount[27];// solveCount[i] 记录其他人做i题的人数

void init() {
    memset(dp, 0x0, sizeof(dp));
    for (int iterTime = 0; iterTime <= MaxTime; ++iterTime)
        dp[0][iterTime] = 1;
    memset(solveCount, 0x0, sizeof(solveCount));
}

void prepare() {
    int costTime;// 读入Zyj做每一题所需的时间
    for (int iterProb = 1; iterProb <= m; ++iterProb) {
        scanf("%d", &costTime);
        // j=0 的情况不需要处理,已经初始化好了
        // 由于使用了滚动数组,从大到小更新
        for (int iterSolv = iterProb; iterSolv > 0; --iterSolv)
            // 直接从Zyj解该题所需时间考虑,剩下时间小于该时间的话Zyj也解不出来
            for (int iterTime = costTime; iterTime <= MaxTime; ++iterTime)
                dp[iterSolv][iterTime] += dp[iterSolv - 1][iterTime - costTime];
    }
}

void readSolves() {
    // 读入n个人的做题情况
    for (int iterPerson = 0; iterPerson < n; ++iterPerson) {
        int acc = 0, solvedTag;// acc用于累加每个人做题总数,solvedTag表示是否解题
        for (int iterProb = 0; iterProb < m; ++iterProb) {
            scanf("%d", &solvedTag);
            acc += solvedTag;
        }
        // 累加总共做出acc道题的人数
        ++solveCount[acc];
    }
}

void read() {
    scanf("%d%d%d%d", &m, &n, &a, &b);
    prepare();
    readSolves();
}

int work() {
    // rank代表Zyj做i题以上能拿的名次
    // Zyj有拿第一的可能,但也一定是同题数的最后一名
    int rank = 1, result = 0;
    // 从全做m题开始遍历到只做1题
    for (int iterSolv = m; iterSolv > 0; --iterSolv) {
        rank += solveCount[iterSolv];
        if (a < rank && rank < b)
            result += dp[iterSolv][MaxTime];
    }
    // 若做0题,则与其他做0题的人并列排名
    if (a < rank && rank < b)
        result += dp[0][MaxTime];
    return result;
}

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;
}

题材大意

有 \(N\) 种物品与一个容量为 \(X\)
的背包,每种物品都发生无限件可以动用。若在一样种方案使得刚刚放满背包,求这种方案受到所运用物品的极小件数。

C. 星界游神 llm

参考思路

动态规划,完全背包问题变种,时间复杂度 \(O(NX)\) 等。
参考《背包九说》。

Problem Description

L2m
向星界游神学艺,星界游神教会他平种技术后大笑“后继有人”后溘然去世。于是
L2m 成了新的星界游神。
L2m 比较大,可以搜集红蓝绿三种植调和之音。但是本的星界游神比较弱,教受
L2m 的技术要消耗同等数量之调停的音才能够起。
Zyj 就想掌握,L2m 最多克发小坏技术,好于 L2m 技能用光后败他。

参考代码

标程:

#include <stdio.h>
#include <string.h>

int kase,n,x,c[1010];
int dp[1010];

int main(void)
{
    scanf("%d",&kase);
    while (kase--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for (int i=0;i<n;++i)
            scanf("%d",&c[i]);
        scanf("%d",&x);
        for (int i=0;i<=x;++i)
            for (int j=0;j<n;++j)
                if (i>c[j] && dp[i-c[j]])
                {
                    if (!dp[i])
                        dp[i]=dp[i-c[j]]+1;
                    else
                        dp[i]=dp[i-c[j]]+1<dp[i]?dp[i-c[j]]+1:dp[i];
                }
                else if (i==c[j])
                    dp[i]=1;
        if (dp[x])
            printf("%d\n",dp[x]);
        else
            printf("%d\n",-1);
    }

    return 0;
}

ZYJ:

#include <stdio.h>

inline void getMin(int& a, const int b) {
    if (a > b) a = b;
}

const int INF = 0x3f3f3f3f;
const int MAXN = 101;
const int MAXX = 1010;

int N, amount;
int cost[MAXN];
int dp[MAXX];

void read() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", cost + i);
    }
    scanf("%d", &amount);
}

void work() {
    dp[0] = 0;
    for (int i = 1; i <= amount; ++i) {
        int tmp = INF;
        for (int j = 0; j < N; ++j) {
            if (cost[j] <= i) {
                getMin(tmp, dp[i - cost[j]]);
            }
        }
        dp[i] = tmp + 1;
    }
    printf("%d\n", dp[amount] >= INF ? -1 : dp[amount]);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        read();
        work();
    }
    return 0;
}

Input

首先尽就出一个正整数 T (\(T\leq
1000\)),代表了 T 个情形。
联网下去的 T 行,分别是三个整数 \(0<R,B,G<10^9\),代表大佬 L2m
所具有的吉、蓝、绿三种调和之音。

C. ljc 吃糖

Output

求你对此各种情况输出大佬能来多少坏技术。

Description

ljc
喜欢吃甜,每一样颗糖会让他供一个单位的脑能量。对于每道题,他起码要有
m1 能才见面设想去举行,且 AC 这道题用吃 m2 能量(即 ljc 能量数超过等于
m1 时才能够去 AC 这道题,AC 完成后 ljc 剩余(当前能值-m2)能量)。
本 ljc 的上马能量也 n,比赛题目数为 k,问若 ljc 想使 AK
(All-Killed,即 AC 所有问题),则他起码要准备稍颗糖?

Sample Input

1
1 3 2

Input

第一尽输入一个正整数 T 表示数据组数,每组第 1 行两单数 n, k,接下去 k
行为简单只正整数 m1, m2。
保证有数据 \(T, n, k, m1, m2 \leq
1000\),且 \(m1 \geq m2\) 。

Sample Output

1

Output

每组数据占一执行,输出 ljc 至少要准备的糖的多少。

解题思路

  • 马上是2015年广东省强原题,我改变了下题面作为签到题放上来啦。
  • 以要耗费同等数量的疏通的音,所以三只变量之间在制约,释放技能次数在三者的极其小值。
  • 央最好小值应该格外好要吧,1. if-else; 2.
    原则表达式(a<b)?(a<c?a:c):(b<c?b:c); 3.
    使用min函数std::min(a,b); 4.
    自己写单min函数int min(int a,int b){return a<b?a:b;}
  • 光阴复杂度:O(1)

    #include
    #include

    using std::min;

    int main() {

    int T, R, B, G;
    scanf("%d", &T);
    while (~scanf("%d%d%d", &R, &B, &G)) {
        printf("%d\n", min(min(R, B), G));
    }
    return 0;
    

    }

Sample Input

1
0 8
4 2
6 4
8 6
10 8
12 10
14 12
16 14
18 16

比赛提交代码中发觉的题目

  1. 纵横代码了..把别的问题的代码到高达来了..;
  2. 而且提交了exe、txt上来..;
  3. 恶意提交exe,当自身怀念打开源码看交了呀鬼时,程序卡了好久..;
  4. 付的代码中富含system("pause");,导致编译错误or超时(大概是为此VC6.0写的?我建议选手们除了写作业和试验他不要用VC6.0);
  5. 对R,G,B三单数字开奇怪的加权or除法,没看明白为什么而这样做;
  6. 思将计结果保存后再也一次性输出..结果保存之尚非对准;还有输出漏了一个for(i=1;i<T;i++);呃..再强调平等合,我们是可计算截止一个情形后随即输出的;
  7. 出口的上忘记换行。你想什么,比如你如果分别出口1暨2,结果而输出了12,能平等吗;
  8. 发出选手把富有情况的答案尽加起了才输出,啊,咋回事啊,是自我之题面阅读性差嘛QAQ

Sample Output

74

D. Oyk 剪纸

Hint

ljc 做题的次第可以随心所欲排列,顺序不同, AK 所欲之糖数不必然同。
若是一旦因此到排序,你可调用 C 语言的 qsort 函数或者 C++ 的 sort 函数。

Problem Description

Oyk 又跟 Zlm 剪纸了。因为过去底剪纸都是一个倾向的,他们操纵更换个道。
拿同摆矩形纸分割为 a*b 的网格,每次可推去 n 个格子以内组成的矩形。
Oyk 希望能够剪到结尾一个格子,那么他当先剪还是后剪?
图片 1

只要 n=5 时,下列方案遭 1,2,5 为有效方案,3 不是(因为其不是独矩形),4
也未是(因为由 6>5 单格子组成)
瞩目,剪了事后要纸断开了,可以任选一部分推,如同它们并未断开一样,只是不容许而剪到中的大多个组成部分;剪下的组成部分即使丢弃了,不再动。

题材大意

于得一名目繁多几何单任务,每个任务都出一个先验条件 precondition 和形成消耗
cost ,现在具备有限的非可再生资源数量 N
,问尽少用续多少资源才会得所有任务。

该问题是“给定不可续资源,问尽多能做到哪些任务”的变种,难度持平。

Input

输入有多组(少于1000组)数据,处理到文件尾。每行有三个数字,a,b和
n(均为小于10000之正整数),由空格隔开。

参照思路

贪婪算法。时间复杂度 \(O(klogk)\)

若是当前最为老可用能量也 N ,任务队列为 prob[] ,如果一个职责 \(prob_i\) 不可知被成功,一定是它的先验需求
\(prob_i.m1 > N\) ,否则由
\(m1 \leq m2\)
一定立,任何一个任务还好于增选成功。

再度设存在个别独任务 a 和 b 能够以梯次完成,那么势必要是 \(a.m2 + b.m1 < b.m2 + a.m1\)
,因为事先形成的天职会预先耗费能量,若前方任务消耗得极度多,则会促成未满足后面任务之先验条件,进而需要持续地补充能量。如果同多样任务还能够满足这无异于谱,就可以尽量少地填补能量,使得能量利用效率最大化。因此我们得因这等同思维为任务排序。
愈吧可转正为 \(a.m1 – a.m2 > b.m1 –
b.m2\) 即针对差值排序,思想为是相仿之。

Output

本着每个样例。输出 1 如果当先走,否则输出 2。

参照代码

并未找到标程,以下由 ZYJ 提供:

#include <stdio.h>
#include <algorithm>

using std::sort;

const int MaxN = 1000;

struct Problem {
    int precond, cost;
    int priority;
    bool operator<(const Problem& cmp) const {
        return priority > cmp.priority;
    }
} prob[MaxN];

int n, k;

void read() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; ++i) {
        scanf("%d%d", &prob[i].precond, &prob[i].cost);
        prob[i].priority = prob[i].precond - prob[i].cost;
    }
}

void work() {
    sort(prob, prob + k);
    int res = 0;
    for (int i = 0; i < k; ++i) {
        if (n >= prob[i].precond) {
            n -= prob[i].cost;
        } else {
            res += prob[i].precond - n;
            n = prob[i].precond - prob[i].cost;
        }
    }
    printf("%d\n", res);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        read();
        work();
    }
    return 0;
}

Sample Input

1 3 1
1 3 3

D. 姓名字母排列

Sample Output

1
1

Description

自古以来,如果安列一客无序名单是一个装有争议性、颇为劳动的题材。通常的做法是准姓名拼音的英文字母排字典序。
某某平等上 Zyj
突发奇想,能不克把有人数的名拼在一起成为一个差,并且是串在享有拼接方案受到字典序是极小之吗?比如有三单人口之名字:zyh、zy、zyj,显然会出以下六种组成(加入空格是便民阅读,实际排列不应当空格):

zyh zy zyj
zyh zyj zy
zy zyh zyj
zy zyj zyh
zyj zyh zy
zyj zy zyh

众目睽睽只有亚栽 zyhzyjzy 是所有方案面临字典序最小之。
现在于您同样卖榜,你会招来有此最小方案也?

Hint

1 3 1 中,不管剪哪一个格子,总会剩下零星个,Zlm 再推一个剩余一个,Oyk
能剪到最后一个。
1 3 3 中,Oyk 可以一样不善把整个纸剪了,Oyk 还是会剪到最终一个。

Input

第一实施输入一个正整数 \(N < 10^6\)
代表名字数量。
接下来 \(N\)
行,每行输入一个一味含小写字母的字符串(当然也未分包空格),代表每个人的名。
保证一个人的名字最老尺寸不超 20 ,保证拥有人数名字长度的总和小于 \(10^6\) 。

解题思路

  • 找规律题,但本身无见面。于是还要让Oyk教了自我平不良剪纸….
  • Oyk:推荐先琢磨的藏问题:
    • 一个圆桌上加大硬币,先放开满(剩余空间不可知更容纳)为大,先手怎么放才能够赢;
    • 变种:一个直径d圆桌放直径p圆盘,先放满为借助,问先手会免可知获胜;
    • 同样维剪纸:一长长纸带划为n格;一条环形纸带划为n格;
  • 率先观察任意大小的矩形网格纸,知道不管先手剪去啊部分,后手总能够依据对称性剪去划一的一对;如果先手能够先挖掉矩形纸的中游一块,而让剩下的纸仍然具有中心对称的特性,则获了继手自然胜局势(注意不连续的张不可知以剪,并要剪小矩形)。
  • 由对称性的在,我们组织最小不同例子,分别是边长为\(1\times 1\)、\(1\times 2\)、\(2\times 2\)的矩形纸:
    • 事先证实其是最好小不同例:
      1. 对于\(1\times
        1\)的情形,先手总是青出于蓝。在限的两侧同时加上一行要同等排不影响对称性,在无尽的单侧添加会由于针对称性而变化吗外两种情景;
      2. 对于\(1\times
        2\)的状况,先手只能全部以完才获胜。在无尽的两侧同时丰富一行要同排列不影响对称性,在边的单侧添加会由于针对称性而转变也其它两种植状况;
      3. 对于\(2\times
        2\)的图景,先手只能全部以完才获胜。在边的两侧同时添加一行要一致排列非影响对称性,在边的单侧添加会由于针对称性而生成也其他两栽情形;
      4. 不去一般性,考察\(2\times
        1\)的状况,发现旋转后及\(1\times
        2\)的状态等,不欲另外考虑。
    • 对此三单不同情况的等价类,边长的奇偶性相同,因此得出三栽先手自然胜策略:同也奇取1,同也突发性取4,一奇一偶取2;
    • 明显,如果用获得之极致少格子数不盖N的话,先手无法占先获对如局势,而后手总能够当率先商家补一起获取对如局势所急需的格子,从而获得胜利。
  • 小结:根据两止长奇偶性考察N的轻重缓急。
  • 时复杂度:O(1)

Output

输出名字排列拼接方案,要于所有中方案受到满足字典序最小。

参考代码

#include <stdio.h>

int main() {
    int a, b, n;
    while (~scanf("%d%d%d", &a, &b, &n))
        puts(4 >> (a % 2 + b % 2) > n ? "2" : "1");
    return 0;
}

Sample Input

3
hello
world
zyj

E. Zyj 穿越到太古

Sample Output

helloworldzyj

Problem Description

Zyj 又消极比赛了,这次他吃 SCNU
的大佬们追杀穿越到了史前。他改成了古希腊的一个将,但是他的队伍给 Hyr
带领 SCNU 的大佬们围住在山上。眼看突破无望,但是 Zyj
军队里之官兵又休愿意投降,就想为老殉职。但是 Zyj
就无甘于了。他想念:宝宝心里苦啊,不就是赛的下睡觉个觉嘛。于是他想发出一个办法给好躲过制裁。
将军队里面剩余的有所人数从 1 到 N 开始编号,每次数 M 个人,从 1
开始屡屡。被一再到之不胜人以老殉职。然后下一个总人口前仆后继于 1 开始频繁。Zyj
要逃避就只好成为最终一个献身的人头,这样他就算会乖乖投降了。请你告知 Zyj
要挑编号是多少才能够避开制裁。
按部就班有 3 私房,编号 1,2,3。每次数 2 单,第一单殉职:2。剩下 1,3。第 2
只殉职:1。只剩下3。于是 zyj 一始发摘编号 3 可以规避。

Hint

一经要是用到排序,你可调用 C 语言的 qsort 函数或者 C++ 的 sort 函数。

Input

发差不多组数据,数据不超 100
组,输入到文件尾了。每组数据并一实行两单数,第一只数 N
代表人的总额,第二独数 M 代表每次数略个人(\(0\leq N\leq 1000\),\(0\leq M\leq 1000000000\))。

问题大意

原来原题:《最酷累》,1998 年 NOIP 全国联赛提高组,codevs 1860;
原题:《ZLM 的扑克牌》,2015 年华南师范 ACM 新生赛(逃;
加若干个小写的英文字母串,求平栽方案使得所有串按该方案的顺序相邻首尾拼接后,得到的初串在具有方案遭字典序最小。

Output

输出一行,一个整数代表 zyj 一始发要挑谁号码才能够在在。

参考思路

贪婪算法,需要先严格弱序化(strict weak ordering)。

  1. 单串字典序不控制拼接串字典序。如果就英文字母串的属性来说,显然每个串都发一个“A-Za-z”的“字典序”,既然发生一个约定成俗的字典序,它们中间本是于的,也足以排序;但是连无可知印证按照字典序排好之错拼接起来,得到的初串在享有拼接方案面临,它吗是本字典序的太小元或特大元。很爱找到反例:
    bacd 和 b 可以凑合成 bacdb 和 bbacd 两种植, 虽然 b 是原串集合 {b,
    bacd} 中之卓绝小元,但 bbacd 不是拼接串集合 {bacdb, bbacd}
    的无比小元,因此 b 不可知消除在 bacd 的前。
  2. 起新涉嫌。基于上面的构思,很容易想到以原串集合任意元素两点滴合接比较。对于任意串
    A 和 B ,大概发生 3 栽情况:

    • A 和 B 在初始处没有公共子串。直接以字典序排就哼了,比如 AB <
      BA 显然会说了算发 A < B ;
    • A 和 B 在起来处有一个缺的公共子串。这时 A 可以讲为 PQ 而 B
      可以解释为 PR ,对于 Q 和 R 的比较而回了第一种植状况;
    • A 是 B 在起的子串,或掉。假如是前者,则 B 可以解释为 AP
      ,对 AAP 和 APA 的比较实在是第二种状况,对 A 和 P
      的于。但倘若 A 和 P 又当始发处来公共子串,甚至是循环的为?比如
      A 暨 B ,而 B = AA..AP 甚至 B = AA..AQR 且 A = QSQS..QS 呢?这时
      A 比较缺少,先上一起到 B 的长度,有或是 A/P 甚至是 S/Q 、 S/R 、
      Q/R 的比较,取决于循环节的尺寸。

Sample Input

5 3
4 6

参考代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const int MaxCount = 1E6 + 1;
const int MaxLength = 20 + 1;

int N;
char names[MaxCount][MaxLength] = {0};

void read() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%s", names[i]);
    }
}

int namesCmp(const void* a, const void* b) {
    static char p[MaxLength << 1], q[MaxLength << 1];
    strcat(strcpy(p, (char*)a), (char*)b);
    strcat(strcpy(q, (char*)b), (char*)a);
    return strcmp(p, q);
}

void work() {
    qsort(names, N, MaxLength, namesCmp);
    for (int i = 0; i < N; ++i) {
        printf("%s", names[i]);
    }
    putchar('\n');
}

int main() {
    read();
    work();
    return 0;
}

Sample Output

4
3

E. Substring

解题思路

  • 不是自家来之写,只是自我去的多寡。数据如下:

    500 999999999
    500 999999797
    500 999999792
    500 643242600
    500 715619198
    491 999999999
    499 999999797
    503 999999792
    509 643242600
    521 715619198
    500 1
    523 1
    
  • 可能大家还在教科书上了循环数数之法,但当时是雅缓慢的,复杂度高及\(O(NM)\),妥妥的TLE。

  • 理所当然,如果你无死心,一定要学循环数数,那吧堪的,因为只有\(N\)个人,当\(M>N\)时,数到结尾一个人数单会再由第一私房开始屡屡由,不容许频发第\(M\)个人来,所以循环数数之长应该是\(M\%N\)。时间复杂度\(O(\sum^{N}_{i=2}M\%i)=o(N^2)\)。
  • 自道自之写是得良心的,所以推广了了\(O(N^2)\)的算法,因此用一个数组标记每个人,每次你总算有那个人(数组元素的下标)之后,直接拿数组后面的素于前方更换就相当给删掉那个人了,也便是复标号。无论是int数组前换,还是组织体数组重标号,还是vector删除元素,都是\(O(N^2)\)的时光复杂度。
  • 可惜场上未曾多少同学想到如果\(M\%N\),几乎都一直循环\(M\)的尺寸。我确实不知底原委在乌,是C语言课上的无限次了啊?请你们当团结之处理器及测试一下,你的计算机跑\(10^9\)长度的巡回需要多长时间。
  • 正解:
    • 假设当前数号到\(num\),好的外已经出局了,原来的顺序\(num+1\)个人成了新的次\(num\)个人;
    • 倘自新的先后\(num\)个人开始于后反复发第\(M\)个人出局,而总人数只有\(N\)个人,所以下同样不成会数号到\(num’=(num+M)\%N\),第\(num’\)个人出局,类推。
    • 从而获一个递推公式:\(R_i=(R_{i-1}+M)\%N\),当\(i=N\)时,总人数就剩下一个丁,\(R_N\)就是Zyj想只要的数码。
  • 时间复杂度:\(O(N)\)

Description

一个字符串的子串表示原字符串中一致段连接的一些。例如,字符串”121″的子串总共有六个,它们各自是”1″(前一个),”2″,”1″(后一个),”12″,”21″和”121″。但”11″不是”121″的子串,因为个别个’1’在原串中不连续。我们以为空串也非是子串。
现受您一个独含有’0’和’1’两种植字符的字符串,问她含相同’0’和’1’的子串有几乎单。例如,字符串”0101″中符合条件的子串有4只。它们分别是”01″(前一个),”10″,”01″(后一个),”0101″。

参照代码

#include <stdio.h>

int main() {
    int n, m, i, s = 0;

    while (~scanf("%d%d", &n, &m)) {
        s = 0;
        for (i = 2; i <= n; i++) {
            s = (s + m) % i;
        }
        printf("%d\n", s + 1);
    }
    return 0;
}

Input

输⼊只发一行,为加的字符串。字符串长度不超越100,且仅含’0’和’1’两栽字符。

比赛提交代码中发现的题目

  1. 飞了长短为\(M\)的轮回,不再多说;
  2. 当数据还会输入一个整数\(T\),但是此地是一旦读到EOF的;
  3. 发生同学因此了链表..但是链表不克好随机询问的话,还是模拟循环数数而曾经;

Output

输出为一个屡屡,表示符合条件的子串的个数。注意最后出一个换行符。

F. 贪吃蛇

Sample Input

00110011

Problem Description

贪吃蛇是一个万分红的一日游。小蛇每吃少一个食物,就见面长长一格;撞至障碍物或自己,就会终结游戏。
此间拿贪吃蛇的规则有点发改:

  1. 蛇所于世界的增长为 W,高呢 H,坐标为左上角 (1,1) 至右下角 (W,H)。
  2. 刚刚起经常,蛇长度为 1,位于 (1,1) 处,初始方向向东。
  3. 每秒可以遵循下 W 表示发展,A 表示向左,S 表示为下,D
    表示为右侧,或非按照按钮,来准备对蛇进行转向,但只有发生准备的转发和眼前趋势垂直时,转向中。
  4. 列秒在尝转向后,向新势头移动 1
    格(如果转正成功)。如果吃到食物,长度增加 1,否则长度不换。
  5. 世界是环形的,即从右边离开边界会自左边还入,以此类推
  6. 相见至自己,蛇长度恢复为 1,方向、位置不转移。

Sample Output

10

Input

产生差不多组样例,处理到文件截止。每组样例第一行三个数字
W,H,N(0<W,H<500,0<N<100000)
下面 N 行,每行:第一个字符为 WASDNwasdn 之一,字母代表那同样秒的按键,N
代表那无异秒不按键;大写表示吃到食物,小写表示不曾。后面紧接一个空格,然后一个
64 位无符号整数\(a_i\)。

Hint

字符串”00110011″中符合条件的子串分别吗”01″(前一个),”10″,”01″(后一个),”0011″
(前一个),”0110″,”1100″,”1001″,”0011″(后一个),”011001″,”00110011″,共10只。

Output

对每个样例,输出一行,其值为 \(\sum_{t=1}^{N}a_t
\sum_{x=1}^{W}\sum_{y=1}^{H}3^{yW+x}c_{txy} mod
2^{64}\),其中 \(c_{txy}\)
表示第 t 秒 (x,y) 处,有蛇也 1,没有蛇也 0

题目大意

加任意 01 串,求含有相同数量的 ‘0’ 和 ‘1’ 之接连子串有多少个。

Sample Input

3 2 8
a 0
s 0
D 0
N 0
n 0
w 1
s 0
n 1

参照思路

遍历计数。时间复杂度 \(O(L^2)\) 或
\(O(L^3)\) ,其中 \(L = |S|\) 即字符串的长度。
从左到右扫一任何字符串,统计中扫了的 ‘0’ 和 ‘1’
底数据,若数量相等则扫了的子串符合条件,进行添加。
是因为一个字符串的子串有 \(L + (L – 1) +
\ldots + 2 + 1 = \frac{L(L + 1)}{2}\) 个,所以可能只要全套历 \(L\) 次起点, \(1 \ldots (L – i)\) 次终点。

Sample Output

15552

样例解释:
图片 2

输出为 \(1(3^{1\times 3 + 2} + 3^{2\times 3

  • 1} + 3^{2\times 3 + 2}) + 1\times 3^{1\times 3 + 2} mod 2^{64} =
    9234\)

参考代码

\(O(L^3)\) 复杂度的解法:

#include <stdio.h>
#include <string.h>

char str[101];

void read() {
    scanf("%s", str);
}

void work() {
    int len = strlen(str);
    int res = 0;
    for (int i = 0; i < len; ++i) {
        for (int j = i; j < len; ++j) {
            int zeroCnt = 0, oneCnt = 0;
            for (int k = i; k <= j; ++k) {
                str[k] == '0' ? ++zeroCnt : ++oneCnt;
            }
            if (zeroCnt == oneCnt) {
                ++res;
            }
        }
    }
    printf("%d\n", res);
}

int main() {
    read();
    work();
    return 0;
}

\(O(L^2)\)
复杂度的解法只以一念之间,只要您肯怀念:

void work() {
    int len = strlen(str);
    int res = 0;
    for (int i = 0; i < len; ++i) {
        int zeroCnt = 0, oneCnt = 0;
        for (int j = i; j < len; ++j) {
            str[j] == '0' ? ++zeroCnt : ++oneCnt;
            if (zeroCnt == oneCnt) {
                ++res;
            }
        }
    }
    printf("%d\n", res);
}

解题思路

  • 模拟题。直接模拟就哼,没什么特别的技艺。
  • 光阴复杂度:O(玄学)

F. 法特狗

参照代码(出题人的代码)

#include <stdio.h>
#include <stdlib.h>
#include <queue>
int z[500][500], q;
unsigned long long vu[300000]={1};
inline void setp(int x, int y) {
    z[x][y]=q;
}
inline void clrp(int x, int y) {
    z[x][y]=0;
}
inline bool seep(int x, int y) {
    return z[x][y]==q;
}
int main() {
    int w,h,n;
    for (n=1; n<300000; n++) {
        vu[n] = vu[n-1] * 3;
    }
    while (~scanf("%d%d%d",&w,&h,&n)) {
        char c[2];
        unsigned long long val=0, ali, map=vu[w+1];
        q++;
        int x=1, y=1, d='d';
        std::queue<int> L;
        L.push(w+1);
        while (n--) {
            scanf("%s%llu", &c, &ali);
            c[1]=c[0]<'a';
            if(c[1]) c[0]+=32;
            switch (c[0]) {
            case 'd': case 'a':
                if(d=='w' || d=='s') d=c[0]; break;
            case 'w': case 's':
                if(d=='a' || d=='d') d=c[0]; break;
            }
            switch (d) {
            case 'a':
                x--;
                if(x==0) x=w;
                break;
            case 's':
                y++;
                if(y>h) y=1;
                break;
            case 'd':
                x++;
                if(x>w) x=1;
                break;
            case 'w':
                y--;
                if(y==0) y=h;
                break;
            }
            if (c[1]) {
                //got new
            } else {
                int t=L.front()-1;
                L.pop();
                int y=t/w, x=t%w+1;
                clrp(x,y);
                map-=vu[w*y+x];
            }
            if (seep(x,y)) {
                map=0;
                q++;
                std::queue<int>t;
                std::swap(L,t);
            }
            L.push(y*w+x);
            setp(x,y);
            map+=vu[w*y+x];
            val+=ali*map;
        }
        printf ("%llu\n", val);
    }
}

Description

确定性, cgq 因为脸黑而从未失去玩法特狗这无异暂缓游戏,不过他老板 gou4shi1
经常发问他有英灵厉不厉害,为了一劳永逸, cgq
决定写个次为持有英灵打独分叉。
以法特狗里,每张卡牌都对准许正在一个英灵。设 \(n\) 为卡池里有所卡牌的数据, \(m\) 为卡池里产生微微张卡牌 y 使得,英灵 x
的持有属性都不止等于英灵 y 的对应属性(注意, y 可以是 x
本身),则英灵x的评分也 \(\frac{m}{n}\) 。
今认为每个英灵只生四只属性(耐久、敏捷、魔力、幸运),每个属性只出四个阶段(ABCD
, A 最强, D 最弱)。给起一个卡池所有英灵的特性,要求受所有英灵评分。

G. equation

Input

输入第一执是一个整数 n ( \(1 \le n \le
100000\) ),代表卡池里有所卡牌的数目。
接下是 n
行,每行四单深写字母,分别表示每个英灵的坚固、敏捷、魔力、幸运。

Problem Description

叫出一个个系数均非负的多项式\(f(x)\),是否在\(x>0\)使得\(f(x)=1\)?

Output

出口 n 行,每行一个浮点数(小数点后保留少数号),代表每个英灵的评分。

Input

每行一个样例,有差不多只数字(均低于25000,最多精确到6员小数)分别代表各项系数。具体地说,第\(i\)个数字代表\(f\)的\((i-1)\)次方项系数。没有排有之数字系数为0。

Sample Input

4
AAAA
AAAD
CBCD
DDDD

Output

倘发生解则输出解,若有差不多只解则从小到特别出口,精确到四位小数,若无脱输出空行。

Sample Output

1.00
0.75
0.50
0.25

Sample Input

0.5 1

Hint

1.00 = 4/4
0.75 = 3/4
0.50 = 2/4
0.25 = 1/4

Sample Output

0.5000

题目大意

加以若干独物品,每个物品含有四个属性,每个属性又生四栽价值,当且仅当一个物品所有性能的价都自愧不如等于另一个物料,才可以说这个物品比其他一个品。求于随意一个物料,比其的物品数。

Hint

欠输入表示\(f(x)=1x+0.5=1\)解为\(x=0.5\)

参照思路

四维偏序关系(partial ordering relation)计数。

虽然发出四个维度,但出于每一个维度的界定比小,所以状态数片,只有 \(4^4 = 256\)
个,完全可以用标记数组记录转:先预处理发生同样种状态的卡牌有微张,对于各级种卡牌,找来比较它弱的卡牌数量,最后根据卡牌的输入顺序直接计算输出答案。时间复杂度
\(O(256 \times 256 + N)\) 或 \(O(256N)\) 。

L2M 说可以将每个状态加起,时间复杂度 \(O(4
\times 256 + N)\) 。

符数组可以是 ‘D’ – ‘A’ 变基映射成 0 – 3 的季维属性数组,这样盖会发生 5
或 8 个 for
循环;也足以是储存哈希(hash)成四迈入制数的一模一样维状态数组;当然某些同学直接打表算状态吧可,就是发出接触奇怪hhh。

解题思路

  • 二分法。
  • 当各类系数非负,且\(x\geq
    0\)时,\(f(x)\geq
    0\)恒成立且\(f(x)\)在\([0, +\infty)\)上枯燥递增。

    • 如果\(\exists x>0,
      f(x)-1=0\),则\(f(0)-1<0\),即\(f(0)<1\);
    • 观增长不过缓慢的一个出解函数\(f(x)=1\times
      10^{-6}x=0.000001x\)(所给数仅精确到6各项小数),也在\(f(10^6)=1\),取最近底素数\(f(10^6+3)>1\);
    • 综上,我们好以\((0,
      10^6+3)\)区间上第二分来满足\(f(x)=1\)的答案。二分叉精度也\(10^{-6}\)。
  • 当常数件高于或等1,则\(\forall C\geq
    1, \forall x>0, f(x)=g(x)+C>1\)恒成立,此时无解。
  • 当\(f(10^6+3)<1\),说明出现比较\(1\times
    10^{-6}\)更有些的系数,即系数全为0,此时无解。
  • 时复杂度:设\(f(x)\)最多有N项,最坏\(O(N log_2((10^6+3)\times
    1/10^{-6}))=O(40N)\)

轻错点解析

  1. 偏序关系不可比:由于 C/C++
    函数库里的排序方法要求从严弱序,而这里是四维偏序,即随意两单物品
    \(X\) 和 \(Y\) ,当且仅当 \(X.p1 \leq Y.p1\) 且 \(X.p2 \leq Y.p2\) 且 \(X.p3 \leq Y.p3\) 且 \(X.p4 \leq Y.p4\) 都满足时才发生 \(X \preccurlyeq Y\) ,比如 \(ABCD \preccurlyeq AABB\) ,但 \(ABCD\) 和 \(BACD\)
    不可比较。你可以根据偏序关系之定义来好证明一下,总的是匪得以一直开展较排序(comparison
    sort)的,即使 hash 成四向前制数也格外(数字本身为是严格序);
  2. 多少漂移:由于要计算并出口浮点数,部分所以 float
    的同学有或会见逢浮点数数据漂移问题;
  3. 卡牌可还:一张卡牌只恐是鲜的 256 种植状态,卡池里 \(N\)
    张牌肯定有双重的;但结尾却如根据卡牌的输入顺序来输出(即相当于可更而切莫一样);
  4. 反向映射:因为原先的属于性值是 ‘A’ – ‘D’ ,如果依照是顺序映射成 0 – 3
    的语,大概就是是 ‘D’ < ‘A’ 等价于 3 > 0
    ,这样使小心,对属于性值的涉嫌比较而倒着来;如果 0 – 3 代表 ‘D’ – ‘A’
    就甭花就脑细胞了。

参照代码(出题人的代码)

#include <stdio.h>
#include <stdlib.h>
double g[1000007];
int n=0;
double f(double x) {
    double ans=0, leg=1;
    for (int i=0; i<n; i++) {
        ans+=g[i]*leg;
        leg*=x;
    }
    return ans;
}
int main() {
    char c;
    while (~scanf("%lf%c",g+n++,&c)) {
        if(c=='\n') {
            if (g[0]>=1 || f(1000009)<1) puts("");
            else {
                double L=0, R=1000009;
                for (; R-L>1e-6; ) {
                    double M=(L+R)*.5;
                    if (f(M)<1) L=M;
                    else R=M;
                }
                printf("%.4f\n", L);
            }
            n=0;
        }
    }
}

参考代码

标程 1 (\(O(256N)\)):

#include <stdio.h>

const int N = 1e5 + 10;
const int M = 4;
int a0[N], a1[N], a2[N], a3[N];
int b[M][M][M][M];

int main() {
    int n;
    scanf("%d\n", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%c%c%c%c\n", &a0[i], &a1[i], &a2[i], &a3[i]);
        a0[i] = 'D' - a0[i]; a1[i] = 'D' - a1[i]; a2[i] = 'D' - a2[i]; a3[i] = 'D' - a3[i];
        b[a0[i]][a1[i]][a2[i]][a3[i]]++;
    }
    for (int i = 0; i < n; ++i) {
        int ans = 0;
        for (int j0 = 0; j0 <= a0[i]; ++j0)
            for (int j1 = 0; j1 <= a1[i]; ++j1)
                for (int j2 = 0; j2 <= a2[i]; ++j2)
                    for (int j3 = 0; j3 <= a3[i]; ++j3)
                        ans += b[j0][j1][j2][j3];
        printf("%.2f\n", (double)ans/n);
    }
    return 0;
}

标程 2 (\(O(256 \times 256 +
N)\)):

#include <stdio.h>

const int N = 1e5 + 10;
const int M = 4;
int a0[N], a1[N], a2[N], a3[N];
int b[M][M][M][M], c[M][M][M][M];

int main() {
    int n;
    scanf("%d\n", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%c%c%c%c\n", &a0[i], &a1[i], &a2[i], &a3[i]);
        a0[i] = 'D' - a0[i]; a1[i] = 'D' - a1[i]; a2[i] = 'D' - a2[i]; a3[i] = 'D' - a3[i];
        b[a0[i]][a1[i]][a2[i]][a3[i]]++;
    }
    for (int i0 = 0; i0 < M; ++i0)
        for (int i1 = 0; i1 < M; ++i1)
            for (int i2 = 0; i2 < M; ++i2)
                for (int i3 = 0; i3 < M; ++i3)
                    for (int j0 = 0; j0 <= i0; ++j0)
                        for (int j1 = 0; j1 <= i1; ++j1)
                            for (int j2 = 0; j2 <= i2; ++j2)
                                for (int j3 = 0; j3 <= i3; ++j3)
                                    c[i0][i1][i2][i3] += b[j0][j1][j2][j3];
    for (int i = 0; i < n; ++i)
        printf("%.2f\n", (double)c[a0[i]][a1[i]][a2[i]][a3[i]]/n);
    return 0;
}

ZYJ 的季上制标记解法(O\((4 \times 256
\times 256 + N)\),虽然大多了单常反复 4
但即便是自豪地比标程快(骄傲.jpg)):

#include <stdio.h>

int N;
int cardSet[100100];
int cardMap[256];
int leqCount[256];

void addCard(int idx, const char* card) {
    int val = 0;
    for (const char *p = card + 3; p >= card; --p) {
        val <<= 2;
        val |= 'D' - *p;
    }
    cardSet[idx] = val;
    ++cardMap[val];
}

void read() {
    char card[5];
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%s", card);
        addCard(i, card);
    }
}

int leqCard(int a, int b) {
    for (int i = 4; i > 0; --i) {
        if ((a & 3) > (b & 3)) {
            return 0;
        }
        a >>= 2;
        b >>= 2;
    }
    return 1;
}

void work() {
    for (int i = 0; i < 256; ++i) {
        if (cardMap[i]) for (int j = 0; j < 256; ++j) {
            if (cardMap[j] && leqCard(j, i)) {
                leqCount[i] += cardMap[j];
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        printf("%.2lf\n", (double)leqCount[cardSet[i]] / N);
    }
}

int main() {
    read();
    work();
    return 0;
}

01/22/17更新:牛顿迭代套

由于逆天出题人二分叉时尚未设想精度误差,导致有些数额与事实上事实不符。这里让来牛顿迭代解除
注:

  1. 早已跟Mathematica对比正确;
  2. deriv()是近似求导;
  3. 实质上我更赞成被迭代多少糟糕,比如100蹩脚,而未是迭代到指定精度。

    #include
    #include #include

    const int MAXM = 1000003;
    const double Eps = 1e-7;

    int count = 0;
    double coeff[1000007];

    std::pair calc(double x) {

    double func = .0, deriv = .0, p = 1.0;
    for (int i = 0; i < count; ++i) {
        double item = coeff[i] * p;
        func += item;
        deriv += i * item;
        p *= x;
    }
    return std::make_pair(func, deriv);
    

    }

    double func(double x) {

    double res = .0, p = 1.0;
    for (int i = 0; i < count; ++i) {
        res += coeff[i] * p;
        p *= x;
    }
    return res;
    

    }

    double deriv(double x) {

    return (func(x + Eps / 2.) - func(x - Eps / 2.)) / Eps;
    

    }

    inline int test() {

    return coeff[0] < 1 && func(MAXM) > 1;
    

    }

    void work2() {

    if (test()) {
        double x0 = .0, x = 1.0;
        while (fabs(x - x0) > Eps) {
            x0 = x;
            //x = x - (func(x) - 1) / deriv(x);
            std::pair<double, double> newton = calc(x);
            x = x - (newton.first - 1) / newton.second;
        }
        if (x > 0) printf("%.4f", x);
    }
    putchar('\n');
    

    }

    int main() {
    /* freopen(“new_in.txt”, “r+”, stdin);

    freopen("new_out2.txt", "w+", stdout);*/
    char c;
    while (~scanf("%lf%c", &coeff[count++], &c)) {
        if (c != '\n') continue;
        work2();
        count = 0;
    }
    return 0;
    

    }

G. zyj 打印奖状

H. 续时间

Description

zyj
又为受去打印奖状啦!但是学院办公室的打印机实在太辣鸡,经常把奖状文字打歪。为了让学院更换打印机,
zyj
把团结于院得的有奖状都拿出去,用以展示这打印机打出去的奖状到底歪成什么法。为了好表示,
zyj
决定将各国一样张奖状的仿范围中心以及奖状纸张中心的几乎哪里距离列举出,用以表观地展示打印机的误差。
zyj 天天都设打印奖状,日理万机,所以他要而拉他就这职责。

Problem Description

Czj快毕业了,但他还惦记留下于学里,于是找到了SCNU最劲的魔法师Wwj买时。
Wwj觉得他极其愚蠢了,想只要为难他转,就因故了划分身术boom的刹那化为了众多只Wwj。
Ccr经过一番明察暗访,发现\(N\)个Wwj的佛法不同,第\(i\)个Wwj只能给Czj延长\(T_i\)的在校时间,但收费在心情,是心情的\(P_i\)倍,而眼下Wwj的心绪是\(D_i\)。
Hyr经过一番侦探,发现魔法值不自然要是了用了,比如当前Wwj收费\(C\),Czj可以以出\(C * a\%\)的奇珍异宝,来换取对应只有\(T_i * a\%\)的时间。
不怕Czj家财万贯,天天要Lht奶茶喝,也按捺不住如此高昂的费。所以他单带总共价值为M的宝,去寻找Wwj的魔法分身换时间。
Lzp想掌握Czj最多会顺延多添加之在校时间。

Input

zyj
得的奖状数不胜数,所以输入文件包若干组奖状数据。每组奖状数据包含两履行,第一执行是零星个浮点数
a, b(a, b > 0) ,表示奖状的大小;第二履是四独浮点数 x, y, l, w(x, y
>= 0; l, w > 0)
,表示奖状上文字范围左上较量的坐标和文字范围的长和有钱。输入数据保证文字范围势必完全在奖状面积内。输入到文件结尾结束。

Input

第一行为一个恰恰整数\(T<50\),代表有\(T\)种情况。
仲履输入每种状况的\(N\)和\(M\),均是刚整数,\(N\leq 1000\),\(M\leq 10000\)。
接下来\(N\)行,每行有三单刚刚整数,分别是\(T_i\)、\(P_i\)、\(D_i\),均无浮\(100\)。

Output

针对许每一样组奖状数据输出奖状中心和仿区域核心的几乎哪里距离,保留 3 位小数。

Output

对各种情景,输出Czj最酷能延长的岁月,由题意知可能是小数,请保留4个小数。

Sample Input

3.0 4.0
1.0 1.0 1.0 1.0
2.0 2.0
1.0 1.0 1.0 1.0
3.0 3.0
0.0 0.0 3.0 3.0

Sample Input

1
3 10
10 3 2
5 2 2
5 3 2

Sample Output

0.500
0.707
0.000

Sample Output

15

Hint

double 类型的输入输出格式: scanf(“%lf”) / printf(“%f”)
主题数据量大,请以 scanf/printf ,使用 cin/cout 会导致超时

解题思路

  • 自发之书还是良心题。这书是故贪心法做。我理解新生想当缺乏日内想出来要挺难之,定位是中等题(什么给难题?你看上面那片只..正常人会开的?)
  • 自我之题面是发出强调 a% 的,但是我写LaTeX公式时无对准百分号 %
    做转义处理,导致pdf上未曾出示出,影响局部同学没有看懂题,十分对不起。
  • 正解:
    1. 盖财富是一定的,所以富含了使花尽少之代价,买到最好多之货品。想搭了及时点,你就是了解应该要错过算性价比(或单价)(单价及性价比互为倒数);
    2. 只是此的价位计算方法不雷同,因为最后之费是\(P_i\times
      D_i\),所以性价比是\(\frac{T_i}{P_i\times
      D_i}\);
    3. 对具备种类商品的性价比进行排序,优先采购性价比最高(单价低于)的。最后由于足买有数据商品而休欲全买(即允许打
      a%),把剩余的钱数与性价比同样就,就是还能够置办的 a% 数量之货色。
  • 贪得无厌策略证明:
    • 万一当一个管用的贾方案被,存在性价比重新胜似之货品产生盈余(没置办),那么请该性价比更强的商品,而非足够请原方案被相应总价之性价比最低商品,总能够赢得重新多数据的货物。
    • 为此具有购买性价比高商品的一对最优解的总额是大局最优解。

问题大意

吃一定两单矩形,其中多少矩形一定让模仿在怪矩形之中。给出怪矩形的丰富宽,小矩形的左上角顶点坐标和丰富宽,求出片只矩形中心的几乎哪距离。

参考代码(这里运用结构体排序,并因而了C++语法)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>

void generate() {
    FILE *outFile = freopen("in.txt", "w+", stdout);
    int T = rand() % 10 + 11;
    fprintf(outFile, "%d\n", T);
    while (T--) {
        int N = rand() % 1000 + 1;
        int M = rand() % 10000 + 1;
        fprintf(outFile, "%d %d\n", N, M);
        while (N--) {
            int Ti = rand() % 100 + 1;
            int Pi = rand() % 100 + 1;
            int Di = rand() % 100 + 1;
            fprintf(outFile, "%d %d %d\n", Ti, Pi, Di);
        }
    }
}

struct Magic {
    int T, P, D, cost;
    double ratio;

    bool operator<(const Magic &c) const {
        return fabs(ratio - c.ratio) > 1e-7 && ratio < c.ratio;
    }
} magic[1010];

int main() {/*
  generate();
  freopen("in.txt", "r+", stdin);
  freopen("out.txt", "w+", stdout);*/
    int T, N, M;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d\n", &N, &M);
        for (size_t i = 0; i < N; ++i) {
            int Ti, Pi, Di;
            scanf("%d%d%d\n", &magic[i].T, &magic[i].P, &magic[i].D);
            magic[i].cost = magic[i].P * magic[i].D;
            magic[i].ratio = (double) magic[i].T / magic[i].cost;
        }
        std::sort(magic, magic + N);
        double res = 0.;
        for (size_t i = N - 1; i >= 0; --i)
            if (M > magic[i].cost) {
                M -= magic[i].cost;
                res += magic[i].T;
            } else {
                res += M * magic[i].ratio;
                M = 0;
                break;
            }
        printf("%.4f\n", res);
    }
    return 0;
}

参照思路

签证到开,公式乱整就尽。

出题及解题总结

轻错点解析

  1. 眼看书没有说了解凡平行于 x 轴的丰富,是平于 y
    轴的松,举报出题人;
  2. 即书没有说亮 a / x / l 一定对承诺同 b / y / w
    一定对应,举报出题人;
  3. 输入输出:如果因此 scanf / printf 作输入输出,前者要指定具体是 %f /
    %lf / %Lf 的哪位,而后者的 float / double 都是用 %f 输出,当然 long
    double 还是用 %Lf ;
  4. 数据漂移:由于要算并出口浮点数,部分为此 float
    的同桌来或会见赶上浮点数数据漂移问题;

自己校ACM吃枣药丸

参照代码

#include <stdio.h>
#include <math.h>

double a, b;
double x, y, width, height;

inline double dist(double x1, double y1, double x2, double y2) {
    return sqrt(pow(x1 - x2, 2.f) + pow(y1 - y2, 2.f));
}

int main() {
    while (~scanf("%lf%lf", &a, &b)) {
        scanf("%lf%lf%lf%lf", &x, &y, &width, &height);
        double res = dist(a / 2.f, b / 2.f, x + width / 2.f, y + height / 2.f);
        printf("%.3f\n", res);
    }
    return 0;
}

建议、意见、吐槽

欢迎在人世评论区提出问题,12月内本身都见面回升and更新。

本文基于图片 3知共享署名-非商业性使用-相同方式同享
4.0
国际许可协议颁发,欢迎引用、转载或演绎,但是要保留本文的署名BlackStorm和本文链接http://www.cnblogs.com/BlackStorm/p/SCNUCPC\_2016\_For\_Freshman\_Final\_Solution.html,且未经许可不克用于商业目的。如发疑点还是授权协商请暨本人联系。

H. CG 之争

Description

众目睽睽, cgq 和 cgy 名字中单单差一个许。为了保住 CG 这个名称, cgq
作为擂主给 cgy 出了单难题:要是 cgy 能以 1s 内报出 \(\frac{(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}}{\sqrt{5}}\)
,就会获一致不善正式挑战 cgq 的火候。 cgy 好菜呀,而且他的 1s
十分宝贵,于是求助于你,请您帮忙他告来之累。

Input

大多组数,每一样组一行是 cgq 给有底一个正整数 n
,输入到文件结尾结束(\(n \leq
80\))。

Output

对诺为各级一样组 n 求出 \(\frac{(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}}{\sqrt{5}}\)
,保留 3 位小数。

Sample Input

1
2

Sample Output

1.000
1.000

Hint

double 和 long double 精度都有数,求 80 次方会满怀不生。

问题大意

求斐波那契数列的第 \(k\) 项值。

参考思路

打表 or 记忆化递推。递推的时复杂度 \(O(80)\) ,还有 \(O(N)\) 的输入输出。

因浮点数类型存不生 80 次方这么老的数(存储员数不足够 or
表示精度不够),可以查找一下题材让闹之公式,容易理解凡是斐波那么契数列的通项公式;也得找一下
C/C++ 语言是怎么处理大数计算、高精度科学计算的,用高精算法求 80
次方也足以。

善错点解析

  1. 封存 3
    位小数是骗而的。因为斐波那契是单整数屡排,就算用公式算,考虑上精度损失相当题材后拿走的尚是单整数;
  2. 无作记忆化处理的递归是会过的。递归空间是一样株二交叉树,不发记忆化处理的话语不过酷出
    80 层,复杂度高及 O(2^N) 指数爆炸算到地老天荒;
  3. 非作记忆化处理的递推是唯恐会见过的。因为发多组输入数据呀,你的复杂度是
    O(80T) 哦;
  4. 之所以浮点数类型递推到最后精度不够是会 WA
    的。有些同学便举行了优化,从奇怪之地方拿到了第 79 、 80
    桩一直用字符串输出, emmm… 也是好的。

参考代码

#include <stdio.h>

#define LL long long
#define lld "%lld"

const int MaxN = 80;

LL fib[MaxN + 1] = {0, 1};

inline void init() {
    for (int i = 2; i <= MaxN; ++i) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}

int main() {
    int N;
    init();
    while (~scanf("%d", &N)) {
        printf(lld".000\n", fib[N]);
    }
    return 0;
}

I. 人形质量单位

Description

每个人之品质可能同样,或许不同。于是乎,如果盖人们的体重作为一个计量单位,那么可以产生略种不同之组合为?
设有 n(\(1 \leq n \leq 10\))
种不同的成色,第 i 种质量大小也
wi,第
i 单质量产生
xi
个人(其到底分量不超过 300000kg
),要求编程输出这些人形能如出不同品质之种数,但未包一个丁吗无用之景象。

Input

先是实践输入质量之种数 n
第二履输入每种质量之质地
其三尽输入每种质量的食指的总人口

Output

出口可以约的成色种数

Sample Input

3
1 2 3
2 1 2

Sample Output

10

Hint

题目大意

有 \(N\) 种物品,每种物品来 \(X_i\) 个还价值吗 \(W_i\)
。可以无限制选择物品,求使得所取物品总价值不同之方案往往。

参照思路

动态规划,或记忆化搜索。
若果限了人口,求最好充分总质量,那即便是多又背包问题,参看《背包九称》。
此处只是求方案往往,拿个记数组记录转不怕哼了,时间复杂度 \(O(N\sum{W_iX_i})\) 等。

易错点解析

  1. 莫不会见出同学想到枚举的方式,即假要总共发生 P 个人,从选 1 私房及选 P
    个人不断整合出,看起稍许种不同之到底质量不就是哼了吧?但要是专注,最可怜情况下而选方案数是小于等于
    \(C^1_P + C^2_P + \ldots + C^P_P =
    2^P – 1\) 的(当且只是当有着项目质量值 \(W_i\) 互质,且非存在 \(p \leq X_j \land q \leq X_i\)
    使得 \(W_i = p \land W_j = q\)
    时取等号),考虑到闹 10 种植品质还各种质地产生 100 个人,总人数最多大臻
    1000 这是如算到地老天荒的节拍;

参照代码

标程(\(O(N\sum{X_i\sum{W_iX_i}})\)):

#include<iostream>

using namespace std;
int main()
{
    int max=0;
    int n,w[305],x[105];
    bool p[300*100*10+5];
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=1;i<=n;i++)
    {
        cin>>x[i];
        max+=x[i]*w[i];
    }
    for(int i=1;i<=max;i++) p[i]=false;
    p[0]=true;

    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=x[k];i++)
            for(int j=max;j>=w[k];j--)
            {
                if(p[j]==false && p[j-w[k]]==true) p[j]=true;
            }
    }
    int ans=0;
    for(int i=1;i<=max;i++)
    {
        if(p[i]) {ans++; }
    }
    cout<<ans;
}

\(O(N\sum{W_iX_i})\) :

#include <stdio.h>
#include <string.h>

const int MaxN = 10, MaxW = 301, MaxX = 101;
const int MaxM = MaxN * MaxW * MaxX;

int N, maxWeight;
int W[MaxW], X[MaxX], flag[MaxM];

void read() {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", W + i);
    }
    for (int i = 0; i < N; ++i) {
        scanf("%d", X + i);
        maxWeight += W[i] * X[i];
    }
}

int curr[MaxM];

void work() {
    int res = 0;
    flag[0] = 1;
    for (int i = 0; i < N; ++i) {
        memset(curr, 0, sizeof(curr));
        for (int j = W[i]; j <= maxWeight; ++j) {
            if (!flag[j] && flag[j - W[i]] && curr[j - W[i]] < X[i]) {
                flag[j] = 1;
                curr[j] = curr[j - W[i]] + 1;
                ++res;
            }
        }
    }
    printf("%d\n", res);
}

int main() {
    read();
    work();
    return 0;
}

J. 训练 ZetaGo

Description

L2M 未来科技支出企业研制了平等缓慢新的智能机器人 ZetaGo
,它可把任何事物都盘算产生一个特色值,在经过重排后好为此做出一系列之决定。
以检验 ZetaGo 的重排能力,需要人工进行监察上(supervised
learning)训练。 LLM 作为 L2M
手下的如出一辙名为实验员,就要每天进行如此的苦差事。
今天之重排规则是这般的:已领略一组特征值 A ,要求重新排列后底整合 B
可以满足任意两独相邻元素的积(\(B_i *
B_{i+1}\))为 4 的翻番。 ZetaGo
经过表决运算后会见让来是否留存这么平等种植重排方案, LLM
要根据决定结果告知她对怪,以便改正学习型。
今日 LLM 实在最好难为呀,想拜托你帮助拉。

Input

首先实践输入一个正整数 \(T \leq 10\)
代表在训练组数。
接下来 \(3T\) 行,每 \(3\) 行首先是一个正整数 \(2 \leq N \leq 1000\)
代表正在特征值的个数,接下一样行是用空格隔开的特征值 \(A_i\) (其中 \(1 \leq A_i \leq 10^9\) 且 \(0 \leq i < N\) ),最后一履行 ZetaGo
会给来她的论断结果 “yes” 或者 “no” 。

Output

要而告诉 ZetaGo 它的判断结果对怪,输出 “AC” 或者 “WA”
表示对要错(不包括引号)。

Sample Input

3
2
4 4
no
3
1 2 4
yes
4
1 2 2 4
yes

Sample Output

WA
AC
AC

Hint

样例 2 解释:1 4 2
样例 3 解释:1 4 2 2

题材大意

给得一组数据,问是不是留存这样同样种排列,使得重排后底多少,任意相邻元素两星星互相就的价是
4 的翻番,再和机器人输入的“它的论断结果”作比。

参照思路

规律题,统计数据关系。时间复杂度 \(\theta(N)\) 。

分拣讨论,可以用数字分为三类: 4 的倍数、是 2 的翻番但不是 4
的倍数、奇数。

  1. 显然,任何数和 4 的倍数相乘,其结果依然是 4 的翻番,因此是文武双全搭配;
  2. 明朗,任意 2 的倍数只出一个因子 2 ,因此它们只能两鲜内部互相就才会收获 4
    的翻番,必须相邻地放一起;
  3. 对此自由奇数,和 2 的倍数相乘不合乎题意,只能与 4 的翻番相间搭配。

之所以可先排所有 cnt1 个奇数,每半单奇数之间插入一个 4 的翻番,需要
\(cnt1 – 1\) 个 4 的翻番;若存在 2
的倍数,需要以出一个 4 来连续它们,这样用 \(cnt1\) 个 4 的翻番。判断一下 4
的倍数有多少个,是否满足条件,并将判断结果和机器人的互较,得出答案。

容易错点解析

  1. 稍稍同学规律找对了,可惜忘记每次都使初始化;
  2. 有些同学规律找对了,可惜和机器人结果的对比反了;
  3. 微同学规律找对了,可惜统计 4 的翻番时也顺手算进 2 的倍数了;
  4. 稍加同学规律找对了,可惜忘记是倍数

参照代码

#include <stdio.h>

int T, N;
int cnt1, cnt2, cnt4;
char ans[4] = "yes";

void init() {
    cnt1 = cnt2 = cnt4 = 0;
}

void read() {
    int rd;
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", &rd);
        if (rd & 3) {
            (rd & 1) ? ++cnt1 : ++cnt2;
        } else {
            ++cnt4;
        }
    }
    scanf("%s", ans);
}

void work() {
    puts(ans[0] == "ny"[cnt4 >= cnt1 - !cnt2] ? "AC" : "WA");
}

int main() {
    scanf("%d", &T);
    while (T--) {
        init();
        read();
        work();
    }
}

K. 强迫症患者

Description

cgy是一个分外有强迫症的丁,他同看到小数就全身难给。然而有雷同上,他撞了这么一条只有整数和除号构成的姿势:1/2/4/16
,他的强迫症又来了,加上了括号让式子变成了 (1/2)/(4/16)=2
把它成为了整数。但是运动方走方,他又遇到了一个墙上写满了之风格的相,cgy突然发现有些式子可以通过加括号来受结果变成整数,有些也大。但是他手下没有纸和笔,于是就没把这想法写下来,现在公会透过就同密密麻麻数字来判定他们是否可经过加括号成为整数么

Input

一个平头 n(n<=100) 表示来几乎组数据
连着下去输入 m(m<=1000) 表示来 m 个数字,再下来一行输入 m
个刚刚整数(每个数字不浮 1000 ),表示式子中之数字。

Output

于各一样履行输入,如果得以透过加括号改为整数就输出 Yes ,否则输出 No 。

Sample Input

3
3
1 2 4
4
1 5 6 9
4
1 4 2 2

Sample Output

Yes
No
Yes

Hint

题材大意

让得一弄错除法式子 a / b / c / …
,可以对拖欠姿势任意加括号因转移中一些运算符(除号变乘号),问是否在这么平等种加括号方案,使得所有式子的积极分子得以整除分母。

参照思路

野心勃勃 + 最大公约数,时间复杂度 \(O(N)\) 。

盖括号可以任意加,一定是同样种植最妙方案,使得除了次只数只能当作除数外,其他数字的积为为除数,若她的乘积及第二单数的最大公约数为
1
,则证实所有的反复就起来还无克整除第二个数,否则第二单数除因之最大公约数后那个价吗
1 (被除掉了,也堪知道呢为约分了)。

野心勃勃策略证明:假如从最了不起方案遭去某一个括号,使得还有另外一组反复和第二独数相就作为除数,若其他剩余的数的乘积不能够整除第二只数,当然为无克整除这个新的还怪之除数;若剩余的一再的乘积能整除这个新除数,根据乘法结合律,它们也会整除单独的老二个数,因此得证。

爱错点解析

  1. 乘法溢起:因为 int
    乘法有或溢起,为了避免大精计算,干脆每次都吃第二独数除因有数跟其的最大公约数,只要到结尾时第二单数成为
    1 ,说明她于此历程遭到给除掉啊;
  2. 约分:整个过程实际上就一定给约分,我们当大概分时就是当探寻分子与分母的最大公约数并跟除,这个应该很好掌握;
  3. 运算结合性:现代生人设计出的算术乘法、算术除法符号是不对结合的,也即是毫无疑问是起漏洞百出为右侧算的,这点应该没有问题吧,所以
    a / b / c 一定当于 ((a / b) / c) 也并未问题吧….

参照代码

#include <stdio.h>

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void work() {
    int M, a, b;
    scanf("%d%d%d", &M, &a, &b);
    b /= gcd(a, b);
    for (int i = 2; i < M; ++i) {
        scanf("%d", &a);
        b /= gcd(a, b);
    }
    puts(b == 1 ? "Yes" : "No");
}

int main() {
    int N;
    scanf("%d", &N);
    while (N--) {
        work();
    }
    return 0;
}

L. Oyk 捏泡泡纸

Description

资深的剪纸大师 Oyk
今年匪剪纸了,最近干活压力很,他改成吗捏泡泡纸来放松心情。由于 Czj
每天上班摸鱼,他吃缉拿恢复陪 Oyk 捏泡泡纸。
早已清楚一张完整的泡泡纸上会见产生 \(N\)
个泡泡,他们预定每次每个人且得以 paji 掉 2
的幂次(1,2,4,8,16,…,\(2^k\))个泡泡,并且连接由 Oyk
先捏,轮流下直到捏了。他们都想由自己来捏完整张泡泡纸,且他们都够聪明,总会计算选择最好有益团结的策略。
看他们捏泡泡太无聊了,我思念先了解他们谁会刚好在结尾捏完整张泡泡纸。

Input

莫不会见出差不多执行输入,请而一直处理到文件尾。
每行会输入一个正整数 \(N \leq 10^6\)

Output

于每张泡泡纸,请而告知我故事之究竟。
而是 Oyk 最后捏了,输出 “Oyk Oyk!” (不包括引号,下同)。
使是 Czj 最后捏了,输出 “diu,Czj!” 。

Sample Input

4
5
6

Sample Output

Oyk Oyk!
Oyk Oyk!
diu,Czj!

Hint

于样例 3 ,无论 Oyk 先捏 1 / 2 / 4 个还改变不了泡泡纸最后为 Czj 捏了。

问题大意

原题:与 hdu 1847 几乎一模一样。
止发生同等堆若干数据之物料,规定每人每次可取 \(2^{\mathbb{k}}\)
个,取完者胜,问先手是否会获胜。

参考思路

巴什博弈变种,找有先手必败态,发现 \(N =
3\mathbb{k}\) 先手必败。时间复杂度 \(O(1)\) 。

可事先枚举出前几只数比如 1 ~ 10 观察先手的胜败情况,发现 \(N = 3\)
是第一只先手必败态,想方用早晚败态转移给对方就可知获得胜利。发现任何数总能够加
1 或 2 成为 3 的翻番,而另外 \(3\mathbb{k}\) 都无克整除 \(2^{\mathbb{p}}\) ,剩下的一再总会是 \(3\mathbb{m} + 1\) 或 \(3\mathbb{m} + 2\) ,这样单需要拿走 1
个或 2 个就可知将 \(3\mathbb{m}\)
的状态转移给对方,直到 \(N = 3\)
,因此我们得以规定 \(N =
3\mathbb{k}\) 是据游戏之先手必败态。

出于数量比小,也同意递推的做法,复杂度 \(o(NlogN)\) 。原理是这般的,假设当前发出
\(N\) 个,如果得到走 \(2^{\mathbb{p}}\)
个后针对手是必败态,说明及时无异企业先手是顺利的,遍历一合所有的效仿即可。这同样考虑实际看似于
SG 函数,各位好自行去探听 SG 函数的规律,把这题当作 SG 的入门题hhh。

轻错点解析

  1. 莫亮发生没同桌将 Oyk 看成了 Qyk …(逃;

参照代码

标程:

#include <stdio.h>

int main() {
    int N;
    while (~scanf("%d", &N)) {
        puts(N % 3 ? "Oyk Oyk!" : "diu,Czj!");
    }
    return 0;
}

递推解法(改自一个同桌的交给):

#include <stdio.h>

const int MAXN = 1E6;
int win[MAXN + 1];

void init() {
    for (int i = 1; i <= MAXN; ++i) {
        for (int j = 1; j <= i; j <<= 1) {
            if (!win[i - j]) {
                win[i] = 1;
                break;
            }
        }
    }
}

int main() {
    init();
    int N;
    while (~scanf("%d", &N)) {
        puts(win[N] ? "Oyk Oyk!" : "diu,Czj!");
    }
    return 0;
}

M. 光棍节活动

Description

一年一度的光棍节活动中,cgy
的班级想弄一个别开生面的移位,要求将班上的男生与女生到分组,规则如下:

  1. 每个组里男生数要同,女生数也要是一律;
  2. 及一个组中的男生数不克当女生数;
  3. 每组中男生与女生分别要生 2 名或以上;
  4. 务必使分成 2 只或以上的组,组数也使尽可能的差不多才好游戏;

而无克圆满分组,将随机抽出一称作男生和同一称作女生组成一批进行装扮情侣活动,重复进行(尽量少之次数)抽人直到剩下的子女大人数恰好可以健全分组。
如若一直不在完美分组,那么除了成功组队进行装扮情侣的外,可能会见多出多男生要女生没有组队哦(同性才是的确好!)。

cgy 安排 lxy 实施是方案,但 lxy 脸红心跳,想请您帮助拉。

Input

率先实践输入正整数 \(T \leq 100\)
代表共计发生 \(T\) 种情况。
接下来 \(T\) 行,每行包含两个正整数
\(N < 10^5\) 和 \(M < 10^5\) 代表正该种情况中有 \(N\) 名男生和 \(M\) 名女生。

Output

对于各种状况,请您帮忙计算起了美分组数和扮情侣数,在一行中输出,用空格隔开。
一经在尚未组队的骄子,你可以重新为 ta 们输出都仅输出一行 “happy single
dog!” (不包引号)聊表庆祝。

Sample Input

3
18 24
19 25
18 19

Sample Output

6 0
6 1
0 18
happy single dog!

Hint

样例解释:
对于样例 1 ,可以圆满分组为最多 6 组,每组有 3 称作男生 4
名女生,不需要重减去人展开装扮情侣活动。
对于样例 2 ,先抽出一对送给 FFF 团,之后虽跟样例 1 一样啊。
于样例 3 ,只能抽出 18
对玩假扮情侣活动,然后下一行也剩下的不得了妹纸出口 happy single dog! 。

问题大意

出一定量堆数量不同的物料,要求对该进行分组,且完成组数最大化;
非克只是分一个组,否则不深受分组;
未克随便分组,每个组的动静而一如既往;
加入规则 2 ,一个组中不同品类物品数量不同;
在规则 3 ,一个组中任意一栽物品数量不呢 1 。
(由于自身原来的主次忘记考虑规则 3
,所以比赛被即删掉了,后来察觉数吧绝非卡掉,改不移都是对的)

参考思路

数关系规律题,枚举到能够请最大公约数为止。
假设少独数据等则一直通正是假扮情侣。
假使简单单数据相差 1 则早晚非能够要 gcd 。
倘枚举过程遭到最为特别勤得整除最小数,则不饱规则 3 。
若枚举失败,那就是未能够到家分组了。

参照代码

脚的代码已经考虑了平整 3 :

#include <stdio.h>

int N, M;

void swap(int &a, int &b) {
    const int t = a;
    a = b;
    b = t;
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void read() {
    scanf("%d %d", &N, &M);
}

void work() {
    int perfect = 0, fake = 0;
    bool hasSingle = false;
    if (N > M) {
        swap(N, M);
    }
    if (N == M) {
        fake = N;
    } else if (N + 1 == M) {
        hasSingle = true;
        fake = N;
    } else {
        int groupCnt = 1;
        while (N && (1 == (groupCnt = gcd(M, N)) || N == groupCnt)) {
            ++fake;
            --N;
            --M;
        }
        if (!N) {
            hasSingle = true;
        } else {
            perfect = groupCnt;
        }
    }
    printf("%d %d\n", perfect, fake);
    if (hasSingle) {
        puts("happy single dog!");
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        read();
        work();
    }
    return 0;
}

初赛复盘

一如既往开始自是从未想过如果把题目排成这顺序的,我们的背锅侠忘记调啦!于是只能在
7
分钟发了条@全员说难度不照梯次,然而大家要么好按部就班梯次做(摊手.jpg)。于是就又闹矣同样堆积被打击信心之爆零啦
qwq

继之便由于没有充分验题,陆续发现了卡 cin
之类的意料之外问题,改了点儿不行数据重判了多不善,又拿本 AC 的吃重判成 TLE
了“咦重判完 AC 反而易少了”(药丸.jpg)。

然后安利一下 qu 老师家之可能还算好用的金山 WPS
写得;借助这奇怪之写作(?)工具临时对发现的有些题目,一些未曾说理解的事项作了个补充(虽然感觉并没人拘禁),于是像
system("pause") 之类的到后期似乎从来不当选手们的交付中出现了了。

整体区分度良好,从最后排名来拘禁,做对题目数上阶段性分布;除了 A
题是个看起大概其实大家还没学了的非常坑客,对 H 题《CG
之如何》难度估算错误,显然大家都没听说过斐波那契的通项公式;对 M
题《光棍节活动》难度估算错误,虽然和 K
题《强迫症患者》一样是要因此到要最大公约数的算法,但题面明显较复杂,陈述有待优化,甚至出现有书人自己还渗透考虑中一个标准的状;对
L 题《Oyk
捏泡泡纸》难度估算错误,显然大家找找规律的力量要十分大之,之前是看这个博弈题比较麻烦证明,然而大家敢于交题。。

完整题目质量优,除了各自问题题意有待加强、条件描述不精确或其他小问题他,涉及的知识点较咸,没有还出题;除了各自选手在
F
题用到批处理生成长段代码,正解解答代码量适中,涉及的少数程序语言文化大致相符教xue学xi进度。

出题总结

题号 题目 ZYJ 预xia估cai难度 正确率(正确/提交) 通过率(正确人数/有效人数) 出题人
A 诡异的计数法 2.8 9.88%(100/1012) 61.64%(90/146) Cgy
B 数发票 4.0 11.43%(28/245) 13.01%(19/146) Cgy
C Ljc 吃糖 2.5 8.82%(30/340) 14.38%(21/146) Ljc
D 姓名字母排列 2.5 9.59%(21/219) 8.22%(12/146) Zyj
E Substring 2.0 51.08%(118/231) 74.66%(109/146) Zlm
F 法特狗 3.0 7.29%(25/343) 12.33%(18/146) Cgq
G Zyj 打印奖状 1.0 26.97%(140/519) 88.36%(129/146) Cgy
H Cg 之争 1.8 21.55%(86/399) 53.42%(78/146) Cgy
I 人形质量单位 4.0 20.00%(16/80) 6.85%(10/146) Lxy
J 训练 ZetaGo 3.0 21.02%(78/371) 47.95%(70/146) Zyj
K 强迫症患者 2.5 21.26%(44/207) 27.40%(40/146) Lxy
L Oyk 捏泡泡纸 3.0 59.90%(118/197) 74.66%(109/146) Zyj
M 光棍节活动 2.2 11.35%(43/379) 26.03%(38/146) Zyj

呃,文字性的事物辣么烦,怎么可能会见生出出题总结这种事物嘛。

最后

初赛并无是为拿大家,而是被大家感受 ACM
程序设计竞赛是安的,算法和数据结构是独什么事物,对于一个已经清楚之问题,如何抽象出它的模子并找到适合的不二法门,在较好的特性外解决它们。
本年应当也是第一年许转专业的同班参加,一开始还老担心他们大都学了半学期《数据结构》会无会见无限强了之(逃)。可能对于多数同校来说,参加
ACM
新生赛或许是首先潮这样强密度地思量与化解问题,但无论是萌新也好,还是改变专业的校友也好,希望咱们这次比赛可以是若踹上标准成长途径的第一步,相信吗只是各位的诸多在世历程的同有点段,未来之生活还很丰富,可能你见面像我平莫名其妙地改变了前端开发,可能您晤面召开一些重新幽默之东西,可能你以后会开同样号称教职工,也说不定您晤面继续深入计算机科学的研究被,甚至可能好上算法竞赛和算法研究与统筹,往小了说后面还有
CTF 竞赛(逃)。
不顾,希望这次比赛能为你感触及电脑科学的法及程序设计的魅力,让你的编程能力有所锻炼与加强,让你的构思空间与知识面有所扩大,而不光是待在外部上的“这个极度碍事矣”“这个来什么用嘛”“我随后总会学到之”,谢谢!

本文基于图片 4文化共享署名-非商业性使用-相同方式并享
4.0
国际许可协议揭晓,欢迎引用、转载或演绎,但是得保留本文的签字BlackStorm与本文链接http://www.cnblogs.com/BlackStorm/p/SCNUCPCFF-2017-Solutions.html,且未经许可不可知用于商业目的。如产生疑点还是授权协商请以及自沟通。

相关文章