CF1016賽后總結

文章目錄

前言
T1:Ideal Generator
T2：Expensive Number
T3:Simple Repetition
T4：Skibidi Table
T5:Min Max MEX
T6:Hackers and Neural Networks
T7:Shorten the Array

前言

由于最近在半期考試，更新稍微晚了一點，還望大家見諒 ~~（保佑我考好一點）~~。

T1:Ideal Generator

題目翻譯：

如果 $[a_1,a_2,\dots,a_k]=[a_k,a_{k-1}\dots,a_1]$ ，我們稱一個由 $k$ 個正整數組成的數組 $a$ 為回文數組。例如，數組 $[1, 2, 1]$ 和 $[5, 1, 1, 5]$ 是回文的，而數組 $[1, 2, 3]$ 和 $[21, 12]$ 則不是。
我們稱一個數 $k$ 為理想生成器，如果任意整數 $n(n\ge k)$ 都可以表示為恰好長度為 $k$ 的回文數組的元素之和。數組中的每個元素都必須大于 $0$ 。
例如，數字 $1$ 是一個理想生成器，因為任何自然數 $n$ 都可以使用數組 $[n]$ 生成。然而，數字 $2$ 不是理想生成器——不存在長度為 $2$ 且總和為 $3$ 的回文數組。
判斷給定的數字 $k$ 是否為理想生成器。

附上樣例：

輸入：

輸出：

YES
NO
YES
YES
NO

~~從樣例看出好像是奇數就行。~~

這道題其實很好想，我們這么思考：當 $k$ 是奇數時，中間必然會有一個單獨的數與自己相對應，所以中間這個數很自由，可以是任何正整數，但如果 $k$ 是偶數，那么就要左右能各分一半，否則就不成立。（看不懂的自己思考。）

~~代碼當課后習題了……~~

T2：Expensive Number

題目翻譯：

一個正整數 $n$ 的成本被定義為該數字nn除以其各位數字之和的結果。

例如，數字 $104$ 的成本是 $\cfrac{104}{1+0+4}=20.8$ ，數字 $111$ 的成本是 $\cfrac{111}{1+1+1}=37$ 。

給定一個不含前導零的正整數 $n$ 。你可以從數字 $n$ 中移除任意數量的數字（包括不移除），使得剩余數字至少包含一位且嚴格大于零。剩余數字不能重新排列。因此，你可能會得到含有前導零的數字。

例如，給定數字 $103554$ 。如果你決定移除數字 $1$ 、 $4$ 和一個數字 $5$ ，你將得到數字 $035$ ，其成本為 $\cfrac{035}{0+3+5}=4.375$ 。

為了使數字的成本盡可能小，你需要移除的最少數字數量是多少？

附上樣例：

輸入：

輸出：

~~又是一道水題……~~

題目中說了：要讓成本盡可能的小。那我們看看成本最小是多少嘛。

毫無疑問，當然是 $1$ 了，當這個數只有一位時正好滿足（不信可以試試看）。

所以，題目其實就是在變相的詢問把一個數變成一位數所刪掉的最小數字數量。

因為可以有前導零，所以對于某一位數 $i$ ，從 $i ? 1$ 到 $1$ 需要把所有數字刪掉，而從 $n$ 到 $i$ 只需要把不是零的數刪掉就行了。

現在最主要的問題就在于這個 $i$ 是第幾位。

既然我們要盡可能的少刪數，那么我們就要盡可能的多優化，怎么優化呢？

對于 $i$ 后面來講，所有的數都會被刪，沒有例外，所以無法優化。而對于 $i$ 前面來講，只要不是 $0$ 才會被刪，也就是說是 $0$ 就不會被刪咯。這就是我們優化的地方：讓盡可能多的 $0$ 到前面去。所以 $i$ 就是從低到高第一個不是 $0$ 的那一位，然后寫代碼就對了。

~~代碼也很簡單，又多了一道課后習題……~~

T3:Simple Repetition

題目翻譯：

帕莎熱愛質數！在嘗試尋找生成質數的新方法時，他對網上發現的一個算法產生了興趣：

要獲得新數字 $y$ ，只需將數字 $x$ 的十進制表示（不含前導零）重復 $k$ 次。

例如，當 $x = 52$ 且 $k = 3$ 時，得到 $y = 525252$ ；當 $x = 6$ 且 $k = 7$ 時，得到 $y = 6666666$ 。

帕莎非常希望生成的數字 $y$ 是質數，但他還不知道如何驗證這個算法生成的數字是否為質數。請幫助帕莎判斷 $y$ 是否為質數！

附上樣例：

輸入：

輸出：

NO
NO
YES
NO

這題挺簡單，我直接把我的題解搬下來：

首先最好想的情況： $k = 1$ 時，這時候直接判斷 $n$ 是不是質數就對了，讓我們來看其他情況。

如果 $n = 1$ 且 $k\not=1$ ，那么我們可以得到的是除了 $k = 2$ 的情況，其他情況下都是合數，具體證明大家可以自己去搜，過程過長，不在這里贅述了。

如果 $n\not=1$ 且 $k\not=1$ ，那么這個數就必定是質數，原因：任何一個 $\overline{\underbrace{a_1a_2a_3\dots a_1a_2a_3\dots}_{k\text{個循環}}}$ 的數必定能寫成這樣的形式： $\overline{a_1a_2a_3\dots}\times\underbrace{\underbrace{100\dots}_{n\text{個數}}\underbrace{100\dots}_{n\text{個數}}\dots}_{k-1\text{個循環}}1$ ，所以它必然是一個合數。

代碼實現：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,k;
bool pd(int x)
{for(int i=2;i*i<=x;i++){if(x%i==0){return false;}}return true;
}
signed main()
{cin>>t;while(t--){cin>>n>>k;if(n>=1&&k>1){if(n==1&&k==2){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}else if(n>1&&k==1){cout<<(pd(n)?"YES":"NO")<<endl;}else if(n==1&&k==1){cout<<"NO"<<endl;}}return 0;
}

T4：Skibidi Table

題目翻譯：

瓦迪姆喜歡用整數填充方形表格。但今天他想出了一種有趣的填充方式！例如，我們有一個大小為 $2\times2$ 的表格，行號從上到下遞增，列號從左到右遞增。我們在左上角單元格放置 $1$ ，右下角放 $2$ ，左下角放 $3$ ，右上角放 $4$ 。這就是他全部的樂趣所在！

幸運的是，瓦迪姆現在有一個大小為 $2^n\times2^n$ 的表格。他計劃用 $1$ 到 $2^{2n}$ 的升序整數來填充它。為了填充如此大的表格，瓦迪姆會將其劃分為 $4$ 個相同的小方形表格，首先填充左上角的子表，然后是右下角的子表，接著是左下角的子表，最后是右上角的子表。每個子表會繼續被劃分成更小的子表，直到表格尺寸縮小到 $2\times2$ 為止，此時他會按照上述順序進行填充。

現在瓦迪姆迫不及待要開始填充表格，但他有 $q$ 個兩類問題：

位于第 $x$ 行第 $y$ 列的單元格中的數字是多少；

數字 $d$ 會出現在哪個單元格坐標中。

請幫助回答瓦迪姆的問題。

看到的第一眼：分治。

第二眼……額，沒有第二眼了（已經 $\color{green}{AC}$ 了）。

這道題非常非常非常簡單，對于第一種提問，我們只需要設一個 dfs 就行，然后帶上五個參數，分別表示當前在哪一行、當前在哪一列、當前格子的尺寸、當前的取值下限、當前的取值上限，然后我們就可以寫出如下轉移：

$\begin{cases}\operatorname{dfs1}(x,y,\frac{l}{2},sl,sl+\frac{(sr-sl+1)}{4}-1)&\operatorname{if}1\le x\le \frac{l}{2},1\le y \le \frac{l}{2}\\\operatorname{dfs1}(x-\frac{l}{2},y-\frac{l}{2},\frac{l}{2},sl+\frac{(sr-sl+1)}{4},sl+\frac{(sr-sl+1)}{2}-1)&\operatorname{if}\frac{l}{2}\lt x\le l,\frac{l}{2}\lt y \le l\\\operatorname{dfs1}(x-\frac{l}{2},y,\frac{l}{2},sl+\frac{(sr-sl+1)}{2},sl+\frac{(sr-sl+1)}{4}\times3-1)&\operatorname{if}\frac{l}{2}\lt x\le l,1\le y \le \frac{l}{2}\\\operatorname{dfs1}(x,y-\frac{l}{2},\frac{l}{2},sl+\frac{(sr-sl+1)}{4}\times3,sr)&\operatorname{if}1\le x\le \frac{l}{2},\frac{l}{2}\lt y \le l\end{cases}$

（打這一段真不容易……）

第二種帶六個參數，分別是當前在哪一行、當前在哪一列、當前格子的尺寸、當前的取值下限、當前的取值上限、當前的值（這個就是輸入的那個數，一直不變），然后再手推一下就行了。

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,q,pw_2[66];
void dfs1(int x,int y,int l,int sl,int sr)
{if(l==1){cout<<sl<<endl;return;}if(x>=1&&x<=l/2&&y>=1&&y<=l/2){dfs1(x,y,l/2,sl,sl+(sr-sl+1)/4-1);}else if(x>l/2&&x<=l&&y>l/2&&y<=l){dfs1(x-l/2,y-l/2,l/2,sl+(sr-sl+1)/4,sl+(sr-sl+1)/2-1);}else if(x>l/2&&x<=l&&y>=1&&y<=l/2){dfs1(x-l/2,y,l/2,sl+(sr-sl+1)/2,sl+(sr-sl+1)/4+(sr-sl+1)/2-1);}else{dfs1(x,y-l/2,l/2,sl+(sr-sl+1)/2+(sr-sl+1)/4,sr);}
}
void dfs2(int x,int y,int s,int l,int sl,int sr)
{if(l==1){cout<<x<<" "<<y<<endl;return;}if(s>=sl&&s<=sl+(sr-sl+1)/4-1){dfs2(x,y,s,l/2,sl,sl+(sr-sl+1)/4-1);}else if(s>=sl+(sr-sl+1)/4&&s<=sl+(sr-sl+1)/2-1){dfs2(x+l/2,y+l/2,s,l/2,sl+(sr-sl+1)/4,sl+(sr-sl+1)/2-1);}else if(s>=sl+(sr-sl+1)/2&&s<=sl+(sr-sl+1)/2+(sr-sl+1)/4-1){dfs2(x+l/2,y,s,l/2,sl+(sr-sl+1)/2,sl+(sr-sl+1)/2+(sr-sl+1)/4-1);}else{dfs2(x,y+l/2,s,l/2,sl+(sr-sl+1)/2+(sr-sl+1)/4,sr);}
}
string s;
signed main()
{pw_2[0]=1;for(int i=1;i<=65;i++){pw_2[i]=pw_2[i-1]<<1;}cin>>t;while(t--){cin>>n>>q;int x=0,y=0;while(q--){cin>>s;if(s=="->"){cin>>x>>y;dfs1(x,y,pw_2[n],1,pw_2[2*n]);}else{cin>>x;dfs2(1,1,x,pw_2[n],1,pw_2[n*2]);}}}return 0;
}

T5:Min Max MEX

題目翻譯：

給定一個長度為 $n$ 的數組 $a$ 和一個數字 $k$ 。

子數組定義為數組中一個或多個連續元素組成的序列。你需要將數組 $a$ 分割成 $k$ 個互不重疊的子數組 $b_1,b_2,\dots,b_k$ ，這些子數組的并集等于整個數組。此外，你需要最大化 $x$ 的值，該值等于所有子數組的最小 $\operatorname{MEX}(b_i)$ （針對 $i\in[1..k]$ ）。

$\operatorname{MEX}(v)$ 表示數組 $v$ 中未出現的最小非負整數。

觸發關鍵詞：最小的最大。

第一眼算法：二分答案。

這個二分答案我就不多說了，我們主要看這個判斷函數怎么寫。

題目中還有一條信息我們沒用：切成 $k$ 份。

正向思路：直接枚舉，看看從那切成 $k$ 份滿足題意。

這樣的話還不如不寫二分答案……

逆向思路：按照當前二分出來的 $\operatorname{MEX}$ 來分割，看看是否比 $k$ 份多。

非常好的方案，只需要循環一下然后看看能分割成幾份就行了！

代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,k,a[200006];
bool check(int x)
{int t=0,num=0;vector<int>v(x+6,0);//標記數組for(int i=1;i<=n;i++){if(!v[a[i]]&&a[i]<=x){v[a[i]]=1;if(a[i]<x){num++;}}if(num>=x){t++;for(int j=0;j<v.size();j++){v[j]=0;}num=0;}}return t>=k;
}
signed main()
{cin>>t;while(t--){cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}int l=0,r=n,mid=0,ans=0;while(l<=r){mid=l+r>>1;if(check(mid)){ans=mid;l=mid+1;}else{r=mid-1;}}cout<<ans<<endl;}return 0;
}