Stack
#include<iostream>
#include<cstdio>
#define mod 7
using namespace std;
int f[][],n;
int main(){
freopen("stack.in","r",stdin);freopen("stack.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
for(int j=;j<=i;j++){
if(j)f[i][j]=f[i-][j]+f[i][j-];
else f[i][j]=;
while(f[i][j]>=mod)f[i][j]-=mod;
}
printf("%d",f[n][n]);
return ;
}
100分 卡特兰数求第n项取模
Cube
/*
记录每个点下面有多少元素top[i]，他所在并查集的大小，每次移动操作就把移动后在上面的那部分中所有的点的top加上它移动到的病茶几的大小，修改复杂度很高，查询是O(1)的
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 30010
using namespace std;
int p,fa[maxn],sz[maxn],top[maxn];
char ch[];
int find(int x){
if(fa[x]==x)return fa[x];
return fa[x]=find(fa[x]);
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("cube.in","r",stdin);freopen("cube.out","w",stdout);
scanf("%d",&p);
int n=;
for(int i=;i<=;i++)fa[i]=i,sz[i]=;
while(p--){
scanf("%s",ch);
int x,y;
if(ch[]=='M'){
scanf("%d%d",&x,&y);
n=max(n,max(x,y));
int f1=find(x),f2=find(y);
if(f1!=f2){
for(int i=;i<=n;i++){
if(find(i)==f1){
top[i]+=sz[f2];
}
}
fa[f1]=f2;
sz[f2]+=sz[f1];
sz[f1]=;
} }
else{
scanf("%d",&x);
n=max(n,x);
printf("%d\n",top[x]);
}
}
}
70分 暴力并查集
#include<iostream>
#include<cstdio>
#define maxn 30010
using namespace std;
int p,cnt[maxn],sum[maxn],fa[maxn];
char s[];
int find(int x){
if(x==fa[x])return fa[x];
int f=fa[x];
fa[x]=find(fa[x]);
cnt[x]+=cnt[f];
return fa[x];
}
void merge(int x,int y){
fa[y]=x;
cnt[y]+=sum[x];
sum[x]+=sum[y];
sum[y]=;
}
int main(){
freopen("cube.in","r",stdin);freopen("cube.out","w",stdout);
for(int i=;i<=;i++)fa[i]=i,sum[i]=;
scanf("%d",&p);
while(p--){
scanf("%s",s);
int x,y;
if(s[]=='M'){
scanf("%d%d",&x,&y);
merge(find(x),find(y));
}
else {
scanf("%d",&x);
printf("%d\n",sum[find(x)]-cnt[x]-);
}
}
}
100分 带权并查集
Zuma
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
map<string,bool>vis;
string s,snow;
struct node{
string s;
int step;
}cur,nxt;
queue<node>q;
void down(){
string pre=snow;
snow="";
for(int i=;i<pre.length();){
while(pre[i]==''&&i<pre.length())i++;
snow=snow+pre[i];i++;
}
}
void updata(){
string pre=snow;
bool flag=;
for(int i=;i<pre.length();i++){
if(pre[i]==pre[i-]&&pre[i]==pre[i+])flag=,snow[i]=snow[i-]=snow[i+]='';
}
if(flag){
down();
updata();
}
}
int main(){
//freopen("Cola.txt","r",stdin);
freopen("zuma.in","r",stdin);freopen("zuma.out","w",stdout);
cin>>s;
vis[s]=;
cur.s=s;cur.step=;
//cout<<s<<endl;
bool flag=;
int n1=,n0=;
for(int i=;i<s.length();i++){
if(s[i]==s[i-]){
flag=;break;
}
if(s[i]=='')n0++;
if(s[i]=='')n1++;
}
if(flag==){
int ans=;
if(s[]=='')n0++;
if(s[]=='')n1++;
if(n1%==&&n0%==&&n1==n0){
ans=+(n1/)+((n0-)/)+;
printf("%d",ans);
return ;
}
if(n1%==&&n0%==&&n1==n0){
ans=+((n1-)/)+((n0-)/);
printf("%d",ans);
return ;
}
if(n1<n0)swap(n1,n0);
if(n1%==&&n0==n1-){
ans=+((n1-)/)+(n0/);
printf("%d",ans);
return ;
}
if(n1%==&&n0==n1-){
ans=+(n1/)+((n0-)/);
printf("%d",ans);
return ;
}
}
q.push(cur);
while(!q.empty()){
cur=q.front();q.pop();
int len=cur.s.length();
//cout<<cur.s<<endl;
if(len==){printf("%d",cur.step);return ;}
for(int i=;i<=len;i++){//在第i个前面插
snow="";
snow=snow+cur.s.substr(,max(,i));
snow=snow+"";
snow=snow+cur.s.substr(i,len-i);
string now=snow;
updata();
if(!vis[snow]){
vis[snow]=;
nxt.s=snow;nxt.step=cur.step+;
q.push(nxt);
if(nxt.s.length()==&&nxt.s[]!=''&&nxt.s[]!=''){printf("%d",nxt.step);return ;}
}
//cout<<snow<<endl; snow=now;
snow[i]='';
updata();
if(!vis[snow]){
vis[snow]=;
nxt.s=snow;nxt.step=cur.step+;
q.push(nxt);
if(nxt.s.length()==&&nxt.s[]!=''&&nxt.s[]!=''){printf("%d",nxt.step);return ;}
}
//cout<<snow<<endl;
}
}
fclose(stdin);fclose(stdout);
return ;
}
65分 宽搜
/*
区间dp，情况有些多需要讨论
首先连续相同的颜色为了方便要合并，记录每个块的颜色，就可以dp了
dp[l][r]表示合并这段区间的最小步数，分几种情况
这段区间是奇数(为了避免区间长度为2的情况)
1. color[l]==color[r] && tot[l]+tot[r]==2 --> dp[l][r] 可从 dp[l+1][r-1]+1 转移过来。
2. color[l]==color[r] && tot[l]+tot[r]>2 --> dp[l][r] 可从 dp[l+1][r-1] 转移过来。
3. color[l]==color[k]==color[r](k∈(l,r) && [l,k],[k,r] 为奇数) -->可从dp[l+1][k-1]+dp[k+1][r-1]转移过来。
这段区间是偶数
普通的转移 dp[l][r] =min(dp[l][r] , dp[l][k]+dp[k+1][r]);
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 257
using namespace std;
int dp[maxn][maxn],col[maxn],a[maxn];
char s[maxn];
int n,m,ans;
int main(){
freopen("zuma.in","r",stdin);freopen("zuma.out","w",stdout);
scanf("%s",s);n=strlen(s);
a[]=;m=;
for(int i=;i<n;i++){
if(s[i]==s[i-]){
col[m]=s[i]-'';
a[m]++;
}
else {
a[++m]=;
col[m]=s[i]-'';
}
}
for(int len=;len<=m;len++){
for(int i=;i<=m;i++){
int j=i+len;
if(j>=&&j<=m){
dp[i][j]=*n;
if(len==)dp[i][j]=-a[i];
else {
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][k]+dp[k+][j],dp[i][j]);
if((j-i)%==){
if(a[i]+a[j]==){
if(col[i]==col[j])
dp[i][j]=min(dp[i][j],dp[i+][j-]+);
}
else
if(col[i]==col[j])
dp[i][j]=min(dp[i][j],dp[i+][j-]);
if(a[i]+a[j]<)
for(int k=i+;k<j;k+=)
if(a[k]==)dp[i][j]=min(dp[i+][k-]+dp[k+][j-],dp[i][j]);
}
}
}
}
}
printf("%d\n",dp[][m]);
return ;
}
100分 区间dp