Codeforces Round #267 (Div. 2)

A大水

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main(){
    int n,p,q,res;
    while(cin>>n){
        res=0;
        while(n--){
            cin>>p>>q;
            if(q-p>=2){
                res++;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

 

B大水

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,k,arm[1005],fed;
int check(int a,int b){
    int res=0;
    while(a||b){
        if(a%2!=b%2)res++;
        a/=2,b/=2;
    }
    if(res<=k)return 1;
    return 0;
}
int main(){
    int i,j,res;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        res=0;
        for(i=0;i<=m;i++){
            scanf("%d",&arm[i]);
        }fed=arm[m];
        for(i=0;i<m;i++){
            if(check(arm[i],fed)){
                res++;
           //     cout<<arm[i]<<"ddd\n";
            }
        }
        cout<<res<<endl;
    }
    return 0;
}

 

C：dp，转移方程为

dp[i][j]=max(dp[i+1][j],dp[i+m][j-1]+sum[i]);

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,k;
long long num[5005],sum[5005],dp[5005][5005];
int main(){
    int i,j;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
        for(i=0;i<n;i++){
            scanf("%I64d",&num[i]);
        }
        memset(sum,0,sizeof(sum));
        for(i=0;i<=m-1;i++){
            sum[0]+=num[i];
        }
        for(i=1;i+m<=n;i++){
            sum[i]=sum[i-1];
            sum[i]-=num[i-1];
            sum[i]+=num[i+m-1];
        }
        memset(dp,0,sizeof(dp));
        for(j=1;j<=k;j++){
            for(i=n-m*j;i>=0;i--){
                dp[i][j]=max(dp[i+1][j],dp[i+m][j-1]+sum[i]);
            }
        }
        long long res=0;
        for(i=0;i<=n-m*k;i++){
            res=max(dp[i][k],res);
        }cout<<res<<endl;
    }
    return 0;
}

 
D施工完成，先建图，对图进行Tarjan缩点，然后在DAG上dp即可

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
const int nMax=400005;
const int mMax=800005;
int vis[nMax];
class edge{
public:
    int u,v,nex;
};edge e[mMax],e2[mMax];
int k,k2,head[nMax],head2[nMax];
void addedge(int a,int b){
 //   cout<<a<<" add "<<b<<endl;
    e[k].u=a;
    e[k].v=b;
    e[k].nex=head[a];
    head[a]=k;k++;
}
void addedge2(int a,int b){
  //  cout<<a<<" 222add222 "<<b<<endl;
    e2[k2].u=a;
    e2[k2].v=b;
    e2[k2].nex=head2[a];
    head2[a]=k2;k2++;
}
int dfn[nMax],low[nMax],sta[nMax],top,atype,belon[nMax],dep;   //atype ǿ��ͨ�����ĸ���
bool insta[nMax];

class nod{
public:
    int lth,rrr;
}dp[nMax*4];
string str[nMax],dic1[nMax],dic2[nMax];
int len[nMax],numr[nMax],n,m;


void Tarjan(int u){                 //�ҵ�Tarjanģ��
    int i,j;
    dfn[u]=low[u]=++dep;
    sta[++top]=u;
    insta[u]=1;
    for(i=head[u];i;i=e[i].nex){
        int v=e[i].v;
        if(!dfn[v]){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else{
            if(insta[v])low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        atype++;              //ǿ��ͨ��������
        //dp[atype].lth=dp[atype].rrr=nMax;
        do{
            j=sta[top--];
//            if(atype==3){
//                cout<<j<<"aaaaaaaaaaaaaaaaa\n";
//            }
            belon[j]=atype;   //��j�������ڵ�type����ͨ��
            if(numr[j]<dp[atype].rrr||(numr[j]==dp[atype].rrr&&len[j]<dp[atype].lth)){
                dp[atype].lth=len[j];
                dp[atype].rrr=numr[j];
            }
            insta[j]=0;
        }while(u!=j);
    }
}
void buildremap(){
    int i;
    for(i=1;i<k;i++){
        if(belon[e[i].u]!=belon[e[i].v]){
            addedge2(belon[e[i].u],belon[e[i].v]);
        }
    }
}
void init(){
    k=k2=1;
    dep=1;
    top=atype=0;
    memset(insta,0,sizeof(insta)); //�Ƿ���ջ��
    memset(head,0,sizeof(head));   //��̬����ͷָ��
    memset(head2,0,sizeof(head2));   //��̬����ͷָ��
    memset(low,0,sizeof(low));     //Tarjan��low����
    memset(dfn,0,sizeof(dfn));     //Tarjan��dfn����
    memset(belon,0,sizeof(belon)); //��¼ÿ����������һ��ǿ��ͨ����
}
void ToUpperString(string &str)
{
    transform(str.begin(), str.end(), str.begin(), (int (*)(int))toupper);
}
void ToLowerString(string &str)
{
    transform(str.begin(), str.end(), str.begin(), (int (*)(int))tolower);
}
int getr(string &s) {
    int res = 0, l = s.length();
    for(int i = 0; i < l; ++i)
        if (s[i] == 'r')
            ++res;
    return res;
}
map<string,int>mpp,fpp;
void dfs(int l){
    vis[l]=1;
    for(int i=head2[l];i;i=e2[i].nex){
        int v=e2[i].v;
        if(!vis[v]){
            dfs(v);
        }
        if(dp[v].rrr<dp[l].rrr||(dp[v].rrr==dp[l].rrr&&dp[v].lth<dp[l].lth)){
            dp[l].lth=dp[v].lth;
            dp[l].rrr=dp[v].rrr;
        }
    }
}
int main(){
    int i,llc;
    while(scanf("%d",&n)!=EOF){
        llc=1;
        mpp.clear();
        fpp.clear();
        for(i=0;i<n;i++){
            cin>>str[i];
            ToLowerString(str[i]);
        }
        init();
        scanf("%d",&m);
        for(i=0;i<m;i++){
            cin>>dic1[i]>>dic2[i];
            ToLowerString(dic1[i]);
            ToLowerString(dic2[i]);
            fpp[dic1[i]]=llc;
            if(!mpp[dic1[i]]){
                mpp[dic1[i]]=llc;
                fpp[dic1[i]]=llc;
                len[llc]=dic1[i].length();
                numr[llc++]=getr(dic1[i]);
            }
            if(!mpp[dic2[i]]){
                mpp[dic2[i]]=llc;
                len[llc]=dic2[i].length();
                numr[llc++]=getr(dic2[i]);
            }
            if(mpp[dic1[i]]!=mpp[dic2[i]])
                addedge(mpp[dic1[i]],mpp[dic2[i]]);
        }
        for(i=0;i<nMax;i++){
            dp[i].lth=nMax;
            dp[i].rrr=nMax;
        }
        for(i=1;i<llc;i++){
            if(!dfn[i])Tarjan(i);
        }
//        for(i=1;i<=atype;i++){
//            cout<<"i= "<<i<<" len= "<<dp[i].lth<<" dpdp rrr"<<dp[i].rrr<<endl;
//        }
        buildremap();
        memset(vis,0,sizeof(vis));
        long long ffa=0,ffb=0;
        for(i=0;i<n;i++){
            if(!fpp[str[i]]){  //û�г�������ߵ�
               ffa+=getr(str[i]);
               ffb+=str[i].length();
            }else{
                if(!vis[belon[mpp[str[i]]]]){
                    dfs(belon[mpp[str[i]]]);
                }
                ffa+=dp[belon[mpp[str[i]]]].rrr;
                ffb+=dp[belon[mpp[str[i]]]].lth;
               // cout<<"addr "<<dp[belon[mpp[str[i]]]].rrr<<" addl "<<dp[belon[mpp[str[i]]]].lth<<endl;
            }
        }
        printf("%I64d %I64d\n", ffa, ffb);
    }
    return 0;
}