AtCoder Beginner Contest 307（E,F,G)
E(dp)
这个题大意就是我们需要组成一个长度为\(n\)的数组，满足两个相邻的数字不可以相等，其中，\(a_1\)和\(a_n\)也是相邻的，我们可以选择的数字为\(0\)到\(m-1\),问最后有多少种不同的组成方式满足以上条件。
题目大意很简单，就是有点难想，如果\(a_1\)和\(a_n\)不相邻的，那么这个问题很简单，但是这个是相邻的，这样，我们对于最后一个位置，第一个位置是哪一个数是很重要的
我们可以记录每一位和第一位选择的数字之间的关系，是否相等
我们先假定这第一位为一个数字，后面我们只需要\(dp[n] [0]\)再乘以\(m\)种不同的可能即可
然后对于每一位数字的选择
所以我们可以得到状态转移方程
\[dp[i][0]=dp[i-1][0]\times(m-2)+dp[i-1][1]\times(n-1) \]\[dp[i][1]=dp[i-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>
#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=1e6+10;
const int mod=998244353;
int t;
int n,m;
int dp[maxn][2];
void solve()
{
cin>>n>>m;
dp[1][1]=1;
dp[1][0]=0;
for (int i=2;i<=n;i++)
{
dp[i][1]=dp[i-1][0];
dp[i][0]=((dp[i-1][0]*(m-2))%mod+(dp[i-1][1]*(m-1))%mod)%mod;
}
int ans=dp[n][0];
ans=(ans*m)%mod;
cout<<ans<<"\n";
return ;
}
signed main ()
{
//ios;
// cin>>t;
t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
F(dijkstra)
这个题的大意就是有\(n\)个房间，\(m\)个道路，其中，最开始，有一个病毒感染了\(k\)个房间，然后有\(d\)天，其中，只要在已经感染的房间到其他未感染的房间的距离小于\(x_i\),那么这样病毒就可以传染到路的另外一个房间
问，对于每一个房间，第一次被感染的时间是多少
对于每一次，我们可以判断由上一次被感染的房间到达的下一个房间的区间
如果满足距离的条件，那么就是这一天被感染的，在前面的步骤都已经判断好了，我们需要再次更新此次被感染的房间的下一个房间的距离，后面再一次判断，知道到达最后一天
具体操作可以看代码
#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=3e5+10;
const int mod=998244353;
int t;
int n,m,k,d;
int a[maxn],x[maxn],ans[maxn];
vector<pair<int,int>>g[maxn];
int dis[maxn];
void solve()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
ans[i]=-1;
vis[i]=false;
dis[i]=inf;
}
priority_queue<pair<int,int>>q;
for (int i=1;i<=m;i++)
{
int u,v,val;
cin>>u>>v>>val;
g[u].push_back({v,val});
g[v].push_back({u,val});
}
cin>>k;
for (int i=1;i<=k;i++)
{
int u;
cin>>u;
dis[u]=0;
ans[u]=0;
for (auto [v,val]:g[u])
{
if(dis[v]>dis[u]+val)
{
dis[v]=dis[u]+val;
q.push({-dis[v],v});
}
}
}
cin>>d;
for (int i=1;i<=d;i++)
{
int dis1;
cin>>dis1;
vector<int>infected;
while (!q.empty())
{
auto [dis2,u]=q.top();
if(dis[u]>dis1) break;
q.pop();
if(ans[u]!=-1) continue;
ans[u]=i;
infected.push_back(u);
for (auto [v,val]:g[u])
{
if(dis[v]>dis[u]+val)
{
dis[v]=dis[u]+val;
q.push({-dis[v],v});
}
}
}
for (auto u:infected)
{
for (auto [v,val]:g[u])
{
if(dis[v]>val)
{
dis[v]=val;
q.push({-dis[v],v});
}
}
}
}
for (int i=1;i<=n;i++)
{
cout<<ans[i]<<"\n";
}
return ;
}
signed main ()
{
//ios;
// cin>>t;
t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
G(dp)
这个题的大意为给你一个数组，我们把这个数组按照下面的操作
\(1\),\(a_i\)变成\(a_i+1\)，\(a_{i+1}\)变成\(a_{i+1}-1\)
\(2\),\(a_i\)变成\(a_i-1\)，\(a_{i+1}\)变成\(a_{i+1}+1\)的操作数字
把这个数组的极差小于等于\(1\)(\(max-min<=1\))
要想极差尽量少，那么我们就可以把这\(sum\)平均分，但是可能并不能均分，那么可能存在一些数字需要多一
我们可以设计一个\(dp[i]\)代表多分出\(i\)个\(1\),答案就是多分出\(sum%n\)个\(1\)，即\(dp[n] [sum%n]\)但是我们发现如果是一个二维的数组可能会超内存，我们可以只用\(dp[i]\)记录，每次记录上一轮的\(dp\)
然后我们在考虑每一种状态时需要的操作数量
对于每一个数字，它只有两种目标\(ave\)和\(ave+1\)，但是我们并不是直接的判断目标和\(a_i\)之间的差，因为每一次操作可以影响两个数字，我们我们需要的是\(a_i\)减去前面对这一个位置的影响，就相当于在经过前面的\(i-1\)次操作后对\(a_i\)的影响，变成了另外一个数字\(cur\),\(a_i\)减去他们多的，然后以\(cur\)到目标数字的差，然后就可知操作数了，关于这其中的具体操作，可以看见代码
但是对于\(sum%n\)，可能会出现负数，我们为了让它加\(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=5e3+10;
int t;
int n,a[maxn];
void solve()
{
cin>>n;
int sum=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
int ave=sum/n;
int mod=sum%n;
if(mod<=0)
{
mod+=n;
ave--;
}
vector<int>dp1(mod+2,inf);
dp1[0]=0;
sum=0;
int now=0;
for (int i=1;i<=n;i++)
{
vector<int>dp2(mod+2,inf);
for (int last=0;last<=mod;last++)
{
int val=0;
int need=now+last-sum;
int cur=a[i]-need;
val=abs(cur-(ave+1));
if(last!=mod)dp2[last+1]=min(dp2[last+1],dp1[last]+val);
val=abs(cur-(ave));
dp2[last]=min(dp2[last],dp1[last]+val);
}
sum+=a[i];
now+=ave;
dp1=dp2;
}
int ans=dp1[mod];
cout<<ans<<"\n";
return ;
}
signed main ()
{
//ios;
// cin>>t;
t=1;
while (t--)
{
solve();
}
system ("pause");
return 0;
}