首页 > 代码库 > 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; }
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; }
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; }
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; }
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; }
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; }
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; }
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; }
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; }
2017年上海金马五校程序设计竞赛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。