第七届ACM趣味程序设计竞赛第四场(正式赛) 题解

Final Pan's prime numbers

题目连接:

http://acm.uestc.edu.cn/#/problem/show/1272

题意

给你n,要求你在[4,n]范围内找到一个最大的质数x,使得x-4和x+4也是质数

题解:

数学

只有7是满足的

为什么?

  1、若 n = 3x,因为n>4,所以n必为合数,不符。
2、若 n = 3x + 1,
则 n - 4 = 3x - 3 = 3(x-1) ,即(n -4 ) % 3 == 0,有且只有n=7时满足
3、若 m = 3x + 2,
则 n + 4 = 3x + 6 = 3 * (x+2),显然n+4为合数,不符
所以n<7时输出-1,n>=7时输出7即可

代码如下:

#include<bits/stdc++.h>
using namespace std; int main()
{
int n;scanf("%d",&n);
if(n<7)return puts("-1");
else printf("7\n");
}

ZhangYu Speech

题目连接:

http://acm.uestc.edu.cn/#/problem/show/1269

题意

给你n个数,m次询问

每次询问是这样的:

输入x

将会构造出一个新的序列,这个新的序列b[i] = a[x] - a[i] (i<x)

然后要求你计算出这个B序列中小于0的数的和Sum1,大于0的数的和的绝对值Sum2

如果Sum1>Sum2 输出Keep dis

如果Sum1=Sum2 输出Next time

如果Sum1<Sum2 输出I aggre

题解:

前缀和

维护前缀和,a[i][j]表示前i个数中,大小为j的数一共有多少个

然后我们就可以处理询问了~

每次处理询问的时候:

Sum1+=a[x][j]*(s[x]-j) (s[x]>j的时候)
Sum2+=a[x][j]*(j-s[x]) (s[x]<j的时候)

然后扫一遍10个数就好了~

代码

#include<bits/stdc++.h>
using namespace std; int a[100001][11];
int n,m;
string s;
int main()
{
scanf("%d%d",&n,&m);
cin>>s;
for(int i=0;i<s.size();i++)
{
if(i!=0)for(int j=0;j<10;j++)a[i][j]=a[i-1][j];
a[i][s[i]-'0']++;
}
while(m--)
{
int x;scanf("%d",&x);
int tmp = s[x-1]-'0';
long long A=0,B=0;
for(int i=0;i<10;i++)
{
if(i<tmp)A+=(tmp-i)*a[x-1][i];
else B+=(i-tmp)*a[x-1][i];
}
if(A==B)printf("Next time\n");
else if(A>B)printf("Keep some distance from me\n");
else printf("I agree\n");
}
}

Playfair

题目连接:

http://acm.uestc.edu.cn/#/problem/show/1270

题意

首先给你一个密码串,你需要通过这个密码串生成5*5的密码矩阵

这个密码矩阵的构造方式如下:

这个矩阵依次填入密码串的字符,如果密码串中的字符出现了多次,只算第一次出现的那次。

密码串中的j视作i,大写视作小写。

剩下没有填满的格子,就按照字典序去填。

然后给你一个串,你需要输出加密后的串。

需要忽略除了字母的任何字符,空格。

加密方式如下:

我们首先把串分组,相邻的两个为一组,如果相邻的两个相同的话,就在这两个之间插入一个x。

分组之后,如果同组的元素都在同一行,就输出右边的,如果都在同一列,就输出下面的,如果都不是,就输出mp[l1][r2],mp[l2][r1]

题解:

模拟题

认真读题之后,就没什么坑了。。。

模拟题多读几遍 T T(别问我为什么

代码

#include<bits/stdc++.h>
using namespace std;
int mp[10][10];
int vis[30];
int l[30];
int r[30];
string s,txt,temp,txt1;
int main()
{
vis['j'-'a']=1;
cin>>s;
int tot = 0,flag = 0;
for(int i=0;i<s.size();i++)
if(s[i]=='j')s[i]='i';
for(int i=0;i<5;i++)//构造密码矩阵
{
for(int j=0;j<5;j++)
{
if(s[tot]=='j')
s[tot]='i';
while(tot<s.size()&&vis[s[tot]-'a'])
tot++;
if(tot==s.size())flag = 1;
if(flag){for(int k=0;k<26;k++)
if(vis[k]==0){mp[i][j]=k;break;}}
else
mp[i][j]=(int)(s[tot]-'a');
vis[mp[i][j]]=1;
}
} for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
l[mp[i][j]]=i,r[mp[i][j]]=j; while(cin>>temp)txt1+=temp;
//大写变小写,去掉奇怪的东西
for(int i=0;i<txt1.size();i++)
{
if(txt1[i]<='Z'&&txt1[i]>='A')
txt1[i]=txt1[i]-'A'+'a';
if(txt1[i]=='j')txt1[i]='i';
if(txt1[i]<='z'&&txt1[i]>='a')txt+=txt1[i];
} for(int i=0;i<txt.size();i++)
{
if(i==txt.size()-1)break;
if(txt[i]==txt[i+1])
{
int l1 = l[txt[i]-'a'];
int r1 = r[txt[i]-'a'];
int l2 = l['x'-'a'];
int r2 = r['x'-'a'];
if(l1 == l2)
cout<<(char)(mp[l1][(r1+1)%5]+'a')<<(char)(mp[l2][(r2+1)%5]+'a');
else if(r1 == r2)
cout<<(char)(mp[(l1+1)%5][r1]+'a')<<(char)(mp[(l2+1)%5][r2]+'a');
else
cout<<(char)(mp[l1][r2]+'a')<<(char)(mp[l2][r1]+'a');
}
else
{
int l1 = l[txt[i]-'a'];
int r1 = r[txt[i]-'a'];
int l2 = l[txt[i+1]-'a'];
int r2 = r[txt[i+1]-'a'];
if(l1 == l2)
cout<<(char)(mp[l1][(r1+1)%5]+'a')<<(char)(mp[l2][(r2+1)%5]+'a');
else if(r1 == r2)
cout<<(char)(mp[(l1+1)%5][r1]+'a')<<(char)(mp[(l2+1)%5][r2]+'a');
else
cout<<(char)(mp[l1][r2]+'a')<<(char)(mp[l2][r1]+'a');
i++;
}
}
}

Search gold

题目连接:

http://acm.uestc.edu.cn/#/problem/show/1271

题意

给你n行m列的矩阵,你一开始在(1,1)这个位置,如果你到某个格子,你身上的权值就会加上a[i][j],如果你权值为负数,就会死掉

问你在保证不走出去,以及不死掉的情况下,权值最多为多少

一开始在(x,y),下一步可以走到(x+1,y)(x,y+1)(x+2,y+1)(x+1,y+2)

题解:

动态规划

dp[i][j]表示走到当前格子所能获得的最大权值,很显然dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-2][j-1],dp[i-1][j-2])+a[i][j]转移过来的

稍微注意下,如果dp[x][y]为负数的话,就不要从这儿转移过来就好了

代码:

#include<bits/stdc++.h>
using namespace std;
const long long inf = 9999999999999LL;
long long dp[1002][1002];
long long a[1002][1002];
int dx[5]={1,0,1,2};
int dy[5]={0,1,2,1};
int n,m;
int check(int x,int y)
{
if(x<1||x>n)return 0;
if(y<1||y>m)return 0;
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
dp[i][j]=-inf;
scanf("%lld",&a[i][j]);
}
dp[1][1]=a[1][1];long long ans = -1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(dp[i][j]<0)continue;
ans = max(ans,dp[i][j]);
for(int k=0;k<4;k++)
{
int x = i+dx[k];
int y = j+dy[k];
if(!check(x,y))continue;
dp[x][y]=max(dp[i][j]+a[x][y],dp[x][y]);
}
}
}
cout<<ans<<endl;
}

God Qing's circuital law

题目连接:

http://acm.uestc.edu.cn/#/problem/show/1273

题意

有n个男孩子,n个女孩子,男孩子和女孩子可以组合在一起,组合一起的Value = p[i] * v[i]

然后问你,一共有多少种组合,第一个人的组合,能力值最高

题解:

暴力容斥

首先我们枚举每一个女孩子和第一个人组合的情况

然后枚举后面的熊孩子,对于每个熊孩子再数出一共有多少种组合比他厉害,就可以暴力容斥了~

代码

#include<bits/stdc++.h>
using namespace std;
#define maxn 120
const int mod = 1e9 + 7;
long long a[maxn];
long long b[maxn];
long long c[maxn];
bool cmp(int A,int B)
{
return A>B;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
for(int i=0;i<n;i++)
scanf("%lld",&b[i]);
sort(a+1,a+n,cmp);
sort(b,b+n);
long long ans = 0;
for(int i=0;i<n;i++)
{
long long p = a[0]*b[i];
int tot = 0;
long long k = b[i];
for(int j=0;j<n;j++)
{
if(j==i)continue;
c[tot++]=b[j];
}
long long ans2 = 1;
int flag = 0;
for(int j=1;j<n;j++)
{
long long tmp = -1;
for(int t=0;t<tot;t++)
{
if(a[j]*c[t]>=p)
break;
tmp = t;
}
tmp = tmp + 2 - j;
if(tmp<=0)
{
flag = 1;
break;
}
ans2 = (ans2 * tmp)%mod;
}
if(flag==0)
ans = (ans + ans2)%mod;
}
printf("%d\n",ans);
}

Open the lightings

题目连接:

http://acm.uestc.edu.cn/#/problem/show/1268

题意

给你n栈灯,一开始只有第m盏灯是亮着的。

然后你可以打开第i盏灯,如果第j盏灯是亮着的,而且abs|j-i|<=2

然后问你一共有多少种方式能够打开所有灯

题解:

动态规划

f[n]表示开了n盏灯的方案数,则f[n]=(f[n-2])*(n-1)+f[n-1]。

由于第一盏灯的两方相互不影响,设i为最初的灯 则答案为f[i-1]f[n-i]c(n-1,i-1)

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const LL oo=1000000007;
LL n,m,i,j,c[1111][1111],b[1111],ans;
int main(){
scanf("%I64d%I64d",&n,&m);
if(n==1){
printf("1\n");return 0;
}
b[1]=1;b[2]=2;
for(i=3;i<=n;++i){
b[i]=(((b[i-2])*(i-1))%oo+b[i-1])%oo;
}
if(m==n||m==1){
printf("%I64d\n",b[n-1]);
return 0;
}
c[0][0]=1;
for(i=1;i<=n;++i){
c[i][0]=1;
for(j=1;j<=i;++j)c[i][j]=(c[i-1][j]+c[i-1][j-1])%oo;
}
ans=((b[m-1]*b[n-m])%oo*c[n-1][m-1])%oo;
printf("%I64d\n",ans);
return 0;
}
上一篇:[打基础]OI/ACM基本功&一些小功能的实现&一些错误(持续更新)


下一篇:【node.js】全局变量、常用工具、文件系统