今天把之前vj上没写的题目写了，但有几道题不能提交了。还写了上周测试的补题。嘿嘿

CF18B Platforms

题目描述

In one one-dimensional world there are nn platforms. Platform with index kk (platforms are numbered from 1) is a segment with coordinates [(k-1)m,(k-1)m+l][(k−1)m,(k−1)m+l] , and l<ml<m . Grasshopper Bob starts to jump along the platforms from point 00 , with each jump he moves exactly dd units right. Find out the coordinate of the point, where Bob will fall down. The grasshopper falls down, if he finds himself not on the platform, but if he finds himself on the edge of the platform, he doesn't fall down.

输入格式

The first input line contains 4 integer numbers nn , dd , mm , ll ( 1<=n,d,m,l<=10^{6},l<m1<=n,d,m,l<=106,l<m ) — respectively: amount of platforms, length of the grasshopper Bob's jump, and numbers mm and ll needed to find coordinates of the kk -th platform: [(k-1)m,(k-1)m+l][(k−1)m,(k−1)m+l] .

输出格式

Output the coordinates of the point, where the grosshopper will fall down. Don't forget that if Bob finds himself on the platform edge, he doesn't fall down.

题意翻译

题目描述：在一坐标轴上给出n块板子，每个板子所占的空间为[(k-1)m,(k-1)m+l]（l<m）,一个青蛙从原点0起跳，每次跳d距离远，问最后青蛙会落在哪里（没落在板子上就结束跳跃） 输入：一行四个整数n，d，m，l 输出：一个整数，即青蛙最后的落点 1<=n,d,m,l<=10^6 l<m

Translated by 稀神探女

输入输出样例

输入 #1复制

2 2 5 3

输出 #1复制

4

输入 #2复制

5 4 11 8

输出 #2复制

20

思路

吐槽一下题目这个k都没说是什么，导致昨天看题根本没看懂

1、“在一坐标轴上给出n块板子，每个板子所占的空间为[(k-1)m,(k-1)m+l]（l<m）”这句话的意思是

2、青蛙🐸从原点开始跳，每次跳d个单位长度，于是结果分两种情况

①在板的末尾如果再跳则跳到空隙里，那么输出在板尾的位置

②否则就一直跳，输出最后的位置

3、注意要用long long

代码实现

#include<bits/stdc++.h>
using namespace std; 
int main()
{long long n,d,m,l,ans=0;  cin>>n>>d>>m>>l; for(long long i=1;i<=n;i++){if(ans<((i-1)*m)){break;}while(ans<=(i-1)*m+l){ans=(((i-1)*m+l)/d)*d+d;}}cout<<ans;return 0;
}

CF30B Codeforces World Finals

题目描述

The king Copa often has been reported about the Codeforces site, which is rapidly getting more and more popular among the brightest minds of the humanity, who are using it for training and competing. Recently Copa understood that to conquer the world he needs to organize the world Codeforces tournament. He hopes that after it the brightest minds will become his subordinates, and the toughest part of conquering the world will be completed.

The final round of the Codeforces World Finals 20YY is scheduled for DDDD . MMMM . YYYY , where DDDD is the day of the round, MMMM is the month and YYYY are the last two digits of the year. Bob is lucky to be the first finalist form Berland. But there is one problem: according to the rules of the competition, all participants must be at least 18 years old at the moment of the finals. Bob was born on BDBD . BMBM . BYBY . This date is recorded in his passport, the copy of which he has already mailed to the organizers. But Bob learned that in different countries the way, in which the dates are written, differs. For example, in the US the month is written first, then the day and finally the year. Bob wonders if it is possible to rearrange the numbers in his date of birth so that he will be at least 18 years old on the day DDDD . MMMM . YYYY . He can always tell that in his motherland dates are written differently. Help him.

According to another strange rule, eligible participant must be born in the same century as the date of the finals. If the day of the finals is participant's 18-th birthday, he is allowed to participate.

As we are considering only the years from 20012001 to 20992099 for the year of the finals, use the following rule: the year is leap if it's number is divisible by four.

输入格式

The first line contains the date DDDD . MMMM . YYYY , the second line contains the date BDBD . BMBM . BYBY . It is guaranteed that both dates are correct, and YYYY and BYBY are always in [01;99][01;99] .

It could be that by passport Bob was born after the finals. In this case, he can still change the order of numbers in date.

输出格式

If it is possible to rearrange the numbers in the date of birth so that Bob will be at least 18 years old on the DDDD . MMMM . YYYY , output YES. In the other case, output NO.

Each number contains exactly two digits and stands for day, month or year in a date. Note that it is permitted to rearrange only numbers, not digits.

题意翻译

题意描述

关于 Codeforces 的网站 king Copa 经常被报道，使得它在要使用网站进行训练和比赛的人之间迅速流行开来。最近， Copa 明白，要征服世界，他需要组织世界 Codeforces 锦标赛。他希望在这次比赛之后之后，最聪明的人将成为被挑选出来成为他的下属，然后征服世界最艰难的部分将会完成。

Codeforces 世界总决赛的最后一轮定于 YYYY 年 MMMM 月 DDDD 日举行，其中 DDDD 是当天的日期， MMMM 是当月的月份， YYYY 是当年的年份的最后两位。Bob 很幸运地能成为来自 Berland 的一名决赛选手。但有一个问题：根据比赛规则，所有参赛者在决赛时必须年满 1818 岁。 Bob 出生于 BYBY 年， BMBM 月，BDBD 日。这个日期记录在他的护照上，他的护照复印件已经寄给了组织者。但是 Bob 了解到，在不同的国家，日期的书写方式是不同的。例如，在美国，先写月份，然后写日期，最后写年份。

鲍勃想知道是否有可能重新排列他出生日期的数字，以便他在 YYYY 年， MMMM 月， DDDD 日那天至少 1818 岁。他看出，在他的祖国，日期写的顺序不一样。请帮帮他。 根据另一个奇怪的规则，合格的参赛者必须与决赛日期出生在同一个世纪。如果决赛当天刚好是参赛者的 1818 岁生日，则他可以参加。

因为我们只考虑从 20012001 年到 20992099 年的决赛年份，所以使用以下规则：如果年份的数字可以被 44 整除，那么年份就是闰年。

输入格式：

第一行包括三个数字 DD,MM,YYDD,MM,YY ，第二行包括三个数字 BD,BM,BYBD,BM,BY ，数据保证两个日期的正确性，并且 BYBY 和 YYYY 保证在 [ 01 ，99 ][01，99] 中。

输出格式：

如果可能通过重新排列出生日期的顺序，让 Bob 在比赛当天至少 1818 岁，则输出 YES 。如果不能，则输出 NO。

输入输出样例

输入 #1复制

01.01.98
01.01.80

输出 #1复制

YES

输入 #2复制

20.10.20
10.02.30

输出 #2复制

NO

输入 #3复制

28.02.74
28.02.64

输出 #3复制

NO

思路

列举所有情况

代码实现

#include<bits/stdc++.h>
using namespace std;
int md[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int d,m,y,dd,mm,yy;
int fun(int d1,int m1,int y1)
{if(m1<1||m1>12||d1<1||d1>md[m1]+(m1==2&&y1%4==0)) //不合法情况 return 0; return (y1+18<y||y1+18==y&&m1<m||y1+18==y&&m1==m&&d1<=d);//合法情况 
}
int main()
{int d1,m1,y1;scanf("%d.%d.%d%d.%d.%d",&d,&m,&y,&dd,&mm,&yy);if(fun(dd,mm,yy)||fun(dd,yy,mm)||fun(mm,dd,yy)||fun(mm,yy,dd)||fun(yy,dd,mm)||fun(yy,mm,dd))//列举cout<<"YES"<<endl;elsecout<<"NO"<<endl;return 0;
}

B-B

定义一个二维数组：

int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output

左上角到右下角的最短路径，格式如样例所示。

Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

思路

1、广搜

2、将起点入队

3、队首结点可到达的点入队

4、如果没有可到达的点，将队首结点出队

5、重复该步骤知道到达目标位置或队列为空

代码实现

#include<bits/stdc++.h>
using namespace std;
int a[100][100],v[100][100];//存图，记录
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct p{int x,y,cnt;int stepx[100],stepy[100];
}start;
queue<p> q;//申请队列 
void bfs(int x , int y,int step)
{while(!q.empty()){p s=q.front();q.pop();if(s.x ==4&&s.y ==4){printf("(0, 0)\n");for(int i=0;i<s.cnt;i++)printf("(%d, %d)\n",s.stepx[i],s.stepy[i]);return;}for(int k=0;k<4;k++){p temp=s;temp.x =s.x +dir[k][0];temp.y =s.y +dir[k][1];if(temp.x<0||temp.x>5||temp.y<0||temp.y>5||a[temp.x][temp.y]==1||v[temp.x][temp.y]==1)continue;v[temp.x][temp.y]=1;temp.stepx[temp.cnt ]=temp.x;temp.stepy[temp.cnt++ ]=temp.y;q.push(temp);}}
}
int main()
{for(int i=0;i<5;i++)for(int j=0;j<5;j++){scanf("%d",&a[i][j]);}start.x =0;start.y =0;q.push(start);//将起点入队bfs(1,1,0); return 0;} 

C-C

You are given a string consisting of parentheses ( ) and [ ]. A string of this type is said to be correct:

• if it is the empty string
• if A and B are correct, AB is correct,
• if A is correct, (A) and [A] is correct.

Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.

Input

The first line contains the number of test cases n. Each of the next n lines contains the string of parentheses ( ) and [ ].

Output

For each test case print in a separate line "Yes" if the expression is correct or "No" otherwise.

Example 1

Input example #1 content_copy

3
([])
(([()])))
([()[]()])()

Output example #1 content_copy

Yes
No
Yes

Example 2

Input example #10 content_copy

22
((()())))
([)]((([[[]]])])
([])
(([()])))
([()[]()])()
[(])
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
(])
[)]
[)))]
[[)]
([])
(([()])))
([()[]()])()
([)]
(
()(
[()

Output example #10 content_copy

No
Yes
No
No
Yes
No
Yes
No
Yes
No
Yes
No
No
No
No
Yes
No
Yes
No
No
No
No

思路

若是左括号就入栈，如果是右括号就出栈首元素与其配对，配对成功则继续访问下一个字符，否则退出。若全部配对成功则输出yes，反之输出no

代码实现

#include<bits/stdc++.h>
using namespace std;bool fun(char c1,char c2)
{if(c1=='('&&c2==')')return 1;if(c1=='['&&c2==']')return 1;return 0;
}
int main()
{int T;char str[150];cin>>T;getchar();while(T--){stack<char> s;gets(str);int leap=1,flag=0,cntl=0,cntr=0;int len = strlen(str);//如果为空串，返回Yesif(len==0){cout<<"Yes"<<endl;continue;}//如果向左的括号与向右的括号数量不一致，返回Nofor(int i=0;i<len;++i){if(str[i]=='('||str[i]=='[')    cntl++;else cntr++;if(cntr>cntl) {flag=1;break;} //判断类似：))((}if(flag==1||cntl!=cntr){cout<<"No"<<endl;continue;}//将向右的括号入栈，与向左的比较for(int i=0;i<len;++i){if(str[i]=='('||str[i]=='['){s.push(str[i]);}else if(!s.empty()){if(fun(s.top(),str[i])){s.pop();continue;}else{leap=0;break;}}}if(leap)  cout<<"Yes"<<endl;else      cout<<"No"<<endl;}return 0;
}

F-F

冰冰子最近新学习了队列和栈两种重要的数据结构，他知道它们具有push 和pop操作。

而冰冰子现在想同时研究栈和队列，于是，他开始了一个实验。

现在，假设队列和栈都是空的。给定一系列push k和pop操作之后，冰冰子想知道队列和栈中分别存的数字。若队列或栈已经空了，仍然接收到pop操作，则输出error。

Input

第一行为m，表示有m组测试输入，m<100。
每组第一行为n，表示下列有n行push k或pop操作。（n<150）
接下来n行，每行是push k或者pop，其中k是一个整数。
（输入保证同时在队列或栈中的数不会超过100个）

Output

对每组测试数据输出两行，第一行是队列情况，若在队列空时收到pop操作，则输出error。其余情况将队列按照对头至队尾顺序输出队列中所有元素，中间用空格隔开。第二行是栈的情况，若在栈空时收到pop操作，则输出error。其余情况下按照栈底至栈顶的顺序输出栈中所有元素。

Sample Input

2
4
push 1
push 3
pop
push 5
1
pop

Sample Output

3 5
1 5
error
error

思路

1、如果队列或栈为空而要进行pop操作则输出error

2、不为空pop操作则队首出队，栈尾出栈

3、push操作则将元素进队进栈

4、将操作之后的队和栈剩余元素分别存在数组b，c中

5、分别遍历输出

代码实现

#include<bits/stdc++.h>
using namespace std;
int main()
{int b[100],c[100] ,top,top1,beg, tmp;int  m, n, a;char s[5];cin>>m;while(m--){tmp=0;beg=0;top=-1;top1=-1;cin>>n;while(n--){cin>>s;if(s[1]=='o'){if(top==-1||top1==-1){tmp=1;}top--;beg++;}else{cin>>a;b[++top]=a;c[++top1]=a;}}if(tmp){cout<<"error"<<endl;cout<<"error"<<endl;continue;}if(top!=-1){for(int i=beg; i<=top1; i++)cout<<c[i]<<" ";cout<<endl;for(int i=0; i<=top; i++)cout<<b[i]<<" ";cout<<endl;}}return 0;
}