510. Distinct Substrings

给你一个N,让你求有恰有N个不同字串的,尽可能短的,如有多个就字典序最小的那个的字符串。。。
我感觉没有任何思路,只能暴搜。。
肯定要减枝,就是估计一个当前以当前字符串为前缀的最大可能的不同子串数。。
我不知道对不对,我是在后面defghijk这么加上去再算不同字串数的。。
计算不同字串数的话题目中也说是标准的SA问题,但我直接用Set了。。
Code:

#include<cstring>#include<iostream>#include<string>#include<cstdlib>#include<set>#define Rep(i,n) for(int i=0;i<n;i++)using namespace std;int n;string C;int Get(const string&a){ set<string> S;int n=a.size(); for(int i=0;i<n;i++) for(int j=1;i+j<=n;j++) S.insert(a.substr(i,j)); return S.size();}int Cal(int p,char u){ for(int i=p;i<C.size();i++) C[i]=++u; return Get(C);}void Dfs(int p,char u){ int N=Cal(p,u); if(N<n)return; if(p==C.size()) { if(N==n) { cout<<C<<endl; exit(0); } return; } for(char a=’a';a<=u;a++) { C[p]=a; Dfs(p+1,u); } if(u<‘z’){C[p]=++u;Dfs(p+1,u);}}int main(){ cin>>n; for(int i=1;;i++) { C.resize(i); Dfs(0,’a’-1); }}

SGU 505. Prefixes and suffixes

就是给你一大堆字符串,然后每次询问以一个给定串为前缀,
一个给定串为后缀的字符串有几个?
我是一直没有思路的,但是在做出网易比赛的拿到有道搜索框之后
我就已经知道算法了。。但是
一直WA,今天才发现是犯了个SB错误囧啊。。。
是这样的,将所有字符串排序,由那题我明白了所有由某个前缀的字符串是一个区间,
然后将所有字符串
全部反过来排序,那么由某个后缀的字符串也是一个区间,把这些字符串都标上其在
第一遍排序中的排名。。那么问题就成了,在[a,b]中,[l,r]之间的数有几个。。
那么由两种办法,一种是在线算法,就是建个线段树,那么是LogN^2的。。
另一种就是离线算法,只需要一个树状数组就OK了。。。
鉴于第一个可能TLE。。所以我用了离线算法。。编写上需要注意一些东西。。
我发现关于string的话,cin还是蛮快的。。
Code:
include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#define pb push_back
#define Rep(i,n) for(int i=0;i<n;i++)
#define All(x) x.begin(),x.end()
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
using namespace std;
const int maxn=100000,maxm=100000;
string S[maxn],R[maxn];
int n,m,Ans[maxm]={},A[maxn];
struct Data
{
    int l,r,num,d;
    Data(int _l,int _r,int _num,int _d):l(_l),r(_r),num(_num),d(_d){}
};
vector<Data> E[maxn];
bool AsPrefix(const string&str,const string&prefix)
{
    if(str.size()<prefix.size()||str.substr(0,prefix.size())!=prefix)
        return false;
    return true;
}
void get(string S[maxn],string pre,int&l,int&r)
{
    l=lower_bound(S,S+n,pre)-S;
    pre[pre.size()-1]++;
    r=lower_bound(S,S+n,pre)-S;
}
struct TreeArray
{
    int H[maxn+10];
    TreeArray(){memset(H,0,sizeof(H));}
    void Add(int l,int d)
    {
        l++;
        for(;l<=n;l+=(l&-l))
            H[l]+=d;
    }
    int operator[](int l)
    {
        l++;int ret=0;
        for(;l>0;l-=(l&-l))
            ret+=H[l];
        return ret;
    }
}T;
int main()
{
    //freopen("in","r",stdin);
    cin>>n;Rep(i,n)cin>>S[i],R[i]=S[i],reverse(All(R[i]));
    sort(S,S+n);sort(R,R+n);
    Rep(i,n)
    {
        string tmp=R[i];reverse(All(tmp));
        A[i]=lower_bound(S,S+n,tmp)-S;
    }
    cin>>m;string Pre,Suf;
    Rep(i,m)
    {
        cin>>Pre>>Suf;
        int l,r,a,b;
        get(S,Pre,l,r);
        if(l==r)continue;
        reverse(All(Suf));
        get(R,Suf,a,b);
        if(a==b)continue;
        E[b-1].pb(Data(l,r-1,i,1));
        if(a)E[a-1].pb(Data(l,r-1,i,-1));
    }
    Rep(i,n)
    {
        T.Add(A[i],1);
        tr(e,E[i])Ans[e->num]+=(T[e->r]-T[e->l-1])*e->d;
    }
    Rep(i,m)printf("%dn",Ans[i]);
}

[SDOI2009]SuperGCD

[SDOI2009]SuperGCD

Time Limit:4000MS Memory Limit:65536K
Total Submit:34 Accepted:6
Case Time Limit:1000MS

Description

Sheng bill有着惊人的心算能力,甚至能用大脑计算出两个巨大的数的GCD(最大公约
数)!因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你,并要求和你比
赛,但是输给Sheng bill岂不是很丢脸!所以你决定写一个程序来教训他。

Input

共两行:
第一行:一个数A。
第二行:一个数B。

Output

一行,表示A和B的最大公约数。

Sample Input

Sample Output

Hint

对于20%的数据,0 < A , B ≤ 10 ^ 18。
对于100%的数据,0 < A , B ≤ 10 ^ 10000。

Source

Day1
总算AC了这题,感谢GCD。。。
然后是算法。。。TMD八中OJ居然没有Java。。。。只好自己写高精度,算法是这样的。。
设这两个数是A,B
那么若2|A和B (A,B)=2(A/2,B/2)。。
若2|A且2不整除B, (A,B)=(A/2,B)..
若A和B都是奇数,设A<B,(A,B)=(A,B-A)…
关键是一般的高精度超时很严重啊。。
于是压位,我压了10位。。结果因为Long Long的问题WA了几次。。。
然后把所有的2放在一起乘。。。
就很快了。。。
Orz。sevenk神牛。。
Code:

#include<cstdio>#include<cstring>#include<iostream>#define Rep(i,n) for(int i=0;i<n;i++)using namespace std;typedef unsigned long long ull;const int maxn=10000+10,L=10;const ull m=1e10;char C[maxn+10];ull P[L];struct BigInt{ ull H[maxn/L+1];int l; BigInt() { memset(H,0,sizeof(H));l=0; } void divide() { ull d=0; for(int i=l;i>=0;i–) { d*=m;d+=H[i]; H[i]=d/2;d%=2; } while(l&&!H[l])l–; } int mod() { return H[0]%2; } void operator*=(int x) { ull d=0; for(int i=0;i<=l;i++) { d+=H[i]*x;H[i]=d%m; d/=m; } while(d)H[++l]=d%m,d/=m; } void operator-=(const BigInt&o) { ull d=0; for(int i=0;i<=l;i++) { H[i]-=d; if(H[i]<o.H[i])H[i]+=m,d=1; else d=0; H[i]-=o.H[i]; } while(l&&!H[l])l–; } void ReadIn() { memset(C,0,sizeof(C)); scanf("%s",C);int s=0;l=0;ull a=0; for(int i=strlen(C)-1;i>=0;i–) { a+=(C[i]-‘0′)*P[s++]; if(s==L)H[l++]=a,s=0,a=0; } if(!s)l–;else H[l]=a; } void Print() { printf("%I64d",H[l]); for(int i=l-1;i>=0;i–)printf("%010I64d",H[i]); } bool operator<(const BigInt&o)const { if(l!=o.l)return l<o.l; for(int i=l;i>=0;i–) { if(H[i]<o.H[i])return true; if(H[i]>o.H[i])return false; } } bool iszero()const{return l==0&&H[l]==0;}}A[2];int main(){ freopen("in","r",stdin); P[0]=1;Rep(i,L-1)P[i+1]=P[i]*10; A[0].ReadIn();A[1].ReadIn(); int a=0,b=1,c=0; while(true) { if(A[b]<A[a])a^=b^=a^=b; //A[a].Print();printf(",");A[b].Print(); //puts(""); if(A[a].iszero()) { while(c>=16)A[b]*=(1<<16),c-=16; while(c–)A[b]*=2; A[b].Print(); break; } int i=A[a].mod(),j=A[b].mod(); if(!i)A[a].divide(); if(!j)A[b].divide(); if(!i&&!j)c++; if(i&&j)A[b]-=A[a]; }}61254

Page 3 of 3123