喜欢的话就坚持吧

10月 15

题目大意:

给你一个字符串s,你可以对他进行一种操作,就是把串s的除最后一个字符翻转后接到s后面
比如s=’abcab’
那么操作完了就是abcabacba;
现在给你一个串r,是进行多次操作(可以不操作)后的s串的前缀,问初始s串的可能长度。(显然比r长的都有可能,你只需要输出小于等于r的)

继续阅读

阅读全文 >>

10月 12

题目大意

给了你一个序列a,每次查询给一个区间[l,r]
查询 l \leq i< j \leq r且a_i \oplus a_j的二进制表示下有k个1的二元组(i,j)的个数。\oplus是指按位异或。

对于5%的数据,为样例
对于30%的数据,1 \leq n , m \leq 5000
对于50%的数据,空间限制为512MB
对于100%的数据,1 \leq n , m \leq 100000 , 0 \leq ai , 2^k < 16384

继续阅读

阅读全文 >>

10月 11

题目大意

点我看题)给你一颗树,每次使一个点(不)为关键点,你可以从任意一关键点出发,遍历所有点再回到出发点。对于每次操作,求最小路径。

继续阅读

阅读全文 >>

10月 08

啊?da♂rk連鎖。
……原題省略。

題目大意:

給你一棵n個節點的樹,然後往樹上添m條非樹邊。
允許你砍掉一條樹邊和一條非樹邊
使這個圖形變成兩個連通塊。
問有多少種切發?

继续阅读

阅读全文 >>

9月 26

题目大意

找到一个字符串中所有前半等于后半的字符串,如abab,按长度从短到长删除其左半部分,如果长度相等,则先删最左边的。
输出删除后剩余的字符串。

继续阅读

阅读全文 >>

9月 26

题目大意:

给定一个长度为n的小写字母串。问你有多少对相交的回文子 串(包含也算相交),对p取模,1<=n<=2*10^6。

如题所说,我们要求香♂蕉的回文串。
思考我有什么关于字符串的算法,kmp?manacher?hash?
显然要用manacher。
想想manacher求了些什么?
最长回文串?每个点的回文半径?
考虑什么样的两个串是符合条件的,某个回文串的中心离另一个回文串的中心不超过他们两最大的回文半径。
emm…
大概O(n^2)
感觉不可做了。
这是一定有什么奇技淫巧?
我们考虑什么样的是不合条件的?
对于一个位置i
以i结尾的回文串和以i后面任意字符开头的回文串的组合都是合法的。
我们可以拿总数-不合法的=合法的。
挺简单?
没错。(其实我现学的manacher)

#include <cstdio>
#include <algorithm>
#include <cstring>

#define int long long
using namespace std;
const int N=4000005;
const int mod=51123987;

char s[N],s1[N];
int p[N],len,ans,tot,n;
int f[N][2];
inline int be()
{
    int len1=strlen(s);
    s1[0]='$';s1[1]='#';
    int j=2;
    for(int i=0;i<len1;++i)
    {
        s1[j++]=s[i];
        s1[j++]='#';
    }
    s1[j]='';
    return j;
}
inline void manacher()
{
    len=be();
    int max_len=-1;
    int id,mx=0;
    for(int i=1;i<len;++i)
    {
        if(i<mx) p[i]=min(p[2*id-i],mx-i);
        else p[i]=1;
        while(s1[i-p[i]]==s1[i+p[i]]) p[i]++;
        if(mx<i+p[i])
        {
            id=i;mx=i+p[i];
        }
        max_len=max(max_len,p[i]-1);
    }
}
signed main()
{
    scanf("%lld%s",&n,s);
    manacher();
    for(int i=2;i<len;++i)
    {
        int len1=p[i]/2,pos=i/2;
        if(len1==0) continue;tot+=len1;
        if(i&1)
        {
            f[pos-len1+1][1]++;f[pos+1][1]--;
            f[pos+1][0]++;f[pos+len1+1][0]--;
        }
        else
        {
            f[pos-len1+1][1]++;f[pos+1][1]--;
            f[pos][0]++;f[pos+len1][0]--;
        }
    }
    len=strlen(s);
    for(int i=1;i<=len;++i)
    {
        f[i][1]+=f[i-1][1];f[i][0]+=f[i-1][0];
    }f[len+1][1]=0;
    for(int i=1;i<=len;++i)
    {
        f[len-i+1][1]+=f[len-i+2][1];
    }
    for(int i=1;i<=len;++i)
    {
        ans+=f[i][0]*f[i+1][1];ans%=mod;
    }tot%=mod;
    printf("%lldn",((tot*(tot-1)/2)%mod+mod-ans)%mod);
}

阅读全文 >>

9月 25

题目大意

给你一张m个点p条边的无向图,你有n张车票,每张票有一个权值t[i],你过路的代价是你任意付一张票,边权/t[i],你要从a到b,问是否有可行解。
1<=n<=8; 2<=m<=30; 1<=a,b<=m(a!=b) 1<=ti<=10; 1<=路长<=100

继续阅读

阅读全文 >>