AtCoder Beginner Contest 299(E,F)
E （最短路）
题目大意为有\(n\)个点和\(m\)条边，我们我个这些点匹配颜色（有两种颜色），但是要满足下面的条件
必须由一个点的颜色是\(1\)
然后给出\(k\)点限制
对于\(p_i\)这一个点，离他最近的一个颜色为\(1\)的点的最近距离为\(d_i\)
既然知道某个点距离\(1\)的最短路为\(d\)，那么从这个点出发最小距离小于\(d\)的点，都一定不能是\(1\),我们可以预先处理出那些点一定是不能是\(1\)的，然后再从这个点出发找，找到一个距离为\(d\)且可以为\(1\)的点，否则找不到，则输出\(-1\)
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=3e5+10;
const int mod=998244353;
int n,m;
vector<int>g[maxn];
vector<int>color,forbid;
int k;
vector<pair<int,int>>op;
void bfs1(int s,int d)
{
vector<int>dis(n+1,inf);
vector<bool>vis(n+1,false);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
dis[s]=0;
q.push({dis[s],s});
while (!q.empty())
{
auto [dd,u]=q.top();
q.pop();
if(dd>d) break;
if(vis[u]) continue;
vis[u]=true;
if(dd<d)
{
forbid[u]=1;
}
for (auto v:g[u])
{
if(dis[v]>dis[u]+1)
{
dis[v]=dis[u]+1;
q.push({dis[v],v});
}
}
}
return ;
}
bool bfs2(int s,int d)
{
vector<int>dis(n+1,inf);
vector<bool>vis(n+1,false);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
dis[s]=0;
q.push({dis[s],s});
while (!q.empty())
{
auto [dd,u]=q.top();
q.pop();
if(dd>d) break;
if(dd==d&&!forbid[u])
{
color[u]=1;
return true;
}
if(vis[u]) continue;
vis[u]=true;
for (auto v:g[u])
{
if(dis[v]>dis[u]+1)
{
dis[v]=dis[u]+1;
q.push({dis[v],v});
}
}
}
return false;
}
signed main ()
{
cin>>n>>m;
color.resize(n+1,0);
forbid.resize(n+1,0);
for (int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
cin>>k;
for (int i=1;i<=k;i++)
{
int s,d;
cin>>s>>d;
op.push_back({s,d});
bfs1(s,d);
}
bool yes=true;
for (auto [s,d]:op)
{
if(bfs2(s,d))
{
continue;
}
else
{
yes=false;
break;
}
}
if(yes)
{
cout<<"Yes\n";
if(k==0) color[1]=1;
for (int i=1;i<=n;i++)
{
cout<<color[i];
}
cout<<"\n";
}
else
{
cout<<"No\n";
}
system ("pause");
return 0;
}
F（dp,子串）
这个题的大意就是给出一个字符串，找到一个非空字符串\(t\),可以得到一个\(s\)为\(tt\),且\(s\)为题目给出的字符串的子串
子串：原来的字符串删除若干个字符
这就代表着\(tt\)里面的字符的顺序只要是符合要求的即可
然后我们可以看到这个\(t\),不断地制造\(t\)
对于一个满足要求的\(tt\),我们需要从原来的字符串里面去找，不如把找\(tt\)转换成在原来的字符串里面找到一前一后一样的子串
对于此时的字符\(now\),此时的位置为\(r\)我们要找到一个\(l\)（这个位置的字符同样是\(now\),是第一个出现该字符的位置，这样就把以\(r\)可以作为\(tt\)的结尾的所有情况都包括了）
我们可以得到一个初状态\(dp[l] [r] =1\),代表着第一个字符串以\(st\)结尾，第二个字符串以\(r\)结尾，前面的都是满足的（初状态只有这一个字符，所以不需要考虑，直接\(dp[l] [r] =1\)
然后我们需要继续深入，往后找后面可以存在的字符,但是后面的前面一个不能超过\(r\)（不然这两个字符串的顺序不是一前一后了，而是相交了），后面不能超过\(n\),
假设\(i,j\)是此时的两个字符串的结尾位置，我们的下一个就在他们位置的后面
假设存在这样一个字符\(k\),\(i\)后面的位置\(nl\)存在，在\(j\)的后面的位置\(nr\)存在
那我们可以得到状态转移方程如下
\[dp[nl][nr]=dp[nl][nr]+dp[i][j] \]我们取得的答案就是每一个不同结尾，对于此时的位置，只要是结尾的下一个\(now\)字符是\(r\),(这一次刚好是以\(r\)作为界限，\(r\)是第二个的开头，其他的情况，在其他的时候也已经加上了）可以加上这个答案
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=100+10;
const int mod=998244353;
int n;
string s;
void add(int &x,int c)
{
x+=c;
if(x>=mod)
{
x-=mod;
}
return ;
}
signed main ()
{
cin>>s;
n=s.size();
s=" "+s;
vector<int>pos(26,-1);
vector<vector<int>>nxt(n+1);
for (int i=n;i>=1;i--)
{
int now=s[i]-'a';
nxt[i]=pos;
pos[now]=i;
}
int ans=0;
for (int st=2;st<=n;st++)
{
int now=s[st]-'a';
vector<vector<int>>dp(n+1,vector<int>(n+1,0));
int l=pos[now],r=st;
dp[l][r]=1;
for (int i=l;i<r;i++)
{
for (int j=r;j<=n;j++)
{
for (int k=0;k<26;k++)
{
int nl=nxt[i][k];
int nr=nxt[j][k];
if(nl==-1||nr==-1||nl>=r) continue;
add(dp[nl][nr],dp[i][j]);
}
}
}
for (int i=l;i<r;i++)
{
for (int j=r;j<=n;j++)
{
if(nxt[i][now]==r)//如果nxt[i][now]小于r的话，前面可能已经加过一次了，大于更是不可能，我们加的只是此时刚好以r作为界限的情况
{
add(ans,dp[i][j]);
}
}
}
}
cout<<ans<<"\n";
system ("pause");
return 0;
}