白书 出类拔萃–中级篇 I
前言
各位dalao看我发文就知道我与别人的七夕形成了鲜明的对比 QAQQQQQ
不过今天最后1min内AC了一题，真香~
最后祝各位有男女票的99啦，没男女票的早日脱单 ヾ(o◕∀◕)ﾉヾ
- 尺取法
https://blog.csdn.net/consciousman/article/details/52348439 - 反转（开关）
https://blog.csdn.net/qq_31805821/article/details/52879949
Subsequence - POJ - 3061
题意
给定一组序列和一个数S，求一个区间和大于或等于S的区间，要求区间长度最小，输出这个区间长度
思路1 —— 二分
二分是显然的嘛，二分区间长度，如果有能大于或等于S的区间就缩小长度，否则放大长度，最后的就是答案了
思路2 —— 尺取法
当区间和 < S时则扩右区间，>= S时则更新一下答案，然后缩左区间，最后如果区间和 < S还不能扩展的话就可以break了
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N];
int main(){
int t;
scanf("%d", &t);
while(t--){
int n;
ll lower;
scanf("%d%lld", &n, &lower);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
ll sum = 0;
int l = 1, r = 1;
int ans = inf;
while(true){
while(r <= n && sum < lower) sum += a[r++];
if(sum < lower) break;
ans = min(ans, r - l);
sum -= a[l++];
}
if(ans == inf) puts("0");
else printf("%d\n", ans);
}
}
Jessica’s Reading Problem - POJ - 3320
题意
给定一段序列，要求选出一个区间，包含序列中出现的数，并且该区间长度最小，输出这个区间长度
思路 —— 尺取法
首先用set得出数的种类数量
用尺取法，如果还没包含所有的数则扩展右区间，否则更新答案然后缩左区间
这个过程中，可以用map记录下在当前区间中数出现了几次，以便维护本区间数的种类
具体来讲就是，扩右区间时若该数出现0次，那么当前区间种类数+1，缩左区间时若该数出现1次，那么当前区间种类数-1
最后如果既不能向右扩展，区间种类数又比序列数的种类数量少，就break
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
using namespace std;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N];
map<int, int> mp;
set<int> st;
int main(){
int n;
while(~scanf("%d", &n)){
mp.clear();
st.clear();
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
st.insert(a[i]);
}
int l = 1, r = 1;
int sum = 0, anssum = st.size();
int ans = inf;
while(true){
while(r <= n && sum < anssum){
if(mp[a[r]] == 0){
sum++;
}
mp[a[r]]++;
r++;
}
ans = min(ans, r - l);
if(mp[a[l]] == 1){
sum--;
}
if(r > n && sum < anssum) break;
mp[a[l]]--;
l++;
}
printf("%d\n", ans);
}
}
Face The Right Way - POJ - 3276
题意
给定一段序列B和F，要求在其中选出长度为K的区间进行翻转，翻转时区间中的B会变为F，F会变为B，现在要求整段序列都变为F，求最小的操作次数M和最小的K（K > 1）
思路 —— 开关问题
看了题解真的跪了 orz
用sum维护这个数翻转后对其后区间的影响，那么被影响的数最终的影响则是 a[i] + sum
那么如何维护sum呢，遍历到某个数时加上某个数的影响 sum += f[i]，同时减去前面已经失去影响的数的影响 sum -= f[i - k + 1]
然后枚举K就可以了
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;
const int N = 5000 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N], f[N];
int judge(int k, int n){
int sum = 0, cnt = 0;
for(int i = 1; i <= n - k + 1; i++){
if((a[i] + sum)&1){
f[i] = 1;
cnt++;
}else{
f[i] = 0;
}
sum += f[i];
if(i >= k) sum -= f[i - k + 1];
}
for(int i = n - k + 2; i <= n; i++){ //已不能再产生影响的，即区间已遍历到最后，做检查
if((a[i] + sum)&1) return -1;
sum -= f[i - k + 1];
}
return cnt;
}
int main(){
int n;
while(~scanf("%d", &n)){
for(int i = 1; i <= n; i++){
getchar();
if(getchar() == 'B') a[i] = 1;
else a[i] = 0;
}
int ansk = 1, anscnt = n;
for(int k = 1; k <= n; k++){
int tmp = judge(k, n);
if(tmp != -1 && tmp < anscnt){
ansk = k;
anscnt = tmp;
}
}
printf("%d %d\n", ansk, anscnt);
}
}
Fliptile - POJ - 3279
题意
给定一个01矩阵，可以选择其中任意多个位置进行翻转，每次翻转会对翻转的那个格子和其上下左右四个格子（如果有）产生影响，0变为1或1变为0，问如何翻转才能使得其全变为0
思路
看了题解也是跪了 orz
枚举第一行的摆法(2^15规模)，因为第一行确定了下来，那么就只能过通过第二行消除第一行的1，此时第二行也确定了下来，那么就只能够通过第三行消除第二行的1，以此类推，到最后一行，判定是否全为0，若全为0则对比答案以及更新答案
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 15 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int Gbak[N][N], G[N][N], ans[N][N], cur[N][N];
void solve(int n, int m, int& sum){
int cnt = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
G[i][j] = Gbak[i][j];
}
}
for(int j = 1; j <= m; j++){
if(cur[1][j] == 0) continue;
cnt++;
G[1][j] ^= 1;
for(int k = 0; k < 4; k++){
int newi = 1 + dx[k];
int newj = j + dy[k];
if(newi < 1 || newj < 1 || newi > n || newj > m) continue;
G[newi][newj] ^= 1;
}
}
for(int i = 2; i <= n; i++){
for(int j = 1; j <= m; j++){
if(G[i - 1][j] == 0) { cur[i][j] = 0; continue;}
G[i][j] ^= 1;
cur[i][j] = 1;
cnt++;
for(int k = 0; k < 4; k++){
int newi = i + dx[k];
int newj = j + dy[k];
if(newi < 1 || newj < 1 || newi > n || newj > m) continue;
G[newi][newj] ^= 1;
}
}
}
if(cnt >= sum) return;
bool flag = true;
for(int j = 1; j <= m; j++){
if(G[n][j] == 1){
flag = false;
break;
}
}
if(flag){
sum = cnt;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
ans[i][j] = cur[i][j];
}
}
}
}
void dfs(int i, int n, int m, int& sum){
if(i > m){
solve(n, m, sum);
return;
}
cur[1][i] = 0;
dfs(i + 1, n, m, sum);
cur[1][i] = 1;
dfs(i + 1, n, m, sum);
cur[1][i] = 0;
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &Gbak[i][j]);
}
}
int sum = inf;
dfs(1, n, m, sum);
if(sum == inf) puts("IMPOSSIBLE");
else{
//printf("%d\n", sum);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
printf("%d", ans[i][j] );
if(j < m) putchar(' ');
}
puts("");
}
}
}
}
Matrix Power Series - POJ - 3233
题意
求矩阵 A^1 + A^2 + … + A^k
思路
二分求和，记sum(k) = A^1 + A^2 + … + A^k，则
若k为奇数，则 sum(k) = sum(k/2) + A^(k/2) * sum(k/2) + A^k
若k为偶数，则 sum(k) = sum(k/2) + A^(k/2) * sum(k/2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
const int N = 30 + 5;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct matrix{
int met[N][N];
};
matrix a;
int mod;
matrix multilply(matrix a, matrix b){
matrix c;
for(int i = 1; i < N; i++){
for(int j = 1; j < N; j++){
c.met[i][j] = 0;
for(int k = 1; k < N; k++){
c.met[i][j] += a.met[i][k] * b.met[k][j];
if(c.met[i][j] >= mod) c.met[i][j] %= mod;
}
}
}
return c;
}
matrix add(matrix a, matrix b){
matrix c;
for(int i = 1; i < N; i++){
for(int j = 1; j < N; j++){
c.met[i][j] = a.met[i][j] + b.met[i][j];
if(c.met[i][j] >= mod) c.met[i][j] %= mod;
}
}
return c;
}
matrix quickPow(int k){
matrix base = a, ans;
for(int i = 1; i < N; i++){
for(int j = 1; j < N; j++){
if(i == j) ans.met[i][j] = 1;
else ans.met[i][j] = 0;
}
}
while(k){
if(k&1) ans = multilply(ans, base);
base = multilply(base, base);
k >>= 1;
}
return ans;
}
matrix dfs(int k){
if(k == 1) return a;
matrix tmp = dfs(k/2);
if(k&1) return add(add(tmp, multilply(quickPow(k/2), tmp)), quickPow(k));
else return add(tmp, multilply(quickPow(k/2), tmp));
}
int main(){
int n, k;
while(~scanf("%d%d%d", &n, &k, &mod)){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
scanf("%d", &a.met[i][j]);
}
}
matrix ans = dfs(k);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
printf("%d", ans.met[i][j]);
if(j < n) putchar(' ');
}
puts("");
}
}
}
Sumdiv - POJ - 1845
题意
求矩阵 A^B 的所有因子和
思路
（本题不是白书的）
和上一题差不多，将A表示为 n1^k1 * n2^k2 * …，其中n为质因子，k1为其所含个数，记sum(a, b) = a^0 + a^1 + … + a^b，那么不难发现A^B的所有因子和就是 sum(n1, k1) * sum(n2, k2) * …（用纸和笔推一推就明白了）
因此将A进行质因数分解，在此之前打张表，注意不要打到5e7，会MLE，打到sqrt(5e7)就行，再对A进行质因数分解，最后用上题结论解即可
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 50000 + 15;
const int M = 5133 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
const int MOD = 9901;
bool used[N];
int prime[M], pp;
int fac[33], pfac;
int faccnt[33];
void getPrime(){
memset(used, true, sizeof(used));
for(int i = 2; i < N; i++){
if(used[i]){
prime[pp++] = i;
}
for(int j = 0; i*prime[j] < N; j++){
used[i*prime[j]] = false;
if(i%prime[j] == 0){
break;
}
}
}
}
void getFac(int x){
memset(faccnt, 0, sizeof(faccnt));
int i = 0;
pfac = 0;
while(x != 1 && i < pp){
if(x%prime[i] == 0){
fac[pfac] = prime[i];
while(x%prime[i] == 0){
faccnt[pfac]++;
x /= prime[i];
}
pfac++;
}
i++;
}
if(x != 1){
fac[pfac] = x;
faccnt[pfac++] = 1;
}
}
int quickPow(int a, int b){
int ans = 1, base = a%MOD;
while(b){
if(b&1) ans = ans*base;
base = base*base;
b >>= 1;
if(ans >= MOD) ans %= MOD;
if(base >= MOD) base %= MOD;
}
return ans >= MOD ? ans : ans%MOD;
}
int dfs(int a, int b){
if(b == 1) return a >= MOD ? a%MOD : a;
int tmp = dfs(a, b/2);
if(tmp >= MOD) tmp %= MOD;
if(b&1) return (tmp + quickPow(a, b/2)*tmp + quickPow(a, b))%MOD;
else return (tmp + quickPow(a, b/2)*tmp)%MOD;
}
int main(){
getPrime();
//printf("%d\n", pp);
int a, b;
while(~scanf("%d%d", &a, &b)){
if(b == 0){
puts("1");
}else{
getFac(a);
int res = 1;
for(int i = 0; i < pfac; i++){
res = res * (dfs(fac[i], b*faccnt[i]) + 1);
if(res >= MOD) res %= MOD;
}
printf("%d\n", res);
}
}
}
