SCAU2021春季個(gè)人排位賽第三場(chǎng)（OI）部分題解
B題 洛谷P7107
?
題目背景
暑假期間，學(xué)校不提供午餐，Gnar 只好找伙計(jì)們一起點(diǎn)外賣。
尷尬的是，外賣很快送到卻沒人樂意去校門口拿，畢竟戶外可是?35\degree\!\text{C}35°C?高溫！此時(shí) Gnar 想到了好主意：“我給一人捏了一張紙團(tuán)，其中一張寫有記號(hào)，不如我們抓鬮決定，誰抽到帶記號(hào)的誰去拿！”
于是 Gnar 連續(xù)拿了六天的外賣。
這可讓他不服又委屈：“換個(gè)規(guī)則！一人準(zhǔn)備三張紙團(tuán)，五張有記號(hào)，每人抽三張，記號(hào)最多的去拿！”
Gnar 緊張地展開手中的紙團(tuán)，兩個(gè)記號(hào)赫然映在眼前。大伙們剛想放聲大笑他的非酋運(yùn)氣，有人緩緩舉起三張紙片說道：“我也抽到了兩個(gè)記號(hào)……”
題目描述
好奇的 Gnar 想研究一般情況下抽到最多記號(hào)的人數(shù)。他給參與抓鬮的?nn?人一人準(zhǔn)備了?mm?張捏好的紙團(tuán)，一共?nmnm?張，其中恰好?kk?張?zhí)崆皩懥擞浱?hào)。隨后每個(gè)人在均勻打亂的紙團(tuán)中各抽?mm?張。
一個(gè)人抽到最多的記號(hào)，當(dāng)且僅當(dāng)沒有人抽到的記號(hào)比他還多。請(qǐng)你幫 Gnar 判斷是否可能會(huì)恰好?\boldsymbol{p}p?個(gè)人抽到最多的記號(hào)。Gnar 喜歡追根問底，所以如果有可能，你還需構(gòu)造每個(gè)人抽的紙團(tuán)中分別有多少帶記號(hào)、有多少不帶記號(hào)。
形式化地，假設(shè)第?ii?個(gè)人抽到了?x_ixi??張帶記號(hào)的紙團(tuán)和?y_iyi??張不帶記號(hào)的紙團(tuán)，你的構(gòu)造應(yīng)滿足：
- x_i, y_i \ge 0xi?,yi?≥0，x_i + y_i = mxi?+yi?=m。
- \displaystyle \sum_{i = 1}^{n} x_i = ki=1∑n?xi?=k。
- 有且僅有?\boldsymbol{p}p?個(gè)互不相同的?jj?使?\displaystyle x_j = \max_{i = 1}^{n} \{x_i\}xj?=i=1maxn?{xi?}。
輸入格式
輸入四個(gè)整數(shù)?n, m, k, pn,m,k,p，含義詳見題目描述。
輸出格式
第一行輸出?YES?或?NO（不區(qū)分大小寫，yEs?/?No?均可），表示是否會(huì)恰好?pp?個(gè)人抽到最多的記號(hào)。
如果第一行輸出?YES，接下來?nn?行每行輸出?x_i, y_ixi?,yi?，表示每個(gè)人抽到帶與不帶記號(hào)的紙團(tuán)個(gè)數(shù)。
因答案可能不唯一，本題采用 Special Judge，只要構(gòu)造符合題面中的要求均視為正確。
輸入輸出樣例
輸入 #1復(fù)制
3 3 5 2輸出 #1復(fù)制
YES
2 1
2 1
1 2輸入 #2復(fù)制
3 3 3 2輸出 #2復(fù)制
NO輸入 #3復(fù)制
3 3 5 3輸出 #3復(fù)制
NO說明/提示
【樣例解釋 #1】
樣例給出了一種滿足題述條件的構(gòu)造。
【樣例解釋 #2】
不論如何，記號(hào)的分布從高到低只有三種情況：\{3,0,0\}{3,0,0}，\{2,1,0\}{2,1,0}，\{1,1,1\}{1,1,1}，抽到最多記號(hào)的人數(shù)分別對(duì)應(yīng)?11，11，33。因此無法構(gòu)造?p = 2p=2?的方案。
【數(shù)據(jù)規(guī)模與約定】
本題采用捆綁測(cè)試。你必須通過 Subtask 中所有的測(cè)試點(diǎn)才能獲得該 Subtask 的分?jǐn)?shù)。
- Subtask #1 (15 points)：n,m \le 8n,m≤8。
- Subtask #2 (15 points)：n,m \le 100n,m≤100。
- Subtask #3 (20 points)：n,m \le 10^5n,m≤105。
- Subtask #4 (10 points)：p = 1p=1。
- Subtask #5 (40 points)：無特殊限制。
對(duì)于所有的數(shù)據(jù)，保證?1 \le p \le n \le {10}^51≤p≤n≤105，1 \le m \le {10}^91≤m≤109，0 \le k \le n m0≤k≤nm。
?
題意：n*m張紙條里，有k張含有標(biāo)記。打亂順序每個(gè)人抽m張紙條，其中恰好p個(gè)人拿到了最多的含標(biāo)記的紙條。假設(shè)幸運(yùn)兒就是拿標(biāo)記最多的，這題的意思就是幸運(yùn)兒不是一個(gè)，而是p個(gè)。是否有這種情況發(fā)生，如果有請(qǐng)列出情況。
?
題解：
我一開始想法是，枚舉p個(gè)人該拿多少?gòu)垬?biāo)記紙條。每個(gè)人最多拿m張紙條，那么就直接從1枚舉到m。
如果有一個(gè)i，也就是p個(gè)人每人拿i張標(biāo)記紙條，使得剩下n-p個(gè)人每個(gè)人含有標(biāo)記紙條都小于i，那么這個(gè)i就是答案。
但是，很明顯，超時(shí)。
然后我就想調(diào)二分，既然答案已知是在1到m，二分了一下，還是有些特殊情況沒弄出來。
?
然后就是正解：
既然有k張標(biāo)記紙條，要先給p個(gè)人都拿同樣的數(shù)量，然后再讓剩下的n-p人分標(biāo)記紙條，那么我們?yōu)樯恫恢苯颖M量讓p個(gè)人拿盡量多的標(biāo)記紙條呢？也就是直接讓p個(gè)人拿k/p張紙條，這樣子就少了之前的枚舉，且符合題意。但是要注意，也有可能k/p會(huì)大于m，所以我們?nèi)個(gè)人每人取min（m，k/p）張紙條。設(shè)q=min（m，k/p）。
按照題意，剩下的n-p的人就不能超過q，那么就讓剩下的人取q-1，然后取到無為止，那不就滿足條件了！
?
但是還是要思考一下如何出現(xiàn)NO，我們現(xiàn)在p個(gè)人取q已經(jīng)是取得最多的情況了，那么只有剩下的標(biāo)記紙條每人q-1張還出現(xiàn)多了，那就肯定是不符合題意的，就是NO的了。
也就是k-p*q > (n-p) *(q-1)的時(shí)候，就是NO的時(shí)候。
那么這樣就很明顯了，思路就是這樣。
代碼：
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <string.h>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdlib>
using namespace std;
long long n,m,k,p;
void read_in()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m>>k>>p;
}
void work()
{
int q=min(m,k/p);
if(k-p*q>(n-p)*(q-1))
{
cout<<"NO";
return ;
}
cout<<"YES"<<endl;
for(int i=1;i<=p;i++)
{
cout<<q<<' '<<m-q<<endl;
k=k-q;
}
for(int i=p+1;i<=n;i++)
{
if(k>=q-1)
{
cout<<q-1<<' '<<m-q+1<<endl;
k=k-(q-1);
}
else
if(k>0)
{
cout<<k<<' '<<m-k<<endl;
k=0;
}
else
cout<<0<<' '<<m<<endl;
}
}
int main()
{
read_in();
work();
return 0;
}?
?
?
?
C題? 洛谷P7106
?
題目背景
我喜歡安靜，你熱愛喧鬧；我忠于溫暖，你酷愛涼爽。
如果任何事物都有反面，那拼接這個(gè)世界的顏色呢？
只有白與黑嗎？
題目描述
為了形式化地描述顏色，我們引入?RGB 顏色值，用三元組?(r,g,b)(r,g,b)?表示一種顏色，其中?r,g,br,g,b?分別為該顏色的?R 值、G 值、B 值，滿足?0 \le r,g,b \le 2550≤r,g,b≤255?且皆為十進(jìn)制整數(shù)。
顯然，這套顏色系統(tǒng)一共可以表示?256 \times 256 \times 256 = 16\,777\,216256×256×256=16777216?種不同的顏色。對(duì)于顏色?(r,g,b)(r,g,b)，定義其反色的 RGB 顏色值為?(255-r,255-g,255-b)(255?r,255?g,255?b)。
然而人們發(fā)現(xiàn)，單純地使用 RGB 顏色值很不方便，復(fù)制顏色時(shí)要復(fù)制三個(gè)值。
于是誕生了十六進(jìn)制顏色碼，即形如?#EBA932?長(zhǎng)度為?77?的字符串。具體而言：
- 字符串的第一位是?
#，為顏色碼標(biāo)識(shí)符。 - 字符串的第二、三位是十六進(jìn)制數(shù)碼，拼成的十六進(jìn)制數(shù)等于十進(jìn)制下所示顏色的 R 值。
- 字符串的第四、五位是十六進(jìn)制數(shù)碼，拼成的十六進(jìn)制數(shù)等于十進(jìn)制下所示顏色的 G 值。
- 字符串的第六、七位是十六進(jìn)制數(shù)碼，拼成的十六進(jìn)制數(shù)等于十進(jìn)制下所示顏色的 B 值。
十六進(jìn)制數(shù)碼從小到大包含?0，1，2，3，4，5，6，7，8，9，A，B，C，D，E，F，注意?A，B，C，D，E，F?均為大寫。
現(xiàn)在你收到了一組十六進(jìn)制顏色碼，請(qǐng)你輸出其反色的十六進(jìn)制顏色碼。
提示：顏色的 RGB 值與十六進(jìn)制碼之間可以相互轉(zhuǎn)換（參考樣例解釋 #2）
輸入格式
一行，輸入長(zhǎng)度為?77?的字符串，表示原色的十六進(jìn)制顏色碼。
輸出格式
一行，輸出長(zhǎng)度為?77?的字符串，表示反色的十六進(jìn)制顏色碼。
輸入輸出樣例
輸入 #1復(fù)制
#FFFFFF
輸出 #1復(fù)制
#000000
輸入 #2復(fù)制
#EBA932
輸出 #2復(fù)制
#1456CD
說明/提示
【樣例解釋 #1】
轉(zhuǎn)換后原色的 RGB 值為?(255,255,255)(255,255,255)，反色的 RGB 值為?(0,0,0)(0,0,0)，對(duì)應(yīng)十六進(jìn)制碼?#000000。
【樣例解釋 #2】
轉(zhuǎn)換后原色的 RGB 值為?(235,169,50)(235,169,50)，反色的 RGB 值為?(20,86,205)(20,86,205)，對(duì)應(yīng)十六進(jìn)制碼?#1456CD。
為避免理解偏差，此處特別解釋?#EBA932?轉(zhuǎn)換后 B 值為?5050?的原因：提取字符串的第六、七位，拼成的十六進(jìn)制數(shù)為?(32)_{16}(32)16?，則有?(32)_{16} = 3 \times 16^1 + 2 \times 16^0 = 50(32)16?=3×161+2×160=50。
【數(shù)據(jù)規(guī)模與約定】
本題共有 10 個(gè)測(cè)試點(diǎn)，每通過一個(gè)測(cè)試點(diǎn)可獲得 10 points。
對(duì)于?10\%10%?的數(shù)據(jù)，為樣例 #1。
對(duì)于另外?30\%30%?的數(shù)據(jù)，輸入與輸出字符串均不包含大寫字母。
對(duì)于所有的數(shù)據(jù)，保證給定字符串為合法十六進(jìn)制顏色碼。
?
題意：
兩個(gè)字符組成一個(gè)十六進(jìn)制數(shù)，一共3個(gè)十六進(jìn)制數(shù)，將其轉(zhuǎn)化為十進(jìn)制后，設(shè)其十進(jìn)制為x，則將其轉(zhuǎn)化成255-x，然后再重新組成十六進(jìn)制。
?
題解：
沒什么好說，直接模擬。
?
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <string.h>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdlib>
using namespace std;
string st;
int len=7;
char c[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
void read_in()
{
cin>>st;
}
void out_ans(int k)
{
cout<<c[k/16]<<c[k%16];
}
void work()
{
int r,g,b,sum=0,ki=1;
for(int i=6;i>0;i--)
{
int k;
if(st[i]<='Z' && st[i]>='A')
k=st[i]-'A'+10;
else
k=st[i]-'0';
sum=sum+k*ki;
ki*=16;
if(i==1)
r=sum;
if(i==3)
g=sum;
if(i==5)
b=sum;
if(i%2==1)
sum=0,ki=1;
}
r=255-r;g=255-g;b=255-b;
cout<<"#";
out_ans(r);
out_ans(g);
out_ans(b);
}
int main()
{
read_in();
work();
return 0;
}?
?
D題 P7108
?
題目背景
遙遠(yuǎn)的圣地生長(zhǎng)著一棵不為人知的靈樹，或有萬山之高。
但有一日，藏匿于根系的腐朽力量爆發(fā)，靈樹已無法支撐往日屹立沖天的高度。
題目描述
靈樹最初的形態(tài)可以看作一棵高度為?{10}^{ {10}^{ {10}^{10}}}10101010?的滿?aa?叉樹，高度定義為根結(jié)點(diǎn)到葉子結(jié)點(diǎn)之間的邊數(shù)。
受腐朽力量影響，靈樹只能維持高度恰好為?hh?的滿?bb?叉樹形態(tài)。為了轉(zhuǎn)換至該形態(tài)，靈樹有兩種魔法：
- 移花：選擇一條邊?u \to vu→v（uu?是?vv?的父結(jié)點(diǎn)），移除這條邊以及以?vv?為根的整棵子樹。
- 接木：選擇一條邊?u \to vu→v（uu?是?vv?的父結(jié)點(diǎn)）和一個(gè)結(jié)點(diǎn)?ww（ww?不能是?vv?子樹中或已移除的結(jié)點(diǎn)），將這條邊原先?uu?一端改接到?ww。該魔法只能在根結(jié)點(diǎn)到?\boldsymbol{u}u?之間的邊數(shù)?\le 10^{10^{10}}≤101010?時(shí)使用。
靈樹累積的魔法力量有限，它不得不用最少次數(shù)的魔法完成轉(zhuǎn)換。這是個(gè)漫長(zhǎng)的過程，即使次數(shù)最少也會(huì)顯得異常大，你只需要求出最少次數(shù)對(duì)?10^9 + 7109+7?取模的結(jié)果。
輸入格式
輸入首行給定數(shù)據(jù)組數(shù)?TT。
接下來?TT?行，每行包含三個(gè)整數(shù)?a,b,ha,b,h，表示一組數(shù)據(jù)。
輸出格式
對(duì)于每組數(shù)據(jù)輸出一行一個(gè)整數(shù)，表示該數(shù)據(jù)的答案對(duì)?10^9 + 7109+7?取模的結(jié)果。
輸入輸出樣例
輸入 #1復(fù)制
2 1 2 1 3 2 1
輸出 #1復(fù)制
2 7
說明/提示
【樣例解釋 #1】
下為?a=1a=1，b=2b=2，h=1h=1?時(shí)的兩步轉(zhuǎn)換過程，圖中高度極大的冗余子樹已用省略號(hào)代替。
可以證明，該數(shù)據(jù)的答案不可能低于?22。
【數(shù)據(jù)規(guī)模與約定】
本題采用捆綁測(cè)試。你必須通過 Subtask 中所有的測(cè)試點(diǎn)才能獲得該 Subtask 的分?jǐn)?shù)。
- Subtask #1 (3 points)：h = 0h=0。
- Subtask #2 (4 points)：a = ba=b。
- Subtask #3 (8 points)：a = 1a=1。
- Subtask #4 (8 points)：b = 1b=1。
- Subtask #5 (17 points)：h \le 10h≤10。
- Subtask #6 (15 points)：h \le 10^6h≤106，各測(cè)試點(diǎn)存在?\overline{a},\overlinea,b，其數(shù)據(jù)滿足?a=\overline{a}a=a，b=\overlineb=b。
- Subtask #7 (15 points)：h \le 10^6h≤106。
- Subtask #8 (30 points)：無特殊限制。
所有測(cè)試點(diǎn)（樣例除外）均含有?10^6106?組數(shù)據(jù)，即?T = 10^6T=106。請(qǐng)務(wù)必采用較快的 IO（輸入/輸出）方式。
對(duì)于所有的數(shù)據(jù)，保證?1 \le a,b \le 10^91≤a,b≤109，0 \le h \le 10^90≤h≤109。
?
題意：
理解為無限高度的滿a叉樹通過割邊舍棄這條邊，或者把這條邊接到點(diǎn)上，運(yùn)用這兩個(gè)操作變成高度為h的滿b叉樹。
?
題解：
分類討論，推公式。
當(dāng)b>a?的時(shí)候的公式很好推，只需要不斷的拆h+1層的分支去補(bǔ)，然后再把剩下的h+1層全割掉。很容易推出來公式為 a*(b^h)
當(dāng)a>=b時(shí)，公式有點(diǎn)難推，當(dāng)時(shí)我推出來的是(a-b)(b^h-1)/(b-1)+a*(b^h)，但是不知道為什么錯(cuò)了。
?
但是，即使我們改不對(duì)這道題，我們也還是要在其中學(xué)到知識(shí)。
?
這題正解需要 “逆元” 來維護(hù)，以前就常聽逆元是什么了，現(xiàn)在稍微學(xué)習(xí)一下。
?
什么是逆元？
如果 b?* i?
逆元有什么作用呢？當(dāng)計(jì)算a / b (mod p) 的值時(shí)，如果b很大，則經(jīng)度可能會(huì)爆，則我們可以轉(zhuǎn)換為 a * i （mod p），這樣子就能避免經(jīng)度的損失。
?
如何求逆元？
現(xiàn)在先學(xué)了一種快速冪求逆元的方法先。
這個(gè)方法運(yùn)用了費(fèi)馬小定理：若gcd（a，p）==1 ，則 存在?
那么有?
?
?
?
實(shí)話講現(xiàn)在越打信心越低，慢慢來吧。
?
?
?
?
?
?
?
?
?
