难度
不断网:☆☆☆
断网:☆☆☆☆
/* 卡特兰数取模 由于数据范围小，直接做。 考试时断网。忘记卡特兰数公式，推错了只有5分。 数学公式要记别每次都现用现搜！！！ */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; int f[1007]; int n,m,ans; int main() { freopen("stack.in","r",stdin); freopen("stack.out","w",stdout); scanf("%d",&n); f[0]=1;f[1]=1; for(int i=2;i<=n;i++) for(int j=0,k=i-1;j<=i-1 && k>=0;j++,k--) f[i]+=(f[j]*f[k])%7; printf("%d",f[n]%7); return 0; }
/* 模数较小是一个坑点，直接做逆元可能爆掉(模数很小许多数没有逆元) 答案是 2n!/(n!*(n+1))! 如果直接逆元,2n!预处理很可能成为零，但做了除法后答案可能不是零，就会出错。 所以7的倍数要单独考虑 这里记录了7的倍数的因子里7的幂，然后分子分母就可以加加减减了。这个题用不到。 原来逆元还可以直接搞... */ #include<bits/stdc++.h> #define N 1007 using namespace std; int n,m,d,c,r; int fac(int n) { r=1; for(int i=1;i<=n;i++) { if(i%7) r=r*i%7; else { int x=i; while(x%7==0) {x/=7;c+=d;r=r*x%7;} } }return r; } int inv(int x) { for(int i=1;i<7;i++) if(i*x%7==1) return i; } int main() { scanf("%d",&n); d=1;c=0; r=fac(2*n); int ans=(r*inv(fac(n))%7*inv(fac(n+1))%7)%7; printf("%d ",c?0:ans); return 0; }
/* 带权并查集 维护链底，链顶，并查集找链底，并维护链的大小 合并时两个链顶链底都要维护。别忘了链底size大小改为1。 */ #include<iostream> #include<cstdio> #include<cstring> #define N 30007 using namespace std; int n,m,ans,cnt; int top[N],dep[N],siz[N]; int find(int x) { if(x==dep[x]) return x; int tmp=dep[x]; dep[x]=find(tmp); siz[x]+=siz[tmp]; return dep[x]; } void merge(int a,int b) { int r1=find(a),r2=find(b); dep[r1]=top[r2]; top[r2]=top[r1]; siz[r1]=1; } int main() { freopen("cube.in","r",stdin); freopen("cube.out","w",stdout); int x,y;char ch; scanf("%d",&n); for(int i=1;i<=n;i++) top[i]=dep[i]=i; while(n--) { cin>>ch; if(ch=='M') { scanf("%d%d",&x,&y); merge(x,y); } else { scanf("%d",&x);find(x); printf("%d ",siz[x]); } } return 0; }
/* 区间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 N 257 using namespace std; int dp[N][N],col[N],a[N]; char s[N]; int n,m,ans; int main() { freopen("zuma.in","r",stdin); freopen("zuma.out","w",stdout); scanf("%s",s);n=strlen(s); a[1]=1;m=1; for(int i=1;i<n;i++) { if(s[i]==s[i-1]) { col[m]=s[i]=='0'?0:1; a[m]++; } else { a[++m]=1; col[m]=s[i]=='0'?0:1; } } for(int len=0;len<=m;len++) { for(int i=1;i<=m;i++) { int j=i+len; if(j>=1 && j<=m) { dp[i][j]=2*n; if(len==0) dp[i][j]=3-a[i]; else { for(int k=i;k<j;k++) dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]); if((j-i)%2==0) { if(a[i]+a[j]==2) { if(col[i]==col[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]+1); } else { if(col[i]==col[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]); } if(a[i]+a[j]<4) for(int k=i+2;k<j;k+=2) { if(a[k]==1) dp[i][j]=min(dp[i+1][k-1]+dp[k+1][j-1],dp[i][j]); } } } } } } printf("%d ",dp[1][m]); return 0; }