自闭练习赛(1)


278 观看次数
1484 字数
1 评论

(已黑化)

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;
}

评论区

只有一个人

0.五葉魔法書
2020 September 22nd

文章不错,如果排版能更好些就行了

添加新评论