3 条题解
-
2
建议宁老师把题目数量调整至 4~5 题，这样能使得我们更加深入地思考每一道题。
本题就是，其实注意到一些性质很快就可以做出来，但是大家场上没有充分思考。
首先注意到每个点的对应唯一，然后我们发现其实就是在序列上选出一些数来看看有没有逆序对。
然后注意到逆序对最后一个字是对，也就是两个数的关系，所以我们并不在乎给定的字符集整体，而是它们当中的每一对。
于是我们枚举26*26的字符对，进行预处理，然后暴力判断即可。
然后我以为本题多测，于是想到了更优秀的做法，建议宁老师加强数据到
好了我来填坑了，我们前面已经提到，其实就是对于所有的字母对求是否存在逆序对。
然后我们其实可以同时处理所有的字母对，我们首先考虑，一般来说我们在统计逆序对的时候使用树状数组统计个数，这里我们可以类似去处理。
这里我不再多写，代码里有注释，自己学习理解一下，因为我不太好用单纯的文字进行描述。
#include<bits/stdc++.h> using namespace std; char a[100005],b[100005]; int id[100005],cntt[100005]; vector<int>vec1[30],vec2[30]; int S[26],c[100005],n,m; //我们其实可用类似的方法来统计一个字母集合。 //以下的树状数组可以统计每一个数字对应的字母集合。 inline int lowbit(int x){return x&-x;} inline void add(int x,int S){for(int i=x; i<=m+1; i+=lowbit(i))c[i]|=S;} inline int sum(int x){int ans=0;for(int i=x; i; i-=lowbit(i))ans|=c[i];return ans;} int main(){ scanf("%s%s",a+1,b+1); n=strlen(a+1),m=strlen(b+1); for(int i=1; i<=n; i++)vec1[a[i]-'a'].push_back(i); for(int i=1; i<=m; i++)vec2[b[i]-'a'].push_back(i); for(int i=0; i<26; i++){ if(vec1[i].size()!=vec2[i].size())S[i]|=(1<<i); while(vec1[i].size()>vec2[i].size())vec2[i].push_back(0); for(int j=0; j<vec1[i].size(); j++){ int x=vec1[i][j],y=vec2[i][j]; id[x]=y; } }for(int i=1; i<=n; i++){ S[a[i]-'a']|=sum(m-id[i]); add(m-id[i]+1,(1<<a[i]-'a')); /*但是我们发现，因为树状数组存储的东西必须满足可差分性。而集合的并显然不满足，不过没有关系 我们可以考虑把它倒序存到树状数组里，这样查找的时候就是前多少项的并，然后就不需要可差分性了。 */ } for(int i=0; i<26; i++){ for(int j=0; j<26; j++){ if((S[i]>>j)&1)S[j]|=(1<<i); /* 我们要把这个邻接矩阵对称一下。*/ } } int t;scanf("%d",&t); while(t--){ char ch[30];scanf("%s",ch+1); int s=0; int t=strlen(ch+1); for(int i=1; i<=t ;i++)s|=(1<<ch[i]-'a'); bool ok=1; for(int i=1; i<=t; i++){ if(s&S[ch[i]-'a']){ ok=0; break; } } if(ok){ putchar('Y'); }else{ putchar('N'); } } return 0; } ``` ` -
-2
考虑两个字母是否能够同时出现
bool check(char x,char y){ int cnt = 0; for(char c : a) if(c == x) cnt++; for(char c : b) if(c == x) cnt--; if(cnt != 0) return 0; for(char c : a) if(c == y) cnt++; for(char c : b) if(c == y) cnt--; if(cnt != 0) return 0; int i = 0,j = 0; int n = a.size(); int m = b.size(); while(i < n && j < m){ while(i < n && a[i] != x && a[i] != y) i++; while(j < m && b[j] != x && b[j] != y) j++; if(i < n && j < m && a[i] != b[j]) return 0; i++; j++; } return 1; }然后每读入一个s判一下就好
-
-8
对 A、B 进行预处理，尝试寻找形如 “颜色 p 和颜色 q 不能共存” 的限制。
若颜色 x 在 A、B 中出现次数不一样，则一定不选，记为 f (x,x)=1.
剩余部分构成了若干组相同颜色匹配，如图：
容易发现，若 p 和 q 共存，则一定存在 p 的一组匹配与 q 的一组匹配交叉
故枚举 p、q 的一组匹配（A 中的第 a 个 B 中的第 b 个）。
记 A 中 a 前面 q 的个数为 c1，B 中 b 前面 q 的个数为 c2，通过二分求出 c1、c2，若 c1≠c2，则 f (p,q)=f (q,p)=1。
解释:若c1>c2，则A中第c1个q在B中的匹配一定在b右边，故一定交叉。反之亦然。
对于每一组查询，枚举每一条限制，若都满足则合法，否则不合法。
时间复杂度分析：枚举所有 p 和 q 的一组匹配，等价于枚举所有匹配，最多为 n。
这部分时间复杂度 O (sn logn)，s 表示字母种类数。
限制最多 s² 条，查询复杂度 O (s²k) 总复杂度 O (sn logn + s²k)，s=26
别急 后面还有#include<bits/stdc++.h> using namespace std; string s1,s2,s; int len1,len2,a[101000],b[101000],cnt1[33],cnt2[33]; int v1[33][101000],v2[33][101000]; int unok[33][33],k;//unok即为不可行关系 int vis[33]; signed main(){ ios::sync_with_stdio(0);cin.tie(0); cin>>s1>>s2; len1=s1.size();len2=s2.size(); s1=" "+s1;s2=" "+s2; for(int i=1;i<=len1;i++){ a[i]=s1[i]-'a'+1; v1[a[i]][++cnt1[a[i]]]=i; //A串中颜色a[i]出现第cnt1[a[i]]次是在位置i }for(int i=1;i<=len2;i++){ b[i]=s2[i]-'a'+1; v2[b[i]][++cnt2[b[i]]]=i; } for(int i=1;i<=26;i++){//p if(cnt1[i]!=cnt2[i]) unok[i][i]=1; else{ for(int j=1;j<=cnt1[i];j++){//每一组匹配 int xa=v1[i][j],xb=v2[i][j]; for(int o=1;o<=26;o++){//q if(o==i||cnt1[o]==0||cnt2[o]==0) continue; //二分 int al=0,ar=cnt1[o]; while(al<ar){ int mid=(al+ar+1)/2; if(xa<v1[o][mid]) ar=mid-1; else al=mid; } int bl=0,br=cnt2[o]; while(bl<br){ int mid=(bl+br+1)/2; if(xb<v2[o][mid]) br=mid-1; else bl=mid; } if(bl!=al) unok[i][o]=unok[o][i]=1; } } } } cin>>k; for(int i=1;i<=k;i++){ cin>>s; int len=s.size();s=" "+s; memset(vis,0,sizeof(vis)); for(int j=1;j<=len;j++) vis[s[j]-'a'+1]=1; int flag=0; for(int fr=1;fr<=26;fr++){ for(int to=1;to<=26;to++){ if(unok[fr][to]&&vis[fr]&&vis[to]){ flag=1; break; } }if(flag) break; } if(flag) cout<<"N"; else cout<<"Y"; } return 0; }Update 1.7
听说有个人要加大数据卡我
考虑优化：
注意到二分每个颜色q的时候最前面的部分被考虑了多次，于是考虑同时处理每一个q。
处理出当前 A 串中 a 前面的每一个颜色的出现次数 cnta 和 B 串中 b 前面每一个颜色的出现次数 cntb。
若cnta[q]≠cntb[q] 则交叉。
可达到均摊复杂度 O (sn)。
查询部分，注意到我们可以把限制的第二维二进制压缩成一个数，复杂度变为 O (sn)。
总复杂度 O (sn)，s=26
#include<bits/stdc++.h> using namespace std; //#define int long long const int inf=1e15; string s1,s2,s; int len1,len2; int a[1010000],b[1010000]; int cnt1[33],cnt2[33]; int v1[27][1010000],v2[27][1010000]; int unok[33],k;//unok即为不可行关系 int vis; int cnta[33],cntb[33]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>s1>>s2; len1=s1.size(); len2=s2.size(); s1=" "+s1; s2=" "+s2; for(int i=1;i<=len1;i++){ a[i]=s1[i]-'a'+1; v1[a[i]][++cnt1[a[i]]]=i; //A串中颜色a[i]出现第cnt1[a[i]]次是在位置i }for(int i=1;i<=len2;i++){ b[i]=s2[i]-'a'+1; v2[b[i]][++cnt2[b[i]]]=i; } for(int i=1;i<=26;i++){//p if(cnt1[i]!=cnt2[i]) unok[i]=(unok[i]|(1<<i)); else{ memset(cnta,0,sizeof(cnta)); memset(cntb,0,sizeof(cntb)); for(int j=1;j<=cnt1[i];j++){//每一组匹配 int xa=v1[i][j],xb=v2[i][j]; for(int x=v1[i][j-1]+1;x<=xa;x++) cnta[a[x]]++; for(int x=v2[i][j-1]+1;x<=xb;x++) cntb[b[x]]++; for(int o=1;o<=26;o++){//q if(o==i||cnt1[o]==0||cnt2[o]==0) continue; if(cnta[o]!=cntb[o]){ // unok[i][o]=unok[o][i]=1; unok[i]=(unok[i]|(1<<o)); unok[o]=(unok[o]|(1<<i)); } } } } } cin>>k; for(int i=1;i<=k;i++){ cin>>s; int len=s.size(); s=" "+s; vis=0; for(int j=1;j<=len;j++){ vis=(vis|(1<<(s[j]-'a'+1))); } int flag=0; for(int x=1;x<=26;x++){ if(vis&(1<<x))flag=(flag|(vis&unok[x])); if(flag) break; } if(flag) cout<<"N"; else cout<<"Y"; } return 0; }Edited by ZT
- 1
