T1 特殊字符串
解题思路
\(f_{i,j}\) 表示前 \(i\) 个字符中结尾为 \(j\) 的最大贡献。
转移枚举当前位置于之前位置结尾的组合加上贡献即可。
对于边界问题，容易发现选择 1 一定不劣。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"RP++"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e5+10,INF=1e18;
int n,m,ans,f[N][30],val[30][30];
char s[N],ch1,ch2;
#undef int
int main()
{
#define int long long
freopen("shiki.in","r",stdin); freopen("shiki.out","w",stdout);
n=read(); scanf("%s",s+1); m=read();
for(int i=1,v;i<=m;i++)
{
getchar(); ch1=getchar(); getchar(); ch2=getchar(); v=read();
val[ch1-'a'][ch2-'a']+=v;
}
for(int i=1;i<=n;i++) for(int j=0;j<26;j++) f[i][j]=-INF; f[1][s[1]-'a']=0;
for(int i=2;i<=n;i++)
{
for(int j=0;j<26;j++) f[i][j]=f[i-1][j];
for(int j=0;j<26;j++) f[i][s[i]-'a']=max(f[i][s[i]-'a'],f[i-1][j]+val[j][s[i]-'a']);
}
for(int i=0;i<26;i++) ans=max(ans,f[n][i]); printf("%lld",ans);
return 0;
}
T2 宝可梦
解题思路
调了一下午，换了两三种做法，最后换回我原来的做法，尝试着调了一下段错误，发现真的只是数组开小了那么简单！！！
我还以为是系统栈空间炸了。。。
如果当前方向是可以走的话直接向前走，否则的话因为是沿着右墙走所以直接左转。
然后对于右手边没有墙的时候，就直接向右手边走就好了。50行精品超短小暴力
由于题目保证路径是唯一的因此所有点之间形成了一种树形结构。
那么我们选择一个出发点一直走一定会遍历完整张图，并且形成了一个欧拉序。
于是我们就可以对于一个点按照正反方向走两边（询问是有方向的），对于每一个询问查找对应点之间的距离就好了。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"RP++"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=5e5+10,INF=1e18;
int n,m,q,all,sum[10],pos[5][N][5];
int r[10]={0,4,3,1,2},l[10]={0,3,4,2,1};
int d1[10]={0,-1,1,0,0},d2[10]={0,0,0,-1,1};
vector<char> e[N];
bool vis[N];
char ch[N];
inline int id(int x,int y){return (x-1)*m+y;}
void work(int x,int y,int fx)
{
int p=fx,tx=x,ty=y;
pos[p][id(x,y)][fx]=min(pos[p][id(x,y)][fx],sum[p]);
int nx=x+d1[fx],ny=y+d2[fx];
if(e[nx][ny]=='.') sum[p]++,x=nx,y=ny;
else fx=l[fx];
if(e[x+d1[r[fx]]][y+d2[r[fx]]]=='.') fx=r[fx];
while(x!=tx||y!=ty||p!=fx)
{
pos[p][id(x,y)][fx]=min(pos[p][id(x,y)][fx],sum[p]);
int nx=x+d1[fx],ny=y+d2[fx];
if(x==tx&&y==ty&&fx==p) break;
if(e[nx][ny]=='.') sum[p]++,x=nx,y=ny;
else for(int i=1;i<=3;i++)
{
fx=r[fx];
if(x==tx&&y==ty&&fx==p) break;
}
if(x==tx&&y==ty&&fx==p) break;
if(e[x+d1[r[fx]]][y+d2[r[fx]]]=='.') fx=r[fx];
}
}
#undef int
int main()
{
#define int long long
freopen("pokemon.in","r",stdin); freopen("pokemon.out","w",stdout);
n=read(); m=read(); memset(pos,0x3f,sizeof(pos));
for(int i=1;i<=n;i++)
{
e[i].push_back('X'); scanf("%s",ch+1);
for(int j=1;j<=m;j++) e[i].push_back(ch[j]);
e[i].push_back('X');
}
for(int i=0;i<=m+1;i++) e[0].push_back('X'),e[n+1].push_back('X');
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) all+=(e[i][j]=='.');
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(e[i][j]=='.'){for(int k=1;k<=2;k++)work(i,j,k);goto V;}
V:; q=read();
while(q--)
{
int x,y,tx,ty,fx; x=read(); y=read(); tx=read(); ty=read();
scanf("%s",ch+1); fx=(ch[1]=='U')?1:((ch[1]=='D')?2:((ch[1]=='L')?3:4));
int ans=INF;
for(int p=1;p<=2;p++)
for(int i=1;i<=4;i++)
{
if(pos[p][id(x,y)][fx]>=INF||pos[p][id(tx,ty)][i]>=INF) continue;
if(pos[p][id(tx,ty)][i]>=pos[p][id(x,y)][fx]) ans=min(ans,pos[p][id(tx,ty)][i]-pos[p][id(x,y)][fx]);
else ans=min(ans,sum[p]+(pos[p][id(tx,ty)][i]-pos[p][id(x,y)][fx]));
}
printf("%lld\n",ans);
}
return 0;
}
T3 矩阵
解题思路
其实就是一个爆搜，显然如果有两个相邻的点数值相等答案就是 -1 。
否则的话由于是等比数列搜索深度不会超过 \(log\) 层，因此复杂度是对的。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"RP++"<<endl
#define left Left
#define right Right
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=4e4+10;
int n,m,ans=1;
int d1[10]={0,1,-1,0,0};
int d2[10]={0,0,0,1,-1};
unordered_map<int,int> mp[N];
vector<int> s[N];
inline int id(int x,int y){return (x-1)*m+y;}
inline bool check(){return (1.0*clock())/(1.0*CLOCKS_PER_SEC)<=0.98;}
void dfs(int x,int y,int dis,int num)
{
ans=max(ans,dis);
for(int i=1;i<=4;i++)
{
int nx=x+d1[i],ny=y+d2[i];
if(s[nx][ny]==s[x][y]*num)
dfs(nx,ny,dis+1,num);
}
}
void solve(int i,int j)
{
for(int k=1;k<=4;k++)
{
int x=i+d1[k],y=j+d2[k];
if(s[x][y]<s[i][j]||s[x][y]%s[i][j]) continue;
dfs(x,y,2,s[x][y]/s[i][j]);
}
}
#undef int
int main()
{
#define int long long
freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout);
n=read(); m=read(); for(int i=0;i<=m+1;i++) s[0].push_back(0),s[n+1].push_back(0);
for(int i=1;i<=n;i++)
{
s[i].push_back(0);
for(int j=1;j<=m;j++) s[i].push_back(read());
s[i].push_back(0);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=4;k++)
{
int x=i+d1[k],y=j+d2[k];
if(s[x][y]==s[i][j]) printf("-1"),exit(0);
}
for(int i=1;i<=n&&check();i++)
for(int j=1;j<=m&&check();j++)
solve(i,j);
printf("%lld",ans);
return 0;
}