Skip to main content

模拟

参考资料​

简介​

模拟（Simulate）就是用计算机来模拟题目中要求的操作。

模拟题目通常具有码量大、操作多、思路繁复的特点。由于它码量大，经常会出现难以查错的情况，如果在考试中写错是相当浪费时间的。

例题​

洛谷 P7426 [THUPC 2017] 体育成绩统计

请你根据数据计算每一位同学的学号、百分制总评成绩以及等级。

Code (1)
#include <bits/stdc++.h>
#define f(x,y) (x*60+y)
#define g(x,y,z) (x*3600+y*60+z)
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
const int N=10005;
const int day[13]={0,0,31,59,90,120,151,181,212,243,273,304,334};
const int sun[2][7]={{21,19,17,14,11,7,3},{10,9,8,7,6,4,2}};
const int plan[2][5]={{18,15,12,9,6},{5,4,3,2,1}};
const int test[3][10]=
{
	{f(12,30),f(13,0),f(13,30),f(14,0),f(14,30),f(15,10),f(15,50),f(16,30),f(17,10),f(18,0)},
	{f(6,40),f(6,57),f(7,14),f(7,31),f(7,50),f(8,5),f(8,20),f(8,35),f(8,50),f(9,0)},
	{20,18,16,14,12,10,8,6,4,2}
};
pair<int,string> level[11]={{95,"A"},{90,"A-"},{85,"B+"},{80,"B"},{77,"B-"},{73,"C+"},{70,"C"},{67,"C-"},{63,"D+"},{60,"D"},{0,"F"}};
map<ll,int> mp;
struct Stu
{
	ll id;
	char sex;
	int score,cnt1,cnt2,lst;
	bool operator<(const Stu &rhs){return id<rhs.id;}
}P[N];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		char t1;
		int a,b,t2;
		scanf("%lld%*c%c%d%d%*c%d%*c%*c%c%d%d",&P[i].id,&P[i].sex,&P[i].score,&a,&b,&t1,&t2,&P[i].cnt1);
		for(int j=0;j<10;j++)if(f(a,b)<=test[P[i].sex=='F'][j]){P[i].score+=test[2][j];break;}
		P[i].score+=(t1=='P'?10:0)+t2;
		P[i].lst=-inf;
		mp[P[i].id]=i;
	}
	int m;
	scanf("%d",&m);
	while(m--)
	{
		ll id;
		int date,h1,m1,s1,h2,m2,s2,a,b,step;
		double L;
		scanf("%d%lld%d%*c%d%*c%d%d%*c%d%*c%d%lf%d%*c%d%*c%d",&date,&id,&h1,&m1,&s1,&h2,&m2,&s2,&L,&a,&b,&step);
		int x=mp[id];
		int len=(L*1000+0.5),tmp=(day[date%10000/100]+date%100)*86400;
		if(len>=(P[x].sex=='M'?3000:1500)&&(g(h2,m2,s2)-g(h1,m1,s1))*2<=len&&(g(h2,m2,s2)-g(h1,m1,s1))*5>=len&&f(a,b)<=f(4,30)&&len*2<=step*3&&g(h1,m1,s1)+tmp-P[x].lst>=21600)
		{
			P[x].lst=g(h2,m2,s2)+tmp;
			P[x].cnt2++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<7;j++)if(P[i].cnt2>=sun[0][j]){P[i].score+=sun[1][j];break;}
		for(int j=0;j<5;j++)if(P[i].cnt1+P[i].cnt2>=plan[0][j]){P[i].score+=plan[1][j];break;}
		printf("%lld %d ",P[i].id,P[i].score);
		for(int j=0;j<11;j++)if(P[i].score>=level[j].first){printf("%s\n",level[j].second.c_str());break;}
	}
	return 0;
}
洛谷 P5698 [CTSC1998] 算法复杂度

你需要写一个程序，用来求出题目描述的程序的时间复杂度，并以多项式的形式输出。

Solution

解题思路​

思想​

时间复杂度是一个不超过 2020 次的多项式。

用 f(k)f(k) 模拟执行 kk 次的循环的复杂度。

特别地，令 k=0k=0 表示执行 nn 次。

计算​

考虑计算 f(k)f(k) 的复杂度。

初始时，设多项式 P=0P=0。

循环读入字符串 SS 并分类讨论：

  • end\texttt{end}：循环结束。

  • loop x <statement>\texttt{loop x <statement>}

    递归调用 f(x)f(x) 计算 <statement>\texttt{<statement>} 的复杂度。

    将 P←P+f(x)P\gets P+f(x)。

  • op <statement>\texttt{op <statement>}

    将 P←P+<statement>P\gets P+\texttt{<statement>}。

  • break <statement>\texttt{break <statement>} 或 continue <statement>\texttt{continue <statement>}

    如果它（break\texttt{break} 或 continue\texttt{continue}）不在任何一层循环中，请忽略它们。

    根据循环的嵌套关系，读入并忽略后面的语句。

    而 break\texttt{break} 前的语句只会执行 11 次，即 k←1k\gets1。

    特别地，如果当前是在最外层的大循环，直接忽略。

此时 PP 为循环内的复杂度，一共要执行 kk 次，所以该循环的总复杂度为 P×kP\times k。

输出​

倒序遍历多项式的 ii 次项：

  1. 如果系数 ai=0a_i=0，不用输出。
  2. 如果前面有输出，需要输出加号 +。
  3. 对于常数项，输出系数 a0a_0。
  4. 对于非常数项，系数 ai≠1a_i\ne 1 时输出 aia_i；一次项输出 n，其余项输出 n^i。

特别地，如果没有任何输出，需要输出 00。

参考代码​

#include <bits/stdc++.h>
using namespace std;

const int N=22;
struct Poly
{
	int a[N];
	Poly(){for(int i=0;i<N;i++)a[i]=0;}
};
Poly f(int k,bool b)
{
	Poly P;
	string s;
	while(cin>>s&&s!="end")
	{
		if(s=="loop")
		{
			cin>>s;
			Poly T=f(s=="n"?0:stoi(s),1);
			for(int i=0;i<N;i++)P.a[i]+=T.a[i];
		}
		else if(s=="op")
		{
			cin>>s;
			if(s=="n")P.a[1]++;
			else P.a[0]+=stoi(s);
		}
		else if((s=="continue"||s=="break")&&b)
		{
			if(s=="break")k=1;
			int t=1;
			while(t)
			{
				cin>>s;
				if(s=="loop")t++;
				else if(s=="end")t--;
			}
			break;
		}
	}
	if(k)for(int i=0;i<N;i++)P.a[i]*=k;
	else{for(int i=N-1;i>0;i--)P.a[i]=P.a[i-1];P.a[0]=0;}
	return P;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s;
	cin>>s;
	Poly ans=f(1,0);
	bool b=0;
	for(int i=N-1;i>=0;i--)
	{
		if(ans.a[i]==0)continue;
		if(b)cout<<'+';
		if(i==0||ans.a[i]!=1)cout<<ans.a[i];
		if(i>1)cout<<"n^"<<i;
		else if(i==1)cout<<'n';
		b=1;
	}
	if(!b)cout<<0<<'\n';
	return 0;
}