ACM課件(lecture-02)老少皆宜數(shù)學(xué)題

ACM程序設(shè)計杭州電子科技大學(xué)劉春英acm@2/3/20231第二講老少皆宜之?dāng)?shù)學(xué)題2/3/20232今天，你

了嗎？AC2/3/20233每周一星（1）：亦紛菲ぁ幻劍

2/3/20234開胃羹（1）幾個常用單詞：1、vertex(vertices)頂點(diǎn)2、polygon多邊形3、convex凸的4、concave凹的5、segment(線)段（n）;分割（v）2/3/20235開胃羹（2）再來幾個：1、integer整數(shù)2、positive正的3、negative(adj)負(fù)的;(n)負(fù)數(shù)4、factorial(n)階乘;(adj)因子的，階乘的5、digital(n)數(shù)字;(adj)數(shù)字的2/3/20236ACM數(shù)學(xué)題特點(diǎn)分析:題意容易理解算法相對簡單（有些很難的?。。┚幊瘫容^容易ACM/ICPC入門練習(xí)的好選擇下面，分類介紹：2/3/20237從首屆“舜宇”杯說起2/3/20238比賽背景 由于前一年的邀請賽很多學(xué)校沒有做出一道題，所以，這次的比賽特意準(zhǔn)備了幾道簡單的題目，目的就是讓大多數(shù)的學(xué)校都能拿個氣球回去，也好有個交待，于是有…2/3/20239第一類傻瓜型2/3/2023101004:LettheBalloonRise2/3/202311題目評述：

1.一個讓你看到后興奮的題目…

2.只要懂點(diǎn)C或者C++，就可解決該問題。2/3/2023121004題目分析：該題算法思想比較簡單，就是對輸入的字符串進(jìn)行比較和統(tǒng)計。值得注意的一點(diǎn)是：如果用C語言來寫，要注意可能會把第一個數(shù)字后的“回車符”誤認(rèn)為是第一個串，字符串的比較也要用函數(shù)和循環(huán)語句。而C++則在處理字符串方面較為方便。2/3/2023131008:Elevator2/3/202314

實(shí)際上，這是本次比賽最簡單的一題，浙大、浙工大等當(dāng)時訓(xùn)練水平相對較高的學(xué)校基本上10分鐘之內(nèi)解決該題，這也是一個沒有算法的題目。這種題目大家不會錯過的…題目評述：2/3/202315不要分析了吧…2/3/202316第二類基本型2/3/2023171009:

FatMouse'Trade2/3/202318題目特點(diǎn)： 這個題目比前面兩個題目稍難，但是屬于能一眼看出解決辦法的題目。只要靜下心，還是比較容易解決的。2/3/2023191009算法分析：輸入（J,F放入數(shù)組）對數(shù)組排序（按效益，降序）輸出（按效益高低有序交易）2/3/202320第三類技巧型2/3/202321小錘摳縫—— 先來看一個簡單的題目鋪墊一下：2/3/2023221021FibonacciAgain

2/3/202323題目分析：能被3整除的整數(shù)的特點(diǎn)？還要看程序嗎？如果兩個數(shù)的和能被3整除，這兩個數(shù)有什么特點(diǎn)？關(guān)于能否被3整除，這兩個數(shù)一共有多少種組合？2/3/202324Hdoj_1021程序清單：#include<stdio.h>intmain(){longn;

while(scanf("%ld",&n)!=EOF) if(n%8==2||n%8==6)

printf("yes\n"); else

printf("no\n"); return0;}2/3/202325回到正題——大錘搞定2/3/202326ProblemB:NumberSequence2/3/202327題目特點(diǎn)： 這個題目是一個比較典型的ACM競賽題，盡管在真正的大賽中這個題目可能算比較簡單的，但在本次比賽中，本題難度屬于中等，可以說，能做出本題的隊(duì)伍基本都有二等獎以上。 但如果不認(rèn)真分析，有可能會掉入陷阱。2/3/202328Question:暴力能解決問題嗎？2/3/202329拒絕暴力～2/3/202330題目分析： 對于這種題目，千萬不能蠻干！實(shí)際上，有經(jīng)驗(yàn)的同學(xué)看到本題目的數(shù)據(jù)規(guī)模，很快就能知道：這類題目有規(guī)律可循。2/3/202331現(xiàn)在對這題有什么想法???2/3/202332第四類紙老虎型2/3/202333HDOJ_1071TheArea

2/3/202334第一眼：傻了…2/3/202335再一看——2/3/202336拋物線公式：y=ax^2+bx+c已知三點(diǎn)-〉a、b、c系數(shù)公式已知-〉如何求面積？會簡單積分嗎？分析過程：2/3/202337該你思考了…感覺怎么樣？2/3/202338思考題：（2006/3/4HDOJ的練習(xí)賽題目）2/3/202339要點(diǎn)分析：1、暴力的復(fù)雜度是多少？2、哪些陷阱？3、關(guān)鍵在哪？4、順利應(yīng)該多長時間？2/3/202340數(shù)學(xué)公式:1、這個大家都會：1+2+3+4+…n=n(n+1)/22、這個有些同學(xué)忘記了：

1*1+2*2+3*3+…+n*n=n(n+1)(2n+1)/63、合并后得到n(n+1)(n+2)/32/3/202341Anyquestion?2/3/202342課后任務(wù)：一、DIY在線作業(yè)(2):2008《ACMProgramming》Exercise（2）_Math

二、常規(guī)練習(xí)（包含以上作業(yè)）1004、1005、1008、1009、10601012～1014、1019～