Day10

Day10

今天是 又一次 积分赛
我心态很好,真的很好,,,,真的很好。。。。

OJ

再战斐波那契

Problem Description
Description:
小z 学会了斐波那契和 gcd 后,老师又给他出了个难题,求第N个和第M个斐波那契数的最大公约数,这可难倒了小z ,不过在小z 的再三请求下,老师又告诉他了个条件,gcd(N,M)∈[1,90]。
可是,笨拙的小z 还是不会,于是请求你帮他解答这个问题。
已知:

输入格式
输入包括 T 组,T∈[1,10].
接下来 T 行,每行两个整数 N,M, 表示斐波那契的第 N 项和第 M 项,(N,M∈[1,1e18]).
输出格式
输出包含 T 行,每行输出一个整数.
样例
input
3
1 2
2 3
3 4
output
1
1
1

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//gcd(f(m),f(n)) = f(gcd(m,n))这个是规律
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1000];
int main()
{
int n;
scanf("%d",&n);
ll x, y;
a[2] = 1, a[1] = 1;
for(int i = 3; i <= 100; i ++) a[i] = a[i - 1] + a[i - 2];

for(int i = 0; i < n; i ++)
{
scanf("%lld %lld",&x, &y);
printf("%lld\n",a[__gcd(x, y)]);
}
return 0;
}

恐怖的怪物

Description:
一天早上,Dicer一觉醒来,发现自己来到了MineCraft的世界里面,身为MineCraft游戏爱好者的他欣喜不已,于是他在地下挖了一片长方体的空间作为秘密基地,可是他发现光照亮度小于等于7时,会有恐怖的怪物出现,并且他通过查阅资料发现光源方块产生光照每一米(方格)衰减1光照等级。
此规律在坐标轴的3个方向上(东西、南北、上下)均成立。换句话来说,对角线方向的光照衰减依照“曼哈顿距离”(两个点在坐标系上的绝对轴距总和)计算。这意味着,假如地上插着一支火把(光照等级14),则在水平面上与火把相邻的4个方向的方格上光照等级均为13,而在水平面上与火把对角的4个方格上光照等级均为12(譬如,西北方格的光照等级为14-向西1级-向北1级)。
上述这种衰减特性会在光源周围产生菱形的照明。该效果会在光源周围的光源扩散呈钻石状。如果被不透明方块阻挡,光照也可以沿着复杂而弯曲的路径扩散。
如下图所示,红色为光源(亮度等级为14),黑色为秘密物品,其余各个位置光照强度如图所示。

秘密基地为N∗M的空间,不考虑高度,初始地面光照强度为0。为了不生成恐怖的怪物,Dicer布置了一些光源,但他不知道是否仍会生成怪物,现在请你帮助Dicer判断。
注:光源及秘密物品均为不透明方块,且其上方均不会生成怪物。
输入格式
第一行是一个T。(1≤T≤100)
接下来有T组数据,每一组第一行是N,M,(1≤N,M≤1000),接下来有N行,每行M个字符,代表秘密基地地面放置的方块,0代表空气,#代表秘密物品,Y代表萤石(光照等级为15),H代表火把(光照等级为14),F代表附魔台(光照等级为12),R代表激活的红石火把(光照等级为7)。
输出格式
输出包含T行,每行如果仍会生成怪物,输出”Yes”,否则输出”No”。
样例
input
2
2 3
0Y0
00#
3 4
R00#
00R0
0R00
output
No
Yes
input
2
1 5
0Y0R0
2 4
Y#0R
0000
output
Yes
No
input
1
5 4
Y0F0
0000
0000
0000
0000
output
No

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1000+10;

int t,n,m;
char mp[maxn][maxn];
int vis[maxn][maxn];
int d[4][2]={1,0,-1,0,0,1,0,-1};
queue<pii>H,F;
queue<pii>que;
void init(){
while(!que.empty()) que.pop();
while(!H.empty()) H.pop();
while(!F.empty()) F.pop();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
vis[i][j]=0;
}
bool BFS(){
while(!que.empty()){
int x=que.front().first;
int y=que.front().second;
que.pop();
if(vis[x][y]==8) break;
for(int i=0;i<4;i++){
int xx=x+d[i][0];
int yy=y+d[i][1];
if(xx<=0 || xx>n || yy<=0 || yy>m || vis[xx][yy] || mp[xx][yy]!='0') continue;
vis[xx][yy]=vis[x][y]-1;
que.push(pii(xx,yy));
while(vis[xx][yy]==14 && (!H.empty())){
que.push(H.front());
H.pop();
}
while(vis[xx][yy]==12 && (!F.empty())){
que.push(F.front());
F.pop();
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(vis[i][j]<=7 && mp[i][j]=='0') return false;
return true;
}
int main()
{

scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
init();
for(int i=1;i<=n;i++){
scanf("%s",mp[i]+1);
for(int j=1;j<=m;j++){
if(mp[i][j]=='Y') que.push(pii(i,j)),vis[i][j]=15 ;//15
if(mp[i][j]=='H') H.push(pii(i,j)),vis[i][j]=14;//14
if(mp[i][j]=='F') F.push(pii(i,j)),vis[i][j]=12;//12
}
}
if(BFS()) printf("No\n");
else printf("Yes\n");
}
return 0;
}

连连看

Description:
众所周知,《连连看》是一个老少皆宜的游戏。
《连连看》是由黄兴武创作的一款PC端益智类游戏,只要将相同的两张牌用三根以内的线段连在一起就可以消除,规则简单容易上手。
现在呢,Boctorio学长突然想玩连连看了,但不是单纯的玩游戏,他想自己出一局连连看。
由于Boctorio学长是一个蒟蒻,他不知道自己出的连连看是否符合能够通过多次操作将其全部消除,所以想要你帮他检查一下他出的连连看是否符合规则。
输入格式
第一行输入个T,表示T组数据(1≤t≤100)
每组数据第一行两个数 n,m ,表示连连看棋盘的长和宽(1≤n,m≤100)
接下来 n 行,每行输入 m 个正整数aij,表示 m 个棋子 (1≤aij≤n∗m)。
每种棋子只会出现一对,因此数据保证只有一种有效结果。
输出格式
每组数据输出一行。
如果棋盘符合规定,输出”Yes”,否则,输出”No”(不包括引号)。
样例
input
3
2 2
1 2
2 1
3 4
1 6 2 3
4 5 3 1
4 2 6 5
4 4
1 2 3 6
8 4 7 8
5 6 5 7
1 2 3 4
output
No
No
Yes

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mp[200][200];
int n,m;
int sx,sy;
int dir[4][2]={{1,0},{0,1},{0,-1},{-1,0}};//分别对应下,右,左,上
int check(int x,int y){
if(x<0 || x>n+1 || y<0 || y>m+1)
return 1;
return 0;
}

bool judge(int x,int y,int step,int pos){//pos表示上一步方向
if(step>3) return 0;//如果超过了三步,不符合规则
if(mp[x][y]==mp[sx][sy] && pos!=-1){//如果两个字符相等并且不是同一个(由于下面有方向限制,所以两个值不可能相等)
mp[x][y]=0;//删去配对字符
mp[sx][sy]=0;
return 1;
}
if(mp[x][y]!=0 && pos!=-1) return 0;//如果不相等并且不是通路,不符合规则
int i,x1,y1;
for(i=0;i<4;i++){
if(i+pos==3) continue;//不能有正相反的方向 (0.下 3.上) (1.右 2.左)
x1=x+dir[i][0];
y1=y+dir[i][1];
if(check(x1,y1)) continue;//检查是否越界
if(judge(x1,y1,step+(pos==i?0:1),i)){//找到一个就返回
return 1;
}
}
return 0;
}
int main()
{
int t,times,sum;
int i,j;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
memset(mp,0,sizeof(mp));
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
scanf("%d",&mp[i][j]);
}
}
sum=0;
times=0;//times表示查找的次数,大于等于n*m相当于查找一遍还没有找到
i=j=1;
while(sum<n*m && times<n*m){
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
times++;
sx=i,sy=j;
if(mp[i][j]!=0 && judge(i,j,0,-1)){
sum+=2;
times=0;
}
}
}
}
if(sum==n*m){
printf("Yes\n");
}
else{
printf("No\n");
}
}
return 0;
}

Points in rectangle

Description:
在二维平面中有一个矩形,它的四个坐标点分别为(0,a),(a,0),(n,n−a),(n−a,n)。你现在有m个点,现在你想知道有多少个点是在这个矩形内的(边上的也算)。
输入格式
第一行输入n,a(1≤a\<n≤1e3)。
第二行一个正整数m(1≤m≤1e3),代表你拥有的点的个数,接下来m行,每行一个点的坐标xi,yi(1≤xi,yi≤1e3)。
输出格式
第一行输出在矩形内的点的个数,然后输出在矩形内点的坐标,横坐标大的优先,如果横坐标相同,则纵坐标大的优先。如果没有,输出−1。
样例
input
6 1
5
1 2
1 3
2 3
3 4
4 5
output
4
4 5
3 4
2 3
1 2

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
int n, a;
int m;
struct node{
int xo, yo;
}biao[10001];
node biao1[10001];
int cmp(node a, node b)
{
if(a.xo == b.xo) return a.yo > b.yo;
return a.xo > b.xo;
}
int cnt;
bool solve(node point)
{

return point.yo >= -point.xo + a && point.yo >= point.xo - a && point.yo <= point.xo + a && point.yo <= -point.xo + 2 * n - a;
}
int main()
{
cin >> n >> a >> m;
cnt = 0;
for(int i = 0; i < m; i ++)
{
cin >> biao[i].xo >> biao[i].yo;
if(solve(biao[i]))
{
cnt ++;
biao1[i].xo = biao[i].xo;
biao1[i].yo = biao[i].yo;
}
}
sort(biao1, biao1 + m, cmp);
if(cnt == 0) puts("-1");
else
{
cout << cnt << endl;
for(int i = 0; i < cnt; i ++)
{
cout << biao1[i].xo << " " << biao1[i].yo << endl;
}
}
return 0;
}

code2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>

using namespace std;
const int N = 2e3+100;
struct point{
long long x,y;
bool friend operator<(point a,point b){
if(a.x==b.x) return a.y>b.y;
return a.x>b.x;
}
}p[N];
long long n,a;
bool check(point P){
return -P.x+a<=P.y&&-P.x+2*n-a>=P.y&&P.x-a<=P.y&&P.x+a>=P.y;
}
int main(){
//freopen("17.in","r",stdin);
//freopen("17.out","w",stdout);
vector<point> re;
cin>>n>>a;
int m;
cin>>m;
for(int i=1;i<=m;i++){
cin>>p[i].x>>p[i].y;
if(check(p[i])) re.push_back(p[i]);
}
sort(re.begin(),re.end());
if(re.empty()){
cout<<-1<<endl;
}
else{
cout<<re.size()<<endl;
for(auto v:re) cout<<v.x<<' '<<v.y<<endl;
}
return 0;
}

Numbers of interval

Description:

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int maxx = 1e6;
typedef long long ll;
ll a[maxx];
ll b[maxx];
int main()
{
int n, k;
cin >> n >> k;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
b[i] = a[i] + b[i - 1];
}
ll ans = 0;
for(int i = 1; i <= n; i ++)
{
int pos = lower_bound(b + 1, b + n + 1, k + b[i - 1]) - b;
ans += (n - pos + 1);
}
cout << ans << endl;
return 0;
}

/*
这题很巧妙,利用了前缀和与二分查找中的lower_bound
首先是前缀和,不断相加前面每一个数的值,(比普通的定义一个变量相加更好用)存值,方便后便用到
找到第一个大于等于要求数的值,然后后边的数肯定都大,只要计数就行了
*/

剪纸

Description:
中国剪纸是一种用剪刀或刻刀在纸上剪刻花纹,用于装点生活或配合其他民俗活动的民间艺术。在中国,剪纸具有广泛的群众基础,交融于各族人民的社会生活,是各种民俗活动的重要组成部分。其传承赓续的视觉形象和造型格式,蕴涵了丰富的文化历史信息,表达了广大民众的社会认以、道德观念、实践经验、生活理想和审美情趣,具有认知、教化、表意、抒情、娱乐、交往等多重社会价值。
2006年5月20日,剪纸艺术遗产经国务院批准列入第一批国家级非物质文化遗产名录 。2009年9月28日至10月2日举行的联合国教科文组织保护非物质文化遗产政府间委员会第四次会议上,中国申报的中国剪纸项目入选“人类非物质文化遗产代表作名录”。
剪窗花最基本的操作为将剪纸进行多次对折,然后对对折之后的纸进行裁剪,展开后就是一个精美的艺术品。现在我们对问题进行化简,我们利用如下方法将一张形状矩形的纸按照对阵轴进行对折:

假设剪后的形状为一个三角形,则展开效果为:

现在给你一个对折两次且剪切后的图形,请你给出展开的图形形状。
输入格式
多组输入,处理到文件结束。
每组输入第一行两个数字n,m(1≤n,m≤100)。
接下来n行,每行m个字符,表示对折且剪切后的图形。
保证输入字符只包含 ‘.’ 和 ‘’ 。
输出格式
输出展开后的图形。
样例
input
3 3
**.
..

output
……
....
.**
.
.**.
..
..
……

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//F
#include<bits/stdc++.h>
using namespace std;
const int maxx = 1000+10;
char mmp[maxx][maxx];
int main()
{
int n, m;

while(~scanf("%d %d",&n, &m))
{
memset(mmp, '.', sizeof mmp);
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
cin >> mmp[i][j];
if(mmp[i][j] == '*')
{
mmp[i + n][j + m] = '*';
mmp[i][j] = '.';
}
// cout << a[i][j];
}
// puts("");
//
//
//
}
for(int i = 0; i < n * 2; i ++)
{
for(int j = 0; j < m * 2; j ++)
{
if(mmp[i][j] != '*') mmp[i][j] = '.';
if(mmp[i][j] == '*')
{
mmp[2 * n - i - 1][j] = '*';
mmp[i][2 * m - j - 1] = '*';
mmp[2 * n - i - 1][2 * m - j - 1] = '*';
}
}
}
for(int i = 0; i < 2 * n; i ++)
{
for(int j = 0; j < 2 * m; j ++)
{
cout << mmp[i][j];
}
puts("");
}
}

return 0;
}

Fake hpuoj predictor

Description:
总所周知,HPU(Harmonious and Peaceful University) Online Judge具有一个强大的的rating(积分)系统,它采用的是国际上权威的ELO等级分制度(ELO Rating System),LOL,守望先锋,codeforces,topcoder等知名游戏的排行均是采用此制度。
具体算法为:

其中R(A)和R(B)为选手A和B初始的rating,那么E(A)和E(B)即为这两者进行对战后A和B各自获胜的期望。
本场比赛的积分公式即为

RA代表上轮比赛结束后的积分。
K为积分系数,对于不同等级的选手的K是不同的。
SA代表比赛实际总得分,对于每局比赛来说,每赢一个人就会加1分,输了不扣分。
EAi代表A与第i个选手比赛获胜的期望。
对于HPU Online Judge,用户等级表为:

codancer有一个成为Grand Master的梦想,已知他的初始rating为0,他总共参加了m场比赛,对于每场比赛有一个榜单,对于codancer来说,排在他前面的人都打败了他,排在他后面的人都输给了他,因此你可以通过和每个参加比赛的选手比较计算出总得分SA和总期望∑EAi。
那么最终codancer打完本场比赛后的rating为

现在他打完了这m场比赛后他迫切的想知道自己的rating变为了多少(因为管理员太懒了,已经鸽了m场的rating计算了),现在他想让你帮他写一个预测器来预测一下。
输入格式
单组输入,第一行输入一个m(1≤m≤100),代表codancer参加的比赛的数量。
接下来对于每场比赛:
第一行输入一个整数n代表有n(1≤n≤100)个人参加的比赛。
接下来n行每行输入一个字符串和数字,代表参赛选手的用户名和他的rating,codancer即为他自己的用户名(用户名长度不超过20),假如输入的名字为codancer,则不用输入数字(其他参赛选手的rating是不会更新的,因为管理员太懒了)。
输出格式
输出codancer最终的rating,向上取整。
样例
input
3
5
tourist 2000
capryang 1900
boctorio 1800
dicer 1800
codancer
2
codancer
rookie 200
2
wzy 1500
codancer
output
12

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
int n,m,a;
struct node{
char name[30];
double rating;
}p[maxn];
double cal(double rating){
if(rating<1350) return 15.0;
else if(rating<1500) return 20.0;
else if(rating<1600) return 25.0;
else if(rating<1700) return 30.0;
else if(rating<1800) return 35.0;
else return 50.0;
}
double Rating(double rating){
double k=cal(rating);
double ea=0,sa=0;
for(int i=0;i<n;i++){
if(strcmp(p[i].name,"codancer")==0) continue;
ea+=1.0/(1.0+pow(10,(p[i].rating-rating)/400.0));
}
for(int i=0;i<n;i++){
if(strcmp(p[i].name,"codancer")==0){
sa=n-1-i;
break;
}
}
double now_rating=rating+k*(sa-ea);
// return now_rating;
return ceil(now_rating);
}
int main()
{
int m;
scanf("%d",&m);
double codancerNB_rating=0.0;
while(m--){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",p[i].name);
if(strcmp(p[i].name,"codancer")==0){
p[i].rating=codancerNB_rating;
continue;
}
scanf("%lf",&p[i].rating);
}
codancerNB_rating=Rating(codancerNB_rating);
}
printf("%.0lf\n",ceil(codancerNB_rating));
return 0;
}

花花与三猫Catlive

Description:
“大佬”中分和“呆B”李白正在玩一个游戏,游戏规则是这样的:
游戏刚开始的时候,中分和李白相距L步,相对而望。
老父亲和老母亲手中各有一个M个面的均匀骰子。(也就是说可以随机生成[1,m]内的任意一个数字,且概率均等)
在每个回合开始的时候,老父亲和老母亲都会掷一下手中的骰子。
当老父亲的骰子掷到1的时候,中分可以向李白走一步。
当老母亲的骰子掷到m的时候,李白可以向中分走一步。
当中分和李白相遇的时候,游戏结束。
可是老父亲和老母亲刚刚拍完新节目,他们太累了,不想做这个游戏,但是他们还很想知道,这个游戏平均需要多少次才能结束。聪明的你,能告诉他们吗?
结果是一个实数s,可以证明s能被表示成一个分数 qp,请输出q⋅p−1,其中q−1表示q在模109+7意义下的逆元。
输入格式
第一行是一个正整数 T(1≤T≤1000),表示测试样例的组数。
接下来T行,每行两个正整数L,M(1≤L,M≤1000),含义如题面描述。
输出格式
输出包括T行,每行一个答案。
样例
input
2
1 2
2 1
output
1
1

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main()
{
int T;
scanf("%d", &T);
int L, M;
while(T--)
{
scanf("%d %d", &L, &M);
printf("%lld\n", 1LL * L * M * 500000004 % MOD);
}
return 0;
}

code2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//为啥多了几行,学长的意思是打cf的,防止被hack,哈哈
#include<bits/stdc++.h>

const int MOD = 1e9 + 7;
int qpow(int a, int b, int mod){
int res = 1;
while(b){
if(b&1) res = 1LL * res * a % mod;
a = 1LL * a * a % mod;
b >>= 1;
}
return res;
}

int inv(int p, int mod){
return qpow(p, mod - 2, mod);
}

int main(){
int T;
scanf("%d", &T);
int L, M;
while(T--){
scanf("%d %d", &L, &M);
printf("%lld\n", 1LL * L * M * 500000004 % MOD);
}
}

Same String

Description:
有两个只由小写字母组成的长度为n的字符串s1,s2和m组字母对应关系,每一组关系由两个字母c1和c2组成,代表c1可以直接变成c2,你需要判断s1是否可以通过这m组关系转换为s2。
输入格式
第一行输入一个n(1≤n≤100),代表字符串的长度。
第二行和第三行输入两个字符串s1,s2。
第四行输入一个m(1≤m≤325),代表有m组关系。
接下来m行,第i行两个字符ui,vi,代表ui可以直接变为vi。
输出格式
如果s1可以通过这些m组关系转化变为s2,输出”YES”,否则输出”NO”。
样例
input
6
aabbcc
cdbcad
4
a c
c a
a d
b c
output
YES

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6+100;
typedef long long ll;
bool f[26][26];
int main(){
int n,m;
string s1,s2;
cin>>n>>s1>>s2;
cin>>m;
char u,v;
for(int i=1;i<=m;i++){
cin>>u>>v;
f[u-'a'][v-'a']=1;
}
for(int j=0;j<26;j++){
for(int i=0;i<26;i++){
for(int k=0;k<26;k++){
f[i][k]|=(f[i][j]&f[j][k]);
}
}
}
bool check=0;
for(int i=0;i<n;i++){
if(s1[i]!=s2[i]){
if(f[s1[i]-'a'][s2[i]-'a']==0){
check=1;break;
}
}
}
if(check){
puts("NO");
}
else puts("YES");
// }
return 0;
}

---------------- The End ----------------
0%