小结：说实话，今天考的非常不好，今天四道题都会正解，但是都出了问题，T1由于没有读比赛开头的提醒，long long类型用了\(lld\)，没用\(I64d\)，所以挂成了70分，T2忘了删调试的时候的一个中间空格，爆零了，T3矩阵快速幂写挂了，T4主席树写挂了。。离预估差的太远，还是不够细心，T1和T2的错误是真的不该犯。
Problem 1
双色球(ball.cpp/c/pas)
【题目描述】
机房来了新一届的学弟学妹，邪恶的chenzeyu97发现一位学弟与他同名，于是他当起了善良的学长233
“来来来，学弟，我考你道水题检验一下你的水平……”
一个栈内初始有n个红色和蓝色的小球，请你按照以下规则进行操作
- 只要栈顶的小球是红色的，将其取出，直到栈顶的球是蓝色
- 然后将栈顶的蓝球变成红色
最后放入若干个蓝球直到栈中的球数为n
以上3步骤为一次操作
如栈中都是红色球，则操作停止，请问几次操作后停止
chenzeyu97出完题发现他自己不能AC所以想请你帮忙【输入格式】
第一行为一个整数n，表示栈的容量为n
第二行为一个字符串，第i个字符表示自顶向下的第i个球的颜色，R代表红***代表蓝色【输出格式】
一个整数表示操作数
【样例输入】
样例1：
3
RBR样例2：
4
RBBR【样例输出】
样例1：2
样例2：6【数据范围】
\(50%\)的数据，\(1<=n<=20\)
\(100%\)的数据，\(1<=n<=50\)
思路：先忽略R，如果一个位置是B，那么它的贡献是2的n次方(这里n为B在栈中的位置)，然后根据题目条件直接转二进制即可。\(I64啊啊啊！！\)
代码：
#include<cstdio>
#define ll long long
#define maxn 57
char s[maxn];
int n;
ll ans;
int main() {
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
scanf("%d%s",&n,s);
for(int i=0;i<n;++i) if(s[i]=='B') ans+=(1ll<<i);
printf("%I64d\n",ans);
fclose(stdin);fclose(stdout);
return 0;
}Problem 2
魔方(cube.cpp/c/pas)
【题目描述】
ccy（ndsf）觉得手动复原魔方太慢了，所以他要借助计算机。
ccy（ndsf）家的魔方都是333的三阶魔方，大家应该都见过。
（3的“顺时针”改为“逆时针”，即3 4以图为准。）
ccy（ndfs）从网上搜了一篇攻略，并找人翻译成了他自己会做的方法。现在告诉你他的魔方情况，以及他从网上搜到的攻略，请你求出最后魔方变成什么样子。
【输入格式】
第一行，一串数字，表示从网上搜到的攻略。
下面6*3行，每行3个数字，每三行表示魔方一个面的情况，六个面的顺序是前、后、左、右、上、下。
【输出格式】
6*3行，表示处理后的魔方，形式同输入。
【样例输入】
23
121
221
111
123
321
111
123
321
132
132
231
132
121
112
233
332
111
333【样例输出】
123
222
113
212
321
113
122
321
132
121
333
121
211
312
113
331
111
331【数据范围】
\(40\%\)的数据，攻略的长度小于\(5\)且仅有\(4\)种操作的其中一种
\(100\%\)的数据，攻略的长度小于\(100\)
思路：大模拟，没什么好说的，但是……我的调试忘删了，在
中间多输出了一个空格，导致全WA了，真是智障错误。。。
还有，这个题题意是真的描述错了，按样例做才是对的。
代码：
#include<cstdio>
#include<cstring>
#define maxn 107
#define FOR(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
int n,s[maxn],a[11][4][4],b[maxn];
char ss[maxn];
inline void xz(int p, int f) {
int t[4][4];
FOR(i,1,3) FOR(j,1,3) t[i][j]=a[p][i][j];
if(f==1) {
FOR(i,1,3) b[i]=t[1][i];
FOR(i,1,3) a[p][1][i]=t[3-i+1][1];
FOR(i,1,3) a[p][i][1]=t[3][i];
FOR(i,1,3) a[p][3][i]=t[3-i+1][3];
FOR(i,1,3) a[p][i][3]=b[i];
} else {
FOR(i,1,3) b[i]=t[1][i];
FOR(i,1,3) a[p][1][i]=t[i][3];
FOR(i,1,3) a[p][i][3]=t[3][3-i+1];
FOR(i,1,3) a[p][3][i]=t[i][1];
FOR(i,1,3) a[p][i][1]=b[3-i+1];
}
}
inline void work(int f) {
if(f==1) {
FOR(i,1,3) {
b[i]=a[1][i][3];
a[1][i][3]=a[6][i][3];
a[6][i][3]=a[2][i][3];
a[2][i][3]=a[5][i][3];
a[5][i][3]=b[i];
}
xz(4,1);
} else if(f==2) {
FOR(i,1,3) {
b[i]=a[1][i][3];
a[1][i][3]=a[5][i][3];
a[5][i][3]=a[2][i][3];
a[2][i][3]=a[6][i][3];
a[6][i][3]=b[i];
}
xz(4,2);
} else if(f==3) {
FOR(i,1,3) {
b[i]=a[1][1][i];
a[1][1][i]=a[3][1][i];
a[3][1][i]=a[2][1][i];
a[2][1][i]=a[4][1][i];
a[4][1][i]=b[i];
}
xz(5,1);
} else if(f==4) {
FOR(i,1,3) {
b[i]=a[1][1][i];
a[1][1][i]=a[4][1][i];
a[4][1][i]=a[2][1][i];
a[2][1][i]=a[3][1][i];
a[3][1][i]=b[i];
}
xz(5,2);
}
}
int main() {
freopen("cube.in","r",stdin);
freopen("cube.out","w",stdout);
scanf("%s",ss+1);
int n=strlen(ss+1);
FOR(i,1,n) s[i]=ss[i]-'0';
FOR(i,1,6) FOR(j,1,3) FOR(k,1,3) scanf("%1d",&a[i][j][k]);
FOR(i,1,n) work(s[i]);
// puts(""); //这就是那个调试的空格……
FOR(i,1,6) {
FOR(j,1,3) {
FOR(k,1,3)
printf("%d",a[i][j][k]);
puts("");
}
}
fclose(stdin);
fclose(stdout);
return 0;
}Problem 3
czy的后宫(harem.cpp/c/pas)
【题目描述】
czy要妥善安排他的后宫，他想在机房摆一群妹子，一共有n个位置排成一排，每个位置可以摆妹子也可以不摆妹子。有些类型妹子如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种妹子数量无限，求摆妹子的方案数。
【输入格式】
输入有m+1行，第一行有两个用空格隔开的正整数n、m，m表示妹子的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种妹子第j种妹子不能排在相邻的位置，输入保证对称。（提示：同一种妹子可能不能排在相邻位置）。
【输出格式】
输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以1000000007的余数。
【样例输入】
2 2
01
10【样例输出】
7【样例说明】
七种方案为(空，空)、（空，1）、（1、空）、（2、空）、（空、2）、（1,1）、（2,2）。
【数据范围】
\(20\%\)的数据，\(1＜n≤5,0＜m≤10\)。
\(60\%\)的数据，\(1＜n≤200,0＜m≤100\)。
\(100\%\)的数据，\(1＜n≤1000000000，0＜m≤100\)。
注：此题时限1.5s是因为本评测机跑太慢，大家正常做
但写的太丑可能T一俩个点
思路：\(60\)分的思路应该很好想，就是用\(f[i][j]\)表示当前已经选了\(i\)个妹子，最后一个妹子是第j种的方案数，那么转移方程明显是\(f[i][j]+=f[i-1][k]\) (\(k\)可以与\(i\)挨在一起)。然后数据范围\(1e9\)，套一个矩阵加速一下就好了。
代码：
#include<cstdio>
#define maxn 2007
int n,m,map[maxn][maxn];
#define int long long
const int mod=1e9+7;
inline int pls(int a, int b) {int m=a+b;return m<mod?m:m-mod;}
inline int mul(int a, int b) {return 1ll*a*b%mod;}
namespace s1 {
const int N=207;
int f[maxn][maxn],ans;
inline void solve() {
for(int i=0;i<=m;++i) f[1][i]=1;
for(int i=2;i<=n;++i)
for(int j=0;j<=m;++j)
for(int k=0;k<=m;++k)
if(!map[j][k]) f[i][j]=pls(f[i][j],f[i-1][k]);
for(int i=0;i<=m;++i) ans=pls(ans,f[n][i]);
}
}
namespace s2 {
struct node {
int a[maxn][maxn];
}e,d;
inline void init() {
for(int i=1;i<=m;++i) e.a[i][i]=1;
}
inline node pmul(node x, node y) {
node c;
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
c.a[i][j]=0;
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
for(int k=1;k<=m;++k)
c.a[i][j]=pls(c.a[i][j],mul(x.a[i][k],y.a[k][j]));
return c;
}
inline node fpow(node x, int b) {
node ans=e;
for(;b;b>>=1,x=pmul(x,x))
if(b&1) ans=pmul(ans,x);
return ans;
}
int ans;
inline void solve() {
init();
node p;
p=fpow(d,n);
for(int i=1;i<=m;++i) ans=pls(ans,p.a[m][i]);
}
}
signed main() {
freopen("harem.in","r",stdin);
freopen("harem.out","w",stdout);
scanf("%d%d",&n,&m);
if(n<=200) {
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
scanf("%1d",&map[i][j]);
s1::solve();
return printf("%lld\n",s1::ans),0;
}
else {
for(int i=1;i<=m;++i)
for(int j=1,x;j<=m;++j)
scanf("%1d",&x),s2::d.a[i][j]=x==1?0:1;
++m;
for(int i=1;i<=m;++i) s2::d.a[i][m]=s2::d.a[m][i]=1;
s2::solve();
return printf("%lld\n",s2::ans),0;
}
return 0;
}Problem 4
mex(mex.cpp/c/pas)
Description
有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。
Input
第一行n,m。
第二行为n个数。
从第三行开始，每行一个询问l,r。
Output
一行一个数，表示每个询问的答案。
【样例输入】
7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7【样例输出】
3
0
3
2
4思路：主席树，之前mhe学长给我们讲过，当时讲的是线段树做法，用主席树简便一些。但还是写挂了……下面是修正后的代码。
代码：
#include<cstdio>
#include<algorithm>
#include<cctype>
#define maxn 200007
using namespace std;
int a[maxn],t[maxn*20],ls[maxn*20],rs[maxn*20],rt[maxn*20],tot,n,m;
inline int qread() {
char c=getchar();int num=0,f=1;
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) num=num*10+c-'0';
return num*f;
}
const int inf=200007;
inline void pushup(int rt) {
t[rt]=min(t[ls[rt]],t[rs[rt]]);
}
void modify(int &x, int y, int l, int r, int a, int b) {
x=++tot;
t[x]=t[y],ls[x]=ls[y],rs[x]=rs[y];
if(l==r) {
t[x]=b;
return;
}
int mid=(l+r)>>1;
if(a<=mid) modify(ls[x],ls[y],l,mid,a,b);
else modify(rs[x],rs[y],mid+1,r,a,b);
pushup(x);
}
int query(int x,int l,int r,int a) {
if(l==r) return l;
int mid=(l+r)>>1;
if(t[ls[x]]>=a) return query(rs[x],mid+1,r,a);
else return query(ls[x],l,mid,a);
}
int main() {
freopen("mex.in","r",stdin);
freopen("mex.out","w",stdout);
n=qread(),m=qread();
for(int i=1;i<=n;++i) {
a[i]=qread();
modify(rt[i],rt[i-1],0,inf,a[i],i);
}
int ans=0;
while(m--) {
int ll=qread(),rr=qread();
ans=query(rt[rr],0,inf,ll);
printf("%d\n",ans);
}
fclose(stdin);fclose(stdout);
return 0;
}
京公网安备 11010502036488号