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;
}