<style> .reveal .slides { text-align: left; font-size:35px } </style> # third week 2023 I2CP pretrain - MAT and Bitwise and perfix 2022/12/15 ---- 上週的解題狀況實在不甚理想，請有想要打比賽或是修課的同學多花一點時間在解題目上。 若是檢討到已經寫完的題目也可以聽聽看我們的解法，或者去寫其他題目。 同時，對於上週，希望大家寫掉的是 B , C , D , E , F , G ,I ---- ## pA 想法 $A_n = K * A_{n - 1} + L * A_{n - 2}$ $\begin{bmatrix} K&1\\L & 0 \\\end{bmatrix} * \begin{bmatrix} f[1] \\ f[0] \end{bmatrix}$ ---- ## pB 想法 sum = 0, f[1] = 1, f[0] = 0; $\begin{bmatrix} 1&1&0\\0 & 1 & 1 \\ 0 & 1 & 0 \\ \end{bmatrix} * \begin{bmatrix} sum \\ f[1] \\ f[0] \\ \end{bmatrix}$ ---- ## pC 想法 $\begin{bmatrix} 3&1\\1 & 3 \\\end{bmatrix} * \begin{bmatrix} 1 \\ 0\end{bmatrix}$ ---- ## pD 想法 最簡單的簽到題，只看測資感覺也會矇對的題目，基本上這題沒寫感覺是沒動腦。 使用性質:xor的運算 ```cpp= cout<<(x^y)<<"\n"; ``` ---- ## pE 想法 打比賽的要對小數字敏感一點，觀察它們可以幹嘛，像是這題的範圍會<230，那就直接對輸入進來的數字暴力打表就可以了。 每次做and紀錄答案 這題的話記憶體跟時間都沒有問題。 使用性質:and運算，打表處理 ---- ## 實作 ```cpp= #include<iostream> #include<cstring> using namespace std; int t,n,q,m,ans[230]={0}; int main(){ cin>>t; while(t--){ memset(ans,0,sizeof(ans)); //初始化 cin>>n>>q; while(n--){ cin>>m; for(int i=1;i<230;i++) //對範圍打表 ans[i]=max(ans[i],(i&m)); //按照題目要求 } while(q--) cin>>m,cout<<ans[m]<<"\n"; } } ``` ---- ## pF 想法 上課有講過，觀察規律，按照規律直接實作就會變成水題 (但這題蠻難的) 使用性質:觀察規律 ---- 實作 ```cpp= #include<iostream> using namespace std; long long a,b,now,cnt; int main(){ for(int t=1;true;t++){ cout<<"Case "<<t<<": "; cin>>a>>b; if(a==0&&b==0)break; a--,now=2,cnt=0; while(now<=1e13){ //到值域上限就好 long long aa=0,bb=0; aa+=a/now*(now/2); aa+=max(0LL,a-(a/now*now)-(now/2)+1); bb+=b/now*(now/2); bb+=max(0LL,b-(b/now*now)-(now/2)+1); cnt+=bb-aa; now<<=1; //每次檢查每個bit就好 } cout<<cnt<<endl; } } ``` ---- ## pG 想法 上課例題，會發現他就是前綴裸題問最大 使用性質:前綴和 ---- 實作核心代碼 ```cpp= for (int i = k + 1; i <= n; i++){ //k是長度限制 ans = max(ans, sum[i]-sum[i-k]); } cout<<ans<<"\n"; ``` ---- ## pH 想法 二維前綴和以及二維差分，問後面q次詢問的座標再前面m次是否包含在裡面 (若使用vector動態開點可以二維，若不是則只能降維) 使用性質:前綴和，差分 沒有要讓你們過la ---- ## pI 想法 先求出差分數組，然後再求出 $arr_1 ~ arr_n$的gcd(最大公因數) 使用性質:差分 ---- ```cpp= #include <iostream> #include<algorithm> using namespace std; int main() { int x; while (cin >> x && x){ int a[1005]; int N = 1; a[0] = x; while (cin >> x && x) a[N++] = x; int d = abs(a[0] - a[1]); for (int i = 1; i < N-1; i++){ d = __gcd(d, abs(a[i] - a[i+1])); } cout << d << "\n"; } return 0; } ``` ---- ## pJ 想法 先求出差分數組，然後可以檢視三個操作分別會對差分數組造成甚麼影響 使用性質:差分 ---- ```cpp= int main(){ int t,n; cin>>t; while(t--){ cin>>n; int all[n]; int f[n]; for(int i=0;i<n;i++){ cin>>all[i]; if(i>0)f[i]=all[i]-all[i-1]; } f[0]=all[0]; int ans=0; for(int i=1;i<n;i++){ ans+=abs(f[i]); if(f[i]<0)f[0]+=f[i]; } ans+=abs(f[0]); cout<<ans<<endl; } } ```