OJ-ACMer不得不知道的事儿(四)

E  ACMer不得不知道的事儿(四)

Time Limit:1000MS  Memory Limit:65535K

题型: 编程题   语言: 无限制

描述

(正题在分割线之后)

正在做这条题的这位同学,想必你一定有想法成为一名ACMer。
一名ACMer最经常做的事就是在OJ上切题,在学习训练的时候,卡题是常事,所以有些时候为了快速提升可能会选择一些会有错误数据提示的OJ做题,例如CF。

而在开始的初期,有些同学会很奇怪,为什么同样一个数据,在自己电脑跑出来是OJ期望的结果,但是在OJ上的运行结果却是错误的结果。

难道是OJ运行出错了吗????想都别想。

因为如果是数据错误的话,那现象应该是你本机输出的答案跟OJ期望的结果不相同。所以当你本地跑出了一个与OJ的答案相同的结果,
但是OJ的运行结果却不相同时,不用怀疑,是你的问题。

这种情况通常是程序中有未定义行为或者使用了未知的值导致的,下面来详细说一下:

1. 未定义行为。C/C++中官方已经说明了会有不可预料结果的写法,这里通俗地举几个例子。(这里顺便提一下,经常在一些老旧的计算机考试题目里面会有考类似
这种题目的运算结果,如果这么不幸你在考试中遇到了这种题目,不要纠结,随便选一个就好了,实际应用中是不会这样写的,毕竟找个稍微新一点的编译器编译这
种语句都会警告你这是未定义行为)

  a. 在同一个语句中存在对同个变量进行两次或以上的自增自减行为,或自增自减与赋值混用:
    e.g. (1) b = a++ + a--; (2) a = a++; (3) a++ = b;

  b. 函数调用的参数依赖参数表达式计算先后顺序:
    e.g. printf("%d %d\n", a, a++);

  c. 指针修改常量空间的内容(通常你们都不会遇到,可以忽略):
    e.g. const int a = 10; *(* int)&a = 9;

2. 使用未知的值。(定义在全局空间中的变量会默认置0,但其实所有变量在定义的时候赋值一个初始值总会比没初始值要安全)

    a. 使用了未初始化的变量:
    e.g. 
    (1) int sum, a = 10; sum += a; // sum没有初始化但是被用于自加
    (2) int sum = 0, a[3] = {0}; 
         for (int i = 0; i < 3; i++) sum += a[i]; // 数组a初始化的时候并没有全部赋值为0,确定为0的只有a[0],同理应用与字符串。

    b. 越界。越界并不一定会导致非法访问内存,只有在越界且超过程序自身的内存分配范围时且进行了写操作才会导致非法访问内存,而只进行读操作是不会导致崩
    溃的。
    e.g.
    int a[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
    for (int i = 10; i >= 1; i--)   // 冒泡排序,但a下标为10的元素参与了排序,
        for (int j = 0; j < i; j++)  // 导致排序结果依赖未知变量a[10]值的大小
                                            // i正确的循环是i=9;i>=1;i--
            if (a[j] > a[j + 1]) swap(&a[j], &a[j + 1]);

    c. 野指针,道理同b,不解释

上面两点中,使用了未知的值通常是相对容易发生的情况,同学们遇到本机运行数据正确但是OJ运行同样的代码和数据出来不一样的结果时,记得认真审查自己的代
码,不要再抱怨为什么OJ的运行结果跟本机不一样了。

ps: 如果你们对《ACMer不得不知道的事儿》系列感兴趣的话,可以在10、11、12年新生赛中找到题目并阅读其中的科普知识哦~
ACMer不得不知道的事儿
ACMer不得不知道的事儿(一)-----续
ACMer不得不知道的事儿(二)
ACMer不得不知道的事儿(三)

================ 我是分割线 ================

看了这么长科普,该是时候做题了。
题目很简单,给定一段C语言代码片段,判断这段代码中定义的变量在执行完整个代码片段后有多少个变量的值是未确定的,并且输出其他有确定值的变量。

为了简化题目,输入的代码只有以下两种语句:

一、变量声明:
    1. 一行一句声明且只声明一个int变量;
    2. 变量声明时都没有初值;
    3. 声明的变量不会重复,变量名只包含小写字母“a”到“z”,即最多只会有26个变量;

二、赋值操作
    1. 一行一句赋值且不存在连赋值;
    2. 一个变量只会被赋值常量或者一个变量;
    3. 常量必定在int范围内,以十进制形式表示且不存在前导0;
    4. 出现的变量必定已经在前面声明过;

所有输入保证语法正确,片段中不含注释与宏定义。

注意空格

 

输入格式

输入一个n(n <= 1000),代表接下来有n行代码。
紧接着n行,每行一句声明语句或者赋值语句,每行不超过80个字符。

输出格式

输出第一行包含一个数字代表输入的代码中有多少个变量仍然是未确定值。
接下来输出若干行,每行以“变量名”=“值”的形式输出有确定值的变量的值,输出顺序按照变量名字母序,具体请参考样例输出。

输入样例

10
int a;
   int b;
int  c;
c= 1;
b = c;
int d;
d=a;
 b  = a;
a =2;
      d=a;

输出样例

1
a=2
c=1
d=2

Hint

注意空格

Provider

scau_acm

 

#include<cstdio>
#include<cstring>
int main(){
int a[30]={0};
char b[30][85];
int yzhi[30]={0};
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int n,p1,p2,p3,p4,js,meizhi=0;
char tmp[100],bian;
scanf(“%d”,&n);
getchar();
for(int i=1;i<=n;i++){
p1=0;
p2=0;
p3=0;
p4=0;
gets(tmp);
for(int j=0;tmp[j]!=’;’;j++){
if(tmp[j]==’i’&&tmp[j+1]==’n’&&tmp[j+2]==’t’){
j+=3;
p1=1;

}
if(p1==1){
if(tmp[j]>=’a’&&tmp[j]<=’z’){
a[tmp[j]-‘a’]++;

}
}

if(p2==0&&p1==0&&tmp[j]>=’a’&&tmp[j]<=’z’){
bian=tmp[j]-‘a’;
p2=1;

}
if(p2==1){
if(tmp[j]==’=’){
p3=1;
j++;

}
}

if(p3==1&p4==0){
if(tmp[j]==’-‘){
js=0;
b[bian][js++]=’-‘;
for(int q=j+1;tmp[q]>=’0’&&tmp[q]<=’9′;q++){
b[bian][js++]=tmp[q];
}
b[bian][js++]=’\0′;
yzhi[bian]=1;
p4=1;

}
if(tmp[j]>=’0’&&tmp[j]<=’9′){

js=0;
for(int q=j;tmp[q]>=’0’&&tmp[q]<=’9′;q++){
b[bian][js++]=tmp[q];
}
b[bian][js++]=’\0′;
yzhi[bian]=1;
p4=1;
}
if(tmp[j]>=’a’&&tmp[j]<=’z’){
yzhi[bian]=yzhi[tmp[j]-‘a’];
strcpy(b[bian],b[tmp[j]-‘a’]);
p4=1;
}
}

}
}

for(int i=0;i<=25;i++){
if(a[i]>0&&yzhi[i]==0)meizhi++;
}
printf(“%d\n”,meizhi);
for(int i=0;i<=25;i++){
if(yzhi[i]==1)printf(“%c=%s\n”,i+’a’,b[i]);
}
return 0;
}

Sheep回文串

 

C  Sheep回文串

 

Time Limit:1000MS  Memory Limit:65535K

题型: 编程题   语言: 无限制

描述

16级有一位小羊,因为去沈阳了却没有撸串,一直对它念念不忘,现在他想出道字符串的题来考考你们

对于字符串S,如果它的倒序和正序完全重合,那么称S是一个回文串。如level,noon。

对于字符串S,如果S的所有奇数长度的子串都是回文串,那么称S为一个Sheep回文串,如aaa,它共有4个奇数长度的子串,分别是a, a, a, aaa。

现在小羊手上有一个字符串S,它每一次可以将S中的一个字符替换成其它字符,现在他想问你最少替换几次字符可以将S变成Sheep回文串

 

输入格式

一个只包含小写英文字母的字符串S,1<= |S| <= 1000001,且|S|为奇数,其中|S|是字符串S的长度

输出格式

一个整数,表示将字符串S变成Sheep回文串所需要的最少替换次数

输入样例

aaaaabb

输出样例

2

Provider

scau_acm

令奇数位和偶数位的字符相同即可

 

 

OJ-请问您今天要来点魔法吗??

D  请问您今天要来点魔法吗??

Time Limit:1000MS  Memory Limit:65535K

题型: 编程题   语言: 无限制

描述

Cocoa非常喜欢毛茸茸的兔子,于是在家里养了很多兔子。
有一天,Cocoa正在愉快地摸兔子的时候,魔法少女Chino出现了。
Cocoa:姐姐你是谁啊?
Chino:Cocoa,你知道能让兔子变多的魔法吗?
Cocoa:不知道诶,姐姐快教我!
Chino:那么跟我一起念“ca fe la te, ca fe mo ca, ca pu chi--no!”(咖啡拿铁,咖啡摩卡,卡布奇诺)
奇迹发生了,兔子的数量从n只变成了m只!

聪明的Cocoa发现,n和m满足以下关系:
每次把n的最后一位数抹去(十进制下)直到只剩最高位,把产生的所有数求和的结果就是m。
(例如n=123时,m=123+12+1=136。)

第二天,看着m只兔子,Cocoa想:这难道是在做梦吗?
这时候该你出马了,请告诉Cocoa,是否存在n使得施放魔法之后刚好有m只兔子?


(题目背景改编自剧场动画《请问您今天要来点兔子吗?? ~Dear My Sister~》)

 

输入格式

第一行输入一个正整数t(1<=t<=1000),表示将要输入的测试数据数量。
接下来t行,每行包含一个正整数m(1<=m<=10^9)。

输出格式

对于每个m,如果存在n满足关系,请输出n,如果存在多个n同时满足关系请输出最小的一个,如果不存在满足关系的n请输出-1。

输入样例

5
136
1
10
114514
1919

输出样例

123
1
-1
103064
1729


解题思路:
ojac
如图黑色框框和红色框框相同,原数=已知数-已知数去除最后一位的数+最后一列的进位数(由题可知原数<10^9,所以进位不超过8,可枚举进位数数为0-8,再检验所求原数是否正确)。如已知1919,已知数去除一位为1919,假设进位数为0,原数为1728,经检验不成立,假设进位数为1,原数为1729,检验成立,输出并停止假设
代码略,都会写的。

OJ-体育课

体育课

时间限制: 1000ms   内存限制: 64M

描述

我们都知道上体育课时,体育老师会让我们按身高从小到大(或从大到小)排成一排。可是近日体育老师周老师却有点烦心,他教的班级来了几个插班生,可他们有的不守规矩,没有按照身高大小来插入队伍,导致队伍很难看。现在周老师有一个问题:给定一排人的身高,问能否至多去掉一个人,使得队伍里的人的身高又变成从小到大(或从大到小)?

 

注意: 如果一排人的身高为 1 2 2 或 2 2 1是合法的。

输入

第一行一个整数T,表示case数
接着是一个整数n,表示有n个人
接着是n个整数,第i个整数表示第i个人身高为a[i]
T <= 1000 , 2 <= n <= 1000 , a[i] <= 10000

输出

如果可以,输出”YES”,否则输出”NO”。每个case占一行。

样例输入1

3

3

1 4 5

3

9 2 3

5

1 5 2 4 3

样例输出1

YES

YES

NO

 

SOURCE


#include<cstdio>
int a[1005],b[1005],n;
int huan(int j){
int js=0,now,pre,tian=1;
for(int i=1;i<=n;i++){
if(i!=j)
b[++js]=a[i];
}

for(int i=1;i<n-1;i++){

if(b[i]>b[i+1]){
if(tian==1)pre=1;
now=1;
tian++;
}
if(b[i]<b[i+1]){
if(tian==1)pre=0;
now=0;
tian++;
}
if(now!=pre&&tian!=1)
return 0;

}
return 1;
}
int main(){
int j,pd,j2,j3,shuchu,t;
scanf(“%d”,&t);
for(int i=1;i<=t;i++){
j2=0;
shuchu=1;
scanf(“%d”,&n);
for(j=1;j<=n;j++)scanf(“%d”,&a[j]);
if(huan(1)||huan(n)) {
printf(“YES\n”);
}
else{
for(j=2;j<n;j++){
if(a[j]>a[j-1]&&a[j]>=a[j+1]){
j2++;
pd=huan(j);
if(pd){
printf(“YES\n”);
shuchu=0;
break;
}
}
if(a[j]>=a[j-1]&&a[j]>a[j+1]){
j2++;
pd=huan(j);
if(pd){
printf(“YES\n”);
shuchu=0;
break;
}
}
if(a[j]<=a[j-1]&&a[j]<a[j+1]){
j2++;
pd=huan(j);
if(pd){
shuchu=0;
printf(“YES\n”);
break;
}
}
if(a[j]<a[j-1]&&a[j]<=a[j+1]){
j2++;
pd=huan(j);
if(pd){
shuchu=0;
printf(“YES\n”);
break;
}
}
}
if(j2==0)printf(“YES\n”);
else if(shuchu) printf(“NO\n”);
}

}
return 0;
}

OJ-寻找SCAU

寻找SCAU

时间限制: 1000ms   内存限制: 32M

描述

给一个只包含S、C、A、U四种字母(大写)的字符串,问其中有多少SCAU的子序列(不要求连续,但有序)

输入

一个只包含S、C、A、U四种字母(大写)的字符串s, 1<= |s| <= 100000

输出

s中SCAU序列的个数,由于答案可能会很大,请对其求模1000000007(1e9+7)后输出

样例输入1 

SCAUUU

样例输出1

3

样例输入2 

SUAC

样例输出2

0

SOURCE


#include<cstdio>
int qa,z=0,qu[100005];
char x[100005];
int main(){
long js=0,jc=0,ja=0,ju=0,chu=1e9+7;
scanf(“%s”,x);
for(int i=0;x[i]!=’\0′;i++){
if(x[i]==’S’){
js++;
}
if(x[i]==’C’){
jc=(js+jc)%chu;
}
if(x[i]==’A’){
ja=(jc+ja)%chu;
}
if(x[i]==’U’){
z=(z+ja)%chu;
}

}

printf(“%d”,z);
return 0;
}

OJ-一起来填数吧

时间限制: 1000ms   内存限制: 64M

描述


 

给定两个数n,m,我需要你输出这样的n行m列的矩阵:

比如n = 4 , m = 4

1 8  9   16

2  7  10  15

3  6  11  14

4  5  12  13

这个矩阵是这样生成的:

大家懂我的意思了吧?

输入


 

第一行一个整数T,表示case数
每个case有两个整数n,m,表示矩阵有n行m列

1 <= n ,m <= 1000

输出


 

输出n行m列的符合要求的矩阵,注意每个数之间有一个空格,每一行的最后一个数后面不要留有空格。
每个case后输出一个空行。

样例输入1


 

3

4 4

3 4

3 2

样例输出1


 

1 8 9 16

2 7 10 15

3 6 11 14

4 5 12 13

 

1 6 7 12

2 5 8 11

3 4 9 10

 

1 6

2 5

3 4

SOURCE 


 

int a[1005][1005];
int main(){
int js=1,n,m,t;
scanf(“%d”,&t);
for(int k=1;k<=t;k++){
js=1;
scanf(“%d%d”,&n,&m);
for(int i=1;i<=m;i++){
if(i%2){
for(int j=1;j<=n;j++){
a[j][i]=js++;
}
}
else{
for(int j=n;j>=1;j–){
a[j][i]=js++;
}
}
}

for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf(“%d”,a[i][j]);
if(j<m)printf(” “);
}
printf(“\n”);
}

printf(“\n”);
}
return 0;
}