咕咕东是个贪玩的孩子，有一天，他从上古遗迹中得到了一个神奇的圆环。这个圆环由字母表组成首尾相接的环，环上有一个指针，最初指向字母a。咕咕东每次可以顺时针或者逆时针旋转一格。例如，a顺时针旋转到z，逆时针旋转到b。咕咕东手里有一个字符串，但是他太笨了，所以他来请求你的帮助，问最少需要转多少次。
输入只有一行，是一个字符串。
输出最少要转的次数。
zeus
18
| 数据点 | 字符串长度 |
|---|---|
| 1,2 | 小于等于10 |
| 3,4,5 | 小于等于100 |
| 6,7,8,9,10 | 小于等于10000 |
对于每一次的转动，分别算出顺时针和逆时针的转动次数，取最小即可。
完整代码如下：
#include<iostream>
#include<string.h>
using namespace std;
int main(){
string s;
int c=0;
cin>>s;
int ls = 0;//97
int *a = new int [s.length()];
for(int i=0;i<s.length();i++){
a[i] = s[i] - 97;
}
for(int i=0;i<s.length();i++){
int d = ((ls+26)-a[i])%26;
int d2 = ((a[i]+26)-ls)%26;
ls = a[i];
c += min(d,d2);
}
cout<<c<<endl;
return 0;
}咕咕东考试周开始了，考试周一共有n天。他不想考试周这么累，于是打算每天都吃顿好的。他决定每天都吃生煎，咕咕东每天需要买a_iai个生煎。但是生煎店为了刺激消费，只有两种购买方式：①在某一天一次性买两个生煎。②今天买一个生煎，同时为明天买一个生煎，店家会给一个券，第二天用券来拿。没有其余的购买方式，这两种购买方式可以用无数次,但是咕咕东是个节俭的好孩子，他训练结束就走了，不允许训练结束时手里有券。咕咕东非常有钱，你不需要担心咕咕东没钱，但是咕咕东太笨了，他想问你他能否在考试周每天都能恰好买a_iai个生煎。
输入两行，第一行输入一个正整数n(1<=n<=100000)(1<=n<=100000)，表示考试周的天数。
第二行有n个数，第i个数a_i（0<=a_i<=10000）ai（0<=ai<=10000）表示第i天咕咕东要买的生煎的数量。
如果可以满足咕咕东奇怪的要求，输出"YES"，如果不能满足，输出“NO”。（输出不带引号）
4
1 2 1 2
YES
3
1 0 1
NO
| 数据点 | n（上限） | a_i*a**i*（上限） |
|---|---|---|
| 1,2 | 10 | 10 |
| 3,4,5 | 1000 | 10 |
| 6,7 | 10 | 10000 |
| 8,9,10 | 100000 | 10000 |
对于每一天，如果前一天为集数，则当天生煎-1，否则生煎不变，最终看生煎是否剩余即可。
完整代码如下：
#include<iostream>
using namespace std;
int main(){
int n = 0;
cin>>n;
int tmp = 0;
int d = 0;
for(int i=0;i<n;i++){
cin>>tmp;
tmp = tmp - d;
if(tmp<0){
d = 1;
break;
}
else if(tmp%2==0){
d=0;
}
else{
d=1;
}
}
if(d==0){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
return 0;
}众所周知，瑞神已经达到了CS本科生的天花板，但殊不知天外有天，人外有苟。在浩瀚的宇宙中，存在着一种叫做苟狗的生物，这种生物天生就能达到人类研究生的知识水平，并且天生擅长CSP，甚至有全国第一的水平！但最可怕的是，它可以发出宇宙射线！宇宙射线可以摧毁人的智商，进行降智打击！
宇宙射线会在无限的二维平面上传播（可以看做一个二维网格图），初始方向默认向上。宇宙射线会在发射出一段距离后分裂，向该方向的左右45°方向分裂出两条宇宙射线，同时威力不变！宇宙射线会分裂n次，每次分裂后会在分裂方向前进ai个单位长度。
现在瑞神要带着他的小弟们挑战苟狗，但是瑞神不想让自己的智商降到普通本科生 那么菜的水平，所以瑞神来请求你帮他计算出共有多少个位置会被"降智打击"。
输入第一行包含一个正整数 ，表示宇宙射线会分裂 n次 (n <= 30)
第二行包含n个正整数 ，第 n 个数表示第 n 次分裂的宇宙射线会在它原方向上继续走多少个单位长度。
输出一个数ans ，表示有多少个位置会被降智打击
4
4 2 2 3
39
| 数据点 | n |
|---|---|
| 10% | <=10 |
| 40% | <=20 |
| 100% | <=30 |
此题通过搜索算法对每一步的扩展进行遍历，并标记访问过的点，计算访问点总数即可。
踩过的坑：
直接BFS时间和空间复杂度都很高，需要通过剪枝来减少遍历次数。——虽然最终会产生2^n个树叶，但是由于每次只会扩展最多5格，所以不会离开300*300的区域，所以肯定有大量的重复分支，所以通过bool VIS[a][b][c][d]表示第d次分裂方向为c的时候，坐标为a,b的点是否已经扩展，若已扩展，则跳过。
其中，line结构体如下：
typedef struct line {
int start_x,start_y;
int end_x,end_y;
int length;
int dx,dy;
int index;
void sets(int x,int y) {
start_x = x;
start_y = y;
}
void setl(int len) {
length = len;
}
void setfx(int a,int b) {
dx = a;
dy = b;
}
void seti(int in) {
index = in;
}
int getLength() {
int all = 0;
end_x = start_x+dx*(length);
end_y = start_y+dy*(length);
for(int i=1; i<=length; i++) {
if(!visited[start_x+dx*i][start_y+dy*i]) {
visited[start_x+dx*i][start_y+dy*i] = true;
all++;
}
}
return all;
}
} line;BFS过程如下：
while(q.size()) {
pa = q.front();
line left,right;
fx = pair<int,int> (pa.dx,pa.dy);
index = pa.index+1;
if(index==n) break;
if(vis[pa.end_x][pa.end_y][mp2[fx]][pa.index]){
q.pop();
continue;
}
vis[pa.end_x][pa.end_y][mp2[fx]][pa.index] = true;
left.setfx(z[mp[fx].first][0],z[mp[fx].first][1]);
left.setl(a[index]);
left.sets(pa.end_x,pa.end_y);
left.seti(index);
ans += left.getLength();
right.setfx(z[mp[fx].second][0],z[mp[fx].second][1]);
right.setl(a[index]);
right.sets(pa.end_x,pa.end_y);
right.seti(index);
ans += right.getLength();
q.pop();
q.push(left);
q.push(right);
}原文：https://www.cnblogs.com/mopa/p/12528528.html