【每日一题】
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ??
? ? ? ? 比較重要的一個寒假，可惜家中事情有點多、沒有條件訓練，要考研了，每天刷一題。也有想不刷來著，畢竟專業課任務比較突出，復習時間很少、不過不做做題比看不懂題意更難受。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
2019/3/1
題意
P: a {1,2....i....n } 中找出比i大的數有多少個、打印出新序列。
I：a{1,2,3...i..n} ?ai代表i數字所在的位置有ai個數比i大，依次，打印出新序列。 找I和P序列之間得關系
代碼:https://paste.ubuntu.com/p/Z6BX6XMxsT/
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
題意
Colorful Creatures?
用到了數學中否命題的概念，在其二倍的范圍內都行，也就是說超過了其二倍的都不行。
?代碼：https://paste.ubuntu.com/p/q88CQZJTG4
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
2019/3/2
?HDU-1595
題意
打開密碼鎖。 密碼由四位數組成。 每個數字的編號從1到9。
每次，可以在任何數字上加1或減1。 當將1加到'9'時，數字將變為'1'，當減1變為'1'時，數字將變為'9'。 也可以與其鄰居交換數字。 每個動作都將邁出一步。任務是使用最小的步驟來打開鎖。
注意：最左邊的數字不是最右邊數字的鄰居。
每個測試用例以四位數N開頭，表示密碼鎖定的初始狀態。 然后跟著一條線，用另外四個M，表示可以打開鎖的密碼。 每個測試用例后都有一個空行。
1234
2144
answer:2
代碼?https://paste.ubuntu.com/p/H3HJXt449H/
—————————————————————————————————————————————————————
2019/3/4
Atcode-2341
題意
如果一個十進制非負整數的所有數位從高位到低位是不減的，我們稱它為“上升數”，例如1558,11,3,0都是上升數，而10,20170312則不是；
給定整數N，求最小的k使得N能被表示為k個上升數之和。
1≤N≤10500000
題解
一個結論：每個上升數必定能被分解為九個全一數的和；
所謂“全一數”就是指1,1111,11111111這種每一位數都為1的數（包括0），證明顯然。【不顯然】
設N可以被分解成K個全一數之和，顯然答案,則求最小的K。這K個全一數分別為，其中
? ，
? ?。【這個式子是什么意思呢？如果不考慮進位，右邊每一項都會使數位和+1，那么總體就說明9N+K的數位和等于K的數位和，此時K一定是9的倍數；如果考慮進位，那么每進一位數位和就會減少9，因此K仍然要是9的倍數。
由于答案最多不會超過N的位數，枚舉k，寫個高精度亂做就行了。。。注意加法的時候沒有進位就要break，這樣是均攤O(1)的，否則是O(n2)的。記一個數x的各位數之和為d(x)，要想找到一組b使得上式成立，那么應有：d(9N+K)<=K（因為即使不進位，一個b[i]也只能使得數位和+1）。】【不顯然】
代碼
https://paste.ubuntu.com/p/b2y56hGVYy/
———————————————————————————————————————————————————————
2019/3/9
題意
a:b代表兩個球隊打球在某一時刻的比分，給出某時間點(不連續的時間)的各個比分，問在比分之間有多少次最多有多少次平局，即x:x?
代碼?https://paste.ubuntu.com/p/8dZKBhTfsR/
————————————————————————————————————————————————————————
2019/3/9
題意
題目中說的是給出n個數字，要求成一個環，然后要求相鄰之間的數字的差值的絕對值最小，剛開始搜的題意沒有說是成立一個環（直接排了個序submit了 結果wa1)
代碼?https://paste.ubuntu.com/p/PZPD3yZVRj/
——————————————————————————————————————————————————————
2019/3/9
codeforces
題意
從l??到r?中選?n?個數，允許相同。要使最終這n??個數的和是?3的倍數，求有多少個方案，答案mod? 1e9+7(若沒有方案，輸出?0?)
//首先1≤ l ≤ r ≤1e9 1 ≤ l ≤ r ≤ 1e9，顯然不能從l,r下手。我們可以從3思考一下，顯然，求n個數的和為3的倍數，就是余數加起來為3的倍數。所以，對于一個方案，把里面的某一個數換成余數與其相同的數，方案仍然成立。
//f[i][j]?? 為到第?i個數時，前i??個數的和mod?? 3??為j??的方案數。
代碼?https://paste.ubuntu.com/p/WkWQ92XQmQ/
———————————————————————————————————————————————————————
2019/3/17 感覺涼了
問題
給出兩個數a,b（<1000)，算出他們兩個最大不能被表示的數。
思路
簡單dp,數論：在a,b互質的時候，有結論:最大不能被表示的數是a*b-a-b,且不能被表示的數的個數是(a-1)(b-1)/2, 在(a,b)!=1的時候，不知道。
代碼：https://paste.ubuntu.com/p/FrWYBr4HXp/
———————————————————————————————————————————————————————
2019/3/18
問題
給出n個數，求其中k個數的乘積最大是多少，n<=1000
代碼https://paste.ubuntu.com/p/GWWQ3RKCyT/
___________________________________________________________________________________________________
2019/3/18
題意
51nod-1194
給出N和K，求Fib(N) mod Fib(K) ?(1 <= N <= 10^18, 1 <= K <= 10^3)
2014年藍橋杯的C++ A組第九題
求斐波那契的前n項和對m取余
(0 < n, m?< 10^18)
題解
斐波那契數列的性質：
推導有
一直這樣迭代下去最后就會是
因為，所以我們得到，
在第九題中m很大，不能預處理
有，立即推
-----
dalao:https://blog.csdn.net/acdreamers/article/details/21822165
-------------------------------
對于斐波那契數列的性質總結有
若，則
?令，那么利用上述性質，我們替換一下：，得到：
，變換一下順序，即
，所以
?再分的奇偶性進行討論:
（1）為奇數時，
（2）為偶數時，
————————————————————————————————————————————————————————
2019/03/18
題意
小明維護著一個程序員論壇。現在他收集了一份"點贊"日志，日志共有N行。其中每一行的格式是：
ts id
####表示在ts時刻編號id的帖子收到一個"贊"。
####現在小明想統計有哪些帖子曾經是"熱帖"。如果一個帖子曾在任意一個長度為D的時間段內收到不少于K個贊，小明就認為這個帖子曾是"熱帖"。
####具體來說，如果存在某個時刻T滿足該帖在[T, T+D)這段時間內(注意是左閉右開區間)收到不少于K個贊，該帖就曾是"熱帖"。
####給定日志，請你幫助小明統計出所有曾是"熱帖"的帖子編號。
代碼?https://paste.ubuntu.com/p/YFd9CkFM9g/
——————————————————————————————————————————————————————
2019/03/18
題意
螺旋折線
思路
找出(x,x)的dis,之后對x>0 x<0 ?以及x和y的大小關系細化規律
代碼?https://paste.ubuntu.com/p/d2WHbhDvqY/
———————————————————————————————————————————————————————
2019/03/19
題意
星球的居民脾氣不太好，但好在他們生氣的時候唯一的異常舉動是：摔手機。
各大廠商也就紛紛推出各種耐摔型手機。x星球的質監局規定了手機必須經過耐摔測試，并且評定出一個耐摔指數來，之后才允許上市流通。
x星球有很多高聳入云的高塔，剛好可以用來做耐摔測試。塔的每一層高度都是一樣的，與地球上稍有不同的是，他們的第一層不是地面，而是相當于我們的2樓。
如果手機從第7層扔下去沒摔壞，但第8層摔壞了，則手機耐摔指數=7。
特別地，如果手機從第1層扔下去就壞了，則耐摔指數=0。
如果到了塔的最高層第n層扔沒摔壞，則耐摔指數=n
為了減少測試次數，從每個廠家抽樣3部手機參加測試。
某次測試的塔高為1000層，如果我們總是采用最佳策略，在最壞的運氣下最多需要測試多少次才能確定手機的耐摔指數呢？
請填寫這個最多測試次數。
解析
假設在n層的樓中，最大扔的次數是x,
那么在扔1次的時候扔x層，
在x層的樓中最大扔的次數是x次，但是這不是最優的方案，手機也沒有這么多
那么在任何一種樓層模型中，設最大扔的次數是x,那么最大扔的樓層也是x
在n層的樓中
第一次扔x層，
第二次扔x+x-1,(增加了x-1層，這樣保證了在摔第二次的時候最大最次也是x次，若第一次刷壞，第二次用另一個手機摔第1層)
第三次 x+(x-1)+(x-2) (每次增加的樓層都是上一次增加的層數-1，若第二次摔壞，則在第三次的時候用下一個手機去扔x+x-1+1層)
...
第x次扔 x+(x-1)+(x-2)...+(x-(x-1)) ?這樣就保證了在最差的運氣下，最多需要測試的次數。
最后第x次扔的層數是 1+2+3+4+....x
在100層的樓中也就是上式大于等于100
x>=14
第一次在14樓扔，如果碎了的話從一樓再開始扔；
否則在14+13=27層扔，如果碎了的話從15層開始扔；
否則在27+12=39層扔，如果碎了的話從28層開始扔；
……
這樣，最大嘗試次數為14次就行了。http://www.cnblogs.com/Matrix_Yao/p/4793823.html
上面是在有2個手機的情況下得到最差的次數，那么在有第三個手機的情況下就可以轉化到只有兩個手機模型中，把前兩次扔的當做第一次(原先前兩次)仍，下一次扔(原先第三次)的當做第二次
那么就有 1+3+6+10....x>n ?總結出來第x次扔的層數通項是ax=(n*n+n)/2
當n=1000時
....我算出來的不是18 (學長：https://blog.csdn.net/clx55555/article/details/79855677
代碼?https://paste.ubuntu.com/p/tKKjs3PczP/
————————————————————————————————————————————————————————
2019/3/19
題意
代碼https://paste.ubuntu.com/p/DQ8gzm9GNV/
2019/3/22
題意
博覽館正在展出由世上最佳的 M 位畫家所畫的圖畫。
wangjy想到博覽館去看這幾位大師的作品。
可是，那里的博覽館有一個很奇怪的規定，就是在購買門票時必須說明兩個數字，
a和b，代表他要看展覽中的第 a 幅至第 b 幅畫(包含 a 和 b)之間的所有圖畫，而門票
的價錢就是一張圖畫一元。
為了看到更多名師的畫，wangjy希望入場后可以看到所有名師的圖畫(至少各一張)。
可是他又想節省金錢。。。
作為wangjy的朋友，他請你寫一個程序決定他購買門票時的 a 值和 b 值。
輸入輸出格式
輸入格式：
第一行是 N 和 M，分別代表博覽館內的圖畫總數及這些圖畫是由多少位名師的畫
所繪畫的。
其后的一行包含 N 個數字，它們都介于 1 和 M 之間，代表該位名師的編號。
輸出格式：
a和 b(a<=b) 由一個空格符所隔開。
保證有解，如果多解，輸出a最小的。
輸入輸出樣例
輸入樣例#1：
12 5
2 5 3 1 3 2 4 1 1 5 4 3
輸出樣例#1：?
2 7
尺取
代碼https://paste.ubuntu.com/p/D4z9HvhYS4/
————————————————————————————————————————————————————————
2019/3/22
題目
最長上升子序列的源碼版
https://paste.ubuntu.com/p/WCRmPCF5P8/
_____________________________________________________________________________________________________
2019/3/23
題意
一天蒜頭君得到 n 個字符串 si ，每個字符串的長度都不超過 10。
蒜頭君在想，在這 nn 個字符串中，以 si
為后綴的字符串有多少個呢？
輸入格式
第一行輸入一個整數 n。
接下來 n 行，每行輸入一個字符串 si
輸出格式
輸出 n 個整數，第 i 個整數表示以 si?
為后綴的字符串的個數。
n<=1e5
代碼?https://paste.ubuntu.com/p/H23DngXqtH/
2019/3/30
題意：
第1行輸入 曲子數n 和 最多能選的曲子數k (1≤k≤n≤3?10^5)
2 ~ n + 1行 每行輸入 歌曲長度t, 這首歌的美麗值b;
要求找到 k 以下的曲子，并且 t的和乘以最小的b的值最大
https://paste.ubuntu.com/p/rCTytQKRfN/
總結
