霍山做网站,wordpress邮件验证码,软件外包平台的服务机构,上海优秀网站建设公司https://www.zybuluo.com/ysner/note/1311407 题面 几乎所有操作系统的命令行界面\((CLI)\)中都支持文件名的通配符匹配以方便用户。 最常见的通配符有两个#xff0c;一个是星号#xff0c;可以匹配\(0\)个及以上的任意字符#xff1b; 另一个是问号#xff0c;可以匹配恰… https://www.zybuluo.com/ysner/note/1311407 题面 几乎所有操作系统的命令行界面\((CLI)\)中都支持文件名的通配符匹配以方便用户。 最常见的通配符有两个一个是星号可以匹配\(0\)个及以上的任意字符 另一个是问号可以匹配恰好一个任意字符。 现在需要你编写一个程序对于给定的文件名列表和一个包含通配符的字符串判断哪些文件可以被匹配。 \(n\leq100,|S|\leq10^5\)通配符个数\(\leq10\) 解析 由于一些不可言妙的错误我调这破题的时间跨度长达4h状态显然是\(f[i][j]\)表示上面的串匹配到第\(i\)位下面的串匹配到第\(j\)位。 然后注意到上面那串中最值得商榷的是一个通配符匹配哪些字符。 所以可以把上面的串简化为通配符形式通配符之间的部分用哈希与下面匹配就行。 这样复杂度就对了\(O(n*10|S|)\)。 然后讨论下转移就行。 #includeiostream
#includecmath
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includevector
#define ll unsigned long long
#define re register
#define il inline
#define fp(i,a,b) for(re int ia;ib;i)
#define fq(i,a,b) for(re int ia;ib;--i)
using namespace std;
const int N2e5100;
int n,m,tot,sta[50],top,ans;
ll ht[N],hs[N],jc[N];
char T[N],S[N];
bool f[20][N];
il int gi()
{re int x0,t1;re char chgetchar();while(ch!-(ch0||ch9)) chgetchar();if(ch-) t-1,chgetchar();while(ch0ch9) xx*10ch-48,chgetchar();return x*t;
}
int main()
{scanf(%s,T1);nstrlen(T1)1;T[n]?;jc[0]1;fp(i,1,N-100) jc[i]jc[i-1]*2333;fp(i,1,n){ht[i]ht[i-1]*2333T[i];if(T[i]*||T[i]?) sta[top]i;}totgi();while(tot--){scanf(%s,S1);mstrlen(S1)1;S[m]#;fp(i,1,m) hs[i]hs[i-1]*2333S[i];memset(f,0,sizeof(f));f[0][0]1;fp(i,0,top){if(T[sta[i]]*) fp(j,1,m) f[i][j]|f[i][j-1];fp(j,0,m){if(!f[i][j]) continue;re int ltsta[i]1,rtsta[i1]-1,lsj1,rsj(rt-lt1);if(ht[rt]-ht[lt-1]*jc[rt-lt1]hs[rs]-hs[ls-1]*jc[rs-ls1])f[i1][rs(T[sta[i1]]?)]|f[i][j];}}puts(f[top][m]?YES:NO);}return 0;
} SOS谁能帮我查下这份代码问题出在哪里。。。(用来交[AHOI2005]病毒检测 #includeiostream
#includecmath
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includevector
#define ll unsigned long long
#define re register
#define il inline
#define fp(i,a,b) for(re int ia;ib;i)
#define fq(i,a,b) for(re int ia;ib;--i)
using namespace std;
const int N1005;
int n,m,tot,f[N][N],sta[N],top,jc[N],ans;
ll ht[N],hs[N];
char T[N],S[N];
il int gi()
{re int x0,t1;re char chgetchar();while(ch!-(ch0||ch9)) chgetchar();if(ch-) t-1,chgetchar();while(ch0ch9) xx*10ch-48,chgetchar();return x*t;
}
int main()
{scanf(%s,T1);nstrlen(T1)1;T[n]?;jc[0]1;fp(i,1,1000) jc[i]jc[i-1]*2333;fp(i,1,n){ht[i]ht[i-1]*2333T[i];if(T[i]*||T[i]?) sta[top]i;}totgi();while(tot--){scanf(%s,S1);mstrlen(S1)1;S[m]#;fp(i,1,m) hs[i]hs[i-1]*2333S[i];memset(f,0,sizeof(f));f[0][0]1;fp(i,1,top){re int lsta[i-1]1,rsta[i]-1;fp(j,r-l1,m){if(ht[r]-ht[l-1]*jc[r-l1]hs[j]-hs[j-(r-l1)]*jc[r-l1])f[i][j(T[sta[i]]?)]|f[i-1][j-(r-l1)];}if(T[sta[i]]*) fp(j,1,m) f[i][j]|f[i][j-1];}ans1-f[top][m];}printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/yanshannan/p/9795666.html
