1、给定一个迷宫，点号表示不可行，井号表示可行。现在可以改变其中的一些井号的位置。问最少改变多少个井号可以使得从左上角到右下角存在路径。
思路：设高为$n$，宽为$m$，若井号的个数$S$小于$n+m-1$则无解。否则最多改变$n+m-1$个井号即可。令$f[x][y][k]$表示现在到达位置$(x,y)$且中途经过的点号格子数为$k$时最少经过了多少井号格子。这样进行搜索即可。搜过过程中，应该满足$kleq n+m-1$且$k+f[x][y][k]leq S$。
#include <iostream>
#include <set>
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
const int N=20;
int f[N][N][N+N];
int inq[N][N][N+N];
int h[N][N][N+N];
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
struct node
{
int x,y,p;
node(){}
node(int _x,int _y,int _p):
x(_x),y(_y),p(_p) {}
};
queue<node> Q;
void add(int x,int y,int p,int c)
{
if(!h[x][y][p]||f[x][y][p]>c)
{
h[x][y][p]=1;
f[x][y][p]=c;
if(!inq[x][y][p])
{
inq[x][y][p]=1;
Q.push(node(x,y,p));
}
}
}
class MovingCandies
{
public:
int minMoved(const vector<string> t)
{
const int n=(int)t.size();
const int m=(int)t[0].size();
int S=0;
for(int i=0;i<n;++i) for(int j=0;j<m;++j) S+=t[i][j]=='#';
if(S<n+m-1) return -1;
if(t[0][0]=='.') add(0,0,1,0);
else add(0,0,0,1);
while(!Q.empty())
{
const int x=Q.front().x;
const int y=Q.front().y;
const int p=Q.front().p;
const int c=f[x][y][p];
Q.pop();
inq[x][y][p]=0;
if(x==n-1&&y==m-1) continue;
for(int d=0;d<4;++d)
{
const int xx=x+dx[d];
const int yy=y+dy[d];
if(xx>=0&&xx<n&&yy>=0&&yy<m)
{
const int pp=p+(t[xx][yy]=='.');
const int cc=c+(t[xx][yy]=='#');
if(pp>n+m-1||pp+cc>S) continue;
add(xx,yy,pp,cc);
}
}
}
for(int i=0;i<=n+m-1;++i)
{
if(h[n-1][m-1][i]) return i;
}
return -1;
}
};
2、给定一个整数数组，每个数字可以被替换成字符ABC中的一个，相同的数组必须被相同的字符替换。问在被任意替换得到的所有不同的字符串中，包含子列ABC的串有多少个。
思路：一个简单的思路是分别枚举第一个A、第一个B、第一个C出现的位置，这样整个串被分成4部分，第一部分中不能出现A，第二部分不能出现B，第三部分不能出现C。这样复杂度是$O(N^{3})$。现在只枚举第一个A第一个B，然后后面字符任意的总数为$X$,不包含C的总数为$Y$，那么此次枚举对答案的贡献为$X-Y$。这样是$O(N^{2})$的复杂度。实现如代码所示。其中$f[i][j]=0$表示数字$i$可以被替换成字符$j$,$j=0$表示A，$j=1$表示B，$j=2$表示C。$tot[j]$表示有多少种数字有$j$种替换方式。
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
const int mod=1000000007;
const int N=3005;
int p[4][N];
int tot[4];
int f[N][4];
int appears[N];
class MappingABC
{
void init()
{
for(int i=0;i<4;++i)
{
p[i][0]=1;
for(int j=1;j<N;++j) p[i][j]=((long long)p[i][j-1]*i%mod);
}
}
void clear()
{
memset(f,0,sizeof(f));
memset(tot,0,sizeof(tot));
}
int get()
{
int ans=1;
for(int i=0;i<4;++i) ans=((long long)ans*p[i][tot[i]]%mod);
return ans;
}
int cal(int x)
{
int c=0;
for(int i=0;i<3;++i) if(f[x][i]==0) ++c;
return c;
}
void add(int x,int y)
{
--tot[cal(x)];
++f[x][y];
++tot[cal(x)];
}
void sub(int x,int y)
{
--tot[cal(x)];
--f[x][y];
++tot[cal(x)];
}
public:
int countStrings(vector<int> t)
{
const int n=(int)t.size();
for(int i=0;i<n;++i) appears[t[i]]=1;
init();
int ans=0;
const int A=0,B=1,C=2;
for(int k=0;k<2;++k)
{
const int NO_C=k==1;
for(int a=0;a<n;++a)
{
clear();
for(int i=0;i<N;++i) if(appears[i]) ++tot[3];
for(int i=0;i<a;++i) add(t[i],A);
add(t[a],B);
add(t[a],C);
if(NO_C)
{
for(int i=a+1;i<n;++i) add(t[i],C);
}
for(int b=a+1;b<n;++b)
{
if(NO_C) sub(t[b],C);
add(t[b],A);
add(t[b],C);
if(NO_C) ans=(ans-get())%mod;
else ans=(ans+get())%mod;
sub(t[b],A);
sub(t[b],C);
add(t[b],B);
}
}
}
if(ans<0) ans+=mod;
return ans;
}
};
3、构造一个长度为n的数组$A$，使得$A_{i}$和$A_{j}$互质当且仅当$|i-j|=1$。n不大于500。数组中每个数字大于1小于等于$10^{18}$。
思路：我看到的第一种思路是随机。比如有32个素数，$A$中的每个数字由11位素数构成，每次随机选取11个，判断是否可行。第二种思路如下代码所示。假设当前长度$N=2^{k}$，那么每次处理前，前$N/4$的数字是符合要求的。处理之后前$N/2$是符合要求的。为方便说明，假设整个$N$分为四段，$A,B,C,D$，一开始$A$符合要求。且$A$中的奇数位置跟 $B$的偶数位置满足不互质，$A$中的偶数位置跟 $B$的奇数位置满足不互质。那么只要处理使得$A$中的奇数位置跟 $B$的奇数位置满足不互质，$A$中的偶数位置跟 $B$的偶数位置满足不互质即可。
#include <string.h>
#include <stdio.h>
#include <vector>
using namespace std;
int check(int x)
{
for(int i=2;i*i<=x;++i) if(x%i==0) return 0;
return 1;
}
vector<int> prime;
int id;
void init()
{
for(int i=2;i<100;++i) if(check(i)) prime.push_back(i);
}
long long a[1024];
void add(int i,int t)
{
a[i]*=t;
}
class CoprimeNeighbors
{
public:
vector<long long> findAny(int n)
{
init();
for(int i=0;i<4;++i) a[i]=1;
int N=8;
while(N/4<n)
{
const int d=N>>1;
const int M=d-1;
for(int i=0;i<=M;++i) a[i+d]=a[i];
const int p=prime[id++];
const int q=prime[id++];
const int LM=M>>1;
for(int i=0;i<=LM;i+=2) add(i,p),add(i+d,q);
for(int i=LM+2;i<=M;i+=2) add(i,p),add(i+d,q);
for(int i=1;i<=LM;i+=2) add(i,q),add(i+d,p);
for(int i=LM+3;i<=M;i+=2) add(i,q),add(i+d,p);
N<<=1;
}
const int p=prime[id++];
const int q=prime[id++];
for(int i=0;i<n;i+=2) add(i,p);
for(int i=1;i<n;i+=2) add(i,q);
vector<long long> ans;
for(int i=0;i<n;++i) ans.push_back(a[i]);
return ans;
}
};