哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级） 题解
哈尔滨理工大学软件与微电子学院第八届程序设计竞赛同步赛（高年级） 题解
用户2965768
发布于 2018-12-24 11:44:36
发布于 2018-12-24 11:44:36
A
从 1到 n 遍历
若i 为7的倍数， 则加上m中7的倍数的个数
若不是7的倍数， 加上 m除以7的个数
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
long long n,m;
scanf("%lld %lld",&n,&m);
long long sum = 0;
for(long long i = 1;i<=n;i++){
int temp = i%7;
if(i==0)
sum+=(m/7);
else
sum+=(m+temp)/7;
}
printf("%lld",sum);
return 0;
}B 状压DP
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int N, M;
ll dp[1035][1035];
void dfs(int i,int j,int state,int nex) {
if (j==N) {
dp[i+1][nex]+=dp[i][state];
return;
}
if (((1<<j)&state)>0)
dfs(i,j+1,state,nex);
if (((1<<j)&state)==0)
dfs(i,j+1,state,nex|(1<<j));
if (j+1<N && ((1<<j)&state)==0 && ((1<<(j+1))&state)==0)
dfs(i,j+2,state,nex);
return;
}
int main() {
scanf("%d %d",&N,&M);
if(N*M%2==1)printf("0");
else if(N==1) printf("%d",M/2);
else if(M==1) printf("%d",N/2);
else{
memset(dp,0,sizeof(dp));
dp[1][0]=1;
for (int i=1; i<=M; i++) {
for (int j=0; j<(1<<N); j++)
if (dp[i][j]) {
dfs(i,0,j,0);
}
}
printf("%lld\n",dp[M+1][0]);
}
return 0;
}C 签到题
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[1005];
int main()
{
int n,s;
ll sum=0;
scanf("%d %d",&n,&s);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
sum = a[0]*s;
printf("%lld",sum);
return 0;
}D 签到题
E 动态规划
#include <bits/stdc++.h>
using namespace std;
#define ll long long
char a[1005],b[1005];
int dp[1005][1005];
int main()
{
scanf("%s",a);
scanf("%s",b);
int n1 = strlen(a);
int n2 = strlen(b);
memset(dp,0,sizeof(dp));
for(int i=0;i<n1;i++)
for(int j=0;j<=n2;j++)
{
if(a[i]==b[j])
dp[i+1][j+1]=dp[i][j]+1;
else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
}
printf("%d",dp[n1][n2]);
return 0;
}F
模拟 深搜
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int dp[205][205][205];
int dir[][2] = { 1,2,2,1,-1,2,-2,1,1,-2,2,-1,-1,-2,-2,-1 };
struct node{
int x;
int y;
int step;
};
int main()
{
int n,m,k;
while(scanf("%d %d %d",&n,&m,&k)!=EOF)
{
queue<node> q;
while(!q.empty())q.pop();
memset(dp,0,sizeof(dp));
dp[0][0][0] = 1;
q.push( node{0,0,0} );
while(!q.empty())
{
node t = q.front();
q.pop();
if(t.step == k)
break;
for(int i=0;i<8;i++)
{
int tx = t.x + dir[i][0];
int ty = t.y + dir[i][1];
if(tx<0||tx>=n||ty<0||ty>=m)continue;
if(dp[tx][ty][t.step+1]==0)
q.push(node{tx,ty,t.step+1});
dp[tx][ty][t.step+1]+=dp[t.x][t.y][t.step];
dp[tx][ty][t.step+1]%=mod;
}
}
printf("%d\n",dp[n-1][m-1][k]);
}
return 0;
}G
队列+bfs
#include <bits/stdc++.h>
using namespace std;
#define ll long long
char ma[1010][1010];
int n,m,rx,ry,fx,fy;
int dir[][2]={0,1, 0,-1, 1,0, -1,0};
struct node{
int x,y,step;
}now,qian,ff;
int step[1010][1010];
int bfs()
{
queue <node> que;
memset(step,0,sizeof(step));
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
{
if (ma[i][j]=='F')
{
now.x=i;now.y=j;now.step=0;
step[i][j] =0;
que.push(now);
break;
}
}
while (!que.empty())
{
now=que.front();
que.pop();
for (int i=0;i<4;i++)
{
int tx=now.x+dir[i][0];
int ty=now.y+dir[i][1];
if (tx<0||ty<0||tx==n||ty==m) continue;
{
if(step[tx][ty]==0&&ma[tx][ty]!='F'){
qian.x=tx;
qian.y=ty;
qian.step=now.step+1;
step[tx][ty] = qian.step;
que.push(qian);
}
}
}
}
ff.x = rx,ff.y = ry,ff.step = 0;
que.push(ff);
while(!que.empty()){
now=que.front();
que.pop();
for (int i=0;i<4;i++)
{
int tx=now.x+dir[i][0];
int ty=now.y+dir[i][1];
if (tx<0||ty<0||tx==n||ty==m) continue;
{
if(ma[tx][ty]=='E')
return now.step + 1;
if(now.step+1<step[tx][ty]&&ma[tx][ty]!='#'){
qian.x=tx;
qian.y=ty;
qian.step=now.step+1;
step[tx][ty] = qian.step;
que.push(qian);
}
}
}
}
return 0;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
for (int i=0;i<n;i++)
{
scanf("%s",ma[i]);
for (int j=0;j<m;j++)
{
if (ma[i][j]=='S')
{
rx=i;ry=j;
ma[i][j]='#';
}
}
}
int ans=bfs();
if (ans)
printf("PIG PIG PIG!\n");
else
printf("A! WO SI LA!\n");
}
return 0;
}H
I 博弈 水题
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll n,m,k;
while(~scanf("%lld %lld %lld",&n,&m,&k)){
n = n+m;
if(n%2==0&&k%2!=0){
printf("LAOZI CHUI SI NI!\n");
}
else{
printf("HAI YOU SEI!\n");
}
}
return 0;
}J
列举所有情况 00， 25 ， 50， 75结尾
写出第一种其他改一下字符就行
#include <bits/stdc++.h>
using namespace std;
char s[105],a[105];
int main()
{
int s0,s5,s7,s2,ans,t,flag;
while(scanf("%s",s)>0)
{
ans = 10000;
flag = 0;
strcpy(a,s);
s0 = 0; s5 = 0; s7 = 0; s2 = 0;
for(int i=0;i<strlen(a);i++)
{
if(a[i]=='0')s0++;
if(a[i]=='2')s2++;
if(a[i]=='5')s5++;
if(a[i]=='7')s7++;
}
if(s0>=2)
{
t = 0;
flag = 1;
for(int i = strlen(a)-1;i>=0;i--)
{
if(a[i]=='0')
{
for(int j = i;j<strlen(a) - 1;j++)
{
t++;
swap(a[j],a[j+1]);
}
break;
}
}
for(int i = strlen(a)-2;i>=0;i--)
{
if(a[i]=='0')
{
for(int j = i;j<strlen(a) - 2;j++)
{
t++;
swap(a[j],a[j+1]);
}
break;
}
}
ans = min(ans,t);
}
if(s2&&s5)
{ flag = 1;t = 0; strcpy(a,s);
for(int i = strlen(a)-1;i>=0;i--)
{
if(a[i]=='5')
{
for(int j = i;j<strlen(a) - 1;j++)
{
t++;
swap(a[j],a[j+1]);
}
break;
}
}
for(int i = strlen(a)-2;i>=0;i--)
{
if(a[i]=='2')
{
for(int j = i;j<strlen(a) - 2;j++)
{
t++;
swap(a[j],a[j+1]);
}
break;
}
}
ans = min(ans,t);
}
if(s7&&s5)
{ flag = 1;
t = 0; strcpy(a,s);
for(int i = strlen(a)-1;i>=0;i--)
{
if(a[i]=='5')
{
for(int j = i;j<strlen(a) - 1;j++)
{
t++;
swap(a[j],a[j+1]);
}
break;
}
}
for(int i = strlen(a)-2;i>=0;i--)
{
if(a[i]=='7')
{
for(int j = i;j<strlen(a) - 2;j++)
{
t++;
swap(a[j],a[j+1]);
}
break;
}
}
ans = min(ans,t);
}
if (s5&&s0)
{
flag = 1;
t = 0;
strcpy(a, s);
for (int i = strlen(s) - 1; i >= 0; i--)
{
if (a[i] == '0')
{
for (int j = i; j < strlen(s) - 1; j++)
{
t++;
swap(a[j], a[j + 1]);
}
break;
}
}
for (int i = strlen(s) - 2; i >= 0; i--)
{
if (a[i] == '5')
{
for (int j = i; j < strlen(s) - 2; j++)
{
t++;
swap(a[j], a[j + 1]);
}
break;
}
}
ans = min(ans, t);
}
if(!flag)
ans = -1;
printf("%d\n",ans);
}
return 0;
} 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年12月03日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读