傳送門
參考資料：
[1]:官方題解（提取碼：rkcq）
[2]:标程（提取碼：0tiq）
B.Crazy Binary String（字首和）
•題意
給你一個隻包含 0,1 的串 s；
求滿足 0 與 1 的個數相同的子串和子序列；
輸出這兩個串的最大長度；
•題解
求解滿足條件的最大子串長度類似于這道題：?
而最大子序列就是 2×min(0的個數,1的個數);
•Code
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define GCD(a,b) __gcd(a,b) 4 #define ll long long 5 const int maxn=1e5+50; 6 7 int n; 8 char s[maxn]; 9 int a[maxn]; 10 int b[maxn]; 11 map<int ,int >f; 12 13 void Solve() 14 { 15 f.clear(); 16 a[0]=b[0]=0; 17 f[0]=0; 18 19 int zero=0; 20 int one=0; 21 int len=strlen(s+1); 22 for(int i=1;i <= len;i++) 23 { 24 if(s[i] == '1') 25 one++; 26 else 27 zero++; 28 a[i]=a[i-1]+(s[i] == '1'); 29 b[i]=b[i-1]+(s[i] == '0'); 30 } 31 32 int ans=0; 33 for(int i=1;i <= len;++i) 34 { 35 int cur=a[i]-b[i]; 36 if(f.count(cur)) 37 ans=max(ans,i-f[cur]); 38 else 39 f[cur]=i; 40 } 41 printf("%d %d\n",ans,min(one,zero)*2); 42 } 43 int main() 44 { 45 scanf("%d",&n); 46 scanf("%s",s+1); 47 Solve(); 48 49 return 0; 50 }
D.Big Integer（數論）
•參考資料
[1]:韻意
•題意
定義 $A_{n}=\underbrace{1......1}_{n}$；
求滿足 $A_{i^j}$ ≡ $0(mod\ p)$ 的個數，其中 1 ≤ i ≤ n , 1 ≤ j ≤ m；
•題解
參考自資料[1]；
首先将 An 化$A_{n}=\frac{10^{n}-1}{9}$；
$A_{i^j}$ ≡ $0(mod p)$ 轉化$\frac{10^{n}-1}{9}$≡ $0(mod p)$；
現在先不考慮 p = 3 的情況，那麼 $\frac{1}{9}\ mod\ p=inv_{9}$；
$\frac{10^{n}-1}{9}$≡ $0(mod p)$ 轉化為 $(10^{n}-1)\cdot inv_{9}$ ≡ $0(mod p)$；
因為 $inv_{9}\ mod\ p \neq 0$，是以隻能是 $(10^{n}-1)\ mod\ p \neq 0$；
即 $(10^{n}-1)$ ≡ $1(mod p)$；
還記得費馬小定理嗎？
$(a^{p-1})$ ≡ $1(mod p)$；
條件是 GCD(a,p) = 1;
是以，現在也不考慮 p = 2 , 5 的情況；
這樣的話，GCD(10,p) = 1;
那麼 10n ≡ 10n%(p-1);
也就是說目前 mod p 的循環節的長度為 p-1；
但循環節的長度又沒有可能是比 p-1 更小的 d 呢？
有，并且 d 滿足 d | p-1；
這樣的話，隻需在 $O(\sqrt{p-1})$ 枚舉所有 p-1 的因子 fac 即可；
判斷 fac 是否為循環節的條件是 10fac mod p 是否等于 1 ；
并令 d 等于滿足 10fac mod p = 1 的最小的 fac；
求出最小循環節後，就是要找滿足 ij%d = 0 的 i,j 組合了；
首先将 d 進行質因子分解：
$d=f_{1}^{x_1}\cdot\ f_{2}^{x_2}\cdot.....\cdot f_{k}^{x_k}$;
那麼，i 需要滿足：
$f_{1}^{\lceil\frac{x_1}{j}\rceil}\cdot\ f_{2}^{\lceil\frac{x_2}{j}\rceil}\cdot.....\cdot f_{k}^{\lceil\frac{x_k}{j}\rceil}$ | i;
從 1 開始周遊 j，求出目前 j 滿足條件的最小的 i，記為 g：
$g=f_{1}^{\lceil\frac{x_1}{j}\rceil}\cdot\ f_{2}^{\lceil\frac{x_2}{j}\rceil}\cdot.....\cdot f_{k}^{\lceil\frac{x_k}{j}\rceil}$;
那麼，滿足 g | i 的 i 在 n 内共有 $\lfloor\frac{n}{g}\rfloor$ 個，累加到 ans 中；
當 j ≥ max{x1,x2,...,xk} 時，就有 $g=f_{1}\cdot\ f_{2}\cdot.....\cdot f_{k}$，并且之後的 g 也不會改變；
那麼，此時，ans += $\lfloor\frac{n}{g}\rfloor$·(m-j);
對于 p = 2,3,5 的情況，單獨拿出來處理；
很容易發現：
①當 p = 2,5 時，是不存在這樣的 An 的；
②當 p = 3 時，隻有 n%3 == 0 時才會有 An%3 == 0；
也就是說 i = 3,6,9,.... 共 $\lfloor\frac{n}{3}\rfloor$ 種情況，那麼，答案就是 $\lfloor\frac{n}{3}\rfloor\cdot{m}$
•Code
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 5 int p,n,m; 6 int f[100]; 7 int x[100]; 8 9 ll qPow(ll a,ll b,ll mod) 10 { 11 ll ans=1; 12 a %= mod; 13 while(b) 14 { 15 if(b&1) 16 ans=ans*a%mod; 17 a=a*a%mod; 18 b >>= 1; 19 } 20 return ans; 21 } 22 int F() 23 { 24 int d=p-1; 25 ///i*i在int範圍内最大是2147395600 26 ///而n<=1e9 27 ///是以，将i定義為int不會越界 28 for(int i=1;i*i <= p-1;++i) 29 { 30 if((p-1)%i != 0) 31 continue; 32 33 if(qPow(10,i,p) == 1) 34 d=min(d,i); 35 if(qPow(10,(p-1)/i,p) == 1) 36 d=min(d,(p-1)/i); 37 } 38 return d; 39 } 40 int factor(int n) 41 { 42 int k=0; 43 ///判斷時用i*i判斷是否小于n 44 ///如果改成 i<=n 會TLE 45 for(int i=2;i*i <= n;i++) 46 { 47 if(n%i == 0) 48 { 49 f[++k]=i; 50 x[k]=0; 51 } 52 while(n%i == 0) 53 { 54 x[k]++; 55 n /= i; 56 } 57 } 58 if(n != 1) 59 { 60 f[++k]=n; 61 x[k]=1; 62 } 63 return k; 64 } 65 ll Solve() 66 { 67 int d=F();///求出最小的循環節長度d 68 int k=factor(d);///将d進行素因子分解 69 70 ll ans=0; 71 int maxX=*max_element(x+1,x+k+1);///求出最大的指數 72 for(int j=1;j <= m;++j) 73 { 74 int g=1; 75 for(int i=1;i <= k;++i) 76 g *= qPow(f[i],(x[i]+j-1)/j,p);///f[i]^((x[i]+j-1)/j) < p，是以，對p取模不影響 77 78 ans += n/g;///将n/g累加到ans中 79 if(j >= maxX)///如果j >= maxx 後，接下來的j求出的g相同 80 { 81 ans += 1ll*(m-j)*(n/g); 82 break; 83 } 84 } 85 return ans; 86 } 87 int main() 88 { 89 int test; 90 scanf("%d",&test); 91 while(test--) 92 { 93 scanf("%d%d%d",&p,&n,&m); 94 95 ll ans=0; 96 if(p == 3) 97 ans=1ll*n/3*m; 98 else if(p != 2 && p != 5) 99 ans=Solve(); 100 101 printf("%lld\n",ans); 102 } 103 return 0; 104 }
F.Planting Trees（單調隊列優化）
•題意
在一塊 n×n 的土地上植樹；
第(i,j) 塊有棵高為 a[ i ][ j ] 樹;
你的 boss 有強迫症，必須要找一片滿足任意兩棵樹的高度差都不超過 m 的矩形區域；
并且想要這個矩形區域面積盡可能大；
求出這個矩形區域，輸出這個矩形區域包含的樹的個數；
•題解
2019牛客暑期多校訓練營（第三場）
•Code(參考咖啡雞巨巨代碼)
手動實作deque1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e3+50; 4 5 int n,m; 6 int a[maxn][maxn]; 7 int cMax[maxn]; 8 int cMin[maxn]; 9 int p[maxn]; 10 int q[maxn]; 11 int pl,pr; 12 int ql,qr; 13 14 int Solve() 15 { 16 int ans=1; 17 for(int i=1;i <= n;++i) 18 { 19 for(int j=1;j <= n;++j) 20 cMax[j]=cMin[j]=a[i][j]; 21 22 for(int k=i;k <= n;++k) 23 { 24 for(int j=1;j <= n;++j) 25 { 26 cMax[j]=max(cMax[j],a[k][j]); 27 cMin[j]=min(cMin[j],a[k][j]); 28 } 29 30 int l=1; 31 int r=0; 32 pl=1,pr=0; 33 ql=1,qr=0; 34 35 while(r <= n) 36 { 37 if(r-l+1 == 0 || cMax[p[pl]]-cMin[q[ql]] <= m) 38 { 39 ans=max(ans,(k-i+1)*(r-l+1)); 40 41 r++; 42 43 while(pr >= pl && cMax[p[pr]] <= cMax[r]) 44 pr--; 45 p[++pr]=r; 46 while(qr >= ql && cMin[q[qr]] >= cMin[r]) 47 qr--; 48 q[++qr]=r; 49 } 50 else 51 { 52 if(p[pl] == l) 53 pl++; 54 if(q[ql] == l) 55 ql++; 56 l++; 57 } 58 } 59 } 60 } 61 return ans; 62 } 63 int main() 64 { 65 // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 66 int T; 67 scanf("%d",&T); 68 while(T--) 69 { 70 scanf("%d%d",&n,&m); 71 for(int i=1;i <= n;++i) 72 for(int j=1;j <= n;++j) 73 scanf("%d",a[i]+j); 74 75 printf("%d\n",Solve()); 76 } 77 return 0; 78 }
•待調bug
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1000; 4 5 int n,m; 6 int a[maxn][maxn]; 7 int cMax[maxn]; 8 int cMin[maxn]; 9 int p[maxn]; 10 int q[maxn]; 11 int pl,pr; 12 int ql,qr; 13 14 int Solve() 15 { 16 int ans=0; 17 18 for(int i=1;i <= n;++i)///i~k行求最優解 19 { 20 for(int j=1;j <= n;++j) 21 cMax[j]=cMin[j]=a[i][j]; 22 23 for(int k=i;k <= n;++k) 24 { 25 for(int j=1;j <= n;++j) 26 { 27 cMax[j]=max(cMax[j],a[k][j]); 28 cMin[j]=min(cMin[j],a[k][j]); 29 } 30 31 // printf("*********\n"); 32 // printf("i=%d,k=%d\n",i,k); 33 34 pl=ql=1; 35 pr=qr=0; 36 int l=1; 37 int r=1; 38 39 while(r <= n) 40 { 41 while(pr >= pl && cMax[p[pr]] <= cMax[r]) 42 pr--; 43 p[++pr]=r; 44 while(qr >= ql && cMin[q[qr]] >= cMin[r]) 45 qr--; 46 q[++qr]=r; 47 48 // printf("p[pl]=%d,q[ql]=%d\n",p[pl],q[ql]); 49 while(pr>=pl && qr>=ql && cMax[p[pl]]-cMin[q[ql]] > m) 50 { 51 l++; 52 while(pl < l) 53 pl++; 54 while(ql < l) 55 ql++; 56 } 57 if(pr >= pl && qr >= ql && cMax[p[pl]]-cMin[q[ql]] <= m) 58 ans=max(ans,(k-i+1)*(r-l+1)); 59 60 r++; 61 } 62 } 63 } 64 return ans; 65 } 66 int main() 67 { 68 // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 69 int T; 70 scanf("%d",&T); 71 72 while(T--) 73 { 74 scanf("%d%d",&n,&m); 75 for(int i=1;i <= n;++i) 76 for(int j=1;j <= n;++j) 77 scanf("%d",a[i]+j); 78 79 printf("%d\n",Solve()); 80 } 81 return 0; 82 }
•debug
1.huck資料1 6 154 96 182 36 123 57 162 79 95 53 191 137 137 136 90 28 2 65 164 144 150 186 143 89 68 76 84 111 52 130 179 134 142 76 23 170 171 答案：122.錯誤原因
bug代碼中的第 52,54 while() 語句判斷出錯；
錯誤①：應該用 p,q 的隊頭值與 l 比較，而不是索引 pl,ql 與 l 比較；
錯誤②：在使 pl或ql ++ 前，應確定 p,q 非空；
3.更正代碼
1 while(pr >= pl && p[pl] < l) 2 pl++; 3 while(qr >= ql && q[ql] < l) 4 ql++;
•Code(my style)
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1000; 4 5 int n,m; 6 int a[maxn][maxn]; 7 int cMax[maxn]; 8 int cMin[maxn]; 9 int p[maxn]; 10 int q[maxn]; 11 int pl,pr; 12 int ql,qr; 13 14 int Solve() 15 { 16 int ans=0; 17 18 for(int i=1;i <= n;++i)///i~k行求最優解 19 { 20 /** 21 cMax[j]:第j列中的第i~k行的最大值 22 cMin[j]:第j列中的第i~k行的最小值 23 */ 24 for(int j=1;j <= n;++j) 25 cMax[j]=cMin[j]=a[i][j]; 26 27 for(int k=i;k <= n;++k) 28 { 29 for(int j=1;j <= n;++j) 30 { 31 cMax[j]=max(cMax[j],a[k][j]); 32 cMin[j]=min(cMin[j],a[k][j]); 33 } 34 35 pl=ql=1; 36 pr=qr=0; 37 int l=1; 38 int r=1; 39 40 /** 41 p:單調遞減序列，記錄第i~k行,第l~r列最大值 42 q:單調遞增序列，記錄第i~k行,第l~r列最小值 43 */ 44 while(r <= n) 45 { 46 ///單調隊列正常操作 47 while(pr >= pl && cMax[p[pr]] <= cMax[r]) 48 pr--; 49 p[++pr]=r; 50 while(qr >= ql && cMin[q[qr]] >= cMin[r]) 51 qr--; 52 q[++qr]=r; 53 54 ///找到距r最遠的滿足條件的l 55 while(l <= r && cMax[p[pl]]-cMin[q[ql]] > m) 56 { 57 l++; 58 while(pr >= pl && p[pl] < l)///彈數前確定隊列非空 59 pl++; 60 while(qr >= ql && q[ql] < l)///彈數前確定隊列非空 61 ql++; 62 } 63 64 ans=max(ans,(k-i+1)*(r-l+1)); 65 r++; 66 } 67 } 68 } 69 return ans; 70 } 71 int main() 72 { 73 // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 74 int T; 75 scanf("%d",&T); 76 77 for(int i=1;i <= T;++i) 78 { 79 scanf("%d%d",&n,&m); 80 for(int i=1;i <= n;++i) 81 for(int j=1;j <= n;++j) 82 scanf("%d",a[i]+j); 83 84 printf("%d\n",Solve()); 85 } 86 return 0; 87 }
•感想
之前實作單調隊列一直都是用的STL中的deque，自己實作一下，錯誤還不少；
debug了一上午，還好debug成功了；
//bug資料 H.Magic Line（思維）
•題意
給你 n 個點，滿足 n 為偶數，并且這 n 個為不重複的整數點；
求将這 n 個點均分為兩部分的直線 L，即有 n/2 個點嚴格在 L 上方，n/2個點嚴格在 L 下方；
輸出 L 上的任意兩個點 (x1,y1),(x2,y2) 的坐标；
要 x1,y1,x2,y2 為整數，且 |x1|,|y1|,|x2|,|y2| ≤ 109;
•題解
非常有意思的一道題目；
2019牛客暑期多校訓練營（第三場） 首先，将這 n 個點（編号 1~n）按照 x 升序排列，x 相同按照 y 升序排列；
找到中間的兩個點的坐标 (xn/2,yn/2),(xn/2+1,yn/2+1);
①如果 xn/2 ≠ xn/2+1：
點 (xn/2,yn/2+INF),(xn/2+1,yn/2+1-INF) 所确定的直線可将前 n/2 個點劃分為一組，後 n/2 個點劃分為一組；
②如果 xn/2 = xn/2+1：
點 (xn/2 -1,yn/2+INF),(xn/2+1+1,yn/2+1-INF) 所确定的直線可将前 n/2 個點劃分為一組，後 n/2 個點劃分為一組；
對 ② 的些許解釋：
解釋1：為什麼要讓 x±1？
因為這樣的話，會確定 C,D 兩點确定的直線不會和 x = xn/1 -1 的點或 x=xn/2+1 +1 的點重合；
解釋2：為什麼讓 y±INF？
2019牛客暑期多校訓練營（第三場） 很容易證明 四邊形ABCD 為平行四邊形，那麼點 C,D 确定的直線過 線段A,B 的中點，剛好将 A,B 兩點劃分開；
B及其前 n/2 - 1 個點， A及其後 n/2 -1 個點；
•Code
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=2e5+50; 4 5 int n; 6 struct Point 7 { 8 int x,y; 9 bool operator < (const Point &obj) const 10 { 11 if(x != obj.x) 12 return x < obj.x; 13 return y < obj.y; 14 } 15 }p[maxn]; 16 17 int main() 18 { 19 int T; 20 scanf("%d",&T); 21 while(T--) 22 { 23 scanf("%d",&n); 24 for(int i=1;i <= n;++i) 25 scanf("%d%d",&p[i].x,&p[i].y); 26 27 sort(p+1,p+n+1); 28 29 int e=10000000; 30 int x1=p[n/2].x; 31 int y1=p[n/2].y+e; 32 int x2=p[n/2+1].x; 33 int y2=p[n/2+1].y-e; 34 35 if(x1 == x2) 36 { 37 x1--; 38 x2++; 39 } 40 printf("%d %d %d %d\n",x1,y1,x2,y2); 41 } 42 return 0; 43 }
轉載于:https://www.cnblogs.com/violet-acmer/p/11247261.html