A

题意：给定n个数，最多交换n次获得一个不减的序列，求一个合法的交换序列。

题解：每次找从i开始的最小值换到第i个位置就可以了。

#include <cstdio>#include <algorithm>#include <cstring>#include <iostream>#include <cmath>using namespace std;int a[5000],n,max1,maxx;int main(){    scanf("%d",&n);    for (int i=1;i<=n;++i) scanf("%d",&a[i]);    printf("%d\n",n);    for (int i=1;i<=n;++i)    {        max1=2e9;maxx=0;max1=-max1;        for(int j=1;j<=n-i+1;++j) if (a[j]>max1)        {            max1=a[j];maxx=j;        }        swap(a[maxx],a[n-i+1]);        printf("%d %d\n",maxx-1,n-i);    }    return 0;}

B

题意：N个男孩M个女孩参加舞会，每个人有一个能力值，两个跳舞的人必须为一男一女且能力值差在1之内，求最多有多少对。

题解：直接求个匹配就可以了。。

#include <cstdio>#include <cmath>#include <iostream>#include <algorithm>#include <cstring>int num,b[200],a[20000],next[20000],a1[200],a2[200],ans,vis[200],n,m,link[200];using namespace std;int dfs(int x){    for (int i=b[x];i;i=next[i])    {        int y=a[i];        if (!vis[y])        {            vis[y]=1;            if (link[y]==0||dfs(link[y]))            {                link[y]=x;                return 1;            }        }    }    return 0;}void addedge(int x,int y){    ++num;a[num]=y;next[num]=b[x];b[x]=num;}int main(){    scanf("%d",&n);    for (int i=1;i<=n;++i) scanf("%d",&a1[i]);    scanf("%d",&m);    for (int j=1;j<=m;++j) scanf("%d",&a2[j]);    for (int i=1;i<=n;++i)        for (int j=1;j<=m;++j) if (abs(a1[i]-a2[j])<=1) addedge(i,j);    //cout<<num;    for (int i=1;i<=n;++i)    {        memset(vis,0,sizeof(vis));        if (dfs(i)) ans++;    }    printf("%d\n",ans);    return 0;}

C

题意：求最大的和最小的N位数，使得这个N位数各个位数字的和为M。

题解：最大的从前往后一直放9到不能放为止。。最小的从前往后每一位都放能放的最小值。。

#include <cstdio>#include <cmath>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int m,s,ss;int a[1000],b[1000];int main(){    scanf("%d%d",&m,&s);    ss=s;    if (s>m*9)    {        printf("-1 -1\n");        return 0;    }    if (m==1)    {        printf("%d %d\n",s,s);        return 0;    }    if (s==0)    {        printf("-1 -1\n");        return 0;    }    memset(a,0,sizeof(a));    memset(b,0,sizeof(b));    for (int i=1;i<=m;++i)    {        if (i==1) a[i]=max(1,s-(m-i)*9);else a[i]=max(0,s-(m-i)*9);s-=a[i];    }    s=ss;    for (int i=1;i<=m;++i)    {        if (s<=9) b[i]=s;else b[i]=9;s-=b[i];        if (s==0) break;    }    for (int i=1;i<=m;++i) printf("%d",a[i]);    printf(" ");    for (int i=1;i<=m;++i) printf("%d",b[i]);    return 0;}

D

题意：给一个N个点M条边的图，问存在多少个这样的四元组(a,b,c,d) 使得a到b有边 a到d有边 b到c有边 d到c有边。

题解：枚举每一个点作为a，然后把a能到的每个点能到的d的次数统计出来，记为sum[d] 则对于a答案为sigma(c(sum[d],2)) 求和即可。

#include <cstdio>#include <cmath>#include <cstring>#include <iostream>#include <algorithm>#include <vector>using namespace std;vector<int> a[3005];int n,m,x,y;long long ans,flag[3005];int main(){    scanf("%d%d",&n,&m);    for (int i=1;i<=m;++i)    {        scanf("%d%d",&x,&y);        a[x].push_back(y);    }    for (int i=1;i<=n;++i)    {        memset(flag,0,sizeof(flag));        for (int j=0;j<a[i].size();++j)        {            for (int k=0;k<a[a[i][j]].size();++k) flag[a[a[i][j]][k]]++;        }        for (int j=1;j<=n;++j)         {            if (j==i) continue;            if (flag[j]<2) continue;            ans+=flag[j]*(flag[j]-1)/2;        }    }    printf("%I64d",ans);    return 0;}

F

题意：一个N*N的0 1矩阵 要求每个矩阵元素不是0就是1 现在要求每行每列都恰好有两个1，若前m行已给出，求方案总数。

题解：记忆化搜索：

　　DP[A,B]表示还剩下A列需要1个1，B列需要2个1，这时候对应的行数也就能知道了。

　　考虑转移：DP[A,B]有三种情况：两个都填在需要1个1的列 此时答案为c(A,2)*DP[A-2,B]

　　　　　　　　　　　　　　　　　两个都填在需要2个1的列 此时答案为c(B,2)*DP[A+2,B-2]

　　　　　　　　　　　　　　　　　一个填在需要1个1的列，一个填在需要2个的列 此时答案为 A*B*DP[A,B-1]

　　　　　　　边界DP[0][0]=1 直接记忆化搜索即可。

#include <cstdio>#include <iostream>#include <cstring>#include <cmath>#include <algorithm>typedef long long LL;using namespace std;int n,k;int a[505],sum1,sum2;LL dp[505][505],m,ans,map[505][505];char ch[505];LL dfs(int x,int y){    if (map[x][y]!=0) return dp[x][y];    dp[x][y]=0;map[x][y]=1;    if (x==0&&y==0)     {        dp[x][y]=1;        return 1;    }    if (y>=2) dp[x][y]=(dp[x][y]+dfs(x+2,y-2)*y*(y-1)/2)%m;    if (x>=2) dp[x][y]=(dp[x][y]+dfs(x-2,y)*x*(x-1)/2)%m;    if (x>=1&&y>=1) dp[x][y]=(dp[x][y]+dfs(x,y-1)*x*y)%m;    return dp[x][y];}int main(){    memset(map,0,sizeof(map));    memset(dp,0,sizeof(dp));    scanf("%d%d%I64d",&n,&k,&m);    for (int i=0;i<n;++i) a[i]=2;    for (int i=1;i<=k;++i)    {        scanf("%s",ch);        for (int j=0;j<n;++j) if (ch[j]==‘1‘) a[j]--;    }    sum1=0;sum2=0;    for (int i=0;i<n;++i) if (a[i]==1) sum1++;    for (int i=0;i<n;++i) if (a[i]==2) sum2++;    ans=dfs(sum1,sum2);    printf("%I64d\n",ans);    return 0;}

Codeforces Round #277.5 (Div. 2)