Codeforces Round #FF (Div. 2)

A. DZY Loves Hash

水题！！

AC代码例如以下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define inf 100000000
#define M 100005
#define ll long long
#define F(a,b) for(i=a;i<=b;i++)
#define ME(a) memset(a,0,sizeof (a))
using namespace std;

int main()
{
    int i,j;
    int n,m,c;
    int a[305];
    cin>>n>>m;
    ME(a);
    int cc;
    int bj=0;
    F(0,m-1)
    {

        cin>>c;
        if(bj==1)
            continue;
        cc=c%n;
        if(a[cc]==0)
            a[cc]=1;
        else
        {cout<<i+1<<endl;bj=1;}
    }
    int ans=0;
    F(0,m-1)
    {
        if(a[i]==1)
        ans++;
    }
    if(bj==0)
        cout<<"-1"<<endl;
    return 0;
}

B. DZY Loves Strings

水题，题意懂都能写！

AC代码例如以下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define inf 100000000
#define M 100005
#define ll long long
#define F(a,b) for(i=a;i<=b;i++)
#define ME(a) memset(a,0,sizeof (a))
using namespace std;

char a[3005];
int b[500];

int main()
{
    int i,j;
    int k;
    cin>>a>>k;
    F('a','z')
    {
        cin>>b[i];
    }
    int sum=0;
    int l=strlen(a);
    F(0,l-1)
    {
        sum+=(i+1)*b[a[i]];
    }
    int max=b['a'];
    F('a','z')
    {
        if(b[i]>max)
            max=b[i];
    }
    int c=l+1;
    F(c,l+k)
    {
        sum+=i*max;
    }
    cout<<sum<<endl;
    return 0;
}

C. DZY Loves Sequences

AC代码例如以下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define inf 1000000007
#define M 100005
#define ll long long
using namespace std;

int main()
{
    int i,j;
    int n,m;
    int a[100005],b[100005],c[100005];
    cin>>n;
    memset(c,0,sizeof c);
    b[0]=0;a[0]=-inf;
    for(i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]>a[i-1])
            {
                b[i]=b[i-1]+1;
            }
            else b[i]=1;
        }
    c[n+1]=0;a[n+1]=inf;
    for(i=n;i>=1;i--)
    {
        if(a[i]<a[i+1])
            c[i]=c[i+1]+1;
        else c[i]=1;

    }
    int ans=0;
    for(i=n;i>=1;i--)
    {
        if(a[i+1]-a[i-1]>1)
        {
            ans=max(ans,b[i-1]+c[i+1]+1);
        }
        if(i>1)
            ans=max(ans,b[i-1]+1);
        if(i<n)
            ans=max(ans,c[i+1]+1);

    }
    cout<<ans<<endl;
    return 0;
}

D. DZY Loves Modification

主要是优先队列的使用。现将行列的和分别将从大到小的和增数组求出来。再用枚举贪心i行k-i列就可以。

AC代码例如以下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<queue>
#define inf -1000000007
#define M 100005
#define lll long long
using namespace std;

priority_queue<lll > qh,ql;

int a[1005][1005];
int h[1005];
int l[1005];
lll hh[1000005],ll[1000005];

int main()
{
    int i,j,c;
    int n,m,k,p;
    cin>>n>>m>>k>>p;
    int bj=0;
    int id;
    memset(h,0,sizeof h);
    memset(l,0,sizeof l);
    memset(hh,0,sizeof hh);
    memset(ll,0,sizeof ll);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
    {
        cin>>a[i][j];
        h[i]+=(lll)a[i][j];
        l[j]+=(lll)a[i][j];
    }
    for(i=1;i<=n;i++) qh.push(h[i]);
    for(i=1;i<=m;i++) ql.push(l[i]);
    lll sum;
    for(i=1;i<=k;i++)
    {
        sum=qh.top();qh.pop();
        hh[i]=hh[i-1]+sum;
        //cout<<hh[i]<<" "<<hh[i-1]<<endl;
        qh.push(sum-(lll)m*p);
        sum=ql.top();ql.pop();
        ll[i]=ll[i-1]+sum;
        //cout<<ll[i]<<" "<<sum-(lll)n*p<<endl;
        ql.push(sum-(lll)n*p);
    }
    lll ans;
    ans=hh[0]+ll[k];
    //cout<<ans<<endl;
    for(i=1;i<=k;i++)
    {
        ans=max(ans,hh[i]+ll[k-i]-(lll)i*(k-i)*p);
    }
    cout<<ans<<endl;
    return 0;
}

E. DZY Loves Fibonacci Numbers

待续。

。。。。

。