AtCoder Beginner Contest 212(E,F)
E(dp)
题目大意为有\(n\)个点，我们需要找到\(k+1\)个点，用数组\(A\)表示,其中，\(A_i\)和\(A_{i+1}\)也不能一模一样，而且，规定\(A_0\)是\(1\),并且\(A_k\)也是\(1\),而且，还要满足下面的\(m\)种条边是不可以代表为\(A_i\)和\(A_{i+1}\),问我们可以得到多少个不同的\(A\)数组
很明显，这是一个\(dp\),我们可以定义\(dp[i] [j]\)为第\(i\)个点为\(j\)的数组数量
一开始是想一个一个点找，对于每一点，我们要找出所有的可以选择的点（不是一样的，不满足\(u,v\)关系的），但是我们简单的想，对于前面一个点，我们需要枚举，对于前面一个点，下一个可以选择的点还需要选择，可能会超时
所有我们可以换一个思路，正所谓正难则反
我们可以先什么都不考虑，不管这一点是什么，他的前一点可以是\(1\)到\(n\)中的任何一点，然后我们再减去那些不符合规则的点（一样的点和满足\(u,v\)关系的点），对于前一点的\(1\)到\(n\)的选择，都是一样的，可以先赋给该状态，然后再减去
#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>
#include <bitset>
#include <numeric>
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 eps 1e-6
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=5000+10;
const int mod=998244353;
int n,k,m;
int u[maxn],v[maxn];
int dp[maxn][maxn];
signed main ()
{
cin>>n>>m>>k;
for (int i=1;i<=m;i++)
{
cin>>u[i]>>v[i];
}
dp[0][1]=1;
for (int i=1;i<=k;i++)
{
int s=0;
for (int j=1;j<=n;j++)
{
s=(s+dp[i-1][j])%mod;
}
for (int j=1;j<=n;j++)//减去相同的点
{
dp[i][j]=((s-dp[i-1][j])%mod+mod)%mod;
}
for (int j=1;j<=m;j++)//减去满足u,v关系的两个点
{
dp[i][u[j]]=((dp[i][u[j]]-dp[i-1][v[j]])%mod+mod)%mod;
dp[i][v[j]]=((dp[i][v[j]]-dp[i-1][u[j]])%mod+mod)%mod;
}
}
int ans=dp[k][1];
cout<<ans<<"\n";
system ("pause");
return 0;
}
F(倍增，二分)
这个题的大意就是有\(n\)坐城市，\(m\)辆车，其中每一辆车都有着不同的起点\(a\)，终点\(b\)，发车时间\(s+0.5\)，到达时间\(t+0.5\)
然后，还给出\(q\)种询问
如果起点在\(y\)城市，它在\(x\)时间的时候开始等车，后面只要有一辆车在这个城市发车，到达下一个城市，我们需要知道的是在时间\(z\)的时候它在哪一个城市并输出，如果它刚好在车上，它可以输出这辆车的起点和终点
对于这一个问题，如果我们要知道某一个时间的最快发车的一辆车，这个我们可以直接二分\(s\)寻找
但是我们可能不只坐一辆车，所以我们需要知道如果到达了某一辆车后，他的后面的车是那些，这个可以用到倍增
在前面的预处理都已经做好了之后
对于这一个起点，找到最快的一辆车，然后判断不同的情况，有不同的处理
还要继续下一步寻找的是，这一辆车到站的时间，还没有到时间\(z\),那我们可以再下一步寻找，但是我们要是一个一个找也不现实，那这里我们可以用到之前预处理之后的倍增，找到一个最大\(t\)小于\(z\)的车
然后我们再寻找这一辆车之后还可以到的那个城市,我们再根据不同的情况获得答案
具体的可以看代码
#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>
#include <bitset>
#include <numeric>
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 eps 1e-6
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=1e5+10;
const int mod=998244353;
int n,m,q;
int f[maxn][32];
int a[maxn],b[maxn],s[maxn],t[maxn];
vector<pair<int,int>>g[maxn];
void init()
{
for (auto &x:g)
{
sort(x.begin(),x.end());
}
for (int i=1;i<=m;i++)
{
pair<int,int> now={t[i],0};
auto it=lower_bound(g[b[i]].begin(),g[b[i]].end(),now);
if(it==g[b[i]].end())
{
f[i][0]=i;
}
else
{
f[i][0]=it->second;
}
}
for (int j=1;j<=20;j++)
{
for (int i=1;i<=m;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
}
}
return ;
}
signed main ()
{
cin>>n>>m>>q;
for (int i=1;i<=m;i++)
{
cin>>a[i]>>b[i]>>s[i]>>t[i];
g[a[i]].push_back({s[i],i});
}
init();
while (q--)
{
int x,y,z;
cin>>x>>y>>z;
pair<int,int> now={x,0};
auto it=lower_bound(g[y].begin(),g[y].end(),now);
if(it==g[y].end())
{
cout<<y<<"\n";
continue;
}
int v=it->second;
if(z<=s[v])
{
cout<<y<<"\n";
}
else if(z<=t[v])
{
cout<<a[v]<<" "<<b[v]<<"\n";
}
else
{
for (int i=20;i>=0;i--)
{
if(t[f[v][i]]<z)
{
v=f[v][i];
}
}
now={t[v],0};
it=lower_bound(g[b[v]].begin(),g[b[v]].end(),now);
if(it==g[b[v]].end())
{
cout<<b[v]<<"\n";
}
else
{
int nxt=it->second;
if(z<=s[nxt])
{
cout<<b[v]<<"\n";
}
else
{
cout<<a[nxt]<<" "<<b[nxt]<<"\n";
}
}
}
}
system ("pause");
return 0;
}