Part2.1模拟-EW帮帮网

模拟，顾名思义就是题目要求你做什么你就做什么，这样的题目很考验选手的代码组织能力。

这里不仅仅有非常基础的模拟，也有一些非常复杂的题目。

[NOIP2011 提高组] 铺地毯

题目描述

为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有 $n$ 张地毯，编号从 $1$ 到 $n$ 。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。

地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

输入格式

输入共 $n + 2$ 行。

第一行，一个整数 $n$ ，表示总共有 $n$ 张地毯。

接下来的 $n$ 行中，第 $i + 1$ 行表示编号 $i$ 的地毯的信息，包含四个整数 $a, b, g, k$ ，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标 $(a, b)$ 以及地毯在 $x$ 轴和 $y$ 轴方向的长度。

第 $n + 2$ 行包含两个整数 $x$ 和 $y$ ，表示所求的地面的点的坐标 $(x, y)$ 。

输出格式

输出共 $1$ 行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出 -1。

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

-1

提示

【样例解释 1】

如下图， $1$ 号地毯用实线表示， $2$ 号地毯用虚线表示， $3$ 号用双实线表示，覆盖点 $(2, 2)$ 的最上面一张地毯是 $3$ 号地毯。

【数据范围】

对于 $30\%$ 的数据，有 $\le 2$
对于 $50\%$ 的数据， $\le a, b, g, k \le 100$ 。
对于 $100\%$ 的数据，有 $\le n \le 10^4$ , $\le a, b, g, k \le {10}^5$ 。

noip2011 提高组 day1 第 $1$ 题。

代码实现

#include<iostream>
using namespace std;
#define MAX_N 10000
int a[MAX_N+5];
int b[MAX_N+5];
int g[MAX_N+5];
int k[MAX_N+5];
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	scanf("%d%d%d%d",&a[i],&b[i],&g[i],&k[i]);
	int x,y;
	cin>>x>>y;
	for(int i=n-1;i>=0;i--)
	if(a[i]<=x&&a[i]+g[i]-1>=x&&b[i]<=y&&b[i]+k[i]-1>=y)
	{
		cout<<i+1;
		return 0;
	}
	cout<<-1;
	return 0;
}

[NOIP2009 普及组] 多项式输出

题目描述

一元 $n$ 次多项式可用如下的表达式表示：

$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,a_n\ne 0$

其中， $a_ix^i$ 称为 $i$ 次项， $a_i$ 称为 $i$ 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：

多项式中自变量为 $x$ ，从左到右按照次数递减顺序给出多项式。
多项式中只包含系数不为 $0$ 的项。
如果多项式 $n$ 次项系数为正，则多项式开头不出 + 号，如果多项式 $n$ 次项系数为负，则多项式以 - 号开头。
对于不是最高次的项，以 + 号或者 - 号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于 $0$ 次的项，其系数的绝对值为 $1$ ，则无需输出 $1$ ）。如果 $x$ 的指数大于 $1$ ，则接下来紧跟的指数部分的形式为“ $x^b$ ”，其中 $b$ 为 $x$ 的指数；如果 $x$ 的指数为 $1$ ，则接下来紧跟的指数部分形式为 $x$ ；如果 $x$ 的指数为 $0$ ，则仅需输出系数即可。
多项式中，多项式的开头、结尾不含多余的空格。

输入格式

输入共有 $2$ 行

第一行 $1$ 个整数， $n$ ，表示一元多项式的次数。

第二行有 $n + 1$ 个整数，其中第 $i$ 个整数表示第 $n - i + 1$ 次项的系数，每两个整数之间用空格隔开。

输出格式

输出共 $1$ 行，按题目所述格式输出多项式。

样例 #1

样例输入 #1

5 
100 -1 1 -3 0 10

样例输出 #1

100x^5-x^4+x^3-3x^2+10

样例 #2

样例输入 #2

3 
-50 0 0 1

样例输出 #2

-50x^3+1

提示

NOIP 2009 普及组第一题

对于100%数据， $\le n \le 100$ ，$-100 \le $系数$ \le 100$

$\text{upd 2022.8.1}$ ：新增加一组 Hack 数据。

代码实现

#include<iostream>
using namespace std;
int main()
{
	int n,x;
	cin>>n;
	if(n==0)
	{
		cin>>x;
		cout<<x;
	}
	else
	{
		if(n==1)
		{
			if(x>0)
			{
				if(x==1)cout<<"x";
				else cout<<x<<"x";
			}
			if(x<0)
			{
				if(x==-1)cout<<"-x";
				else cout<<x<<"x";
			}
		}
		else
		{
			cin>>x;
			if(x>0)
			{
				if(x==1)cout<<"x^"<<n;
				else cout<<x<<"x^"<<n;
			}
			if(x<0)
			{
				if(x==-1)cout<<"-x^"<<n;
				else cout<<x<<"x^"<<n;
			}
			for(int i=n-1,x;i>=2;i--)
			{
				cin>>x;
				if(x>0)
				{
					if(x==1)cout<<"+x^"<<i;
					else cout<<"+"<<x<<"x^"<<i;
				}
				if(x<0)
				{
					if(x==-1)cout<<"-x^"<<i;
					else cout<<x<<"x^"<<i;
				}
			}
			cin>>x;
			if(x>0)
			{
				if(x==1)cout<<"+x";
				else cout<<"+"<<x<<"x";
			}
			if(x<0)
			{
				if(x==-1)cout<<"-x";
				else cout<<x<<"x";
			}
		}
		cin>>x;
		if(x>0)cout<<"+"<<x;
		if(x<0)cout<<x;
	}	
	return 0;
}

[NOIP2014 提高组] 生活大爆炸版石头剪刀布

题目背景

NOIP2014 提高组 D1T1

题目描述

石头剪刀布是常见的猜拳游戏：石头胜剪刀，剪刀胜布，布胜石头。如果两个人出拳一样，则不分胜负。在《生活大爆炸》第二季第 8 集中出现了一种石头剪刀布的升级版游戏。

升级版游戏在传统的石头剪刀布游戏的基础上，增加了两个新手势：

斯波克:《星际迷航》主角之一。

蜥蜴人:《星际迷航》中的反面角色。

这五种手势的胜负关系如表一所示,表中列出的是甲对乙的游戏结果。

现在，小 A 和小 B 尝试玩这种升级版的猜拳游戏。已知他们的出拳都是有周期性规律的，但周期长度不一定相等。例如：如果小 A 以 石头-布-石头-剪刀-蜥蜴人-斯波克 长度为 $6$ 的周期出拳,那么他的出拳序列就是 石头-布-石头-剪刀-蜥蜴人-斯波克-石头-布-石头-剪刀-蜥蜴人-斯波克-...，而如果小 B 以 剪刀-石头-布-斯波克-蜥蜴人 长度为 $5$ 的周期出拳,那么他出拳的序列就是 剪刀-石头-布-斯波克-蜥蜴人-剪刀-石头-布-斯波克-蜥蜴人-...。

已知小 A 和小 B 一共进行 $N$ 次猜拳。每一次赢的人得 $1$ 分，输的得 $0$ 分；平局两人都得 $0$ 分。现请你统计 $N$ 次猜拳结束之后两人的得分。

输入格式

第一行包含三个整数： $N,N_A,N_B$ ，分别表示共进行 $N$ 次猜拳、小 A 出拳的周期长度，小 B 出拳的周期长度。数与数之间以一个空格分隔。

第二行包含 $N_A$ 个整数,表示小 A 出拳的规律,第三行包含 $N_B$ 个整数，表示小 B 出拳的规律。其中， $0$ 表示 剪刀， $1$ 表示 石头， $2$ 表示 布， $3$ 表示 蜥蜴人， $4$ 表示 斯波克。数与数之间以一个空格分隔。

输出格式

输出一行，包含两个整数，以一个空格分隔，分别表示小 A、小 B 的得分。

样例 #1

样例输入 #1

10 5 6
0 1 2 3 4
0 3 4 2 1 0

样例输出 #1

6 2

样例 #2

样例输入 #2

9 5 5
0 1 2 3 4
1 0 3 2 4

样例输出 #2

4 4

提示

对于 $100\%$ 的数据， $\leq 200, 0 < N_A \leq 200, 0 < N_B \leq 200$ 。

代码实现

#include<iostream>
using namespace std;
#define MAX_N 200
int vd[5][5]={{0,0,1,1,0},{1,0,0,1,0},{0,1,0,0,1},{0,0,1,0,1},{1,1,0,0,0}};
int s1[MAX_N+5],s2[MAX_N+5];
int main()
{
	int n,n1,n2;
	int score1=0,score2=0;
	cin>>n>>n1>>n2;
	for(int i=0;i<n1;i++)cin>>s1[i];
	for(int i=0;i<n2;i++)cin>>s2[i];
	for(int i=0;i<n;i++)
	{
		score1+=vd[s1[i%n1]][s2[i%n2]];
		score2+=vd[s2[i%n2]][s1[i%n1]];
	}
	cout<<score1<<" "<<score2;
	return 0;
}

[NOIP2003 普及组] 乒乓球

题目背景

国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中 $11$ 分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白 $11$ 分制和 $21$ 分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。

题目描述

华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在 $11$ 分制和 $21$ 分制下，双方的比赛结果（截至记录末尾）。

比如现在有这么一份记录，（其中 $\texttt W$ 表示华华获得一分， $\texttt L$ 表示华华对手获得一分）：

$\texttt{WWWWWWWWWWWWWWWWWWWWWWLW}$

在 $11$ 分制下，此时比赛的结果是华华第一局 $11$ 比 $0$ 获胜，第二局 $11$ 比 $0$ 获胜，正在进行第三局，当前比分 $1$ 比 $1$ 。而在 $21$ 分制下，此时比赛结果是华华第一局 $21$ 比 $0$ 获胜，正在进行第二局，比分 $2$ 比 $1$ 。如果一局比赛刚开始，则此时比分为 $0$ 比 $0$ 。直到分差大于或者等于 $2$ ，才一局结束。

你的程序就是要对于一系列比赛信息的输入（ $\texttt{WL}$ 形式），输出正确的结果。

输入格式

每个输入文件包含若干行字符串，字符串有大写的 $\texttt W$ 、 $\texttt L$ 和 $\texttt E$ 组成。其中 $\texttt E$ 表示比赛信息结束，程序应该忽略 $\texttt E$ 之后的所有内容。

输出格式

输出由两部分组成，每部分有若干行，每一行对应一局比赛的比分（按比赛信息输入顺序）。其中第一部分是 $11$ 分制下的结果，第二部分是 $21$ 分制下的结果，两部分之间由一个空行分隔。

样例 #1

样例输入 #1

WWWWWWWWWWWWWWWWWWWW
WWLWE

样例输出 #1

11:0
11:0
1:1

21:0
2:1

提示

每行至多 $25$ 个字母，最多有 $2500$ 行。

（注：事实上有一个测试点有 $2501$ 行数据。）

【题目来源】

NOIP 2003 普及组第一题

代码实现

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s,t;
	while(cin>>t)s+=t;
	int cnt1=0,cnt2=0;
	for(int i=0;s[i]!='E';i++)
	{
		if(s[i]=='W')cnt1++;
		else cnt2++;
		if((cnt1>=11||cnt2>=11)&&abs(cnt1-cnt2)>=2)
		{
			cout<<cnt1<<":"<<cnt2<<endl;
			cnt1=0;
			cnt2=0;
		}
	}
	cout<<cnt1<<":"<<cnt2<<endl;
	cnt1=0;
	cnt2=0;
	cout<<endl;
	for(int i=0;s[i]!='E';i++)
	{
		if(s[i]=='W')cnt1++;
		else cnt2++;
		if((cnt1>=21||cnt2>=21)&&abs(cnt1-cnt2)>=2)
		{
			cout<<cnt1<<":"<<cnt2<<endl;
			cnt1=0;
			cnt2=0;
		}
	}
	cout<<cnt1<<":"<<cnt2;
	cnt1=0;
	cnt2=0;
	return 0;
}

[NOIP2015 提高组] 神奇的幻方

题目背景

NOIp2015 提高组 Day1T1

题目描述

幻方是一种很神奇的 $N\times N$ 矩阵：它由数字 $1,2,3,\cdots \cdots ,N \times N$ 构成，且每行、每列及两条对角线上的数字之和都相同。

当 $N$ 为奇数时，我们可以通过下方法构建一个幻方：

首先将 $1$ 写在第一行的中间。

之后，按如下方式从小到大依次填写每个数 $\ (K=2,3,\cdots,N \times N)$ ：

若 $(K - 1)$ 在第一行但不在最后一列，则将 $K$ 填在最后一行， $(K - 1)$ 所在列的右一列；
若 $(K - 1)$ 在最后一列但不在第一行，则将 $K$ 填在第一列， $(K - 1)$ 所在行的上一行；
若 $(K - 1)$ 在第一行最后一列，则将 $K$ 填在 $(K - 1)$ 的正下方；
若 $(K - 1)$ 既不在第一行，也不在最后一列，如果 $(K - 1)$ 的右上方还未填数，则将 $K$ 填在 $(K - 1)$ 的右上方，否则将 $K$ 填在 $(K - 1)$ 的正下方。

现给定 $N$ ，请按上述方法构造 $\times N$ 的幻方。

输入格式

一个正整数 $N$ ，即幻方的大小。

输出格式

共 $N$ 行，每行 $N$ 个整数，即按上述方法构造出的 $\times N$ 的幻方，相邻两个整数之间用单空格隔开。

样例 #1

样例输入 #1

样例输出 #1

8 1 6
3 5 7
4 9 2

样例 #2

样例输入 #2

样例输出 #2

327 354 381 408 435 462 489 516 543 570 597 624 1 28 55 82 109 136 163 190 217 244 271 298 325
353 380 407 434 461 488 515 542 569 596 623 25 27 54 81 108 135 162 189 216 243 270 297 324 326
379 406 433 460 487 514 541 568 595 622 24 26 53 80 107 134 161 188 215 242 269 296 323 350 352
405 432 459 486 513 540 567 594 621 23 50 52 79 106 133 160 187 214 241 268 295 322 349 351 378
431 458 485 512 539 566 593 620 22 49 51 78 105 132 159 186 213 240 267 294 321 348 375 377 404
457 484 511 538 565 592 619 21 48 75 77 104 131 158 185 212 239 266 293 320 347 374 376 403 430
483 510 537 564 591 618 20 47 74 76 103 130 157 184 211 238 265 292 319 346 373 400 402 429 456
509 536 563 590 617 19 46 73 100 102 129 156 183 210 237 264 291 318 345 372 399 401 428 455 482
535 562 589 616 18 45 72 99 101 128 155 182 209 236 263 290 317 344 371 398 425 427 454 481 508
561 588 615 17 44 71 98 125 127 154 181 208 235 262 289 316 343 370 397 424 426 453 480 507 534
587 614 16 43 70 97 124 126 153 180 207 234 261 288 315 342 369 396 423 450 452 479 506 533 560
613 15 42 69 96 123 150 152 179 206 233 260 287 314 341 368 395 422 449 451 478 505 532 559 586
14 41 68 95 122 149 151 178 205 232 259 286 313 340 367 394 421 448 475 477 504 531 558 585 612
40 67 94 121 148 175 177 204 231 258 285 312 339 366 393 420 447 474 476 503 530 557 584 611 13
66 93 120 147 174 176 203 230 257 284 311 338 365 392 419 446 473 500 502 529 556 583 610 12 39
92 119 146 173 200 202 229 256 283 310 337 364 391 418 445 472 499 501 528 555 582 609 11 38 65
118 145 172 199 201 228 255 282 309 336 363 390 417 444 471 498 525 527 554 581 608 10 37 64 91
144 171 198 225 227 254 281 308 335 362 389 416 443 470 497 524 526 553 580 607 9 36 63 90 117
170 197 224 226 253 280 307 334 361 388 415 442 469 496 523 550 552 579 606 8 35 62 89 116 143
196 223 250 252 279 306 333 360 387 414 441 468 495 522 549 551 578 605 7 34 61 88 115 142 169
222 249 251 278 305 332 359 386 413 440 467 494 521 548 575 577 604 6 33 60 87 114 141 168 195
248 275 277 304 331 358 385 412 439 466 493 520 547 574 576 603 5 32 59 86 113 140 167 194 221
274 276 303 330 357 384 411 438 465 492 519 546 573 600 602 4 31 58 85 112 139 166 193 220 247
300 302 329 356 383 410 437 464 491 518 545 572 599 601 3 30 57 84 111 138 165 192 219 246 273
301 328 355 382 409 436 463 490 517 544 571 598 625 2 29 56 83 110 137 164 191 218 245 272 299

提示

对于 $100\%$ 的数据，对于全部数据， $\leq N \leq 39$ 且 $N$ 为奇数。

代码实现

#include<iostream>
using namespace std;
#define MAX_N 39 
int huanfang[MAX_N+6][MAX_N+6]={0};
//pos=1第一行非最后一列 pos=2第一行最后一列 pos=3非第一行最后一列 pos=4非第一行非最后一列 
int main()
{
	int n;
	cin>>n;
	huanfang[1][(n+1)/2]=1;
	int h=1,l=(n+1)/2,pos=1;
	for(int i=2;i<=n*n;i++)
	{
		if(pos==1)
		{
			huanfang[n][l+1]=i;
			if(l+1==n)pos=3;
			else pos=4;
			h=n;
			l+=1;
		}
		else if(pos==2)
		{
			huanfang[h+1][l]=i;
			pos=3;
			h+=1;
		}
		else if(pos==3)
		{
			huanfang[h-1][1]=i;
			if(h-1==1)pos=1;
			else pos=4;
			h-=1;
			l=1;
		}
		else{
			if(!huanfang[h-1][l+1])
			{
				huanfang[h-1][l+1]=i;
				if(h-1==1)
				{
					if(l+1==n)pos=2;
					else pos=1;
				}
				else{
					if(l+1==n)pos=3;
					else pos=4;
				}
				h-=1;
				l+=1;
			}
			else{
				huanfang[h+1][l]=i;
				h+=1;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			printf("%d ",huanfang[i][j]);
		}
		printf("\n");
	}
	return 0;
 }

[NOIP2017 提高组] 时间复杂度

题目背景

NOIP2017 提高组 D1T2

题目描述

小明正在学习一种新的编程语言 A++，刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序，于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++语言的循环结构如下：

F i x y
    循环体
E

其中F i x y表示新建变量 $i$ （变量 $i$ 不可与未被销毁的变量重名）并初始化为 $x$ ，然后判断 $i$ 和 $y$ 的大小关系，若 $i$ 小于等于 $y$ 则进入循环，否则不进入。每次循环结束后 $i$ 都会被修改成 $i + 1$ ，一旦 $i$ 大于 $y$ 终止循环。

$x$ 和 $y$ 可以是正整数（ $x$ 和 $y$ 的大小关系不定）或变量 $n$ 。 $n$ 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于 $100$ 。

E 表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。

注：本题中为了书写方便，在描述复杂度时，使用大写英文字母 $\operatorname O$ 表示通常意义下 $Θ$ 的概念。

输入格式

输入文件第一行一个正整数 $t$ ，表示有 $t$ （ $\le 10$ ）个程序需要计算时间复杂度。每个程序我们只需抽取其中 F i x y 和 E 即可计算时间复杂度。注意：循环结构允许嵌套。

接下来每个程序的第一行包含一个正整数 $L$ 和一个字符串， $L$ 代表程序行数，字符串表示这个程序的复杂度，O(1) 表示常数复杂度，O(n^w) 表示复杂度为 $n^w$ ，其中 $w$ 是一个小于 $100$ 的正整数，输入保证复杂度只有 O(1) 和 O(n^w) 两种类型。

接下来 $L$ 行代表程序中循环结构中的F i x y或者 E。程序行若以F开头，表示进入一个循环，之后有空格分离的三个字符（串）i x y，其中 $i$ 是一个小写字母（保证不为 $n$ ），表示新建的变量名， $x$ 和 $y$ 可能是正整数或 $n$ ，已知若为正整数则一定小于 $100$ 。

程序行若以E开头，则表示循环体结束。

输出格式

输出文件共 $t$ 行，对应输入的 $t$ 个程序，每行输出 Yes 或 No 或者 ERR，若程序实际复杂度与输入给出的复杂度一致则输出 Yes，不一致则输出 No，若程序有语法错误（其中语法错误只有: ① F 和 E 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出 ERR。

注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 ERR。

样例 #1

样例输入 #1

8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E

样例输出 #1

Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

提示

【输入输出样例解释 $1$ 】

第一个程序 $i$ 从 $1$ 到 $1$ 是常数复杂度。

第二个程序 $x$ 从 $1$ 到 $n$ 是 $n$ 的一次方的复杂度。

第三个程序有一个 F 开启循环却没有 E 结束，语法错误。

第四个程序二重循环， $n$ 的平方的复杂度。

第五个程序两个一重循环， $n$ 的一次方的复杂度。

第六个程序第一重循环正常，但第二重循环开始即终止（因为 $n$ 远大于 $100$ ， $100$ 大于 $4$ ）。

第七个程序第一重循环无法进入，故为常数复杂度。

第八个程序第二重循环中的变量 $x$ 与第一重循环中的变量重复，出现语法错误②，输出 ERR。

【数据规模与约定】

对于 $30\%$ 的数据：不存在语法错误，数据保证小明给出的每个程序的前 $L /2$ 行一定为以 F 开头的语句，第 $L /2 + 1$ 行至第 $L$ 行一定为以 E 开头的语句， $\le 10$ ，若 $x$ 、 $y$ 均为整数， $x$ 一定小于 $y$ ，且只有 $y$ 有可能为 $n$ 。

对于 $50\%$ 的数据：不存在语法错误， $\le 100$ ，且若 $x$ 、 $y$ 均为整数， $x$ 一定小于 $y$ ，且只有 $y$ 有可能为 $n$ 。

对于 $70\%$ 的数据：不存在语法错误， $\le 100$ 。

对于 $100\%$ 的数据： $\le 100$ 。

如果需要Hack请私信@zhouyonglong或发讨论，提供数据和能Hack掉的本题的AC记录。

代码实现

#include<iostream>
#include<string>
#include<stack>
using namespace std;
#define endl '\n' 
void solve()
{
	char f,e;//f='F'or'E' e是变量名 
	string a,b; 
	bool flag[30]={0};//记录某个变量是否还存放在内存 
	bool wr=0,suo=0;//wr记录当前错误，suo记录是否前面是否存在无法进入的循环 
	stack<int>s1;//存放变量序号 
	stack<int>s2;//存放每一个循环是否提供时间复杂度的信息 
	int l,cnt=0,suo_cnt=0,du=0,du_now=0,item;
	//cnt记录当前连续k-n的for的数量，suo_cnt记录距离无法进入循环的深度 ，du记录当前遍历到的最大的复杂度，du_now表示当前遍历到的复杂度，item表示目标复杂度 
	cin>>l;
	string fuzadu;
	cin>>fuzadu;
	for(int i=0;fuzadu[i];i++)//求取目标复杂度 
	{
		if(fuzadu[i]=='('&&fuzadu[i+1]=='1')
		{
			item=0;
			break;	
		}
		if(fuzadu[i]=='^')
		{
			if(fuzadu[i+2]>='0'&&fuzadu[i+2]<='9')
			{
				item=(fuzadu[i+1]-'0')*10+(fuzadu[i+2]-'0');
				break;
			}
			else{
				item=fuzadu[i+1]-'0';
				break;
			}
		}
	}
	for(int i=1;i<=l;i++)//对于每一行 
	{
		cin>>f;
		if(f=='F')
		{
			cin>>e>>a>>b;
			if(wr)continue;//已知错误，输入后直接走人 
			if(!flag[e-'a'])//如果当前变量不存在 
			{
				flag[e-'a']=1;
				s1.push(e-'a');	
			}
			else wr=1; //如果当前变量已存在 
			cnt++;//层数++ 
			if(a[0]>='0'&&a[0]<='9'&&b[0]=='n')//提供复杂度 
			{
				
				if(!suo)
				{
					du_now++;
					s2.push(1);
				}
				else s2.push(0);
				du=max(du,du_now);
			}
			else{//不提供复杂度 
				if(a[0]>='0'&&a[0]<='9'&&b[0]>='0'&&b[0]<='9')
				{
					if(!suo_cnt)//当前不存在无法进入的“锁” 
					{
						//判断前面的常数是否大于后面 
						if(a.size()>b.size())suo=1,suo_cnt++;
						else if(a.size()==1&&a.size()==b.size()&&a[0]>b[0])suo=1,suo_cnt++;
						else if(a.size()==2&&a.size()==b.size()&&((a[0]>b[0])||(a[0]==b[0]&&a[1]>b[1])))suo=1,suo_cnt++;
					}
				}
				//如果前面是n后面不是n 
				else if(a[0]=='n'&&b[0]!='n'&&!suo_cnt)suo=1,suo_cnt++;
				s2.push(0);
			}
		}
		if(wr)continue;//已知错误，输入后直接走人 
		if(f=='E')
		{
			if(cnt<=0)wr=1;//存在多出来的E 
			else 
			{
				int num=s1.top();
				flag[num]=0;//清除当前for中的变量 
				s1.pop();
				int dd=s2.top();
				if(dd)du_now-=1;//当前层提供复杂度，清除后du_now-1 
				s2.pop();
				cnt--;//层数-1 
				if(suo_cnt)suo_cnt-=1;//存在“锁”则深度-1 
				if(!suo_cnt)suo=0;//深度为0则把“锁”解开 
			}
		}
	}
	if(wr)
	{
		cout<<"ERR"<<endl;
		return ;
	}
	if(cnt==0)//层数为0，说明F和E一一对应 
	{
		if(du==item)
		{
			cout<<"Yes"<<endl;
		}
		else cout<<"No"<<endl;
	}
	else cout<<"ERR"<<endl;//存在多余的F 
	return ;
}
int main()
{
	int t;
	cin>>t;
	while(t--)solve();
	return 0;
}

Part2.1模拟

[NOIP2011 提高组] 铺地毯

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

代码实现

[NOIP2009 普及组] 多项式输出

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

代码实现

[NOIP2014 提高组] 生活大爆炸版石头剪刀布

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

代码实现

[NOIP2003 普及组] 乒乓球

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

代码实现

[NOIP2015 提高组] 神奇的幻方

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

代码实现

[NOIP2017 提高组] 时间复杂度

题目背景

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

提示

代码实现

网站公告

今日签到

热门文章

最新发布