A DZY Loves Hash 水题

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

bool f[300];

int main()

{

 long long int p,t;

 int i,j,k,m,n;

 cin>>p>>n;

 bool fs=0;

 memset(f,0,sizeof(f));

 for(i=1;i<=n;i++)

   {

   cin>>t;

   t=t%p;

   if(!f[t])f[t]=1;

     else

        {

         fs=1;

         cout<<i;

         break;

        }

   }

 if(!fs)cout<<-1;

 return 0;

}

B DZY Loves Strings 水题

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

int main()

{

 ios::sync_with_stdio(false);

 char s[1001];

 int v[26],i,j,k,m,n,maxv=0;

 cin>>s;

 cin>>k;

 for(i=0;i<26;i++)

    {

     cin>>v[i];

     if(v[i]>maxv)maxv=v[i];

    }

 long long int ans=0;

 m=strlen(s);

 for(i=0;i<m;i++)

    ans+=(i+1)*(v[s[i]-'a']);

 for(;i<m+k;i++)

    ans+=(i+1)*maxv;

 cout<<ans;

 return 0;

}

C DZY Loves Sequences

枚举修改的位置即可 水

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

using namespace std;

const int maxn=100005;

typedef long long int LL;

LL num[maxn];

int ac[maxn],dc[maxn];

int main()

{//freopen("t.txt","r",stdin);

 int n;

 scanf("%d",&n);

 for(int i=1;i<=n;i++)

 	scanf("%I64d",&num[i]),ac[i]=dc[i]=1;

 for(int i=1;i<=n;)

 	{

 	 int len=1;

 	 for (int j=i+1;j<=n&&num[j]>num[j-1];j++)len++;

 	 for(int j=i;len>1;len--,j++)

 	 	 ac[j]=len;

 	 i=i+ac[i];

	}

 for(int i=n;i>=1;)

 	{

 	 int len=1;

 	 for (int j=i-1;j>=1&&num[j]<num[j+1];j--)len++;

 	 for(int j=i;len>1;len--,j--)

 	 	 dc[j]=len;

 	 i=i-dc[i];

	}

 dc[0]=ac[0]=dc[n+1]=ac[n+1]=0;

 num[0]=-999999999999LL;

 num[n+1]=9999999999999LL;

 int ans=1;

 for(int i=1;i<=n;i++)

 	{

 	 if(num[i-1]<num[i+1]-1)ans=max(ans,1+dc[i-1]+ac[i+1]);

 	 	else ans=max(ans,max(1+dc[i-1],1+ac[i+1]));

	}

 printf("%d\n",ans);

 return 0;

}

DDZY Loves Modification

给定一个矩阵 进行k次操作 每次取一行或一列 累加他们的和 并且将取中的每一个元素减p

每次找最大行或最大列的贪心方法是错误的。可以找到反例。

那么我们考虑如果p=0 我们找最大行或者最大列 K次即可

如果p不等于0 我们发现一个事实

我们必然取a次行和b次列 a+b=k 且最后答案等于p=0的情况下贪心的ans 减去 a*b*p（尝试自己证明）

于是我们枚举取了多少次行 取最大值就行了。

很有趣的一道贪心题。

#include<bits/stdc++.h>

using namespace std;

typedef long long l;

priority_queue<l>Q;

int n,m,k,p,d;

l r[1001],c[1001],S[1000001],P[1000001],a=-99999999999999;

int main(){scanf("%d%d%d%d",&n,&m,&k,&p);

for(int i=1;i<=n;Q.push(r[i]),i++) for(int j=1;j<=m;j++) scanf("%d",&d),r[i]+=d,c[j]+=d;

for(int i=1;i<=k;i++)S[i]=Q.top(),Q.pop(),Q.push(S[i]-m*p);

while(!Q.empty())Q.pop();for(int i=1;i<=m;i++)Q.push(c[i]);

for(int i=1;i<=k;i++)P[i]=Q.top(),Q.pop(),Q.push(P[i]-n*p);

for(int i=1;i<=k;i++)S[i]+=S[i-1],P[i]+=P[i-1];

for(int i=0;i<=k;i++)a=max(a,S[i]+P[k-i]-(l)(i)*(k-i)*p);

printf("%I64d\n",a);}

　　

E. DZY Loves Fibonacci Numbers

首先我们要学习斐波那契数列的两个性质

我们定义原始斐波那契数列即f(1)=f(2)=1 当n>2 f(n)=f(n-1)+f(n-2)

性质一：然后我们定义一般斐波那契数列 即F(1)=a F(2)=b 此时有 F（n）= a*f(n-2)+b*f(n-1)(用归纳法易证得）

性质二：对于一般斐波那契数列的前缀和 我们有如下推导

{fib[n]=fib[n−1]+fib[n−2]fib[n−1]=fib[n−2]+fib[n−3]⇒fib[n]=fib[n−2]+⋯+fib[3]+2⋅fib[2]+fib[1]⇒∑i=1nfib[i]=fib[n+2]−fib[2]

发现了以上两个性质后 我们可以在常数时间内对斐波那契数列进行分解了！

这意味着我们可以用线段树来储存斐波那契数列了 因为不同的一般斐波那契数列之间显然满足线性可加性。（这样意味着我们可以使用线段树的“懒”功能了）

剩下的看代码吧 有点长 不过很清晰

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

#define MAX 300007

using namespace std;

typedef long long LL;

int n,m,a[MAX];

const LL mod = 1e9+9;

LL fib[MAX];

struct Tree

{

    int l,r;

    LL sum,f1,f2;//当前区间要加的一般斐波那契数列前2项（满足线性可加性）

}tree[MAX<<2];

void push_up ( int u )

{

    tree[u].sum = tree[u<<1].sum + tree[u<<1|1].sum;

    tree[u].sum %= mod;

}

void build ( int u , int l , int r )

{

    tree[u].l = l;

    tree[u].r = r;

    tree[u].f1 = tree[u].f2 = 0;

    if ( l == r )

    {

        tree[u].sum = a[l];

        return;

    }

    int mid = l+r>>1;

    build ( u<<1 , l , mid );

    build ( u<<1|1 , mid+1 , r );

    push_up ( u );

}

void init ( )

{

    fib[1] = fib[2] = 1;

    for ( int i = 3 ; i < MAX ; i++ )

    {

        fib[i] = fib[i-1] + fib[i-2];

        fib[i] %= mod;

    }

}

LL get ( LL a , LL b , int n )//一般斐波那契数列的第n项

{

    if ( n == 1 ) return a%mod;

    if ( n == 2 ) return b%mod;

    return (a*fib[n-2]%mod+b*fib[n-1]%mod)%mod;

}

LL sum ( LL a , LL b , int n )//一般斐波那契数列的前缀和

{

    if ( n == 1 ) return a;

    if ( n == 2 ) return (a+b)%mod;

    return ((get ( a , b , n+2 )-b)%mod+mod)%mod;

}

void push_down ( int u )//常数复杂度的拆分

{

    int f1 = tree[u].f1;

    int f2 = tree[u].f2;

    int l = tree[u].l;

    int r = tree[u].r;

    int ll = (l+r)/2-l+1;

    int rr = r-(l+r)/2;

    if ( f1 )

    {

        if ( l != r )

        {

            tree[u<<1].f1 += f1;

            tree[u<<1].f1 %= mod;

            tree[u<<1].f2 += f2;

            tree[u<<1].f2 %= mod;

            tree[u<<1].sum += sum ( f1 , f2 , ll );

            tree[u<<1].sum %= mod;

            int x = f1 , y = f2;

            f2 = get ( x , y , ll+2 );

            f1 = get ( x , y , ll+1 );

            tree[u<<1|1].f2 += f2;

            tree[u<<1|1].f2 %= mod;

            tree[u<<1|1].f1 += f1;

            tree[u<<1|1].f1 %= mod;

            tree[u<<1|1].sum += sum ( f1 , f2 , rr );

            tree[u<<1|1].sum %= mod;

        }

        tree[u].f1 = tree[u].f2 = 0;

    }

}

void update ( int u , int left , int right )

{

    int l = tree[u].l;

    int r = tree[u].r;

    int mid = l+r>>1;

    if ( left <= l && r <= right )

    {

        tree[u].f1 += fib[l-left+1];

        tree[u].f1 %= mod;

        tree[u].f2 += fib[l-left+2];

        tree[u].f2 %= mod;

        int f1 = fib[l-left+1], f2 = fib[l-left+2];

        tree[u].sum += sum ( f1 , f2 , r-l+1 );

        tree[u].sum %= mod;

        return;

    }

    push_down ( u);

    if ( left <= mid && right >= l )

        update ( u<<1 , left , right );

    if ( left <= r && right > mid )

        update ( u<<1|1 , left , right );

    push_up ( u );

}

LL query ( int u , int left , int right )

{

    int l = tree[u].l;

    int r = tree[u].r;

    int mid = l+r>>1;

    if ( left <= l && r <= right )

        return tree[u].sum;

    push_down ( u );

    LL ret = 0;

    if ( left <= mid && right >= l )

    {

        ret += query ( u<<1 , left , right );

        ret %= mod;

    }

    if ( left <= r && right > mid )

    {

        ret += query ( u<<1|1 , left , right );

        ret %= mod;

    }

    return ret;

}

int main ( )

{

    init ( );

    while ( ~scanf ( "%d%d" , &n , &m ) )

    {

        for ( int i = 1; i <= n ; i++ )

            scanf ( "%d" , &a[i] );

        build ( 1 , 1 , n );

        while ( m-- )

        {

            int x,l,r;

            scanf ( "%d%d%d" , &x , &l , &r );

            if ( x == 1 )

                update ( 1 , l , r );

            else

                printf ( "%lld\n" , query ( 1 , l , r ) );

        }

    }

}　

通过这道题 我们对斐波那契数列的认识应该到了一个新的高度了。

　

最新文章

  1. selenium webdriver自动化测试
  2. 为什么要加入&lt;!doctype html&gt;这个文档声明——IE怪异模式
  3. js反射机制
  4. UISearchBar cover first cell of UITableView
  5. Xcode关闭ARC
  6. Python标准库---子进程 (subprocess包)
  7. PHP-通过strace定位故障原因
  8. ASP三种常用传值方式：
  9. 与Google轻轻地擦肩而过
  10. Visual C++ 打印编程技术-内存设备环境
  11. github修改自己的昵称
  12. winform登陆 记住用户名 代码
  13. 从今日起，我会把OpenGL红宝书上的例子用完整的代码形式写在我的博客中，
  14. CodeForces 429B Working out 动态规划
  15. centos下的activemq的配置及PHP的使用
  16. Uncaught TypeError: download is not a function at HTMLAnchorElement.onclick (index.html:25)
  17. JAVA 面试基础
  18. 05 Django REST Framework 分页
  19. 锤子科技&quot;临死前&quot;被&quot;接盘&quot; ，内部人士爆料已改签今日头条母公司
  20. MySQL 误操作后数据恢复（update,delete忘加where条件）

热门文章

  1. Go常量与枚举类型
  2. [luoguP2679] 子串（DP）
  3. BZOJ4551 - [TJOI2016]树
  4. 为docker容器设置独立ip
  5. MS SQLServer Update语法和实例
  6. 在RedHat 5下安装Oracle 10g详解(转)
  7. Intersecting Lines--POJ1269(判断两条直线的关系 &amp;&amp; 求两条直线的交点)
  8. 通过简单的两数相加体会hashmap的好处
  9. Spring中使用构造函数实现Beans自动装配
  10. 制作自己的网站第二步***在Linux上装上需要的软件以及部署项目配置**