学习总结14

# 【CSGRound1】天下第一

## 题目背景

天下第一的 cbw 以主席的身份在 8102 年统治全宇宙后，开始了自己休闲的生活，并邀请自己的好友每天都来和他做游戏。由于 cbw 想要显出自己平易近人，所以 zhouwc 虽然是一个蒟蒻，也有能和 cbw 玩游戏的机会。

## 题目描述

游戏是这样的：

给定两个数 x，y，与一个模数 p。

cbw 拥有数 x，zhouwc 拥有数 y。

第一个回合：x<-(x+y)mod p。

第二个回合：y<-(x+y)mod p。

第三个回合：x<-(x+y)mod p。

第四个回合：y<-(x+y)mod p。

以此类推....

如果 x 先到 0，则 cbw 胜利。如果 y 先到 0，则 zhouwc 胜利。如果 x,y 都不能到 0，则为平局。

cbw 为了捍卫自己主席的尊严，想要提前知道游戏的结果，并且可以趁机动点手脚，所以他希望你来告诉他结果。

## 输入格式

有多组数据。

第一行：T 和 p 表示一共有 T 组数据且模数都为 p。

以下 T 行，每行两个数 x,y。

## 输出格式

共 T 行

1 表示 cbw 获胜，2 表示 zhouwc 获胜，```error``` 表示平局。

## 样例 #1

### 样例输入 #1

```
1 10
1 3
```

### 样例输出 #1

```
error
```

## 样例 #2

### 样例输入 #2

```
1 10
4 5
```

### 样例输出 #2

```
1
```

## 提示

1 <= T <= 200。

1 <= x,y,p <= 10000。

解题思路

运用记忆化搜索，用一个数组来保存对应的x，y的结果。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
short g[10001][10001];
int p;
int dfs(int x,int y)
{int x1,y1;if(g[x][y]==1)return -1;g[x][y]=1;x1=(x+y)%p;                                 //保存第一回合的值y1=(x1+y)%p;                                //第二回合的值if(x1==0)return g[x1][y]=1;if(y1==0)return g[x1][y1]=2;return g[x1][y1]=dfs(x1,y1);
}
int main()
{int x,y,z,t,k;scanf("%d%d",&t,&p);for(z=0;z<t;z++){scanf("%d%d",&x,&y);k=dfs(x,y);if(k==-1)printf("error\n");elseprintf("%d\n",k);}return 0;
}

# 【模板】KMP

## 题目描述

给出两个字符串 s1 和 s2，若 s1 的区间 [l, r] 子串与 s2 完全相同，则称 s2 在 s1 中出现了，其出现位置为 l。  
现在请你求出 s2 在 s1 中所有出现的位置。

定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。  
对于 s2，你还需要求出对于其每个前缀 s' 的最长 border t' 的长度。

## 输入格式

第一行为一个字符串，即为 s1。  
第二行为一个字符串，即为 s2。

## 输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 s2 在 s1 中出现的位置。  
最后一行输出 |s2| 个整数，第 i 个整数表示 s2 的长度为 i 的前缀的最长 border 长度。

## 样例 #1

### 样例输入 #1

```
ABABABC
ABA
```

### 样例输出 #1

```
1
3
0 0 1
```

## 提示

### 样例 1 解释
 
对于 s2 长度为 3 的前缀 `ABA`，字符串 `A` 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 1。

### 数据规模与约定

**本题采用多测试点捆绑测试，共有 3 个子任务**。

- Subtask 1（30 points）：|s1| <= 15，|s2| <= 5。
- Subtask 2（40 points）：|s1| <= 10^4，|s2| <= 10^2。
- Subtask 3（30 points）：无特殊约定。

对于全部的测试点，保证 1 <= |s1|,|s2| <= 10^6，s1, s2 中均只含大写英文字母。

解题思路

KMP算法是两个字符串比较的优化算法，过程比较复杂，但理解起来比较困难，我花了整整半天都在看KMP，还是看的一知半解。

代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
char g[1000100];
char j[1000100];
int ne[1000100];
int main()
{int x,y,z,l;int len,len2;scanf("%s%s",g+1,j+1);len=strlen(g+1);len2=strlen(j+1);for(x=2;x<=len2;x++){y=ne[x-1];while(y&&j[y+1]!=j[x])y=ne[y];if(j[y+1]==j[x])ne[x]=y+1;elsene[x]=0;}y=0;for(x=1;x<=len;x++){while(y&&g[x]!=j[y+1])y=ne[y];if(g[x]==j[y+1])y+=1;if(y==len2){printf("%d\n",x-len2+1);y=ne[y];}}for(x=1;x<=len2;x++)printf("%d ",ne[x]);return 0;
}

# Before an Exam

## 题面翻译

### 题目背景

明天皮特将要考生物。他并不很喜欢生物，但在 d 天前他得知他将不得不参加此次考试。皮特严厉的父母勒令他立即复习，因此他在第 i 天将需要学习不少于 minTime_i 小时，不多于 maxTime_i 小时。他们同时警告皮特：考试前一天，他将被检查他复习的完成情况。

因此，今天皮特的父母会要求他展示他考前复习的学习时间表。然而，他只记录这 d 天以来他复习所用的总计用时 sumTime（小时）.现在他希望知道他能否给他的父母展示一份时间表，包含 d 个数，每个数 schedule_i 表示皮特第 i 天在复习生物上的用时（单位为小时），并应满足上文提及的要求。

### 题目输入

第一行包含两个数：d,sumTime。

(1<= d<=30,0<= sumTime<=240)，意义如上所述。

接下来 d 行，每行两个数：minTime_i,maxtime_i，两个数之间有一个空格，意义如上。(0<= minTime_i<= maxTime_i<=8)

### 题目输出

如果有解，在单独一行输出 `YES`，换行，输出任意一种满足上文要求的解。如果无解，在单独一行中输出 `NO`。

## 样例 #1

### 样例输入 #1

```
1 48
5 7
```

### 样例输出 #1

```
NO
```

## 样例 #2

### 样例输入 #2

```
2 5
0 1
3 5
```

### 样例输出 #2

```
YES
1 4
```

解题思路

先判断能否完成，然后按每天最少去算，多出来的加到每天里，但最多不能超过每天规定的最大值。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{int d,sum,mi=0,ma=0,x,y;int g[50][2];scanf("%d%d",&d,&sum);for(x=0;x<d;x++){scanf("%d%d",&g[x][0],&g[x][1]);mi+=g[x][0];ma+=g[x][1];}if(sum<=ma&&mi<=sum){printf("YES\n");sum-=mi;for(x=0;x<d;x++){if(sum>0){y=0;if(g[x][1]-g[x][0]<sum){printf("%d ",g[x][1]);sum=sum-(g[x][1]-g[x][0]);}else{printf("%d ",g[x][0]+sum);sum=0;}}else{printf("%d ",g[x][0]);}}}elseprintf("NO\n");return 0;
}