（已黑化）

A：nefu1489 青蛙赶路

Description

有一只青蛙，每秒选择走1米或跳m米，青蛙体力不足，所以不能连续两秒都在跳。
青蛙将移动到[l,r]之间，它想知道有多少种不同的方式来实现其目标。
两种方式是不同的，当且仅当它们移动不同的米或花费不同的秒，或者是在一秒钟内，其中一个走而另一个跳。

Input

第一行输入包含2个整数n和m,n是查询数。（n <= 100000,2 <= m <= 100000）
对于下n行，每行包含两个整数l和r.（1 <= l <= r <= 100000）

Output

对于每个查询，输出到达的方案数，最后是模1000000007的答案。

Sample Input

4 4
4 4
1 4
1 5
1 6

Sample Output

2
5
8
12

虽然想到了是dp，但是....哎...我太菜了QAQ。看完题解瞬间顿悟了呜呜呜呜呜。

大体思路是这样的：

设二维数组dp[100009] [2] ,dp[i] [0]表示走到i的答案数，dp[i] [1]是跳到i的答案数。

显然dp[i] [0]=dp[i-1] [0] + dp[i-1] [1] (走到i-1的和跳到i-1的和)

dp[i] [1]=dp[i-m] [0]（从i-m跳过来的，因为不能二连跳，只有这种可能）

然后代码就写好了QAQ

#include <bits/stdc++.h>
using namespace std;
long long dp[100009][2];
long long sum[100009];
int main()
{

    int n,m,l,r;
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++)//到m之前的可能性只有走过去
        dp[i][0]=1;
    for(int i=m;i<=100002;i++)
    {
        dp[i][0]=(dp[i-1][1]+dp[i-1][0])%1000000007;
        dp[i][1]=dp[i-m][0]%1000000007;
    }
    for(int i=1;i<=100002;i++)
        sum[i]=(sum[i-1]+dp[i][0]+dp[i][1])%1000000007;
    while(n--)
    {
        scanf("%d %d",&l,&r);
        printf("%lld\n",(sum[r]-sum[l-1]+1000000007)%1000000007);//取模以后可能会出现sum[l-1]>sum[r]的情况，要小心
    }
    return 0;
}

B：nefu1485 贪吃蛇大作战

Description

贪吃蛇大家一定都玩过吧，现在宋哥也要玩这个游戏，最初的时候贪吃蛇从屏幕的左下角出发，但是有一个非常不幸的事情，就是宋哥的游戏机的左键和下键坏掉了，这意味着什么？没错！他只能操控他的蛇向右或向上走了，假设屏幕被划分为 10^9*10^9 的格子，而贪吃蛇从坐标为 (1,1) 的格子出发，每次操作可以从坐标为 (x,y) 的格子前往坐标为 (x+1,y) 或 (x,y+1) 的格子，在所有格子中有一些格子中有一些食物，宋哥现在想知道，他的贪吃蛇最多能吃到多少食物呢？

Input

输入的第一行包含一个数字 T (1<=T<=10)，代表数据组数，之后的每组数据的每一行包含一个数字 n (1<=n<=1000)，代表有食物的格子数量，之后的 n 行每一行包含三个数字 xi (1<=xi<=10^9),yi (1<=xi<=10^9),pi (1<=xi<=10^6)，分别代表格子的坐标和在这个格子里的食物数量。

Output

输出 T 行，第 i 行为第 i 组数据的答案。

Sample Input

2
3
1 1 1
2 2 2
3 3 3
3
1 3 1
2 2 2
3 1 3

Sample Output

6
3

dp能过是万万没想到的emmmmmmm

不过看了dalao的解释，又一次明白了我是个菜鸡QAQ

因为这题重点不是路径，是经过的点。

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int x;
    int y;
    long long z;
}s[1020];
bool cmp(struct node a,struct node b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;

}
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        long long ans=0;
        cin>>n;
        for(int i=0;i<n;i++)
            cin>>s[i].x>>s[i].y>>s[i].z;
        sort(s,s+n,cmp);
        for(int i=1;i<n;i++)
        {
            long long maxl=s[i].z;
            for(int j=i-1;j>=0;j--)
            {
                if(s[i].x>=s[j].x&&s[i].y>=s[j].y)
                    maxl=max(maxl,s[i].z+s[j].z);
            }
            s[i].z=maxl;
            ans=max(ans,maxl);
        }
        cout<<ans<<endl;
    }
    return 0;
}

C：nefu1494 小L的数列

Description

小L有一串数字，他想将这串数字分为连续的三段，并且每一段数字的和都是相等的，即找到i，j使得sum[1,i-1]=sum[i,j]=sum[j+1,n]。
你能帮助小L得到这样的i，j有几对么？
注意：这三段中每一段必须有数字，不能出现一段为空的情况。

Input

输入有多组，不超过20组
第一行输入n，表示有n个数字。
第二行有n个数字，表示小L拥有的n个数字。
n的取值范围[1,5e5]
每个数字的范围[-1e9,1e9]

Output

一个数字，表示i，j的对数。

Sample Input

5
1 2 3 0 3
4
0 1 -1 0
2
4 1

Sample Output

2
1
0

先占个位置QAQ

等我复习完树状数组再回来==

D：nefu1486 魔法王国

Description

在遥远的青青草原上，有一座魔法王国，王国里有n个城市，现在魔法王国的国王想要在城市间修一些道路，让这些城市互相连通（任意两个城市间均是可达的），在魔法王国修路当然需要魔法了，现在知道有m条双向道路可以被修建，但是每一条道路都需要一定的魔法值，只有魔法值不小于这个值的魔法师才能修建，而且修建之后这个魔法师的魔法值还会损失一。现在魔法王国的国王想要知道如果他只找一个魔法师来建造道路，那么这个魔法师的魔法值至少为多少呢？（题目数据保证一定可以将所有的城市联通）

Input

输入的第一行包含一个数字T(1<=T<=10)，代表数据组数，之后的每组数据的每一行包含两个数字n(1<=n<=10000),m (n-1<=m<=100000)，代表城市的个数和可修建的道路条数，之后的m行每一行包含三个数字u(1<=u<=n),v(1<=v<=n),c(1<=c<=100000)，分别代表双向道路的两个终点城市和修建这条道路所需的魔法值。

Output

输出T行，第i行为第i组数据的答案。

Sample Input

2
4 3
1 2 1
2 3 1
3 4 1
4 3
1 2 1
2 3 2
3 4 3

Sample Output

3
3

看到这道题的时候直接泪目，呜呜呜终于发现一个一眼能看出大体思路的了。

克鲁斯卡尔求最小生成树而已。

需要想一下的是如何处理答案，这点一会结合代码说一下。

第一次做的时候是用了个憨憨做法，不过后来看题解，我又一次的感觉到了自己的憨憨==

（所以这题我为什么卡了一个小时呢？我是万万没想到憨憨竟然输入完数据忘sort了QAQ）

#include <bits/stdc++.h>
using namespace std;
int f[103310];
long long ans[103310];
struct node
{
    int x,y;
    int z;
}s[103310];
bool cmp(struct node a,struct node b)
{
    return a.z<b.z;
}
int findl(int x)
{
    if(f[x]==x)
        return x;
    return f[x]=findl(f[x]);
}
void mergel(int a,int b)
{
    int c=findl(a);
    int d=findl(b);
    if(c!=d)
        f[c]=d;
}
int main()
{

    int t;
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        memset(ans,0,sizeof(ans));
        memset(f,0,sizeof(f));
        int n,m,op,x,y,sum=0;
        int maxl=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            f[i]=i;
        for(int i=0;i<m;i++)
            cin>>s[i].x>>s[i].y>>s[i].z;
        sort(s,s+m,cmp);
        for(int i=0;i<m;i++)
        {
            if(findl(s[i].x)!=findl(s[i].y))
            {
                mergel(s[i].x,s[i].y);
                sum++;
                maxl=max(maxl,s[i].z+n-sum-1);//n个城市需要n-1条路，而修完sum条路还剩下n-1-sum条，用这个加上边权和maxl进行比较就可以了
            }
            if(sum==n-1)
                break;
        }
        cout<<maxl<<endl;

    }
    return 0;
}

E：nefu1492 珍珠项链

emmm先占个位置，这题要用kmp，菜鸡还没学，等学完补上。

戳这里有大佬们的题解

F：nefu1503 Please No More Sigma

Description

给定数列如下

给定n，求下式模1e9+7后的值

Input

第一行一个数字T，表示样例数
以下有T行，每行一个数，表示n。
保证T<=100，n<=100000000

Output

输出式子的值。由于直接求值会很大，输出模1e9+7后的结果。

Sample Input

2
1
2

Sample Output

1
4

三重求和，不是len啊你。

这题属实推自闭了，看完题解依旧自闭呜呜呜呜。

只能说，原来做的矩阵题在第一层，我想到了第二层，这道题已经突破大气层，顶不住呜呜呜。

看了下题解，发现还有这种企业级公式：斐波那契数列前n项和s(n)=f(n+2)-1。

具体推导如下：

当n=1时，命题成立。
假设n=k时，命题成立。
当n=k+1时，
f(k+3)-1

=f(k+1)+f(k+2)-1
=f(k+1)+f(1)+f(2)+……+f(k)
=f(1)+f(2)+……+f(k+1)

所以命题成立。

所以原题的式子可以化成这样：（渣像素+渣字迹）

Input

第一行一个数字T，表示样例数
以下有T行，每行一个数，表示n。
保证T<=100，n<=100000000

Output

输出式子的值。由于直接求值会很大，输出模1e9+7后的结果。

Sample Input

2
1
2

Sample Output

1
4

三重求和，不是len啊你。

这题属实推自闭了，看完题解依旧自闭呜呜呜呜。

只能说，原来做的矩阵题在第一层，我想到了第二层，这道题已经突破大气层，顶不住呜呜呜。

看了下题解，发现还有这种企业级公式：斐波那契数列前n项和s(n)=f(n+2)-1。

具体推导如下：

当n=1时，命题成立。
假设n=k时，命题成立。
当n=k+1时，
f(k+3)-1

=f(k+1)+f(k+2)-1
=f(k+1)+f(1)+f(2)+……+f(k)
=f(1)+f(2)+……+f(k+1)

所以命题成立。

所以原题的式子可以化成这样：（渣像素+渣字迹）

接下来就是很简单的矩阵连乘了==

#include<bits/stdc++.h>
using namespace std;
const int MAX=2;
typedef struct
{
    long long m[MAX][MAX];
}Matrix;
Matrix P={1,1,1,0};
Matrix I={1,0,0,1};
int mod=1000000007;
Matrix mul(Matrix a,Matrix b)
{
    int i,j,k;
    Matrix c;
    for(i=0;i<MAX;i++)
    {
        for(int j=0;j<MAX;j++)
        {
            c.m[i][j]=0;
            for(k=0;k<MAX;k++)
            {
                c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod;
            }
            c.m[i][j]%=mod;
        }
    }
    return c;
}
Matrix quickpow(long long n)
{
    Matrix m=P,b=I;
    while(n>=1)
    {
        if(n&1)
            b=mul(b,m);
        n=n>>1;
        m=mul(m,m);
    }
    return b;
}
int main()
{
    long long t,n;
    long long res;
    cin>>t;
    while(t--)
    {
        cin>>n;
        Matrix d1=quickpow(n+4);
        res=(d1.m[0][0]+d1.m[0][1]-8-3*n-(n*n+n)/2)%mod;
        res=(res+mod)%mod;
        cout<<res<<endl;
    }

    return 0;
}