传送门
参考资料：
[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