AtCoder Beginner Contest 247(E,F)
E(思维)
这个题大意就是给一个长度为\(n\)的数组,一个\(x\)和一个\(y\),问这个数组里面可以找到多少段\([l,r]\)满足这一段里面的最大值是\(x\),最小值是\(y\)
这里的做法是固定最右端,寻找最左端的可能的数量,最后相加
对于每一个位置,都有作为最右端的可能,那么对于一个点\(i\),我们可以去寻找这个最左端的范围
对于这一个范围的最左端就是离\(i\)最近的一个不满足条件的位置(大于最大值或者是小于最小值),最右端就是从\(1\)到\(i\)以来,我们最后一次找到最大值的位置和最小值的位置的较小的那一个(这样从\(min(posx,posy)\)到\(i\),至少存在一个最大值和最小值)
只要存在满足这个范围的最左端,我们就加上去\(res=res+r-l\)
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <bitset>
#include <unordered_map>
using namespace std;
const int maxn=2e5+10;
const int mod=998244353;
const double eps=1e-12;
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
signed main ()
{
int ans=0;
int n,x,y;
cin>>n>>x>>y;
int pre=0;
int posx=0,posy=0;
for (int i=1;i<=n;i++)
{
int now;
cin>>now;
if(now>x||now<y) pre=i;
if(now==x) posx=i;
if(now==y) posy=i;
int r=min(posx,posy);
if(r>pre)
{
ans+=r-pre;
}
}
cout<<ans<<"\n";
system ("pause");
return 0;
}
F(dp)
这个题的大意就是有\(n\)张牌,每一张牌都有两个数\(p\)和\(q\),\(P\)=\(1,2,3,...n\),\(Q\)=\(1,2,3,...n\).
我们需要选择任意张牌,只要这些牌里面的数存在\(1\)到\(n\)的数即可,问有多少种选择,可以满足以上条件
对于一张牌,可能存在两个不同的数,可以把两个数连在一起,我们把这些连在一次的那些数,我们可以把这些数看做一个整体,因为这些数字都存在两个,所以我们允许某些数只出现一个,所以我们要进行一次\(dp\)
dp[i][1][1]//对于i个数,dp[i][1][0]和dp[i][0][1]只存在一个
//对于只有一个数,只存在dp[1][1][1]=1,dp[1][0][0]=1,1个数在一张牌上
dp[1][1][1]=1,dp[1][0][0]=1;
for (int i=2;i<=n;i++)
{
for (int j=0;j<=1;j++)
{
dp[i][j][0]=dp[i-1][j][1];//这一个如果不选择,就需要依靠另外一张牌上的这一个数了
dp[i][j][1]=(dp[i-1][j][0]+dp[i-1][j][1])%mod;//选择的话,上一张有和没有都没有什么关系,都可以
}
ans[i]=(dp[i][0][1]+dp[i][1][0]+dp[i][1][1])%mod;//保证前i个都存在
}
对于每一种环,都会包括\(cnt\)个数,那么这\(cnt\)个数需要\(ans[cnt]\)种选择可以让这\(cnt\)个数都存在
对于每一部分,用乘法计算
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <bitset>
#include <unordered_map>
using namespace std;
const int maxn=2e5+10;
const int mod= 998244353;
const double eps=1e-12;
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
int n,p[maxn],q[maxn];
int f[maxn];
int siz[maxn];
int ans[maxn];
int dp[maxn][2][2];
int find(int x)
{
if(x==f[x]) return f[x];
return f[x]=find(f[x]);
}
void merge(int x,int y)
{
int tx=find(x);
int ty=find(y);
if(tx==ty) return ;
siz[tx]+=siz[ty];
siz[ty]=0;
f[ty]=tx;
return ;
}
void init()
{
dp[1][1][1]=1;
dp[1][0][0]=1;
ans[1]=1;
for (int i=2;i<=n;i++)
{
for (int j=0;j<=1;j++)
{
dp[i][j][0]=dp[i-1][j][1];
dp[i][j][1]=(dp[i-1][j][1]+dp[i-1][j][0])%mod;
}
ans[i]=(dp[i][1][1]+dp[i][1][0]+dp[i][0][1])%mod;
}
return ;
}
signed main ()
{
cin>>n;
init();
for (int i=1;i<=n;i++)
{
f[i]=i;
siz[i]=1;
cin>>p[i];
}
for (int i=1;i<=n;i++)
{
cin>>q[i];
merge(p[i],q[i]);
}
int res=1;
for (int i=1;i<=n;i++)
{
if(find(i)==i)
{
// cout<<siz[i]<<"\n";
res=(res*ans[siz[i]])%mod;
}
}
cout<<res<<"\n";
system ("pause");
return 0;
}
- Beginner AtCoder Contest 247beginner atcoder contest 247 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310