这次难的震 撼 我 妈
先整个短的，后面咕一会儿
给定\(n\times n\)的方格图,一些位置为障碍,一些位置为可能的起点.若将一个可能的位置放上机器人,可以往四个方向走,且每\(D\)秒会变大1(曼哈顿意义上的).求机器人所有可能的覆盖位置.
\(n\le 1000,1\le D \le10^9\)
Observation: 考虑到\(D\ge1\),因而每走至少一格才会变大1,为了到达一个位置而等待扩展部分到达该位置不如直接去走到对应位置(考虑机器人变大更难通过障碍).
自此我们得到对应的算法框架:对于所有的起点S,bfs得到能通过最短路走到的所有位置,然后对于所有可到达的位置计算扩展部分.
对于第一部分,我们考虑提前用一次bfs去计算每个点到最近边界的距离,这样就相当于给每一个点一个时间限制.
对于第二个部分,一种可行的方法是转坐标系然后二维差分,然而比较难写.一种更为简单的写法是再去bfs一遍,注意到一个点可能被到达多次,我们用优先队列维护,只取k最大的一次即可
#include<bits/stdc++.h>
#define y0 pmtx
#define y1 pmtxx
#define x0 pmtxxx
#define x1 pmtxxxx
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define DEBUG printf("Passing Line %d in function [%s].\n",__LINE__,__FUNCTION__)
using namespace std;
typedef pair<int ,int > pii;
typedef vector<int > vi;
typedef long long ll;
typedef unsigned long long ull;
namespace FastIO{
const int SIZE=(1<<20);
char in[SIZE],*inS=in,*inT=in+SIZE;
inline char Getchar(){
if(inS==inT){inT=(inS=in)+fread(in,1,SIZE,stdin);if(inS==inT)return EOF;}
return *inS++;
}
char out[SIZE],*outS=out,*outT=out+SIZE;
inline void Flush(){fwrite(out,1,outS-out,stdout);outS=out;}
inline void Putchar(char c){*outS++=c;if(outS==outT)Flush();}
struct NTR{~NTR(){Flush();}}ztr;
}
#ifndef LOCAL
#define getchar FastIO::Getchar
#define putchar FastIO::Putchar
#endif
template<typename T> inline void read(T &x){
x=0;int f=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘)x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();
x*=f;
}
template<typename T>inline void write(T x){
if(!x)putchar(‘0‘);
if(x<0)x=-x,putchar(‘-‘);
static int sta[40];int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
const int maxn=2007,INF=0x3f3f3f3f;
const ll MOD=998244353;
const ll LINF=0x3f3f3f3f3f3f3f3fll;
const ll P=19260817;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
template<typename T>inline void ckmax(T &x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T &x,T y){x=(y<x?y:x);}
template<typename T>inline T my_abs(T x){if(x<0)x=-x;return x;}
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int &x,int y){x=mod1(x+y);}
inline void sub(int &x,int y){x=mod2(x-y);}
int n,D;
char s[maxn];
int a[maxn][maxn];
int dis[maxn][maxn];
vector<pii> v;
queue<pii > q;
queue<pair<pii,int > > qs;
bool is_good(int x,int y){
return (x>=1)&&(x<=n)&&(y>=1)&&(y<=n);
}
inline void init_dis(){
while(!q.empty()){
int x=q.front().fi,y=q.front().se;
q.pop();
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(is_good(nx,ny)&&dis[nx][ny]==-1)dis[nx][ny]=dis[x][y]+1,q.push(mp(nx,ny));
}
}
}
int vis[maxn][maxn];
priority_queue<pair<int ,pii> > pq;
inline void flood_fill(){
while(!qs.empty()){
int x=qs.front().fi.fi,y=qs.front().fi.se,rt=qs.front().se;
qs.pop();
if(vis[x][y]||rt/D>dis[x][y])continue;
pq.push(mp(min(rt/D+1,dis[x][y]-1),mp(x,y)));
if(rt/D==dis[x][y])continue;
vis[x][y]=1;
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(!vis[nx][ny]&&is_good(nx,ny)&&dis[nx][ny]>(rt)/D)qs.push(mp(mp(nx,ny),rt+1));
}
}
}
int ans=0;
inline void getans(){
memset(vis,0,sizeof(vis));
while(!pq.empty()){
int x=pq.top().se.fi,y=pq.top().se.se,rt=pq.top().fi;
pq.pop();
if(vis[x][y])continue;
vis[x][y]=1;
ans++;
for(int d=0;d<4;d++){
int nx=x+dx[d],ny=y+dy[d];
if(a[nx][ny]==1&&is_good(nx,ny)&&!vis[nx][ny]&&rt>0)pq.push(mp(rt-1,mp(nx,ny)));
}
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
memset(dis,-1,sizeof(dis));
scanf("%d%d",&n,&D);
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=n;j++){
if(s[j]==‘#‘)a[i][j]=0,q.push(mp(i,j)),dis[i][j]=0;
else if(s[j]==‘S‘)a[i][j]=1,qs.push(mp(mp(i,j),0));
else a[i][j]=1;
}
}
init_dis();
flood_fill();
getans();
printf("%d\n",ans);
return 0;
}
//things to remember
//1.long long
//2.array length
//3.freopen
//4 boarder case
不概括了,自己看
Observation: 注意到一个非常重要的事实,由于我们是将所有连续相同字符之间的位置切开,因而对于一个串,它对应的结果串是唯一的。所以对于结果串而言,一种合法划分即对应一种合法初始串。
那么什么样的串是合法串呢？显然的有两个条件：
不难证明这是一个充分必要条件。
由此可以得到一个朴素的DP想法，考虑\(dp[i][ch]\)表示已经把前i个字符割好了，且最后一个子串的首字母为ch，转移时从大往小枚举前一个划分位置\(j\)，判断\(s[j+1\ldots i]\)有无连续相同字符即可。这个东西的复杂度是\(\Theta(n^2)\)的，无法接受。
考虑优化。在这种划分问题中，有一个套路是考虑i时要么加入前一个划分，要么另起一段。这道题中也是同样的道理。令\(dp[i][a][b][c]\)表示最后一段最后一个字母为a，首字母为b，倒数第二段为c。
这样，对于\(s[i+1]\)来说，若\(s[i+1]!=a\)，那么自然可以添加进最后一段。若\(a=c\)，那么最后一段就可以结束，让\(s[i+1]\)自成一段。
这样复杂度即为\(\Theta(n)\)，转移时有一个\(|\Sigma|^4\)级别的常数，此题\(|\Sigma|\)为4，所以没有问题。
#include<bits/stdc++.h>
#define y0 pmtx
#define y1 pmtxx
#define x0 pmtxxx
#define x1 pmtxxxx
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define DEBUG printf("Passing Line %d in function [%s].\n",__LINE__,__FUNCTION__)
using namespace std;
typedef pair<int ,int > pii;
typedef vector<int > vi;
typedef long long ll;
typedef unsigned long long ull;
namespace FastIO{
const int SIZE=(1<<20);
char in[SIZE],*inS=in,*inT=in+SIZE;
inline char Getchar(){
if(inS==inT){inT=(inS=in)+fread(in,1,SIZE,stdin);if(inS==inT)return EOF;}
return *inS++;
}
char out[SIZE],*outS=out,*outT=out+SIZE;
inline void Flush(){fwrite(out,1,outS-out,stdout);outS=out;}
inline void Putchar(char c){*outS++=c;if(outS==outT)Flush();}
struct NTR{~NTR(){Flush();}}ztr;
}
#ifndef LOCAL
#define getchar FastIO::Getchar
#define putchar FastIO::Putchar
#endif
template<typename T> inline void read(T &x){
x=0;int f=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘)x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();
x*=f;
}
template<typename T>inline void write(T x){
if(!x)putchar(‘0‘);
if(x<0)x=-x,putchar(‘-‘);
static int sta[40];int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
const int maxn=200007,INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ll LINF=0x3f3f3f3f3f3f3f3fll;
const ll P=19260817;
template<typename T>inline void ckmax(T &x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T &x,T y){x=(y<x?y:x);}
template<typename T>inline T my_abs(T x){if(x<0)x=-x;return x;}
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int &x,int y){x=mod1(x+y);}
inline void sub(int &x,int y){x=mod2(x-y);}
char s[maxn];
int n;
int dp[maxn][4][4][4];
const char to[]="AGCT";
int ans=0;
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(s[1]==‘?‘||s[1]==to[j])dp[1][j][j][i]=1;
}
}
for(int i=2;i<=n;i++){
for(int a=0;a<4;a++){
if(s[i]!=‘?‘&&s[i]!=to[a])continue;
for(int b=0;b<4;b++){
for(int c=0;c<4;c++){
for(int la=0;la<4;la++){
if(la!=a)add(dp[i][a][b][c],dp[i-1][la][b][c]);
if(la==c)add(dp[i][a][a][b],dp[i-1][la][b][c]);
}
}
}
}
}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
add(ans,dp[n][i][j][i]);
}
}
printf("%d",ans);
return 0;
}
//things to remember
//1.long long
//2.array length
//3.freopen
//4 boarder case
请用您勤劳的双手自己查看。
没啥意思的题，口胡一下。
枚举最左和最右的两只奶牛，然后双指针扫一下竖直方向即可。复杂度\(\Theta(n^3\log n)\)到\(\Theta(n^3)\)左右。
细节比较多，懒得写了。
给定长度为\(n\)的\(a_i,b_i\)，当且仅当\(a_i\le b_j\)时能匹配，问极大匹配数。
\(n\le 2000\)
发现USACO考这种牛逼DP挺多的，学到很多。
题解懒得写了，咕了。
请用您勤劳的双手自己查看。
nb题。
USACO2020DEC Gold/Platinum 解题报告
原文：https://www.cnblogs.com/pmt2018/p/14191111.html