danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26237

[洛谷 P1637]三元上升子序列

2016年9月13日 12:46 | Comments(0) | Category:题解 | Tags:

这个明显是用树状数组进行统计……然而是树状数组统计第一题……so sad

答案很有可能就超int,建议开long long(反正我这么做了)。

代码:

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=30005;
int n;
struct BIT{
    int C[maxn];
    inline int lowbit(int x){
        return x&-x;
    }
    inline void Add(int p,int v){
        while(p<=n){
            C[p]+=v;
            p+=lowbit(p);
        }
    }
    inline int Sum(int x){
        register int ans=0;
        while(x>0){
            ans+=C[x];
            x-=lowbit(x);
        }
        return ans;
    }
    inline int Query(int l,int r){
        return Sum(r)-Sum(l-1);
    }
};

BIT T1,T2;
int A[maxn],A2[maxn];
int siz;
inline void InitLsh(){
    register int i;
    sort(A2+1,A2+n+1);
    siz=unique(A2+1,A2+n+1)-A2-1;
}
inline int GetLsh(int i){
    return lower_bound(A2+1,A2+siz+1,A[i])-A2;
}

int main(){
    register int i,left,right,temp;
    register long long ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        A2[i]=A[i];
    }
    InitLsh();
    for(i=1;i<=n;i++){
        T2.Add(GetLsh(i),1);
    }
    for(i=1;i<=n;i++){
        temp=GetLsh(i);
        T2.Add(temp,-1);
        left=T1.Sum(temp-1);
        right=T2.Query(temp+1,siz);
        ans+=((long long)left)*((long long)right);
        T1.Add(temp,1);
    }
    printf("%lld\n",ans);
    return 0;
}

[洛谷 P1962]斐波那契数列

2016年9月01日 13:18 | Comments(0) | Category:题解 | Tags:

线性代数的很多知识用一句欠揍的话形容就是:只可意会,不可言传。

友矩阵就是一个。友矩阵是一种应用于求递归数列的一种矩阵,作用是将一个旧的递归数列向量变成一个新的递归数列向量。友矩阵长相比较美(qi)观(pa),可以自行问度娘。

关于递归数列[tex]F[/tex],如果假设要用到的从前的信息可以组织为一个列向量[tex]F_{n-1}[/tex],若已知其友矩阵为[tex]A[/tex],则有下公式(这个推导其实并不难,如果你用解线性方程组的思维来看的话):

[tex]F_n=A\mul F_{n-1}[/tex]

可知(假设要用到的从前的信息为[tex]d[/tex]):

[tex]F_n=A^{n-d}*F_d[/tex]

然后我们发现求[tex]A^{n-d}[/tex]可以使用快速幂,这就简单了^_^

不过有个不错的小技巧:快速幂结果矩阵的初始值处理让人很头疼,不过可以直接使用单位矩阵,这样就相当于通常计算中的1辣~

代码:

#include <iostream>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
typedef ull Matrix[2][2];
const ull MOD=1000000007;
#define REP(i,n) for(i=0;i<(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
#define CP_ARR(from,to) memcpy(to,from,sizeof(from))

inline void MatrixMul(Matrix A,Matrix B,int m,int n,int p,Matrix& res){
    Matrix C;
    register int i,j,k;
    CL_ARR(C,0);
    REP(i,m){
        REP(j,p){
            REP(k,n){
                C[i][j]=(C[i][j]+(A[i][k]*B[k][j])%MOD)%MOD;
            }
        }
    }
    CP_ARR(C,res);
}
void MatrixPow(Matrix A,ull x,Matrix& res){
    Matrix a,temp;
    register int i;
    bool used=false;
    memcpy(a,A,sizeof(a));
    CL_ARR(temp,0);
    temp[0][0]=1;
    temp[1][1]=1;
    while(x){
        if(1&x){
            MatrixMul(temp,a,2,2,2,temp);
        }
        x>>=1;
        MatrixMul(a,a,2,2,2,a);
    }
    CP_ARR(temp,res);
}
Matrix Q={{0,1},{1,1}};
Matrix Fib={{1,0},{1,0}};
int main(){
    ull n;
    ios::sync_with_stdio(NULL);
    cin.tie(0);
    cin>>n;
    if(n<=2){
        cout<<1<<endl;
    }else{
        MatrixPow(Q,n-2,Q);
        MatrixMul(Q,Fib,2,2,1,Fib);
        cout<<Fib[1][0]<<endl;
    }
    return 0;
}

[洛谷 P2312]解方程

2016年8月21日 21:32 | Comments(0) | Category:题解 | Tags:

最凶残的NOIP题。

首先我们可能会想到暴力枚举验证(枚举[tex][1,m][/tex]带入),然后我们很快就会想到用几个素数取模乱搞。然后嘛……

对于我们用到的取模数[tex]k[/tex],带入任意[tex]x[/tex],都有[tex]x^{a}\ mod\ k \in Z_{k} (a \in N^{0})[/tex](废话),所以说实际上我们枚举带入的是[tex][1,k)[/tex]。

这个题可以不开高精,因为可以一边读入一边取模

代码:

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=105,maxm=1000005;
const int P1=3079,P2=3083,P3=1000000207;

int X1[maxn],X2[maxn],X3[maxn];
bool Ac_1[P1],Ac_2[P2];

typedef long long ll;

inline ll mul_mod(ll a,ll b,ll Mod){
    return ((a%Mod)*(b%Mod))%Mod;
}

inline int readint(){
    register int ans=0;
    register char c=getchar();
    while(!isdigit(c)){
        c=getchar();
    }
    while(isdigit(c)){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans;
}
inline void read_mod(int& a,int& b,int& c){
    a=b=c=0;
    bool flag=false;
    register char cr=getchar();
    while(!isdigit(cr)){
        if(cr=='-')
            flag=true;
        cr=getchar();
    }
    while(isdigit(cr)){
        a=(mul_mod(10,a,P1)+cr-'0')%P1;
        b=(mul_mod(10,b,P2)+cr-'0')%P2;
        c=(mul_mod(10,c,P3)+cr-'0')%P3;
        cr=getchar();
    }
    if(flag){
        a=(P1-a)%P1;
        b=(P2-b)%P2;
        c=(P3-c)%P3;
    }
}

int n;
bool check(int* A,int x,int Mod){
    int now=0;
    register int i;
    for(i=n;i>=0;i--){
        now=(mul_mod(now,x,Mod)+A[i])%Mod;
    }
    return now==0;
}

vector<int> AnsList;
int main(){
    int m;
    register int i,ans_count=0;
    n=readint();
    m=readint();
    for(i=0;i<=n;i++)
        read_mod(X1[i],X2[i],X3[i]);
    for(i=1;i<P1;i++)
        Ac_1[i]=check(X1,i,P1);
    for(i=1;i<P2;i++)
        Ac_2[i]=check(X2,i,P2);
    for(i=1;i<=m;i++){
        if(Ac_1[i%P1] && Ac_2[i%P2] && check(X3,i,P3)){
            ans_count++;
            AnsList.push_back(i);
        }
    }
    printf("%d\n",ans_count);
    for(i=0;i<AnsList.size();i++){
        printf("%d\n",AnsList[i]);
    }
    return 0;
}

[洛谷 P2679]子串

2016年8月12日 17:40 | Comments(0) | Category:题解 | Tags:

DP神题……

第一眼都能看出来是DP,然后大约构思就出来了,但细节很复杂啊……

看完第一眼后大家大约都能想出来[tex]d[i][j][k][/tex]这样的状态,但是注意[tex]A[i]=B[j][/tex](字符数组细节此处未予考虑)的情况和整体情况要独立对待,否则这题只能233

然后下面就不难想了。但是注意直接开数组会233,要开滚动数组防MLE。

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=1001,maxm=201,maxk=201;
const int MOD=1e9+7;
int d[2][maxm][maxk][2];
char A[maxn];
char B[maxm];
int main(){
    register int i,j,p,now,pre;
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s%s",A,B);
    d[0][0][0][1]=1;
    for(i=1;i<=n;i++){
        now=i%2;
        pre=1-now;
        d[now][0][0][1]=1;
        for(j=1;j<=m;j++){
            if(A[i-1]==B[j-1])
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=(d[pre][j-1][p][0]+d[pre][j-1][p-1][1])%MOD;
                    d[now][j][p][1]=(d[pre][j][p][1]+d[now][j][p][0])%MOD;
                }
            else
                for(p=1;p<=min(k,j);p++){
                    d[now][j][p][0]=0;
                    d[now][j][p][1]=d[pre][j][p][1];
                }
        }
    }
    printf("%d\n",d[n%2][m][k][1]);
    return 0;
}

[洛谷 P2661]信息传递

2016年8月02日 13:38 | Comments(0) | Category:题解 | Tags:

bi了doge了……图论基本不会了……

这提可以直接循环删除所有入度为0的边,这样就只剩环了。然后DFS嘿嘿嘿。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=200001;
int G[maxn];
int to[maxn];
bool vis[maxn];
int n;
inline bool jianz(){
    register int i;
    bool ans=false;
    for(i=1;i<=n;i++){
        if(!vis[i] && !to[i]){
            ans=true;
            to[G[i]]--;
            vis[i]=true;
            G[i]=0;
        }
    }
    return ans;
}
int dfs(int x,int y){
    if(x==y && vis[x]){
        return 0;
    }else{
        vis[x]=true;
        return dfs(G[x],y)+1;
    }
}
int getchen(){
    register int i,ans=0x5ffffff;
    while(jianz());
    for(i=1;i<=n;i++)
        if(!vis[i])
            ans=min(ans,dfs(i,i));
    return ans;
}
int main(){
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d",&G[i]);
        to[G[i]]++;
    }
    printf("%d\n",getchen());
    return 0;
}

[洛谷 P1967]货车运输

2016年4月10日 18:27 | Comments(0) | Category:题解 | Tags:

倍增LCA经典题……

这题的做法就是求最大生成树,然后用倍增LCA法求瓶颈路……

注意一下,两点不连通时输出-1(其实这个用并查集判断不就行了……)!!!

代码: