首页 > 代码库 > Codeforces Round #FF(255) (Div. 2)

Codeforces Round #FF(255) (Div. 2)

A题 

/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 0Xfffffff#define maxntypedef long long ll;typedef pair<int,int> pii;typedef vector<int,int> vii;int p,n;bool h[301];int a[301];int main(){//    freopen("a.txt","r",stdin);//    freopen(".out","w",stdout);    while(cin>>p>>n){        int x;bool find=0;        memset(h,0,sizeof(h));        for(int i=1;i<=n;i++)            cin>>a[i];            for(int i=1;i<=n;i++){            if(h[a[i]%p]){                cout<<i<<endl;                find=1;                break;            }            else h[a[i]%p]=1;        }        if(!find)puts("-1");    }    return 0;}/*DESCRIPTION:*/
View Code

B题 贪心

/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 0Xfffffff#define maxntypedef long long ll;typedef pair<int,int> pii;typedef vector<int,int> vii;char s[1001];int k;int h[27];int main(){//    freopen("a.txt","r",stdin);//    freopen(".out","w",stdout);    while(cin>>s){        cin>>k;        int m=-1;        for(int i=0;i<26;i++){            cin>>h[i];            if(h[i]>m)    m=h[i];        }        ll ans=0;int l=strlen(s);        for(int i=0;i<l;i++)            ans+=h[s[i]-a]*(i+1);        ans+=(l+1+l+k)*k*m/2;        cout<<ans<<endl;    }    return 0;}/*DESCRIPTION:*/
View Code

C题 dp

/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 0Xfffffff#define maxn 100001typedef long long ll;typedef pair<int,int> pii;typedef vector<int,int> vii;int n,a[maxn],s[maxn],e[maxn];int main(){//    freopen("a.txt","r",stdin);//    freopen(".out","w",stdout);    while(cin>>n){        for(int i=1;i<=n;i++)            cin>>a[i];        s[n]=1;        for(int i=n-1;i>=1;i--)            s[i] = (a[i]<a[i+1])? s[i+1]+1 : 1;        e[1]=1;        for(int i=2;i<=n;i++)            e[i] = (a[i]>a[i-1])? e[i-1]+1 : 1;        int ans = max( e[n-1]+1 , s[2]+1 );        for(int i=2;i<=n-1;i++){            if(a[i+1] - a[i-1]>1)                ans = max( ans , e[i-1]+s[i+1]+1 );            else                ans = max(ans , max(s[i+1],e[i-1])+1 );        }    cout<<ans<<endl;    }    return 0;}/*DESCRIPTION:题还是做得太少,这题跟lis一点关系都没有以i为开头的最长连续序列s[i],以i为结尾的最长连续序列e[i]这题恶心,按理来说ai>0,但是数据允许你把ai改成0*/
View Code

D题 优先队列

/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 1e9#define maxn#define rep(i,x,y) for(int i=x;i<=y;i++)#define mset(x) memset(x,0,sizeof(x))typedef long long ll;typedef pair<int,int> pii;typedef vector<int,int> vii;int n,m,k,p;int row[1001],col[1001];ll sc[1000000],sr[1000000];int main(){//    freopen("a.txt","r",stdin);//    freopen(".out","w",stdout);    cin>>n>>m>>k>>p;    mset(row);mset(col);    int x;    rep(i,0,n-1)        rep(j,0,m-1){            cin>>x;            row[i]+=x;            col[j]+=x;        }    priority_queue<int> c,r;    rep(i,0,m-1)    c.push(col[i]);    rep(i,0,n-1)    r.push(row[i]);        sc[0]=0;sr[0]=0;    rep(i,1,k){//把最大的k列存进c中        int x=c.top() , y=r.top();        sc[i] = sc[i-1]+x;    sr[i] = sr[i-1]+y;        c.pop();    r.pop();        c.push(x-n*p);    r.push(y-m*p);    }    ll ans = sr[k];    rep(i,1,k){        ans = max( ans, sc[i]+sr[k-i]-1ll*(k-i)*i*p );    }    cout<<ans<<endl;    return 0;}/*DESCRIPTION:按照某种取法得到解,解与行列选择的顺序无关取了i列,(k-i)行ans = max( sigma(col) + sigma(row) - (k-i)*i*p )将col和row分别用priority_queue储存枚举i,意味着要把最大的k个列存进prq中由于i列中可能会有重复的算法就是:先在prq中找最大col, 把col-n*p存进去,如此循环k次这样prq里有了最大的k个数不过这样占用的内存过大要及时删除由于最大会有1e12的数,故注意要用long longpriority_queue.top()默认返回最大值*/
View Code