牛客每日练习----A-逃脱，A-Tabris减肥记，数圈圈
大提琴的声音就像一条河，左岸是我无法忘却的回忆，右岸是我值得紧握的璀璨年华，中间流淌的，是我年年岁岁淡淡的感伤
链接：https://ac.nowcoder.com/acm/problem/14536
来源：牛客网
题目描述
这是mengxiang000和Tabris来到幼儿园的第四天，幼儿园老师在值班的时候突然发现幼儿园某处发生火灾，而且火势蔓延极快，老师在第一时间就发出了警报，位于幼儿园某处的mengxiang000和Tabris听到了火灾警报声的同时拔腿就跑，不知道两人是否能够逃脱险境？
幼儿园可以看成是一个N*M的图，在图中一共包含以下几种元素：
“.”:表示这是一块空地，是可以随意穿梭的。
“#”：表示这是一块墙，是不可以走到这上边来的，但是可以被火烧毁。
“S”：表示mengxiang000和Tabris所在位子。
“E”：表示幼儿园的出口。
“*”表示火灾发源地（保证输入只有一个火灾发源地）。
已知每秒有火的地方都会向周围八个格子（上下左右、左上、右上、左下、右下）蔓延火势.mengxiang000和Tabris每秒都可以选择周围四个格子（上下左右）进行移动。（假设两人这一秒行动完之后，火势才蔓延开）
根据已知条件，判断两人能否成功逃脱险境,如果可以，输出最短逃离时间，否则输出T_T。
输入描述:
第一行输入一个整数t，表示一共的测试数据组数。 第二行输入两个整数n，m，表示幼儿园的大小。 接下来n行，每行m个字符，表示此格子是什么元素。 t<=200 3<=n<=30 3<=M<=30 保证图中有一个起点，一个出口，一个火灾源处. 为了防止孩子们嬉戏中受伤，墙体是橡胶制作的，可以燃烧的哦。
输出描述:
每组数据输出一行，如果两人能够成功到达出口，那么输出最短逃离时间，否则输出T_T
示例1
输入
复制
3 5 5 *.... ..... ..S#. ...E. ..... 5 5 ...#* ..#S# ...## ....E ..... 5 5 ..... S.... ..*#. ...E. .....
输出
复制
2 T_T T_T
说明
为了防止孩子们嬉戏中受伤，墙体是橡胶制作的，可以燃烧的哦。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int t,n,m,a,b,vis[50][50];
int fx[] = {-1, 1, 0, 0};
int fy[] = {0, 0, -1, 1};
struct node{
int x, y;
int step;
};
void init() {
for (int i = 0; i <50; ++i)
for (int j = 0; j < 50; ++j)
vis[i][j]=0;
}
int bfs(node next, char s[][50]) {
queue<node> q;
q.push(next);
while(!q.empty()) {
next = q.front();
q.pop();
next.step++;
for (int i = 0; i < 4; ++i) {
node p;
p.x = next.x+fx[i];
p.y = next.y+fy[i];
p.step = next.step;
if (p.x >= 0 && p.x < n && p.y >= 0 && p.y < m && s[p.x][p.y] != '#' && vis[p.x][p.y] != 1) {
if (max(abs(p.x - a), abs(p.y - b)) >= p.step && s[p.x][p.y] == 'E')
return p.step;
if (max(abs(p.x - a), abs(p.y - b)) <= p.step)
continue;
q.push(p);
vis[p.x][p.y] = 1;
}
}
}
return -1;
}
int main() {
cin >> t;
char s[50][50];
while(t--) {
init();
node next;
cin >> n >> m;
for (int i = 0; i < n; ++i)
scanf("%s", s[i]);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (s[i][j] == '*') {
a = i; b = j;
}
else if(s[i][j] == 'S') {
next.x = i; next.y = j;
next.step = 0;
vis[i][j] = 1;
}
}
}
int ans = bfs(next, s);
if (ans != -1)
printf("%d\n", ans);
else
printf("T_T\n");
}
return 0;
}链接：https://ac.nowcoder.com/acm/problem/14535
来源：牛客网
题目描述
这是mengxiang000和Tabris来到幼儿园的第三天，Tabris在幼儿园每天都吃的很饱，小小年纪就胖成了W斤，mengxiang000笑话他腿粗，这让Tabris是非常难受，立志想要减肥，就在QQ上更改了他的网名以立誓铭志（不廋到120斤不改名）
他给自己定了一个计划，每天都减T斤，他想知道，他多少天后就能修改QQ网名（小于等于120斤都算是廋到了120斤）。
输入描述:
第一行输入一个整数t，表示一共的测试数据组数。 每组测试数据包含两个数，W,T，表示Tabris现在的体重，以及每天计划减少T斤 t<=100 1<=W<=100000 1<=T<=100000
输出描述:
每组数据输出一行，表示多少天后Tabris就可以更改网名了。
示例1
输入
复制
2 128 7 1450 2
输出
复制
2 665
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n;
int main()
{
cin>>n;
while(n--)
{
int w,t,s=0;
cin>>w>>t;
if(w>120)
s=(w+t-1-120)/t;
cout<<s<<endl;
}
return 0;
}链接：https://ac.nowcoder.com/acm/problem/14531
来源：牛客网
题目描述
tabris有一个习惯，无聊的时候就会数圈圈，无论数字还是字母。
现在tabris更无聊啦，晚上睡不着觉就开始数羊，从a只数到b只。
顺便还数了a到b之间有多少个圈。
但是tabris笨啊，虽然数羊不会数错，但很可能数错圈的个数。
但是tabris很难接受自己笨这个事实，所以想问问你他一共应该数出多少个圈，这样tabris才好判断他到底笨不笨啊。
输入描述:
输入一个T，表示数据组数
每组测试数据包含两个正整数a，b。
T∈[1,1000]
a,b∈[1,1014]
输出描述:
每组数据输出结果，并换行。
示例1
输入
复制
11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 1 100
输出
复制
0 0 0 1 0 1 0 2 1 1 111
备注:
数字的圈的个数请根据样例自行理解。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <ctime>
#include <cctype>
#include <bitset>
#include <utility>
#include <sstream>
#include <complex>
#include <iomanip>
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
ll a[10],jg,t,n,m;
void aa(ll x,ll y)
{
for(ll i=1;i<=x;i*=10)
{
ll cur=(x/i)%10,pre=x/(i*10),after=x-x/i*i;
for(ll j=0;j<=9;j++)
{
if(cur>j)
a[j]+=(pre+1)*i*y;
else if(cur==j)
a[j]+=(pre*i+after+1)*y;
else
a[j]+=(pre*i)*y;
}
a[0]-=i*y;
}
}
int main()
{
cin>>t;
while(t--)
{
jg=0;
cin>>n>>m;
memset(a,0,sizeof(a));
aa(n-1,-1);
aa(m,1);
for(int i=0;i<=9;i++)
{
if(i==0||i==4||i==6||i==9)
jg+=a[i];
else if(i==8)
jg+=2*a[i];
}
cout<<jg<<endl;
}
}