P3538 OKR-A Horrible Poem

#include <bits/stdc++.h>
#define F(i,l,r) for(int i=l;i<=r;i++)
#define FK(x) memset(x,0,sizeof(0))
#define int unsigned long long

using namespace std;
/*-----------------------------*/
const int manx = 5e5 + 10;
//const int mod = 1e9+9;
const int base = 3;

inline int read(){
    char c = getchar();int x = 0,f = 1;
    for(;!isdigit(c);c = getchar())if(c == '-') f = -1;
    for(;isdigit(c);c = getchar()) x = x*10 + (c^48);
    return x * f;
}
int n, p[manx], m, sum[manx], num[500010][26], x, y;
char a[manx];
inline void prepare(){
    p[0] = 1;
    F(i,1,n) p[i] = p[i-1]*base;    
}
inline int apart(int l, int r){
    return (sum[r] - sum[l-1]*p[r-l+1] ) ;
}
inline bool check(int l, int lenth){
    int x1 = apart(x,y-l),x2 = apart(x+l,y);
    if(x1 == x2) return 1;
    return 0;
}
inline int gcd(int x,int y){
    return y ? gcd(y, x%y) : x;
}
signed main(){
   // freopen("d.in","r",stdin);
   // freopen("d.out","w",stdout);
    n = read();
    prepare();
    scanf("%s", a + 1);
    int s = strlen(a+1);
    m = read();
    F(i,1,s) sum[i] = (sum[i-1]*base + a[i]) ;
    F(i,1,s)
    F(j,1,26){
        num[i][j] = num[i-1][j] + (a[i]-'a'+1==j);
    }
    while(m--){
        x = read(), y = read();
        int ans = 0, l = 1, gcd_;
        int k = y - x + 1;
        gcd_ = k;
        F(i,1,26) gcd_= gcd(gcd_, num[y][i] - num[x-1][i]);
        for(int i = 1; i * i<= gcd_; i++){
            if(gcd_% i == 0){
                if(check(k/(gcd_/i), k)){ans = max(ans, gcd_/i);break;} 
                if(check(k/i, k)) ans = max(ans,i);
            }
        }
        printf("%d\n",k/ans);
    }
    return 0;
}

P3879 阅读理解

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    __gnu_pbds::cc_hash_table<string, bitset<1000>> has;
    int n, m, l;
    string s;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l;
        for (int j = 0; j < l; j++) {
            cin >> s;
            has[s][i] = true;
        }
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> s;
        for (int j = 0; j < n; j++) {
            if (has[s][j]) {
                cout << j + 1 << ' ';
            }
        }
        cout << endl;
    }
    return 0;
}

P3065 First G

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,M=3e4+5,S=27;

int n,tot,dgr[S],son[N][S],q[S],Enum,H[S],to[S*S],nxt[S*S];
bool vis[N],mrk[M],lnk[S][S];
string str[M];
char tmp[10005];

inline void AddEdge(int u,int v)
{
    to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
}
//void Insert(char *s)
void Insert(string s)//faster
//直接用全局的tmp略快一点 
{
//  int l=strlen(s),id,u=0;
    int l=s.size(),id,u=0;
    for(int i=0;i<l;++i)
    {
        id=s[i]-'a';
        if(!son[u][id]) son[u][id]=++tot;
        u=son[u][id];
    }
    vis[u]=1;
}
//bool Solve(string s)
bool Solve(int p)//faster
{
    int l=str[p].size(),id,u=0;
    for(int i=0;i<l;++i)
    {
        if(vis[u]) return 0;
        id=str[p][i]-'a';
        for(int j=0;j<26;++j)
            if(son[u][j] && id!=j && !lnk[id][j])
                ++dgr[j], lnk[id][j]=1, AddEdge(id,j);
        u=son[u][id];
    }
    return 1;
}
bool TopoSort()
{
    int h=0,t=0,x;
    for(int i=0;i<26;++i)
        if(!dgr[i]) q[t++]=i;
    while(h<t)
    {
        x=q[h++];
        for(int i=H[x];i;i=nxt[i])
            if(!--dgr[to[i]]) q[t++]=to[i];
    }
    for(int i=0;i<26;++i)
        if(dgr[i]) return 0;
    return 1;
}

int main(){
//  freopen("3065.in","r",stdin);
//  freopen("3065.out","w",stdout);

    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%s",tmp), str[i]=tmp, Insert(str[i]);
    int res=0;
    for(int i=1;i<=n;++i)
    {
        Enum=0;
        memset(H,0,sizeof H);
        memset(lnk,0,sizeof lnk);
        memset(dgr,0,sizeof dgr);
        if(!Solve(i)) continue;
        if(TopoSort()) mrk[i]=1,++res;
    }
    printf("%d\n",res);
    for(int i=1;i<=n;++i)
        if(mrk[i]) printf("%s\n",str[i].c_str());

    return 0;
}