牛客寒假算法训练第四场
A题：https://ac.nowcoder.com/acm/contest/330/A
题解：博弈论，此题先手必胜
留坑待补更详细的解释
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100010];
typedef long long ll;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
printf("Applese\n");
return 0;
}B题：https://ac.nowcoder.com/acm/contest/330/B
题解：构造题，我觉得对于我的坑点数据是n=1,m>2或者m=1,n>2。没有注意特判
思路和官方题解差不多
#include <bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
scanf("%d %d",&n,&m);
if(n%2!=0&&m%2!=0){
printf("-1\n");
}
else if((n==1&&m>2)||(m==1&&n>2)){
printf("-1\n");
}
else {
if(n%2!=0){
for(int i=0;i<n-1;i++){
printf("D");
}
for(int i=0;i<m-1;i++){
printf("R");
}
for(int i=n-1;i>0;i--){
printf("U");
}
for(int i=m-1-1;i>0;i--){
printf("L");
for(int j=0;j<n-2;j++){
if(i%2==0){
printf("D");
}
else printf("U");
}
}
printf("L");
printf("\n");
}
else{
for(int i=0;i<m-1;i++){
printf("R");
}
for(int i=0;i<n-1;i++){
printf("D");
}
for(int i=m-1;i>0;i--){
printf("L");
}
for(int i=n-1-1;i>0;i--){
printf("U");
for(int j=0;j<m-1-1;j++){
if(i%2==0){
printf("R");
}
else printf("L");
}
}
printf("U");
printf("\n");
}
}
return 0;
}C题：https://ac.nowcoder.com/acm/contest/330/C
题解：搜索题，求最短的路径，选择bfs最好。用一个三维数组记录每个点的状态vis[x][y][0/1],代表Applese以火或水属性是否走过点(x,y)。
#include <bits/stdc++.h>
using namespace std;
int n,m;
char maps[110][110];
int vis[110][110][2];
int sx,sy,tx,ty;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
struct pos
{
int x,y,step,stute;
};
int bfs(int startx,int starty,int endx,int endy)
{
queue <pos> q;
vis[startx][starty][0]=1;
struct pos t;
t.x=startx,t.y=starty,t.step=0,t.stute=0;
q.push(t);
while(!q.empty()){
struct pos now,next;
now=q.front();
q.pop();
if(now.x==endx&&now.y==endy){
return now.step;
}
for(int i=0;i<4;i++){
int x1=now.x+dir[i][0];
int y11=now.y+dir[i][1];
int t1=now.step+1;
int stute1=now.stute;
if(maps[x1][y11]=='#'||x1>=n||y11>=m||x1<0||y11<0) continue ;
if(stute1==0&&maps[x1][y11]!='w'&&vis[x1][y11][0]==0){
vis[x1][y11][0]=1;
next.x=x1,next.y=y11,next.step=t1,next.stute=stute1;
q.push(next);
}
if(stute1==1&&maps[x1][y11]!='~'&&vis[x1][y11][1]==0){
vis[x1][y11][1]=1;
next.x=x1,next.y=y11,next.step=t1,next.stute=stute1;
q.push(next);
}
/*if(maps[x1][y11]=='@'&&vis[x1][y11][stute1]==0){
next.x=x1,next.y=y11,next.step=t1,next.stute=stute1;
vis[x1][y11][stute1]=1;
q.push(next);
}
if(maps[x1][y11]=='@'&&vis[x1][y11][stute1^1]==0){
next.x=x1,next.y=y11,next.step=t1+1,next.stute=stute1^1;
vis[x1][y11][stute1^1]=1;
q.push(next);
}*/ //不能这样写
if(maps[x1][y11]=='T'){
return t1;
}
}
if(maps[now.x][now.y]=='@'&&vis[now.x][now.y][now.stute^1]==0){
next.x=now.x,next.y=now.y,next.step=now.step+1,next.stute=now.stute^1;
vis[now.x][now.y][now.stute^1]=1;
q.push(next);
}
}
return -1;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",maps[i]);
for(int j=0;j<m;j++){
if(maps[i][j]=='S'){
sx=i,sy=j;
}
else if(maps[i][j]=='T'){
tx=i,ty=j;
}
}
}
printf("%d\n",bfs(sx,sy,tx,ty));
return 0;
}E题：https://ac.nowcoder.com/acm/contest/330/E
题解：因为左右相邻的都不能有相同颜色，明显当每一行的第一个都确定了颜色时，这一行的状态也就确定了，而每一个格子的颜色只有两种选择。所有答案即为。因为n的数据大小到了
，要用欧拉降幂+快速幂。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define N 1000100
#define mod 1e9+7
using namespace std;
char b[N];
char n[N],m[N];
ll p[N];
ll a, c;
ll quick(ll a, ll b){ //快速幂
ll k = 1;
while(b){
if(b%2==1){
k = k*a;
k %=c;
}
a = a*a%c;
b /=2;
}
return k;
}
void priem(){
memset(p, 0, sizeof(p));
ll i, j;
p[1] = 1;
for(i=2; i<=sqrt(N); i++){
for(j=2; j<=N/i; j++)
p[i*j] = 1;
}
}
ll ola(ll n){ //欧拉函数
ll i, j, r, aa;
r = n;
aa = n;
for(i=2; i<=sqrt(n); i++){
if(!p[i]){
if(aa%i==0){
r = r/i*(i-1);
while(aa%i==0)
aa /= i;
}
}
}
if(aa>1)
r = r/aa*(aa-1);
return r;
}
int main(){
ll d, i, j;
priem();
scanf("%s %s",n,m);
ll l = strlen(n);
ll B=0;
c=mod;
ll oc = ola(c);
for(i=0; i<l; i++){
B = B*10+n[i]-'0';
if(B>oc)
break;
}
if(i==l)
d = quick(2,B);
else{
B=0;
for(i=0; i<l; i++){
B = (B*10+n[i]-'0')%oc;
}
d = quick(2,B+oc);
}
printf("%lld\n",d);
return 0;
}还有强大的python解法:
print(pow(2, int(input().split()[0]), 10**9 + 7))J题：https://ac.nowcoder.com/acm/contest/330/J
签到题就不说了，用公式就好了
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-6
#define pi 3.1415926
int main()
{
double ans,f1,f2;
int a;
scanf("%lf %lf %d",&f1,&f2,&a);
ans=f1*f1+f2*f2+2*f1*f2*cos(a*pi/180);
ans=sqrt(ans);
printf("%lf\n",ans);
return 0;
}