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