SCNU 2015ACM新生赛初赛【1001~1011】个人解题思路

时间:2021-08-08 10:48:05
 
      题目1001
      大意:已知$n$个角色,$m$种怪物种族,$k$个怪物,给出一组角色编号,编号$P_{i}$的角色能肝死编号$i$的怪物,对于给定的一组怪物编号,为了打通关,求切换角色的次数。另外初始默认第$1$个角色上场。
      思路:模拟水题,没啥好说的,先随便弄个数组比如叫$monitors$,于是$monitors[i] = P_{i}$,然后去肝那群怪,初始变量$actor = 1$,循环每次读一个怪物编号$x$,如果$monitors[x] \neq actor$,说明当前角色$actor$并不能肝死这只编号$x$的怪,切换次数$count + 1$,当前角色$actor$改为$monitors[x]$,然后就下一次循环了。
      非官方代码:
 #include <stdio.h>

 int main()
{
int T, n, m, k, act[];
scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &n, &m, &k);
for(int i=; i<=m; i++)
scanf("%d", act+i);
int t=, x, res=;
for(int i=; i<k; i++) {
scanf("%d", &x);
if(t!=act[x]) {
t=act[x];
++res;
}
}
printf("%d\n", res);
}
return ;
}

1001

      题目1002
      大意:自己理解吧,懒得打了。
      思路:在给定的$n \times m$矩阵里,行代表角色,列代表怪物,对应元素就是该行角色打败该列怪物所需时间,那就找出每列的最小值,最后根据怪物编号累加一下时间即可。拿一维数组就够了,读入的同时求最小值,因此不用保存二维的信息。
      非官方代码:
 #include <stdio.h>

 int main()
{
int T, n, m, k, tme[], t;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &n, &m, &k);
for(int i=; i<=m; i++)
scanf("%d", tme+i);
for(int i=; i<n; i++)
for(int j=; j<=m; j++) {
scanf("%d", &t);
if(tme[j]>t)
tme[j]=t;
}
int res=;
for(int i=; i<k; i++)
scanf("%d", &t),
res+=tme[t];
printf("%d\n", res);
}
return ;
}

1002

      题目1003
      大意:没有大意,就是求方程,详细要求自己看去。
      思路:这题不难,真的不难,真的真的不骗你。但搞起来麻烦= =|||首先慢慢来,别想太多,一个一个字符读入,转成数字会吧?标记个小数点的状态就可以读小数了,不会自己单独尝试下。然后读入到$x$或者其他符号比如$+$、$-$、$=$你就要停止一下,把读入的数字加到相应的$a$、$b$、$c$上。所以不是碰到$x$停止的,请加到$c$上,碰到$x$停止的,判断下一个是不是^,是就加到$a$上,否则加到$b$上。那判断^的时候,如果没有^,而是$+$、$-$、$=$怎么办?这里也拿两个状态,比如碰到$+$则$neg = false$,碰到$-$则$neg = true$,碰到$=$则$eql = true$,注意如果$eql$为$true$则符号是要反一下的,因为我们默认移项到$=$的左边。于是前面读数字那里应该利用这两个状态判断正负性。最后根据总共的$a$、$b$、$c$拿公式求一下就好了,代码懒得打所以没有。如果你们能领悟$C$的精髓——函数式编程,不要把所有代码都挤在$main()$里,分开几个函数写,思路是很容易理清的。
      当然你也可以拿字符串函数乱搞,把数字提取出来,不过思路不清晰会坑死自己,而且这种方法的时间常数大点,也就是说运行耗时会长一点点。
 
 
      题目1004
      大意:数位只有两个:$5$和$8$,其中$88888888888888888888$为最小,$55555555555555555555$为最大,请根据给定数字,求它是这样的数字中是第几大的。
      思路:这很简单,$5 > 8$,那$5$和$8$分别改成$1$和$0$不就是二进制了吗?....有一点要注意一下,是求在这种数字中的顺序,而不是求输入的数字中的顺序....不过题目要求第几大,也可以为避免麻烦,设置$5$和$8$分别对应$0$和$1$,这样直接把得到的二进制数转成十进制就可以输出辣。判断$5$和$8$的方法可以直接判断,也可以根据奇偶性判断。
      非官方代码:
 #include <stdio.h>

 int main()
{
int T, m=<<;
char N[];
scanf("%d", &T);
while(T--) {
int x=;
scanf("%s", N);
for(int i=; i<; i++) {
x<<=;
if(N[i]=='')
x|=;
}
printf("%d\n", m-x);
}
return ;
}

1004

      题目1005
      大意:自己看题目去。
      思路:求助你的数学老师。最后得到公式:$m \times m \div n + m - n$。但很不幸由于出题人太水,所以数据精度出了点问题,大部分姿势不对的情况下你大概要减去一个误差才行。。
      非官方代码:
 #include <stdio.h>

 int main() {
int T, n, m;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
printf("%.2lf\n", .*m*m/n+m-n-1E-);
}
return ;
}

1005

      题目1006
 
 
      题目1007
 
 
      题目1008
      题意:每次初始$A$是$0$,$B$是$1$,$+$代表$A = A + 1$,$\ast$代表$B = A \ast B$,求最后$B$会是多少?
      思路:首先判一下极限情况,发现$16$个$+$与$16$个$\ast$的情况会使$B$达到最大:$16^{16} = 2^{64}$,超过long long的范围,甚至unsigned long long都被爆掉了,于是只好用long double类型,当然你也可以考虑用大数......
      非官方代码:
 #include <stdio.h>
#include <iostream>
using namespace std; int main() {
int rd, A=;
long double B=;
cout.precision();
cout<<fixed;
while(~(rd=getchar())) {
if(rd=='\n') {
cout<<B<<endl;
A=; B=;
}
else if(rd=='+')
++A;
else if(rd=='*')
B*=A;
}
return ;
}

1008

      题目1009
      题意:没啥好说的。
      思路:没啥好说的。
      非官方代码:玩玩又不会怀孕对吧。
 #include <iostream>

 template<int N> struct czj { czj<N-> oyk; czj() { std::cout << N << std::endl; } };

 template<> struct czj<> { };

 czj<> wwj;

 int main() { }

1009

      题目1010
      题意:我选择死亡。
      思路:首先你要知道各个寄存器怎么转成$Hex$先,然后你需要一定的英文水平或者一定的搜索技巧,强行学会ModR/M和SIB编码,然后就可以搞出来了。
 
 
      题目1011
      题意:给出若干个点,按顺序求出两点间的距离,的总和。
      思路:这很简单,高中数学搞搞就是了,可是这输入格式是要闹哪样?(╯‵□′)╯︵┻━┻ 另外注意一下起点是第一个点,而不是(0,0,0)。
      非官方代码:
 #include <stdio.h>
#include <math.h> int main() {
int T;
scanf("%d%*c", &T);
for(int cse=; cse<=T; cse++) {
int r, a, b, c, x, y, z;
double res=.;
printf("Case #%d: ", cse);
scanf("%*c%d,%d,%d%*c", &a, &b, &c);
while(r=getchar(), r!='\n') {
scanf("%*c%d,%d,%d%*c", &x, &y, &z);
a-=x; b-=y; c-=z;
res+=sqrt(a*a+b*b+c*c);
a=x; b=y; c=z;
}
printf("%.3f\n", res);
}
return ;
}

1011