在期中和期末复习期间的笔记

从输入到输出

不同进制数

十进制：%d、%lld

十六进制：%x、%llx、%#
输出4位大写十六进制数：%04X
输出时加上0x：使用%#（提醒编译器在输出十六进制数时加上0X）
八进制：%o

十六进制与二进制

十六进制一位对应了4位二进制数，可以直接转换输出，如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
while(~scanf(" %c",&c))
{
    if(c=='0')  printf("0000");
    else if(c=='1')  printf("0001");
    else if(c=='2')  printf("0010");
    else if(c=='3')  printf("0011");
    else if(c=='4')  printf("0100");
    else if(c=='5')  printf("0101");
    else if(c=='6')  printf("0110");
    else if(c=='7')  printf("0111");
    else if(c=='8')  printf("1000");
    else if(c=='9')  printf("1001");
    else if(c=='a')  printf("1010");
    else if(c=='b')  printf("1011");
    else if(c=='c')  printf("1100");
    else if(c=='d')  printf("1101");
    else if(c=='e')  printf("1110");
    else if(c=='f')  printf("1111");
}

如此的简单直白

输入结束的判准

1
通常情况下，可以用EOF(返回值为-1)来判断输入是否结束，也即
1
2
3
4
while(~"scanf("%d",&a))
{
    xxx;
}
但是也有部分情况，正常输入两个值x、y，但用一个代表输入结束：
这时候就要用两次先后读取：

1
2
3
4
5
scanf("%d",&a);
while(~a)
{
    scanf("%d",&b);
}

ASCII码

一般情况下，不用知道特定的ASCII码，利用

1
'A'、'a'、'1'

即可较好代替

非字母数字：取补集

1
s[j]<'0'||(s[j]>'9'&&s[j]<'A')||(s[j]>'Z'&&s[j]<'a')||s[j]>'z'

并且，如果先读入一行int，再读入接下来的char，并且在空格也作为读入的一部分，则要在第一行

1
2
scanf("%d\n",&a);
scanf("%c",ch)

读入整行字符

在C语言中，我们可以通过：

1
2
char s[100];
gets(s);        //gets可以读入空格

的方式，来将一行读入到字符数组中
也可以用

1
2
char s[100];
scanf("%s",s)； //scanf不可以读入空格
如果用%s读入，那么可以不用加入取地址符&，因为已经包含在了%s中

关于读入空格的问题：

1
123 456 789
1
2
scanf("%s",s);
printf("scanf    %s\n",s);

输出为123

1
2
gets(s);
printf("gets    %s\n",s);

输出为123 456 789

“更安全的”字符串输入：fgets

fgets返回一个指针型变量；
fgets的输入格式：

1
2
char ch[n];
fgets(ch,m,stdin);

ch为存储的指针名，m为从该字符串中读入m个字符，stdin为文件指针（stdin表示从输入流stdin即输入缓冲区中读取m个字符到字符数组ch中），如果从文件指针中读入则stdin替换为文件指针。

与fgets对应的fputs

1
fputs(p1,stdout);

fputs和fgets都要求对指针变量进行操作

注意哦，gets(s)、%s针对的是字符型，不能用来处理非字符型的整形数据

另：关于的"%s"

%s是字符型数组的字符串型格式符；强调字符串

1
2
scanf("%s",s);
printf("%s","abcdef");

对于末位字符

在我们的评测环境里，换行符是\r\n，使用这个方法读入之后需要考虑去掉尾部的\r
字符串以’\0’作为结尾一定要以’\0’为结尾才认定是字符串，故需要对末尾赋值为0，判断为字符串输出
我们可以用<string.h>库中的strlen()函数来求出一个字符数组的长度

比如说：

1
2
3
int l=strlen(s);
if(s[l-1]=='\r')
    s[l-1]=0,l--;

这样就可以去掉s末尾的\r

匹配格式的输入：sscanf

sscanf需要配合gets或scanf使用，用来对已经读入的一串字符串进行格式匹配

匹配格式：int sscanf(const char *str, const char *format, …)

数值形数据的转换

整形：

1
2
3
4
5
int year, month, day;
int converted;

converted = sscanf("20191103", "%04d%02d%02d", &year, &month, &day);
printf("converted=%d, year=%d, month=%d, day=%d/n", converted, year, month, day);

输出结果为：

1
converted=3, year=2019, month=11, day=03

浮点型：

1
2
3
4
5
6
double longitude, latitude;
int converted;

converted=sscanf("113.123456789 31.123456789", "%lf %lf", &longitude, &latitude);

printf("converted=%d, longitude=%.9lf, latitude=%lf/n", converted, longitude, latitude);

输出结果为：

1
converted=2, longitude=113.123456789, latitude=31.123457

可以看到sscanf的格式为sscanf("%s","%04d%02d %lf",&a,&b,&c)
即为(“读入数组”,“要求匹配的格式”)

截断

这样的输出格式匹配也可以用来截断一段字符串
如：

1
2
sscanf("12345","%4s",str);
printf("%s",str);

输出结果为：

1
1234

也可以根据空格将gets读入的整行分为不同的字符串

1
2
3
4
char str1[100], str2[100], str3[100];
gets(str1);
sscanf(str1,"%s%s",str2,str3);
printf("%s %s\n",str2,str3);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入：i love c
输出：i love
````

### 数字和字符串

在sscanf中，面向字符串的读入无法直接将数字提取，需要加以区分：

**[0-9]：表示匹配数字**

**[a-z]：表示匹配小写数字，类似可以匹配大写数字**

如：
```c
char str[32] = "";
sscanf("123456abcdedf","%31[0-9a-z]",str);
printf("str=%s/n", str);

输出为：

1
str=123456abcdedf

在这里面，%31表示读入的数组长度，防止溢出

^的作用：到此为止

%[^a]表示读到为止
%[^+]表示读入到+为止
%[^] 表示读入到空格为止

1
2
sscanf("123456abcdef","%31[^a-z]",str)
printf("str=%s/n", str);

输出结果为

1
123456

*的作用：不读入

表示不读入
[%*d%s]表示不读入%d形数据

1
2
sscanf("123456abcdef","%*d%s",str)
printf("str=%s/n", str);

输出结果为：1234

数字和字符串之间的转化：sprintf

1
2
char r[10];
sprintf(r, "%d", date);	//也可以转换浮点型数据，十分强大，通过%.nf控制小数点后的位数

可以将数字转化到char型数组中

类型

int：%d

long long：%lld

char：%c

unsigned int：%u

浮点数取等

因为浮点数在计算机中储存方式的原因，浮点数无法严格相等，只能近似

1
2
3
double a,b,eqs=1e-9;
if(fabs(a-b)<eqs)
    printf("EQUAL!")；

也因为这个原因，可以利用一定的奇淫巧计：
如：每次对a乘2，直到a大于等于b
因为a、b都为浮点数，可以直接使用

1
if(pow(2,i)*a-b>0)

而完全不用考虑如果真的等于了会怎么样，毕竟浮点数里没有相等

取余问题的类型转换

double类型的数据不能用取余运算，只能使用强制类型转换：
例如，提取32.5：

1
a=a-(int)a/10*10；

pow函数

pow函数本身的返回值为double型
要想要使用pow函数进行取余运算，需要先进行强制类型转换，如：

1
2
int w=pow(a,b);
c=c%w;

才可以这样使用

取绝对值

！fabs针对浮点型数据

！abs针对整形数据

使用两者都可以调用<math.h>库

！！！如果混用会在oj上报错！！！

位运算

& ：按位与 1&1=1;1&0=0;

^ :按位异或 1 ^ 1 = 0 ^ 0 = 0；1 ^ 0 = 1;

| :按位或 1|1=1；=1|0=1；0|0=0

~ :取反 全部位置取反，如-1：取反后为0

<< ：左移 将所有数字右移一位，等价于*2

>> ：右移 将所有数字右移一位，等价于/2

位运算的优先级比较诡异，记得添加( )

如果遇到pow(2,n)，不要使用pow函数，使用位运算

^按位异或

n进制按位异或^

按位异或^可以用来判断如下情况：
m组n个相等数，有1个落单的不同数，则可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int b[100],a,n,i,e=1;
while(~scanf("%d",&a)
{
    i=0;
    while(a)
    {
        b[i]+=a%n;
        a/=n
        i++;
    }
}
for(i=0;i<100;i++)  b[i]=b[i]%n;
for(i=0;i<100;i++)
{
    e*=n;
    sum+=b[i]*e;
}

交换两数

1
2
3
a=a^b;
b=b^a;
a=b^a;

还可以写得更简洁一点：

1
a^=b^=a^=b;

n进制按位或

判断奇偶：

1
2
if(a&1)  printf("奇数")
if(!a&1)  printf("偶数")

利用此原理也可以用来提取固定数位的0/1

1
1<<n&a;

对二进制码进行转换

将l到h位置0：

1
2
t=(1<<(h-l+1))-1;
a=a&(~(t<<l));

将l到h位置1：

1
2
t=(1<<(h-l+1))-1;
a=a|(t<<l);

将l到h位反转：

1
2
t=(1<<(h-l+1))-1;
a=a^(t<<l);

利用位运算实现的快速幂

为了避免~卑鄙的~TLE，可以使用快速幂来代替pow函数
对于计算机，什么是快，位运算的二进制编码是最快的，快速幂便基于此
这里实现的是：a^b mod p

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
long long qpow(long long a, long long b, long long p)
{
    long long ans=1;
    a=a%p;
    while(b)
    {
        if(b&1)  ans=(ans*a)%p;
        b>>=1;
        a=a*a%p;
    }

    return ans;
}

int main()
{
    long long a,b,p;
    scanf("%lld%lld%lld",&a,&b,&p);

    printf("%lld",qpow(a,b,p));

    return 0;
}

程序结构

判断结构

if-else

1
2
3
4
5
6
7
8
9
10
11
12
if(A)
{
    xxx;
}
else if(B)
{
    xxx;
}
else
{
    xxx;
}

switch-case

1
2
3
4
5
6
7
8
9
10
11
12
13
switch(a)
{
    case 1:
        xxx;
        break;
    case 2:
        yyy;
        break;
    case 3:
    case 4:
        zzz;
        break;
}

循环结构

for

while

函数递归

传入与传出

传入数组

1
2
3
4
5
6
7
8
9
10
11
int get(int a[])    //这里要写数组的[]
{
    xxx;
    return x;
}

int main()
{
    int a[10];
    get(a);     //这里只要写数组头名
}

数组

一维数组 a[]

多维数组 a[][][][]……

利用数组的排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
int main()
{
    int a[100],i,j,n,flag,temp;
    scanf("%d",&n);
    for(i=0;i<n;i++)  scanf("%d",&a[i]);

    for(i=0;i<n;i++)
    {
        flag=0;
        for(j=0;j<n-1;j++)
        {
            if(a[j]>a[j+1])
            {
                temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;

                flag=1;
            }
        }

        if(flag==0)  break;
    }

    for(i=0;i<n;i++)  printf("%d ",a[i]);

    return 0;
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
int main()
{
    int n,a[100],i,j,flag,temp;
    scanf("%d",&n);
    for(i=0;i<n;i++)  scanf("%d",&a[i]);

    for(i=1;i<n;i++)
    {
        temp=a[i];flag=i;
        for(j=i-1;j>=0;j--)
        {
            if(temp<a[j])  {a[j+1]=a[j];flag=j;}
            else  break;
        }

        a[flag]=temp;
    }

    for(i=0;i<n;i++)  printf("%d ",a[i]);

    return 0;
}

快排

这里的cmp规则为一个简单的递增排序

strcmp的规则正负与快排的要求一致，用正负区分，返回负值为真，正值为假，可以直接return strcmp(s,ch);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
#include<stdlib.h>
int rise(const void *p1,const void *p2)
{
    if(*(int *)p1<*(int *)p2)  return -1;
    else if(*(int *)p1>*(int *)p2)  return 1;
    else  return 0;
}

int main()
{
    int a[1010],n,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)  scanf("%d",&a[i]);

    qsort(a,n,sizeof(int),rise);

    return 0;
}

对二位数组排序的cmp规则

这里的定义是：比较第一位，如果两个二维数组第一位相当，再比较第二位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
//排序规则：按照每行第一个元素升序排序，第一个元素相同时按照第二个元素升序排序
int cmp(const void *p, const void *q)
{
    int *a = (int *)p;
    int *b = (int *)q;
    if(a[0] > b[0]) return 1; //第一个元素a<b，返回1表示p指向的行应该在q指向的行的后面
    else if(a[0] < b[0]) return -1; //第一个元素a>b，返回-1表示p指向的行应该在q指向的行的前面
    else if(a[1] > b[1]) return 1; //此时一定第一个元素a=b，判断第二个元素
    else if((a[1] < b[1]) return -1;
    else return 0; //第一个，第二个元素均相等，返回0表示p指向的行和q指向的行无确定前后关系
}
int main()
{
  //调用qsort函数对二维数组int data[1000][2]前n行根据规则进行排序：
  qsort(data, n, sizeof(data[0]), cmp);

    return 0;
}

快排自己写版本（可修改规则）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<stdio.h>
int a[100005]；
//快速排序
void quick_sort(int num[], int low, int high)
{
    int i=low,j=high,temp,tmp=a[low];
    //任命为中间分界线，左边比他小，右边比他大,通常第一个元素是基准数
    if (i > j)  return;  //如果下标i大于下标j，函数结束运行

    while (i != j)
    {
        while (num[j]>=tmp&&j>i)  j--;
        while (num[i]<=tmp&&j>i)  i++;

        if (j>i)  {temp = num[j];num[j] = num[i];num[i] = temp;}
    }

    num[low] = num[i];num[i] = tmp;

    quick_sort(num, low, i - 1);
    quick_sort(num, i + 1, high);
}
int main()
{
    quick_sort(a,l,r);  //a为数组名，l为排序左端，r为排序右端

    return 0;
}

二分查找AC版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<stdio.h>
int a[500010];
int lfind(int a[],int k,int l,int r)
{
    int mid=(l+r)/2;
    //为什么不+1：偏向左端
    while(l<r)
    {
        if(a[mid]>=k)  r=mid;  //这个=很关键
        else  l=mid+1;

        mid=(r+l)/2;
    }

    if(a[mid]==k)  return mid;
    else  return -1;
}

int rfind(int a[],int k,int l,int r)
{
    int mid=(l+r+1)/2;
    //为什么要+1：偏向右端
    while(l<r)
    {
        if(a[mid]<=k)  l=mid;  //这个=很关键
        else  r=mid-1;

        mid=(l+r+1)/2;
    }

    if(a[mid]==k)  return mid;
    else  return -1;
}

int main()
{
    int n,t,k,i,l,r;
    scanf("%d%d",&n,&t);
    for(i=0;i<n;i++)  scanf("%d",&a[i]);

    while(t--)
    {
        scanf("%d",&k);

        l=lfind(a,k,0,n-1);
        if(l!=-1)
        {
            r=rfind(a,k,l,n-1);

            if(r==l)  printf("%d\n",r);
            else  printf("%d %d\n",l,r);
        }
        else  printf("-1\n");
    }

    return 0;
}

指针

strstr

1
2
3
4
5
char s[100];
char *p=s;

gets(s);gets(a);
p=strstr(s,a);

返回在s中a子串出现的第一个位置

如果想要返回所有位置呢？

控制循环结构，利用while语句，只要返回的指针不为NULL，就进行下一次的strstr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[100],b[100];
char *p1=a,*p2=0;	//预先定义，避免p1、p2成为野指针
fgets(a,100,stdin);	//利用fgets，更安全地读入字符
gets(str);			//读入需要替换打印的字符str

while(p2=strstr(p1,str))
{
    while(p1<p2)	//判断所查找内容不会出现在上一次替换的内部
    {
        putchar(*p1);
        p1++;		//将p1指针移向下一位
    }

    printf("%s",str);
    p1=p2+strlen(str);	//将p1指针后移，下一次查找的起点
}
fputs(p1,stdout);

与字符串相关的库函数

strlen

strlen用于计算字符串的长度，返回值为int型
在循环遍历中应该事先

1
2
int l=strlen(s)
for(i=0;i<l;i++)

不然每一次运行i<strlen(s)时都会遍历一次s，大大增加时间复杂度

sscanf

sscanf需要配合gets和scanf使用，用来对已经读入的一串字符串进行格式匹配

1
int sscanf(const char *str,const char *format,...)

数值形数据的转换

整形：

1
2
3
4
5
int year, month, day;
int converted;

converted = sscanf("20191103", "%04d%02d%02d", &year, &month, &day);
printf("converted=%d, year=%d, month=%d, day=%d/n", converted, year, month, day);

输出结果为：

1
converted=3, year=2019, month=11, day=03

浮点型：

1
2
3
4
5
6
double longitude, latitude;
int converted;

converted=sscanf("113.123456789 31.123456789", "%lf %lf", &longitude, &latitude);

printf("converted=%d, longitude=%.9lf, latitude=%lf/n", converted, longitude, latitude);

输出结果为：

1
converted=2, longitude=113.123456789, latitude=31.123457

可以看到sscanf的格式为sscanf(“%s”,“%04d%02d %lf”,&a,&b,&c);

即为(“读入数组”,“要求匹配的格式”)

截断

这样的输出格式匹配也可以用来截断一段字符串
如：

1
2
sscanf("12345","%4s",str);
printf("%d",a);

输出结果为：

1
1234

也可以根据空格将gets读入的整行分为不同的字符串

1
2
3
4
char str1[100], str2[100], str3[100];
gets(str1);
sscanf(str1,"%s%s",str2,str3);
printf("%s %s\n",str2,str3);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输入：i love c
输出：i love
````

## strcmp：比较两个字符串的字典序
按照字典序比较字符串 str1 和 str2 之间的大小关系，返回值为int型
如果 str1>str2 ，返回正数；如果 str1<str2 ，返回负数；否则返回 0 。
### 比较规则：
(1)从两个字符串的第一个字符开始比较，如果相同，则比较下一个，直到遇到不同字符，那么排在字母表前面的字符小于排在后面的（可以认为比较二者的 ASCII 码）；
(2) 如果两个字符串所有的字符都相同，则二者相等；
(3) 如果一个字符串提前结束，那么长的那个字符串大于短的那个字符串。

### 引入指针按字典序进行排序
在编写快排中的cmp规则时，应该如下写：
```c
int ctrcmp(const void *p1, const void *p2)
{
    char *a = (char *)p1;
    char *b = (char *)p2;
    return strcmp(a, b);
}

也即，自定义快排规则时，应该将原先void的指针强制类型准换为所需类型，再进行转换

strcpy：进行字符串数组之间的复制

将字符串src中的内容复制到字符型数组dst中，复制结束后 dst 的字符串内容和src一样
会将字符串尾部的’\0’也复制到字符串中，要注意甄别

strncpy：将字符串src中最多n个字符复制到字符型数组dst中

1
char* strncpy (char* dst , const char* src , size_t n);

可以认为n为元素个数

如果字符串src的有效长度（不包含结束符）小于n，则strncpy与strcpy的作用相同，实现字符串的复制；
否则，只把src中前n个字符复制到dst数组中（无法保证复制后的dst是个合法字符串，因为无法保证src第n个字符是结束符）；
如果dst的有效长度大于等于n，则相当于改写了dst的前n个字符为src的前n个字符

memcpy

1
void * memcpy ( void * dest, const void * src, size_t num );

memcpy()会复制src所指的内存内容的前num个字节到dest所指的内存地址上。

可以看到，这类字符串函数实际上使用的都是指针地址，数组名也是用作地址使用的

memcpy可以进行数组间n个元素的复制，且特别在于memcpy并不关心被复制的数据类型，只是逐字节地进行复制，这给函数的使用带来了很大的灵活性，可以面向任何数据类型进行复制。

strcpy、strncpy、memcpy的联系与区别

注意：如果在字符串内部完整复制一段较短的字符串，F不能使用strcpy，因为会将末尾的’\0’也复制到字符串中，造成字符串的截断

那么这个时候，就可以使用strncpy或是memcpy这两个函数，选取只复制strlen(ch)的内容，不复制末尾的’\0’

strcat：拼接猫猫🐱字符串函数

1
char* strcat (char* dst, const char* src)
1
2
char dst[1010],str[110];
strcat(dst,str)

将字符串 src 追加到字符串 dst 的尾部。
注意，字符数组dst的空间大小要保证能够容纳追加后形成的字符串。

关键：src末尾的’\0’用于判断字符串是否结束

strncat：将字符串src中最多前n个字符追加到字符串dst的尾部，并在最后添加一个’0’。

1
char* strncat (char* dst , const char* src , size_t n);

如果src的有效字符数（不包括结束符）小于等于n，则strncat与 strcat 等价；否则只将前n个字符追加到 dst 尾部。

strcpy和strcat的区别（str，ch）

strcpy为复制：将ch的内容从i=0开始赋值到str[i]内
strcat为追加：将ch的内容从str的末尾开始赋值

strstr：找出现的第一个字串

1
char *strstr(const char *_Str, const char *_SubStr)

返回类型为指针变量

函数在字符串Str中寻找子串SubStr,如果找到则返回在Str中指向SubStr子串的指针，否则返回空指针NULL。

利用strstr实现不断向后的查找

事实上，strstr是Str作为地址进行向后的查找。也即，Str的数组头名作为地址，提供了查找的起点

可以将Str替换为一个（Str内部的）指针*p，进行从p开始向后的子串查找

例如：实现再mun[210]和som[210]中的子串替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
#include<string.h>
void swap(char *p,char *q)
{
    char c;

    c=*p;
    *p=*q;
    *q=c;
}
char mum[210],son[210];
int main()
{
    int lm,ls,i;
    char *p=mum;
    scanf("%s%s",mum,son);
    ls=strlen(son);

    while((p=strstr(p,son))!=NULL)
    {
        for(i=0;i<ls/2;i++)  swap(p+i,p+ls-i-1);
        p+=ls;  //利用p+ls减少无用的查找，大大提高时间效率
    }
    printf("%s",mum);

    return 0;
}

在这样的代码中while(p=(strstr(p,son))!=NULL)实现了不在已经查找过的部分查找，而是从p+ls不断向后查找

如何判断日期中是否有所需子串

1
2
3
4
5
int islucky(int date) {
    char r[10];
    sprintf(r, "%d", date);
    return strstr(r, "102") == NULL ? 0 : 1;
}

运用sprintf，将数转化为字符串，再利用strstr进行搜索

strchr：搜索所需要的字符或数字

strchr表示在字符串 s 中查找字符 c，返回字符 c 第一次在字符串 s 中出现的位置，如果未找到字符 c，则返回 NULL。

1
char *strrchr(const char *s, int c);

为什么函数的“c”参数是int类型，而不是char类型呢：其实原因很简单，这里用的是字符的 ASCII 码（因为每个字符都对应着一个 ASCII 码），这样在传值的时候既可以传char类型的值，又可以传int类型的值（0~127）。

strrchr：搜索所需要的字符

功能与strchr类似，但是c为char型遍历，只能用于搜索字符

1
char *strrchr(const char * s,char c)

atof：将字符串数字转换为浮点数

需要引入标准库<stdlib.h>
atof()会扫描参数nptr字符串，跳过前面的空格字符，直到遇上数字或正负符号才开始做转换，而再遇到非数字或字符串结束时(‘\0’)才结束转换，并将结果返回。参数nptr字符串可包含正负号、小数点或E(e)来表示指数部分，如123.456或123e-2

1
2
3
4
5
6
double a;
char s[1010];
scanf("%s",s);

a=atof(s);
printf("%lf",a);

一道字符串综合题：E7-I 字符串大练习

时间限制：1000ms 内存限制：65536kb

题目描述

​给出一个待操作字符串 str ，请实现对其的增删改查。具体要求如下：

输入

​第一行一个字符串 str

​接下来不定行，每行表示一次操作，可能为以下情况之一，每行不同内容之间均用一个空格隔开，以下出现的 i,j 表示的位数均从 0 开始计：

  1. 尾接：一个数字 1 ，一个字符串 s ，表示将 s 接到 str 末尾；

  2. 尾删：一个数字 2 ，一个整数 i ，表示删除 str 的第 i 位及其之后的字符；

  3. 插入：一个数字 3 ，一个整数 i ，一个字符串 s ，表示将 s 插入到 str 的第 i 位之前，后面的字符向后顺移；

  4. 删除：一个数字 4 ，两个整数 i,j (i≤j) ，表示删除 str 的第 i 到 j 个字符（包括第 i 和第 j 个），后面的字符向前补位；

  5. 修改：一个数字 5 ，一个整数 i ，一个字符串 s ，表示从 str 的第 i 位开始用 s 覆盖，覆盖是指，从第 i 位开始，将 str 的字符依次替换为 s 的字符，如果 str 长度不够，则向后延长直到 s 结束，如果 s 长度不到 str 结尾，则后续字符保留 str 原字符；

  6. 结束：一个数字 -1 ，表示结束操作。

​最后需要查询字符串出现次数：一个字符串 s ，请输出 s 在 str 中出现的次数（重叠出现也计算在内）。

输出

​输出共两行

​第一行一个整数表示查询结果，即最后查询的字符串 s 在 str 中出现的次数（重叠出现也计算在内）

​第二行一个字符串表示经过若干次操作后最后的 str

样例

输入

1
2
3
4
5
6
7
8
9
aaaaa
1 bbbbbbb
2 10
3 2 bbb
4 7 9
5 8 aabaa
5 1 baa
-1
abaa

输出

1
2
4
abaabaabaabaa

样例解释

每次操作后 str 如下：

第1次操作-1尾接：aaaaabbbbbbb

第2次操作-2尾删：aaaaabbbbb

第3次操作-3插入：aabbbaaabbbbb

第4次操作-4删除：aabbbaabbb

第5次操作-5修改：aabbbaabaabaa

第6次操作-5修改：abaabaabaabaa

最后一次操作之后 str 中有 4 个 abaa

数据范围

str,s 均仅由小写字母组成

保证操作过程中 str,s 长度不超过 10000

操作次数不超过 1000

0≤i≤j<len,len为str长度

Hint

​可能用到头文件string.h中函数strlen,strcat,strcpy,memcpy,strstr

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>
#include<string.h>
char str[20000],s[20000];
int main()
{
    int op,len,pos,i,g=0;
    char *p=str;
    scanf("%s",str);

    while(~scanf("%d ",&op))
    {
        if(op==-1)  break;
        else if(op==1)
        {
            scanf("%s",s);
            strcat(str,s);
        }
        else if(op==2)
        {
            scanf("%d",&pos);
            str[pos]='\0';
            //删去后面的字符串，只需要将第一位赋值为'\0'，注意不是0
        }
        else if(op==3)
        {
            scanf("%d %s",&pos,s);
            strcat(s,str+pos);
            strcpy(str+pos,s);
            //这里十分巧妙地实现了中间插入，先将后面的部分拼接到插入末位，再将字符串覆盖复制
        }
        else if(op==4)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            strcpy(str+l,str+r+1);
        }
        else if(op==5)
        {
            scanf("%d %s",&pos,s);
            len=strlen(s);
            strncpy(str+pos,s,len);
        }
    }

    scanf("%s",s);p=str;
    while((p=strstr(p,s))!=NULL)
    {
        g++;
        p++;
    }
    printf("%d\n%s",g,str);

    return 0;
}

算法

动态规划

贪心算法

贪心算法是在局部处处采用最优解，以尽可能达到全局最优解

01背包问题

为什么叫做01：对于每一个值，只有取或不取两种情况，在求和算符中可以表示为该值0或该值1，故称作01背包问题

利用01背包问题不断尝试在一定范围内的最优解

以下jo[]为每个角度的个数，代码意思为如何获得最接近180°的取值情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
f[0]=1;
for (int i = 0; i < 360; ++i)// 遍历得到每一种可能到达的角度
{
    while (jo[i]--)
    {
        for (int j = 720; j >= 0; --j)
        {
            if (f[j])
            {
                f[(j + i) % 720]++;
                minn = min(minn, abs((i + j) % 360 -180));
                //找到最接近180的角度
            }
        }
    }
}

数学相关知识

高精度pi：double pi=acos(-1)

如果使用定义pi=3.14，在高精度运算中可能因为pi的值出现较大误差，利用<math.h>中提供的反三角函数求出高精度pi的值

1
pi=acos(-1)

凸四边形与凹四边形

如果在四边形内部有一点，到四边形各顶点的距离和最短
那么，对于不同的四边形：

凸四边形：对角线的交点

凹四边形：凹进去的那个顶点

如何判断凹进去的那个顶点呢：利用向量

如果是凹进去的顶点，那么一定有该顶点出发的两边向量点乘小于0；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int x[5],y[5],i,j,k,d[5],flag=0;
double l=0;

for(i=1;i<=4;i++)  scanf("%d%d",&x[i],&y[i]);

for(j=1;j<=4;j++)
{
    for(k=1;k<=4;k++)
    {
        if(k<=3)  d[j]=(x[k]-x[j])*(x[k+1]-x[j]);
        if(k==4)  d[j]=(x[4]-x[j])*(x[1]-x[j]);

        if(d[j]<0)  flag=j;
    }
}

判断区间内n的倍数个数

如何判断[l,r]区间内n的倍数的个数

1
2
3
4
5
6
7
int l,r,a;
scanf("%d%d",&l,&r);

a=r/n-l/n;
if(l%n)  a++;

printf("%d",a);

如何判断(l,r)区间内n的倍数的个数

1
2
3
4
5
6
int l,r,a;
scanf("%d%d",&l,&r);

a=r/n-l/n;

printf("%d",a);

到一系列点的距离和的最小值

如果定义了距离为d((x1,y1,z1),(x2,y2,z2))=∣x1−x2∣+∣y1−y2∣+∣z1−z2∣d((x_1,y_1,z_1),(x_2,y_2,z_2))=|x_1−x_2|+|y_1−y_2|+|z_1−z_2|

使用绝对值求和，那么实际上x、y、z彼此无关，点的取值可以分别在x的最值处、y的最值处、z的最值处取得，最后的点几位这三个坐标的组合

简单模拟可以发现：总在中点处取得最值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
qsort(x,n,sizeof(int),rise);
qsort(y,n,sizeof(int),rise);
qsort(z,n,sizeof(int),rise);

if(n%2)
{
    ax=x[n/2];
    ay=y[n/2];
    az=z[n/2];
}
else
{
    ax=(x[n/2]+x[n/2-1])/2;
    ay=(y[n/2]+y[n/2-1])/2;
    az=(z[n/2]+z[n/2-1])/2;
}

排序问题

排序问题的通性通法；建立数组+递归

隔板排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<stdio.h>
int a[21],sum=0,n,k;

void pn(int t,int g)
{
    int i;

    if((g==0&&t)||(t==0&&g))
        return;
    if(g==0&&t==0)
    {
        for(i=1;i<=k;i++)  printf("%d ",a[i]);
        printf("\n");
        sum++;
        return;
    }

    for(i=1;i<=t-g+1;i++)
    {
        a[k-g+1]=i;
        pn(t-i,g-1);
    }
}

int main()
{
    scanf("%d%d",&n,&k);

    pn(n,k);
    printf("%d",sum);

    return 0;
}

排序1~n的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h>
int n,a[10];

int Check(int m)
{
    int i,t,b[10],flag=0;

    for(i=0;i<10;i++)  b[i]=0;
    for(i=1;i<=m;i++)
    {
        t=a[i];
        b[t]++;
    }
    for(i=1;i<=n;i++)
        if(b[i]>1)  flag=1;

    if(flag)  return 0;
    else  return 1;
}

void pn(int m)
{
    int i,j,flag=0;

    if(Check(n-m)==0)
        return;

    if(m==0&&Check(n))
    {
        for(i=1;i<=n;i++)
            printf("%d ",a[i]);
        printf("\n");

        return;
    }

    for(i=1;i<=n;i++)
    {
        a[n-m+1]=i;

        pn(m-1);
    }
}

int main()
{
    scanf("%d",&n);
    pn(n);

    return 0;
}

旅行计划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<stdio.h>
int a[10];
int n,m,l,sum=0,g;

void go(int s,int t)
{
    int i,j;

    if(t==1)
    {
        a[g-t+1]=s;
        for(j=1;j<=g;j++)  printf("%d ",a[j]);
        printf("\n");
        sum++;

        return;
    }

    for(i=0;i<=s-1;i++)
    {
        a[g-t+1]=i;
        go(s-i,t-1);
    }
}

int main()
{
    int i;
    scanf("%d%d%d",&n,&m,&l);

    for(g=m;g<=l;g++)
        go(n,g);
    printf("%d",sum);

    return 0;
}

反约瑟夫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<stdio.h>
int n,m;
int b[1005];

int z(int h)
{
    if(h%n)  return h%n;
    else  return n;
}

void get(int a,int t)
{
    int i,g=m,flag;

    if(a==0)
    {
        for(i=1;i<=n;i++)  printf("%d ",b[i]);
        return;
    }

    for(i=1;g>0;i++)
    {
        if(b[z(t+i)]==0)
        {
            g--;
            flag=i;
        }
    }

    b[z(t+flag)]=n-a+1;
    get(a-1,z(t+flag));
}

int main()
{
    int i;
    scanf("%d%d",&n,&m);

    for(i=1;i<1005;i++)	b[i]=0;

    get(n,0);

    return 0;
}

又臭又长之思考题目系列

写 在前面：

这里收录了我觉得需要思考的题目，这些题目大多出在E赛，因为真正的考试中很难有足够的时间来思考这些问题

但何乐而不为呢，纸笔加上IDE，足以解出这些巧妙的问题

E1-I 组三角形

题目描述

你和派蒙来到了梦中的桓那兰纳，在这里你们遇到了兰罗摩。兰罗摩给派蒙介绍了一个游戏：

兰罗摩拿出长度为1到 n 的 n 条木棒，派蒙和他轮流从中取出一根，直到只剩下3根木棒。若剩下的三根木棒可以拼成一个三角形（即三根木棒的长度 a,b,c 满足∣a−b∣<c<(a+b)|a−b|<c<(a+b)，那么先手的派蒙获胜，否则兰罗摩获胜。

兰罗摩告诉派蒙，如果派蒙获胜就会把自己珍藏的“暴葬”送给她。派蒙很想要“暴葬”，但是派蒙和超级白化漂浮灵一样笨，你能告诉他他是否能获胜吗？因为兰罗摩很珍惜他的“暴葬”，所以他会采用最优解。

输入格式

第一行一个整数 T ，代表游戏进行的次数。

第 2 到 T+1 行，每行一个整数 n ,代表该次游戏木棒的数量。

输出格式

输出 T 行。

对于第 i 行，若派蒙能在第 i 次游戏获胜，则输出Yes，否则输出No。

样例输入

1
2
1
7

样例输出

1
No

数据范围

对于100%的数据，0<T<10，3<n<1030<T<10，3<n<10^3

示例代码

这道题的灵魂：什么是两个人相对的最优方法？

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
int main()
{
    int T;
    scanf("%d",&T);
    int n[T+1];

    for(int i=1;i<=T;i++)
    {
        scanf("%d",&n[i]);
        if(n[i]%2==0)  printf("Yes\n");
        else  printf("No\n");
    }
    return 0;
}

E2-G 魔法实验 1.0

题目背景

Patchouli Knowledge 是一个生活在大图书馆的魔法使，已经活了百年之久，是一位有着丰富魔法经验的魔女。她可以熟练地使用七种属性（火、水、木、金、土、日、月）的魔法，并将其中几种组合起来释放出更强的力量。最近，她准备研究一种终极魔法，将这七种属性全部结合起来。

题目描述

为了研究融合魔法，Patchouli 需要做 T 次实验。她找来了 n 个魔法容器，并注入不定量的魔力值，可用 a1,a2,…,an 来表示。Patchouli 在实验中可以进行两种操作：

融合：她可以选择两个容器并融合它们的魔力值，得到一个新的容器，其魔力值等于原两个容器魔力值的和，而原容器将被舍弃；

浓缩：她可以选择一个魔力值为偶数 a 的容器，将其中的魔力值浓缩，变为 a2。

在多次实验后 Patchouli 发现，当所有非空容器的魔力值都为奇数时，感应出的灵力会更强。为了快速研究出融合魔法，她需要用最少的操作次数来达成这个条件。

输入

多组数据输入。

第一行一个整数 T，表示数据组数。

对于每组数据：

第一行一个整数 n，表示容器的个数；

第二行 n 个整数 ai，表示第 i 个容器中的魔力值。

输出

共 T 行。

每组数据输出一行一个整数，表示把所有容器中的魔力值变成奇数的最小操作次数。

样例

输入

1
2
3
4
5
6
7
3
2
8 3
3
1 7 3
3
8 4 4

输出

1
2
3
1
0
4

数据范围

1≤T≤103，1≤n≤105，1≤ai≤1091≤T≤103，1≤n≤105，1≤a_i≤109

对于所有测试点，∑n≤2×105∑n≤2×10^5。

示例代码

如何思考这样的问题：在纸上面模拟

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<stdio.h>
#include<math.h>
int main()
{
    int t,n,i,j,k,p,e,m=0,temp,flag=0,min=100;
    long long a[100001];
    scanf("%d",&t);

    for(i=1;i<=t;i++)
    {
        scanf("%d",&n);
        p=0;

        for(j=1;j<=n;j++)
        {
            scanf("%lld",&a[j]);
            if(a[j]%2==0)  p++;
        }


        if(p==0)  m=0;
        else if(p==n)
        {
            for(k=1;k<=n;k++)
            {
                e=0;temp=a[k];
                while(temp%2==0)
                {
                    e++;
                    temp=temp/2;
                }

                if(e<min)  min=e;
            }

            m=min+p-1;
        }
        else  m=p;

        printf("%d\n",m);
    }

    return 0;
}

E3-G 二舅也许能治好我的精神内耗

题目描述

厌倦于大城市里的浮躁与追名逐利，今天我回到了农村老家里，遇到了二舅,他给了我一个整数n,告诉我如果潜心探究出三个整数a,b,c满足(a⊕b)+(b⊕c)+(a⊕c)=n,那么就能治好我的精神内耗。

这里a⊕b表示将a和b进行异或运算。比如1⊕2=3,2⊕3=1。

输入描述

第一行一个整数t，表示有t个测试样例。(1≤t≤1031≤t≤10^3)
接着输入t行，每一行一个整数n。(1≤n≤1091≤n≤10^9)

输出描述

输出t行，输出满足条件的三个整数a,b,c，如果不存在满足条件的三个整数，输出−1。

本题每个样例均可能存在多种输出满足题意。请输出其中任意一种即可。

输入样例

1
2
3
4
5
6
5
4
1
12
2046
194723326

输出样例

1
2
3
4
5
3 3 1
-1
2 4 6
69 420 666
12345678 87654321 100000000

样例解释

在第一个测试样例中，a=3,b=3,c=1,(3⊕3)+(3⊕1)+(3⊕1)=0+2+2=4

第二个测试样例无解,输出−1。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
int main()
{
    int t,a,i;
    scanf("%d",&t);
    for(i=0;i<t;i++)
    {
        scanf("%d",&a);
        if(a%2==0)  printf("0 0 %d\n",a/2);
        else  printf("-1\n");
    }

    return 0;
}

E4-F Cirno 的完美位运算教室

题目背景

寺子屋的教学并不能满足 Cirno 的求知欲，她找到了擅长计算的 Yakumo Ran 学习数学。众所周知，Ran 是 Yakumo Yukari 的式神，而在幻想乡式神就是电脑，所以 Ran 教给了 Cirno 一些位运算的相关知识。

题目描述

Ran 告诉了 Cirno 一个正整数 x ，让她找到一个满足下列条件的最小正整数 y：

x and y>0
x xor y>0

此处 and 表示按位与，xor 表示按位异或。

输入

多组数据输入。

第一行一个整数 T，表示数据组数。

接下来 T 行，每行一个正整数 x，含义见上。

输出

每组数据一行，一个正整数 y，表示答案。

样例

输入

1
2
3
4
5
6
7
6
75
36
15
78
15
34

输出

1
2
3
4
5
6
1
4
1
2
1
2

数据范围

1≤T≤103，1≤x≤2301≤T≤10^3，1≤x≤2^30

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<stdio.h>
#include<math.h>
int main()
{
    int t;
    long long x,y;
    scanf("%d",&t);

    for(int i=0;i<t;i++)
    {
        scanf("%lld",&x);y=1;
        if(x==1)
        {
            printf("3\n");
            continue;
        }

        if(x%2!=0)  y=1;
        else
        {
            while(x%2==0)
            {
                x=x/2;
                y*=2;
            }
            if(x==1)  y++;
        }

        printf("%lld\n",y);
    }

    return 0;
}

E4-G 魔理沙的行窃预兆-I

题目描述

雾雨魔理沙今天也一如既往地来到伏瓦鲁魔法图书馆进行『行窃预兆』，窥觊着图书馆丰富的魔法书资源。

但馆主帕秋莉·诺蕾姬早有准备，在通往图书馆的路径上布下了繁杂的传送魔法阵，这些魔法阵会限制魔理沙的行动。

通向图书馆的路径是一条由正整数组成的长链，如上图。每个格子上的数字表示魔理沙从此格出发行走一步最远能够向右移动几格，例如 4 代表魔理沙从这一格出发一步只能向右移动一格、两格、三格或者四格。

现在，魔理沙位于路径最左侧的一格，目的地是位于最右一格的图书馆入口。

魔理沙是个聪明的魔法使，因此她能够以步数最少的方法前进，请你计算以此法前进的魔理沙的行走步数。

输入

输入为两行

第一行，为路径的长度 n

接下来一行，为 n 个由空格分开的正整数，表示路径上从左到右的每一个数字。

输出

一个整数，为魔理沙到达图书馆所需要的最少步数

样例

输入样例

1
2
10
4 1 1 4 3 2 5 1 5 4

输出样例

1
3

样例说明

如图，这是步数最少的路径之一，其长度为 3

数据范围

对于 62.5%的测试点，2≤n≤102≤n≤10

对于 100%的测试点，2≤n≤10002≤n≤1000

路径上的数字不超过 10

Hint

将宏大的，繁杂的目的拆分成多个简单的，容易思考的步骤，或许能提供一些思路。

譬如说，不去直接思考到达终点的最短路线，而先考虑最后一步：我到达终点的最后一步有几种选择？分别需要多少总步数？

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
int a[1001];
int main()
{
    int n,final,f,i,g=0;
    scanf("%d",&n);final=n;
    for(i=1;i<=n;i++)  scanf("%d",&a[i]);

    while(final>1)
    {
        for(i=n;i>0;i--)  if(a[i]+i>=final)  f=i;

        final=f;
        g++;
    }

    printf("%d",g);

    return 0;
}

E4-H 希卡式打孔纸带·alter

时间限制：1000ms 内存限制：65536kb

题目描述

希卡族的科技已经失传了很久。在复原遗迹中的技术时，公主复原出了古老的程序编辑器的beta版。这种编辑器可以从初始值 1 开始，编辑一个三十二位二进制数。编辑器支持两种操作：左移位（一位）和按位取反。作为公主最忠诚的随从，你要找到编辑得到某个三十二位二进制数（补码）的最少步骤。

输入

多组输入。每行一个int范围内的整数，代表编辑目标。不超过一万组输入。

输出

对于每组数据，输出一个整数，代表最少编辑次数。某个数无法通过编辑得到时，输出-1。

输入样例

1
2
3
-2

输出样例

1
2
3
1

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdio.h>
int main()
{
    long long a;
    int g=0;

    while(~scanf("%lld",&a))
    {
        g=0;
        if(a==0)
        {
            printf("32\n");
            continue;
        }
        if(a==-1)
        {
            printf("33\n");
            continue;
        }

        while(a!=1&&a!=-2)
        {
            if(a%2)  a=-a-1;
            else a=a/2;

            g++;
        }

        if(a==-2)  g++;

        printf("%d\n",g);
    }

    return 0;
}

C6-H I Appreciate Your Creativity.

时间限制：1000ms 内存限制：65536kb

题目背景

很多时候，人对于自己的能力难以做出恰当的判断。当我们一心认为自己已经有了了不起的成就的时候，往往会忘记如何脚踏实地，会误以为自己所了解的就是别人所了解的，认为自己所相信的就是别人所相信的，认为自己所接受的就是别人所接受的。

但世界上还有很多东西比人类更复杂，也有很多东西比人类更理性。比如 oj。

助教团队最近有一个烦恼，就是如何回应“我觉得我的代码很对，为什么会 WA”的提问（虽说有的助教当年也问过这个问题）。现在交给你某一道题的正确输出和待评测输出。你要对其正确性进行评判。

题目描述

现在交给你某一道题的正确输出和待评测输出。你要对其正确性进行评判。

虽然已经告诉了你唯一的正确答案，那道题目的内容已经无关紧要，但简单说明一下：这道题模拟的是几个人之间的交易。每个人初始有一元钱，经过若干次交易，求每个人持有的金钱量。所以，保证所有人最后财产的总和，仍与人数相等。

输入

两行输入。第一行以 STD: 开始，随后是用空格分开的 n 个整数，这是正确答案。

第二行以 ANS: 开始，随后是用若干空格分割的 m 个整数，这是待评测答案。

保证两行的所有整数之和分别等于 n 和 m （并没什么用），保证输入整数的格式均是一般的十进制整型。

输出

第一行，输出 Expected: %d, Received: %d，两处 %d 请输出 n 和 m 。

第二行，若两行的所有整数值完全相同（要求顺序一致），输出 Good Job! 表示对作对本题同学的祝贺。否则，这个输出一定忽略了某些细节，或者是对题面有一些“创新”的理解。此时，输出 I Appreciate Your Creativity 表示对有创新性的同学的鼓励。

样例输入

1
2
STD: 1 2 3 0 0 0
ANS: 1 3 2 0 0 0

样例输出

1
2
Expected: 6, Received: 6
I Appreciate Your Creativity

数据范围

n,m 以及输入总长不超过 5000 。

另外，以下Hint不保证对解题有帮助。

Hint1

如果你尝试了提交，你可能已经 WA 了。如果你 WA 了本题，下面的内容可能对你有帮助：

I Appreciate Your Creativity
希望你有被鼓励到。

Hint2

本题也可以用哈希过。

Hint3

scanf 的返回值不为 EOF 时，代表有效输入个数。

Hint4

sscanf 可以从字符数组进行输入。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
#include<string.h>
char std[5010][5010];
int main()
{
    int n,m,flag=1,state=0,x=0,y=0;
    char temp[5010];

    while(~scanf("%s",temp))
    {
        if(strcmp(temp,"STD:")==0)  state=1;
        else if(strcmp(temp,"ANS:")==0)  state=2;
        else if(state==1)
        {
            strcpy(std[x],temp);
            x++;
        }
        else if(state==2)
        {
            if(strcmp(std[y],temp))  flag=0;
            y++;
        }
    }
    if(x!=y)  flag=0;

    printf("Expected: %d, Received: %d\n",x,y);

    if(flag)  printf("Good Job!");
    else  printf("I Appreciate Your Creativity");

    return 0;
}

E6-I 贤者之石

时间限制：1000ms 内存限制：65536kb

题目描述

为了祝贺 Flandre Scarlet 夺得人气冠军，Patchouli Knowledge 用贤者之石为她制作了新的 LED 灯。Flandre 挑选了两种颜色的宝石，分别可以用 R 和 B 表示。

由于她还不太会控制自己的力量，所以 Patchouli 需要让贤者之石以特定的组合来达到较低的能级。已知当一串宝石中 R 和 B 的数量相等时，能量最低。

Flandre 想知道，Patchouli 送给她的一串 LED 中，能量最低的连续宝石子串的长度最大为多少。

输入

一行一个由 R 和 B 组成的字符串 s。

输出

一行一个整数，表示答案。

样例

输入

1
BRBBBRBRR

输出

1
8

样例解释

RBBBRBRR 为稳定且最长的连续宝石子串。

数据范围

1≤∣s∣≤2×1051≤|s|≤2×10^5

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<stdio.h>
#include<string.h>
char s[200010];
int p[300010];
int main()
{
    int sum=0,N=100010,i,l,max=0;
    scanf("%s",s);l=strlen(s);

    for(i=1;i<=l;i++)
    {
        sum+=(s[i-1]=='B')?1:-1;
        if(p[sum+N]==0&&sum!=0)  p[sum+N]=i;
        else  max=(max>(i-p[sum+N]))?max:(i-p[sum+N]);
    }
    printf("%d",max);

    return 0;
}

/*
注意特判：
BRBR……的情况
即始终有s==0，第一次出现在i=0时
*/

E6-H 哪吒的区间合并（1）

时间限制：1000ms 内存限制：65536kb

题目描述

​给出若干个端点为正整数的闭区间，请进行区间合并，将这些区间合并为不相交的闭区间。

输入

​不定行输入，每行两个空格隔开的正整数 left,right ，表示区间 [left,right]

输出

​输入若干行，表示合并后的区间

​每行包含两个空格隔开的正整数 left,right ，表示区间 [left,right]，各个区间请按升序排列输出。

样例

输入

1
2
3
4
5
6
1000 6666
114514 810975
6666 12345
555 999
5 666
100000 100002

输出

1
2
3
4
5 999
1000 12345
100000 100002
114514 810975

数据范围

​
输入区间个数不超过 106 个

​1≤left<right≤106

Hint

​可以用数组存储区间，每次读入区间，左端点为数组元素的下标，右端点为数组元素的值，最后遍历数组进行合并。

​每次读入区间，也可以标记数组下标分别为区间左端点和右端点的元素，最后遍历一遍输出区间。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
int s[1000010];
int main()
{
    int l,r,g=0,i;

    while(~scanf("%d%d",&l,&r))
    {
        if(r>s[l])  s[l]=r;
    }

    for(l=0;l<=1000000;l++)
    {
        if(s[l]==0)  continue;

        printf("%d ",l);

        for(r=s[l];l<=r;l++)
            if(s[l]>r)  r=s[l];

        l--;
        printf("%d\n",l);
    }

    return 0;
}

/*
这个的循环内部有l的跳跃
不是一般的for语句
*/

E7-C 收集石樱

时间限制：1000ms 内存限制：65536kb

题目描述

熙熙攘攘的旧地狱街道，不时飘落点点樱花，那是灵魂的结晶所凝结而成的粉色石头，被称为「石樱」。

石樱是怨灵们的最爱。

有一个怨灵正在旧地狱收集石樱。石樱分布在编号从 1 到 n 的 n 个节点上。起初，第 i 个节点上的石樱数量为 ai。

它可以选择一个节点作为出发地，每经过一个单位时间，会依次发生如下事件：

  1. 怨灵从节点 a 飘到 b；(|a−b|≤1)
  2. 它收集节点 b 的所有石樱；
  3. 每个节点长出一个新的石樱。
  4. 它想知道，在 m 个单位时间内，最多能收集多少石樱。

输入

第一行一个整数 T ，表示数据组数。

对于每组数据：

第一行两个整数 n,m ，含义见上；

第二行 n 个整数 a1,a2,…,an，ai 表示第 i 个节点的初始石樱数量。

输出

每组数据一行一个整数，表示 m 个单位时间内收集的石樱数量最大值。

样例

输入

1
2
3
4
5
2
8 6
2 6 9 5 10 3 8 7
8 11
3 2 2 2 7 2 1 7

输出

1
2
57
78

样例解释

对于第一组数据，可能的最大路径如下：选取节点 2 为起点，2−3−4−5−6−7−8；

对于第二组数据，可能的最大路径如下：选取节点 5 为起点，5−4−3−2−1−2−3−4−5−6−7−8。

数据范围

1≤T≤104，1≤n≤105，1≤ai≤109，1≤m≤1091≤T≤10^4，1≤n≤10^5，1≤ai≤10^9，1≤m≤10^9。

对于每个测试点，∑n≤2×105∑n≤2×10^5。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
long long a[100010],s[100010];
int main()
{
    int t,i;
    long long n,m,max,tm;
    scanf("%d",&t);

    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            s[i]=s[i-1]+a[i];
        }

        max=0;
        if(m<n)
        {
            for(i=m;i<=n;i++)
            {
                tm=s[i]-s[i-m];
                max=(max>tm)?max:tm;
            }

            max+=(m-1)*m/2;
        }
        else
        {
            max=s[n]-s[0];
            max+=m*n-n*(n+1)/2;
        }

        printf("%lld\n",max);
    }

    return 0;
}

思考：

如果m>n时，如何计算后续增加的石樱？
m>n的情况，所有原先的石樱都能够被收集，影响路径选择的似乎只有后续增加的石樱
那么在这种情况下，直接求解是相当难的

运用逆向思维：

总共增加n*m个，未收集的部分当前所在为1，刚离开为2……且以n为一个循环周期
那么未收集的部分总共有（n+1）*n/2
则收集的部分为m * n-(n+1)*n/2

E8-D Rex的隐身

时间限制：1000ms 内存限制：65536kb

题目描述

眼镜的好舍友 Rex 因为私藏罐装知识要需要躲避教令院的追捕，作为他的好朋友，为了帮助 Rex 脱困，眼镜决定黑进虚空终端，在通缉令上将有关 Rex 的所有可能信息划去。具体规则如下：

通缉令为一行仅有大小写字母的字符串，眼镜需要不区分大小写地将上面先后出现的R，e，x字符删掉，不论中间是否有其他字符间隔。

对于长度为 n 的字符串，从第一个字符开始依次赋予 1,2,3…n 的权值。删去时，若存在多个Rex时，优先删掉三个字母权值之和最小的Rex，再删掉权值之和次之的Rex，如此重复至删除所有的Rex为止。

例如： rqeqxqre 的删除结果为 qqqre

输入

一行，一串字符串表示通缉令

输出

一行，表示眼镜修改后的通缉令

输入样例

RexloveStudybutstudyemmmrx

输出样例

loveStudybutstudyemmmrx

数据范围

字符串长度不超过 500000

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<stdio.h>
#include<string.h>
char s[500010];
int r[500010],e[500010],x[500010];
int main()
{
    int l,i,l1=0,l2=0,l3=0,a=0,b=0,c=0;
    gets(s);
    l=strlen(s);

    for(i=0;i<l;i++)
    {
        if(s[i]=='r'||s[i]=='R')  {r[l1]=i;l1++;}
        else if(s[i]=='e'||s[i]=='E')  {e[l2]=i;l2++;}
        else if(s[i]=='x'||s[i]=='X')  {x[l3]=i;l3++;}
    }

    while(a<l1&&b<l2&&c<l3)
    {
        while(e[b]<r[a])  b++;
        while(x[c]<e[b])  c++;

        if(a<l1&&b<l2&&c<l3)
        {
            s[r[a]]=1;s[e[b]]=1;s[x[c]]=1;
            a++;b++;c++;
        }
    }

    for(i=0;i<l;i++)
        if(s[i]>1)  printf("%c",s[i]);

    return 0;
}

E8-G 魔法实验 3.0

时间限制：1000ms 内存限制：65536kb

题目背景

Kirisame Marisa 在弹幕游戏中败给了 Patchouli Knowledge ，因为 Patchouli 使用的魔法太强大了，她能熟练的使用七种属性（火、水、木、金、土、日、月）的魔法。Marisa 希望精进自己的魔法水平，在她的央求下， Patchouli 同意给她演示两种属性（火、水）魔法的实验。

题目描述

Patchouli 从她的七曜水晶中挑选出了火和水两种属性的水晶，同一些没有注入魔力的空水晶一起排成了一字法阵。水晶共 n 个，从左往右依次编号为 1,…,n，每个空水晶都可以注入火或水的魔力。其中，有 f 个水晶已经注入了火魔力，这些水晶的编号分别为 x1,…,xfx_1,…,x_f；有 w 个水晶已经注入了水魔力，这些水晶的编号分别为 y1,…,ywy_1,…,y_w。

现在，Patchouli 需要向空水晶中注入火或水魔力。为了使不同的魔力交汇在一起，释放出更强的能量，她需要让有相同属性的相邻水晶对的数量最少。

例如，若用 ■ 表示火属性水晶，■ 表示水属性水晶，□ 表示空水晶，n=7 时初始水晶法阵状态为 □■□□□■■ ，注入魔力后 ■■■■■■■ 为最优方案之一，有相同属性的相邻水晶对仅为 □■■□□□□，因此有相同属性的相邻水晶对的数量最小值为 1。

Patchouli 当然知道如何释放出更强的能量，但她想考考 Marisa 对这个魔法的了解程度。

输入

第一行，三个非负整数 n,f,w，表示总水晶数，初始火属性水晶数，初始水属性水晶数；

第二行，f 个正整数 x1,…,xf，表示初始火属性水晶编号；

第三行，w 个正整数 y1,…,yw，表示初始水属性水晶编号。

特别地，若 f=0，则输入第二行为空行；若 w=0，则输入第三行为空行。

输出

一行，一个整数，表示相同属性的相邻水晶对的数量最小值。

样例

输入 #1

10 0 1

7

输出 #1

0

输入 #2

7 2 1

7 2

6

输出 #2

1

数据范围

对于全部数据，1≤n≤105，0≤f+w≤n，1≤xi,yi≤n1≤n≤10^5，0≤f+w≤n，1≤x_i,y_i≤n。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
int a[100010];
int main()
{
    int n,f,w,min,x,g=0,i,p;
    scanf("%d%d%d",&n,&f,&w);min=n;
    for(i=0;i<f;i++)
    {
        scanf("%d",&p);p--;a[p]=1;
        min=(min<p)?min:p;
    }
    for(i=0;i<w;i++)
    {
        scanf("%d",&p);p--;a[p]=2;
        min=(min<p)?min:p;
    }
    x=min;

    for(i=min+1;i<n;i++)
    {
        if(a[i])
        {
            if(a[x]!=a[i])  {if((i-x)%2==0)  g++;}
            else  {if((i-x)%2)  g++;}

            x=i;
        }
    }
    printf("%d",g);

    return 0;
}

附录

附一：为什么会出bug

来自E2-A

Q A
助教，我的代码样例是对的，为什么交上去WA了？ 本地对了就是对了，交上去WA说明评测机有问题。
助教，我的代码为什么过不去样例啊。 调试调试。
助教，为什么我的代码没输入完就输出，这怎么办啊？ 没啥问题。在OJ上输入和输出是分开的，不用担心。
助教,我的代码REG是怎么回事？ SIGESGV大约是数组越界了,SIGFPE大约是除以零了。
助教我的代码OE了。 大约是数组越界了。
助教我的代码CE了。 百度一下报错信息。
助教我的代码什么都不输出。 可能是死循环了，如果显示process exited with return value 3221225477等非零数，可以百度百度这个数字的携带的错误信息。
助教你好可爱。 对对对。