当前位置：首页 > news >正文

胶州企业网站建设怎么样免费建设网站

news 2025/11/6 21:00:20

胶州企业网站建设,怎么样免费建设网站,做服装公司需要什么网站,常州自助建站A - ABC Identity 如果只有AAA,BBB两种字符的话，我们发现要寻找p∈[1,n]p\in [1,n]p∈[1,n]，使得[1:p][1:p][1:p]中AAA的数目与[p1:n][p1:n][p1:n]中BBB的数目相同。如果有A,B,CA,B,CA,B,C三种字符，我们可以先将A,BA,BA,B分离出来&#xf…

A - ABC Identity

如果只有 $A$ , $B$ 两种字符的话，我们发现要寻找 $p∈[1,n]p\in [1,n]$ ，使得 $[1 : p]$ 中 $A$ 的数目与 $[p + 1 : n]$ 中 $B$ 的数目相同。

如果有 $A, B, C$ 三种字符，我们可以先将 $A, B$ 分离出来，再将 $B, C$ 分离出来，最后把 $A, C$ 分离出来，这样最后会生成 $8$ 个子序列 ~~然后无法通过~~

神谕告诉我们， $A, B, C$ 三种字符一共只有 $6$ 种本质不同的排列，因此我们可以考虑把原序列分成长度为 $n$ 的 $3$ 段，从每一段中分别选取一个字符构成 $A, B, C$ 的排列，最后把相同的排列放在一起即可。猜一下结论，这显然是有解的。

~~这种题还是要多尝试~~

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int>v[3][3];
string s;
int n,res[600005];
int has(int x,int y,int z){return x*2+(y-(x<y))*1;
}
int main(){cin>>n>>s;for(int i=0;i<3*n;i++){v[i/n][s[i]-'A'].pb(i);}for(int i=1;i<=n;i++){for(int j=0;j<3;j++){for(int k=0;k<3;k++){for(int l=0;l<3;l++){if(v[0][j].size()&&v[1][k].size()&&v[2][l].size()&&j!=k&&k!=l&&j!=l){res[v[0][j].back()]=has(j,k,l);res[v[1][k].back()]=has(j,k,l);res[v[2][l].back()]=has(j,k,l);v[0][j].pop_back();v[1][k].pop_back();v[2][l].pop_back();}}}}}for(int i=0;i<3*n;i++)cout<<res[i]+1;
}

B - ABC Supremacy

如果只考虑 $S$ 怎么生成 $T$ 的话，怎么做都是 $O(n^2)$ 的。~~数据删除~~

~~上面那种思路可能不太好处理~~ 但是操作是可逆的，因此判断 $S, T$ 同构的一个充分条件是它们都能到达一个相同的状态 $P$ 。所以我们只要求出 $S, T$ 的最小表示即可，这样一个字符串生成的表示是唯一的，就不用担心上述问题了。

~~剩下的就是怎么去寻找最小串。比较烦恼就先咕了~~

显然我们要凑出尽量多的 $A BC$ 串（这里指轮换），并且每次操作相当于将 $A BC$ 串这个整体挪到前面，然后把 $A$ 放在最前面。那么 $BC$ 是固定的吗？如果 $BC$ 不是固定的，这个问题也比较烦恼，~~可以先咕着~~

~~开始慌张~~ ~~不过幸运的是之前的结论还是正确的~~

我们可以把最小表示的定义换成 得到最多的 $A BC$ 轮换组，那么 $BC$ 就肯定是固定的了。

复杂度 $O (n)$ 。

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n;
string s,t;
vector<char>solve(string s){vector<char>v;for(int i=0;i<s.size();i++){v.pb(s[i]);if(v.size()>=3&&(v[v.size()-3]=='A'&&v[v.size()-2]=='B'&&v[v.size()-1]=='C'||v[v.size()-3]=='B'&&v[v.size()-2]=='C'&&v[v.size()-1]=='A'||v[v.size()-3]=='C'&&v[v.size()-2]=='A'&&v[v.size()-1]=='B')){v.pop_back();v.pop_back();v.pop_back();}}return v;
}
int main(){cin>>n>>s>>t;cout<<(solve(s)==solve(t)?"YES":"NO");
}

C - Weird LIS

如果我们能思考清楚 ${A_i\}$ 合法的充要条件，那么这道题也就解决了。

~~或者说能建立双射然后计数也行~~

~~想不太清楚所以先咕了~~

思路其实并不困难，不过可能需要猜几个结论。

$1.1$ 如果 $A_i$ 全部等于 $K$ ，猜测 $K≤⌊n2⌋K\le \lfloor\frac{n}{2}\rfloor$ ，这还是比较容易看出来。
$1.2$ 如果 $K$ 和 $K - 1$ 同时存在，那么 $A_i=K-1$ 的那些点是固定的，我们要在所有 $A_i=K$ 的连续段中挑选一段接在固定的数之间，那么根据 $1.1$ 的推论，这一段的长度不能超过 $⌊l2⌋\lfloor\frac{l}{2}\rfloor$ （ $l$ 表示连续段长度），我们猜测对于更小的情况也是取得到的，因此 $∑⌊li2⌋+cntK−1≥K\sum{\lfloor\frac{l_i}{2}\rfloor}+cnt_{K-1}\ge K$ ，并且 $cntK−1≤Kcnt_{K-1}\le K$ 。

~~这个向下取整好像不太妙，先咕了~~

~~计数这个地方可能要多尝试~~

复杂度 $O(n^2)$ 。不过要注意特判 $A_i=n-1$ 的情况。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=5005;
int n,m,mod;
ll fac[N],inv[N],res;
ll pw(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
void init(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;inv[n]=pw(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
ll binom(int x,int y){if(x<0||y<0||x<y)return 0;return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main(){cin>>n>>m>>mod,init(n+1);for(int x=1;x<n;x++){for(int y=0;y<=(n-x)/2;y++){int L=max(3,x),R=min(m,x+y);if(L<=R)res=(res+binom(x+y,x)*binom(x+1,n-x-2*y)%mod*(R-L+1))%mod;}}for(int i=2;i<=min(m,n/2);i++)res++;if(m==n-1)res++;cout<<res%mod;
}

D - ABC Ultimatum

先考虑怎么判断给定串合法。

~~好像没什么思路先咕了~~

~~不过这题还是有学习的价值的，我们可以照着结论来翻译一下~~

设 $S_a(i),S_b(i),S_c(i)$ 表示 $1∼i1\sim i$ 中 $a, b, c$ 的个数， $M_a=\max (S_b(i)-S_a(i)),M_b=\max(S_c(i)-S_b(i)),M_c=\max(S_a(i)-S_c(i))$ ，则 $S$ 是好的当且仅当 $Ma+Mb+Mc≤nM_a+M_b+M_c\le n$

必要性应该很显然，可以猜一个结论，或者打表证明这是充要的。

~~可能有时间会补一下证明~~

然后暴力复杂度 $O(n^7)$ 。但是很显然可以省去一维状态，因此就可以在 $O(n^6)$ 时间内通过了。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int mod=998244353;
int n,dp[17][17][17][17][17][17],res;
string s;
void add(int &x,int y){if((x+=y)>=mod)x-=mod;
}
int main(){cin>>n>>s;dp[0][0][0][0][0][0]=1;for(int i=0;i<3*n;i++){for(int a=0;a<=n;a++){for(int b=0;b<=n;b++){int c=i-a-b;if(c>n||c<0)continue;for(int j=0;j<=n;j++){for(int k=0;k<=n;k++){for(int l=0;l<=n;l++){int tmp=dp[a][b][c][j][k][l];if(s[i]=='A'||s[i]=='?'){add(dp[a+1][b][c][j][k][max(l,a+1-c)],tmp);}if(s[i]=='B'||s[i]=='?'){add(dp[a][b+1][c][max(b+1-a,j)][k][l],tmp);}if(s[i]=='C'||s[i]=='?'){add(dp[a][b][c+1][j][max(c+1-b,k)][l],tmp);}}}}}}}for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){for(int k=0;k<=n;k++){if(i+j+k<=n)add(res,dp[n][n][n][i][j][k]);}}}cout<<res;
}