自动搬运

查看原文

来自洛谷，原作者为

	king_xbz 是人是鬼都有勾，只有蒟蒻在发抖

搬运于2025-08-24 21:44:24，当前版本为作者最后更新于2020-02-02 20:25:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目翻译不完全，这是许多国外oj拿过来的题的通病，所以我来补充翻译一下

输入格式：

第一行，n；
接下来n行，每行0或1，0对应“（”；1对应“）”

输出格式

得分对12345678910取模的结果

然后再用一个式子简单推一下样例

s（'（（））（）'）=s（'（（））'）+s（'（）'=2*s（'（）'+1=2*1+1=3。

英文渣渣，翻译的不好请见谅。

别的东西题目上说的已经很清楚了；

接下来是做题的思路->

我们可以用定义一个整型变量tops来模拟栈顶指针。

当输入为‘（’入栈，tops++；

当输入为“）”出栈，tops--；

若这一位是‘）’但上一位是‘（’进行x_mod，即计算2^tops次方，并累加入tot；

最后输出tot值即可。

需要注意的是：

1.取模的12345678910会爆int，所以开long long。

2.注意每一步都取模，别因为少%而丢失部分分

最后，上代码，自以为还是蛮简洁易懂的。

#include<bits/stdc++.h>
#define p 345345
#define h 5001
#define fint register int
#define int long long
#define mods 12345678910
using namespace std;
int a[p],tops,tot;
inline int read();
inline int x_mod(int x,int y);
signed main()
{
	int n;
	n=read();
	for(fint i=1;i<=n;i++)
	a[i]=read();
	for(fint i=1;i<=n;i++)
		if(a[i]==0)
		tops++;
		else
		{
		tops--;
		if(a[i-1]==0)
		tot+=x_mod(1,tops),tot%=mods;
		}
	cout<<tot%mods;
	return 0;
}

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}

inline int x_mod(int x,int y)
{
	for(fint i=1;i<=y;i++)
		x*=2,x%=mods;
	return x;
}

总体来说这道题主要还是模拟，只要理解题意难度还是不大的。祝大家AC！