526互联

AtCoder Beginner Contest 307（E,F,G)

发布时间 2023-07-01 18:50:26作者: righting

AtCoder Beginner Contest 307（E,F,G)

E(dp)

E

这个题大意就是我们需要组成一个长度为\(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)

F

这个题的大意就是有\(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)

G

这个题的大意为给你一个数组，我们把这个数组按照下面的操作

\(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;
}