头像

Cccc




离线:1天前



Cccc
4天前

请问如何严格证明tarjan有向图算法逆序为拓扑序呢。。看了y总视频的证明还是有一些迷糊



活动打卡代码 AcWing 1282. 搜索关键词

Cccc
3个月前

AC自动机未优化版

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
queue<int>q;
const int N=1e4+10,M=1e6+10,K=55;
int tr[N*K][26],idx,cnt[K*N],ne[K*N];
char str[M];
void insert()
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int t=str[i]-'a';
        if(!tr[p][t])   tr[p][t]=++idx;
        p=tr[p][t];
    }
    cnt[p]++;
}
void build()
{
    for(int i=0;i<26;i++)
    if(tr[0][i])
    q.push(tr[0][i]);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=0;i<26;i++)
        {
            int p=tr[t][i];
            if(!p)  continue;
            int j=ne[t];
            while(j&&!tr[j][i]) j=ne[j];
            if(tr[j][i])    j=tr[j][i];
            ne[p]=j;
            q.push(p);
        }
    }
}
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        memset(tr,0,sizeof tr);
        memset(cnt,0,sizeof cnt);
        memset(ne,0,sizeof ne);
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>str;
            insert();
        }
        build();
        cin>>str;
        int res=0;
        for(int i=0,j=0;str[i];i++)
        {
            int t=str[i]-'a';
            while(j&&!tr[j][t]) j=ne[j];
            if(tr[j][t])    j=tr[j][t];
            int p=j;
            while(p)
            {
                res+=cnt[p];
                cnt[p]=0;
                p=ne[p];
            }
        }
        cout<<res<<endl;
    }
}



Cccc
4个月前

c++的set迭代器不支持相减操作,请问有什么快捷的方法求得set中某区间范围内存在的值的个数吗



活动打卡代码 AcWing 843. n-皇后问题

Cccc
8个月前
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10;
bool row[N],col[N],x[2*N],fx[2*N];
char g[N][N];
int n;
void dfs(int k)
{
    if(k==n) 
    {
    for(int i=0;i<n;i++)
    printf("%s\n",g[i]);
    cout<<endl;
    return;
    }
    for(int i=0;i<n;i++)
    if(row[i]==false&&col[i]==false&&x[i+k-1]==false&&fx[i-k+n]==false)
    {
    g[k][i]='Q';
    row[i]=true,col[i]=true,x[i+k-1]=true,fx[i-k+n]=true;
    dfs(k+1);
    row[i]=false,col[i]=false,x[i+k-1]=false,fx[i-k+n]=false,g[k][i]='.';
    } 
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    g[i][j]='.';
    dfs(0);
    system("pause");
    return 0;
}