AtCoder Beginner Contest 265(D-E)

D - Iroha and Haiku (New ABC Edition)

题意: 找一个最少含有三个点的区间，将区间分成三块，三块的和分别为p,q,r，问是否存在这样的区间

题解:先预处理一遍前缀和，和每一个前缀和出现的位置，然后从前往后遍历，每次遍历当前位置的前缀和，如果当前位置的前缀和>=(p+q+r)，那么就有可能存在符合条件的区间，在看是否存在前缀和为

sum-p-q-r的点，如果有再判断区间内部是否符合即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pll;

const int N=2e5+5;

const ll inf=1e18;

const ll mod=998244353;

ll a[N],sum[N];

ll n,p,q,e;

unordered_map<ll,ll> mp;

bool check(ll l,ll r){

   ll le=0;

   ll b[3]={p,q,e};

   ll cnt=0;

   for(ll i=l;i<=r;i++){

      le+=a[i];

      if(le==b[cnt]) cnt++,le=0;//如果相等就看下一个区间

      else if(le>b[cnt]) return 0;//如果大于了就证明这个区间不符合条件

   }

   return 1;

}

signed main(){

   ios::sync_with_stdio(false);

   cin.tie(0);cout.tie(0);

   cin>>n>>p>>q>>e;

   for(ll i=1;i<=n;i++){

       cin>>a[i];sum[i]=sum[i-1]+a[i];

       mp[sum[i]]=i;

   }

   for(ll i=1;i<=n;i++){

       if(sum[i]==p+q+e){

         if(check(1,i)){

            cout<<"Yes"<<endl;return 0;

         }

       }

       if(sum[i]>p+q+e){

         if(!mp[sum[i]-p-q-e]) continue;

         if(check(mp[sum[i]-p-q-e]+1,i)){

            cout<<"Yes"<<endl;return 0;

         }

       }

   }

   cout<<"No"<<endl;

}

E - Warp

题意: 给出四种移动的方向，每次选择一种，有m个障碍，不能传送到障碍上，问在进行n次传送的情况下，有几种移动路径。

题解: 每次四种选择，dp问题，问题在于转移方程，因为已知了最后一共要进行n次传送，所以可以遍历每种方向选择的次数。

dp[ i ][ j ][ z ]表示的是第一种移动i次，第二种j次，第三种z次。

转移方程就让他加上他的前一个状态即可。

//这里用set的速度比mp快

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pll;

const int N=2e5+5;

const ll inf=1e18;

const ll mod=998244353;

ll sum[N];

pll px[N];

pll a[N];

ll n,m,dp[305][305][305];

set<pll> mp;

signed main(){

   ios::sync_with_stdio(false);

   cin.tie(0);cout.tie(0);

   cin>>n>>m;

   for(ll i=1;i<=3;i++) cin>>px[i].first>>px[i].second;

   for(ll i=1;i<=m;i++){ cin>>a[i].first>>a[i].second;mp.insert(a[i]);}

   ll ans=0;

   dp[0][0][0]=1;

   for(ll i=0;i<=n;i++)

    for(ll j=0;j<=n-i;j++)

     for(ll z=0;z<=n-i-j;z++){

       if(!i&&!j&&!z) continue;

       ll x=i*px[1].first+j*px[2].first+z*px[3].first;

       ll y=i*px[1].second+j*px[2].second+z*px[3].second;

       if(mp.count({x,y})) continue;//判断是否是障碍

       if(i) dp[i][j][z]=(dp[i][j][z]+dp[i-1][j][z])%mod;//与前一个状态相加

       if(j) dp[i][j][z]=(dp[i][j][z]+dp[i][j-1][z])%mod;

       if(z) dp[i][j][z]=(dp[i][j][z]+dp[i][j][z-1])%mod;

       if(i+j+z==n) ans=(ans+dp[i][j][z])%mod;//如果当前的状态是够n个的，就加上

     }

   cout<<ans;

}

巴特西

AtCoder Beginner Contest 265(D-E)

最新文章

热门文章