1.模拟转圈圈：
题面：一个字符串和一个转盘，一开始转盘指向a，问转盘指向完整个字符串的最小代价是多少。
字符串均为小写字母。
Input：
hzet
Output：
31
这道题现实意义上很简单，就是直接模拟一个一个走就行。因为是一个字母序的环，所以直接取min（字母序距离，26-字母序距离）。换言之直接用ascii计算也可
#include<iostream>
#include<string>
#include<string.h>
#include<cstring>
using namespace std;
int geeet(int a)
{
if(a>=0)
//
{
return a;
}
else
{
return a+26;
}
}
int min(int a,int b)
{
if(a>b)
{
return b;
}
else
{
return a;
}
return 0;
}
int main()
{
string x;
cin>>x;
int sum=min(geeet(x[0]-'a'),geeet('a'-x[0]));
int a=x.length();
for(int i=0;i<a-1;i++)
{
sum+=min(geeet(x[i]-x[i+1]),geeet(x[i+1]-x[i]));
}
cout<<sum<<endl;
return 0;
}
2.依旧模拟：
image.png
题面有些不太清楚。。
需要注意的是：1.给出了两种购买策略，一天可以用很多次这两个其中之一的策略 2.购物券只能留一天。。
所以就很清楚了 ，简单的模拟，每天看看前一天有没有购物券，先用了（不能用直接return false），再看看是奇是偶。能不能给明天留购物券
直接上代码了QAQ
#include<iostream>
using namespace std;
int main()
{
int n;
bool jieguo=true;
cin>>n;
int a[100000+10];
int juan=0;
bool havejuan=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
if(havejuan)
{
if(juan>a[i])
{
jieguo=false;
break;
}
else if(juan==a[i])
{
juan=0;
havejuan=0;
continue;
}
else
{
a[i]=a[i]-juan;
havejuan=0;
}
}
if(a[i]%2==0)
{
continue;
}
if(a[i]%2==1)
{
havejuan=1;
juan=1;
}
}
if(havejuan)
{
jieguo=false;
}
if(!jieguo)
{
cout<<"NO"<<endl;
}
else
{
cout<<"YES"<<endl;
}
return 0;
}
3.一道dfs+剪支的问题
image.png
image.png
首先看……思路。大概看上去题面应该是类似一个二叉树的结构。每一个节点造成一定的影响之后会分裂出两个其他的节点 。两个分裂出来的起点就是该点的终点，而且左右各转了45度。
那基本的思路就有了，定义一个射线类，规定走多长，方向，起点，dfs去对每次分裂的每条射线进行模拟。先确定数据范围，发现300*300的访问数据就够了，先重置为0访问过就标记该点为1，然后记录每次分裂出来的射线加入队列。从队列顶部弹出一个然后先走一段延续的距离再分裂……。
开始码！
#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<cstring>
#include<cmath>
using namespace std;
int vis[1000][1000];
int temp=0;
int a[40];
struct dian
{
int x;
int y;
int ts;
int tb;
};
int tl,tk;
dian xuanzhuan1[2];
void xuanzhuan(dian p)
{
xuanzhuan1[0]=p;
xuanzhuan1[1]=p;
//0 1 0 -1
if(p.tb==0)
{
xuanzhuan1[0].tb=-1;
xuanzhuan1[0].ts=p.ts;
xuanzhuan1[1].tb=1;
xuanzhuan1[1].ts=p.ts;
}
// 1 1 -1 -1
else if((p.tb==-1&&p.ts==-1)||(p.tb==1&&p.ts==1))
{
xuanzhuan1[0].tb=0;
xuanzhuan1[0].ts=p.ts;
xuanzhuan1[1].tb=p.ts;
xuanzhuan1[1].ts=0;
}
//1 0 -1 0
else if(p.ts==0)
{
xuanzhuan1[0].tb=p.tb;
xuanzhuan1[0].ts=-1;
xuanzhuan1[1].tb=p.tb;
xuanzhuan1[1].ts=1;
}
else
{
xuanzhuan1[0].tb=0;
xuanzhuan1[0].ts=p.ts;
xuanzhuan1[1].tb=p.tb;
xuanzhuan1[1].ts=0;
}
}
void kuozhan(dian p,int i)
{
if(!vis[p.x+p.tb*i][p.y+p.ts*i])
{
vis[p.x+p.tb*i][p.y+p.ts*i]=1;
temp++;
}
}
int main()
{
int n;
int times=1;
int yk=1;
cin>>n;
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
{
cin>>a[i];
}
queue<dian> q;
dian p;
dian begin;
tl=0;tk=1;
begin.x=500;
begin.y=500;
begin.tb=0;begin.ts=1;
q.push(begin);
while(yk<n)
{
p=q.front();
q.pop();
for(int i=1;i<=a[yk-1];i++)
{
kuozhan(p,i);
}
dian pl;
pl.x=p.x+p.tb*a[yk-1];
pl.y=p.y+p.ts*a[yk-1];
xuanzhuan(pl);
q.push(xuanzhuan1[0]);
q.push(xuanzhuan1[1]);
times--;
if(times==0)
{
times=pow(2,yk);
yk++;
}
}
cout<<temp<<endl;
return 0;
}
不到一会儿就写完了，然后提交……不出意外的发现爆内存了。因为每次往队列里面加入的都是……分裂之后的射线。而数据范围n<=30。巅峰时会有2^30根射线加入队列……肯定会炸内存。
所以就要剪支了，一开始剪支剪得很复杂……思路是不会再造成影响的射线都不加入了（我怀疑这样搞写出来也会炸时间）。
后来仔细的思考后发现，其实对每层重合的射线剪支就行。就是棋盘一共300*300，算上四个方向也就720000，和2^30比起来……抽屉原理会发现重了好多射线。所以加个访问数据再加上一维方向。每一次分裂前重置这个数据，然后分裂的时候记录下来已经有该次分裂产生射线的位置和方向，进行剪支。
改进后的代码
#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<cstring>
#include<cmath>
using namespace std;
int vis[310][310];
int jianzhi[300][300][3][3];
int temp = 0;
int a[40];
struct dian
{
int x;
int y;
int ts;
int tb;
};
int tl, tk;
dian xuanzhuan1[2];
void xuanzhuan(dian p)
{
xuanzhuan1[0] = p;
xuanzhuan1[1] = p;
//0 1 0 -1
if (p.tb == 0)
{
xuanzhuan1[0].tb = -1;
xuanzhuan1[0].ts = p.ts;
xuanzhuan1[1].tb = 1;
xuanzhuan1[1].ts = p.ts;
}
// 1 1 -1 -1
else if ((p.tb == -1 && p.ts == -1) || (p.tb == 1 && p.ts == 1))
{
xuanzhuan1[0].tb = 0;
xuanzhuan1[0].ts = p.ts;
xuanzhuan1[1].tb = p.ts;
xuanzhuan1[1].ts = 0;
}
//1 0 -1 0
else if (p.ts == 0)
{
xuanzhuan1[0].tb = p.tb;
xuanzhuan1[0].ts = -1;
xuanzhuan1[1].tb = p.tb;
xuanzhuan1[1].ts = 1;
}
else
{
xuanzhuan1[0].tb = 0;
xuanzhuan1[0].ts = p.ts;
xuanzhuan1[1].tb = p.tb;
xuanzhuan1[1].ts = 0;
}
}
void kuozhan(dian p, int i)
{
if (!vis[p.x + p.tb*i][p.y + p.ts*i])
{
vis[p.x + p.tb*i][p.y + p.ts*i] = 1;
jianzhi[p.x][p.y][p.tb+1][p.ts+1];
temp++;
}
}
int main()
{
int n;
int times = 1;
int yk = 1;
cin >> n;
memset(vis, 0, sizeof(vis));
memset(jianzhi, 0, sizeof(jianzhi));
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
queue<dian> q;
dian p;
dian begin;
tl = 0; tk = 1;
begin.x = 150;
begin.y = 150;
begin.tb = 0; begin.ts = 1;
q.push(begin);
while (yk <= n)
{
p = q.front();
q.pop();
for (int i = 1; i <= a[yk - 1]; i++)
{
kuozhan(p, i);
}
dian pl;
pl.x = p.x + p.tb*a[yk - 1];
pl.y = p.y + p.ts*a[yk - 1];
pl.tb = p.tb;
pl.ts = p.ts;
xuanzhuan(pl);
if(!jianzhi[xuanzhuan1[0].x][xuanzhuan1[0].y][xuanzhuan1[0].tb+1][xuanzhuan1[0].ts+1])
{
q.push(xuanzhuan1[0]);
}
if(!jianzhi[xuanzhuan1[1].x][xuanzhuan1[1].y][xuanzhuan1[1].tb+1][xuanzhuan1[1].ts+1])
{
q.push(xuanzhuan1[1]);
}
times--;
if (times == 0)
{
times = pow(2, yk);
memset(jianzhi, 0, sizeof(jianzhi));
yk++;
}
}
cout << temp << endl;
return 0;
}
在炸时间和炸内存的边缘，咳咳，完美的过 了
网友评论