CF 396(2) C 简单dp D 并查集 E 二进制拆位+dfs统计
题意:给出a[26]数组,表示26个英文字母能够存在于长度不超过ai的字符串中。把长度为n的字符串分割,要使得分割后的各个字符串中的字母都满足条件。求有多少种方案,能分割出的最长子串的长度,和分割后子串数量的最小值。
题解:看了代码才发现,就是一个水dp。 取dp[i]表示长度为i的字符串的分割方案数,然后往前推即可,答案就是dp[n]。但这样复杂度是O(n^2),(n<1000),官方题解说有O(n)的做法,不会。。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define FF(i,a,b) for (int i=a;i<=b;i++) #define F(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 1e3+10, mod = 1e9+7; int n, a[26], cnt[N], maxn; ll dp[N]; char s[N]; int main() { cin>>n>>s+1; FF(i,0,25) cin>>a[i]; mes(cnt, INF); dp[0]=1, cnt[0]=0; FF(i,1,n) { int m=a[s[i]-'a']; for(int j=i-1; i-j<=m&&j>=0; j--) { if(j>=1) m=min(m, a[s[j]-'a']); dp[i]=(dp[i]+dp[j])%mod; cnt[i]=min(cnt[i], cnt[j]+1); maxn=max(maxn, i-j); } } cout<<dp[n]<<endl<<maxn<<endl<<cnt[n]<<endl; return 0; }
题意:n个单词,m个关系,每个关系表示两个单词是同义或是反义。q个询问,问两个单词是同义、反义还是没关联。
题解:大神都说是老题,但对我来说还是新题。。。如 i、j是同义,则2*i,2*j相同,2*i-1,2*j-1相同; 如 i、j反义,则2*i,2*j-1相同,2*i-1,2*j相同。 注:并查集变种
// CF396 C #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define FF(i,a,b) for (int i=a;i<=b;i++) #define F(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 1e5+10; int n, m, q, t, fa[N<<1], a, b; string s1, s2; map<string, int >M; int Find(int c) { int p=c, i=c, j; while(fa[p]!=p) p=fa[p]; while(fa[i]!=p) j=fa[i], fa[i]=p, i=j; return p; } void Unite(int u, int v) { int fau=Find(u), fav=Find(v); if(fau!=fav) fa[fav]=fau; } int main() { cin>>n>>m>>q; FF(i,1,n<<1) fa[i]=i; FF(i,1,n) cin>>s1, M[s1]=i; FF(i,1,m) { cin>>t>>s1>>s2; a=M[s1], b=M[s2]; if(t==1) { if(Find(2*a)==Find(2*b-1)) puts("NO"); else { Unite(2*a, 2*b); Unite(2*a-1, 2*b-1); puts("YES"); } } else { if(Find(2*a)==Find(2*b)) puts("NO"); else { Unite(2*a, 2*b-1); Unite(2*a-1, 2*b); puts("YES"); } } } FF(i,1,q) { cin>>s1>>s2; a=M[s1], b=M[s2]; if(Find(2*a)==Find(2*b)) puts("1"); else if(Find(2*a)==Find(2*b-1)) puts("2"); else puts("3"); } return 0; }