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;
}
枚举修改的位置即可 水
#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;
}
给定一个矩阵 进行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 ) );
}
}
}
通过这道题 我们对斐波那契数列的认识应该到了一个新的高度了。