首页 > 代码库 > 2017年上海金马五校程序设计竞赛

2017年上海金马五校程序设计竞赛

A

STEED 这个字符串可以任意变换位子

找到第n个 

深搜 遍历所有可能字符串 然后放到set维护  第n个就可以了

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
 
using namespace std;
 
#define ll long long
#define inf 1000000007
 
string z="STEED";
 
bool vis[5];
set<string>s1;
 
void dfs(int ind,string a)
{
    int ok=0;
    for(int i=0;i<5;i++)
    {
        if(vis[i]==0)
        {
            ok=1;
        }
    }
    if(ok==0)
    {
        //cout<<a<<endl;
        s1.insert(a);
        return ;
    }
    for(int i=0;i<5;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            dfs(i,a+z[i]);
            vis[i]=0;
        }
    }
}
 
int main()
{
    for(int i=0;i<5;i++)
    {
        string a="";
        a=a+z[i];
        vis[i]=1;
        dfs(i,a);
        vis[i]=0;
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i=1;
        for(set<string>::iterator j=s1.begin();i<=n;i++,j++)
        {
            if(i==n)
                cout<<*j<<endl;
        }
    }
    return 0;
}
View Code

B

n*n矩阵

从左上角走到右下角

*到*费用是1  #到其他地方费用2

问最小费用

bfs+优先队列  步数小的优先  步数相同 *优先

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
#include<math.h>
#include<queue>
#include<vector>
 
using namespace std;
 
#define ll long long
#define inf 1000000007
#define MAXN 20010
 
bool vis[55][55];
char z[55][55];
struct node
{
    int x,y,step;
 
};
struct cmp1{
    bool operator ()(node a,node b){
        if(a.step==b.step)
        {
            if(z[a.x][a.y]==*)
                return 0;
            return 1;
        }
        return a.step>b.step;//最小值优先
    }
};
priority_queue<node ,vector<node >,cmp1>q1;
int s1[4]={1,-1,0,0};
int s2[4]={0,0,1,-1};
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%s",z[i]+1);
        memset(vis,0,sizeof(vis));
        while(!q1.empty())
            q1.pop();
        node a;
        a.x=1;
        a.y=1;
        a.step=0;
        q1.push(a);
        vis[a.x][a.y]=1;
        int mx=inf;
        while(!q1.empty())
        {
            node now=q1.top();
            if(now.x==n&&now.y==n)
            {
                mx=min(mx,now.step);
            }
            q1.pop();
            for(int i=0;i<4;i++)
            {
                node b;
                b.x=now.x+s1[i];
                b.y=now.y+s2[i];
                if(b.x>=1&&b.x<=n&&b.y>=1&&b.y<=n&&vis[b.x][b.y]==0)
                {
                    vis[b.x][b.y]=1;
                    if(z[now.x][now.y]==#)
                        b.step=now.step+1;
                    else
                    {
                        if(z[b.x][b.y]==#)
                            b.step=now.step+1;
                        else
                            b.step=now.step;
                    }
                 //  printf("%d %d %d %d %d %d\n",now.x,now.y,now.step,b.x,b.y,b.step);
                    q1.push(b);
                }
            }
        }
        printf("%d\n",mx);
    }
    return 0;
}
View Code

C

n然后n个数字   要在每个数字前面加 一个 + 或者 - 问有多少个不同的结果

暴力  去同

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
 
using namespace std;
 
#define ll long long
#define inf 1000000007
#define MAXN 20010
 
set<ll>s1;
ll z[25];
 
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%lld",&z[i]);
        int en=1<<n;
        s1.clear();
        for(int i=0;i<en;i++)
        {
            ll ans=0;
 
            for(int j=0;j<n;j++)
            {
                if(i&(1<<j))
                    ans=ans+z[j];
                else
                    ans=ans-z[j];
            }
            s1.insert(ans);
        }
        printf("%d\n",s1.size());
 
    }
    return 0;
}
View Code

E 最长回文字串   暴力的 

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
 
using namespace std;
 
#define ll long long
#define inf 1000000007
#define MAXN 20010
 
char z[55];
 
int main()
{
    while(scanf("%s",z)!=EOF)
    {
        int len=strlen(z);
        int mx=0;
 
        for(int i=0;i<len;i++)
        {
            for(int j=i;j<len;j++)
            {
                int a=i;
                int b=j;
                for(;a<=b;a++,b--)
                {
                    if(z[a]!=z[b])
                        break;
                }
                if(a>b)
                    mx=max(mx,j-i+1);
            }
        }
        printf("%d\n",mx);
    }
    return 0;
}
View Code

G 给你n *m矩阵  每次可以向下或者向右走一不  不能走的人输掉

第二个人开始有一次机会 去掉一个点  n+m-2 后手赢  那么 后手可以随便 放一个赢的  

否则 max(n,m)-min(n,m)>=2 后手赢  否则先手赢

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
#include<math.h>
#include<queue>
#include<vector>
 
using namespace std;
 
#define ll long long
#define inf 1000000007
#define MAXN 20010
 
 
int main()
{
    ll n,m;
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
        if((n+m)%2==1){
            if(max(n,m)-min(m,n)>=2)
                printf("YES\n");
            else printf("NO\n");
        }
             
        else
            printf("YES\n");
    }
    return 0;
}
View Code

H n 个数 长度为k的窗子  求最大值  最大平均值 最小方差

最大值单调队列  平均的话 前缀  方差  也是前缀  前缀平方  化简下就可以

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
#include<math.h>
#include<queue>
#include<vector>
 
using namespace std;
 
#define ll long long
#define inf 1000000007
#define MAXN 10000100
 
double z[MAXN];
struct
{
    double w;
    int ind;
}q[MAXN];
double sum[MAXN];
double sum1[MAXN];
 
int main()
{
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        double mi;
        double mx;
        sum[0]=sum1[0]=0;
 
        for(int i=1;i<=n;i++)
        {
            scanf("%lf",&z[i]);
            sum[i]=sum[i-1]+z[i];
            sum1[i]=sum1[i-1]+z[i]*z[i];
 
            if(i==k)
            {
                 mi=sum[i]/k;
                 mx=sqrt(sum1[i]/k-2*mi*sum[i]/k+mi*mi);
            }
            else if(i>k)
            {
                double u=(sum[i]-sum[i-k])/k;
                mi=max(mi,u);
                mx=min(mx,sqrt((sum1[i]-sum1[i-k])/k-2*u*(sum[i]-sum[i-k])/k+u*u));
            }
        }
        double ans=0;
        int fr=1;
        int sz=1;
        q[1].w=z[1];
        q[1].ind=1;
        for(int i=2;i<k;i++)
        {
            while(sz>=fr&&q[sz].w<z[i])
                sz--;
            sz++;
            q[sz].w=z[i];
            q[sz].ind=i;
        }
        for(int i=k;i<=n;i++)
        {
            while(sz>=fr&&q[sz].w<z[i])
                sz--;
            sz++;
            q[sz].w=z[i];
            q[sz].ind=i;
            while(q[fr].ind<i-k+1)
                fr++;
            ans=ans+q[fr].w;
        }
        printf("%.1lf %.1lf %.1lf\n",1.0*ans/(n-k+1),mi,mx);
 
    }
    return 0;
}
View Code

I

求欧拉函数

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
#include<math.h>
using namespace std;
 
#define ll long long
#define inf 1000000007
#define MAXN 20010
 
int ph(int a)
{
    int b=a;
    int c=b;
 
    for(int i=2;i<=sqrt(a);i++)
    {
        if(b%i==0)
        {
            while(b%i==0)
                b=b/i;
            c=c/i*(i-1);
        }
    }
    if(b!=1)
        c=c/b*(b-1);
    return c;
}
 
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",ph(n));
    }
    return 0;
}
View Code

K题

蛇形填数  维护左右上下边界 

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
#include<math.h>
#include<queue>
#include<vector>
 
using namespace std;
 
#define ll long long
#define inf 1000000007
#define MAXN 20010
 
int z[10085];
int x[105][105];
 
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n*m;i++)
            scanf("%d",&z[i]);
        int l,c,t,d;
        l=c=1;
        int r1=m;
        t=2;
        int t1=n;
        int cnt=1;
 
        while(cnt<=n*m)
        {
            for(int i=c;i<=r1;i++)
                x[l][i]=z[cnt++];
            if(cnt>n*m)
            {
                break;
            }
            for(int i=l+1;i<=t1;i++)
                x[i][r1]=z[cnt++];
            if(cnt>n*m)
            {
                break;
            }
            for(int i=r1-1;i>=c;i--)
                x[t1][i]=z[cnt++];
            if(cnt>n*m)
            {
                break;
            }
            for(int i=t1-1;i>l;i--)
                x[i][c]=z[cnt++];
            if(cnt>n*m)
            {
                break;
            }
            l++;
            c++;
            t1--;
            r1--;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<m;j++)
                printf("%d ",x[i][j]);
            printf("%d\n",x[i][m]);
        }
 
    }
    return 0;
}
View Code

O

n  然后2*n个数 分成n组  每组2个数   然后求每组差的绝对值的和 最小 

排序

技术分享
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<set>
#include<iterator>
#include<iostream>
 
using namespace std;
 
#define ll long long
#define inf 1000000007
#define MAXN 20010
ll z[MAXN];
 
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n*2;i++)
            scanf("%lld",&z[i]);
        sort(z+1,z+n+n+1);
        ll ans=0;
        for(int i=1;i<=2*n;i=i+2)
        {
            if(z[i+1]>z[i])
                ans=ans+z[i+1]-z[i];
            else
                ans=ans+z[i]-z[i+1];
        }
        printf("%lld\n",ans);
    }
    return 0;
}
View Code

 

  

2017年上海金马五校程序设计竞赛