网站建设小程序,wordpress文章数据库,电子商务平台的自然人经营者,网站搭建设计合同# 【CSGRound1】天下第一
## 题目背景
天下第一的 cbw 以主席的身份在 8102 年统治全宇宙后#xff0c;开始了自己休闲的生活#xff0c;并邀请自己的好友每天都来和他做游戏。由于 cbw 想要显出自己平易近人#xff0c;所以 zhouwc 虽然是一个蒟蒻#xff0c;也有能和 c…# 【CSGRound1】天下第一
## 题目背景
天下第一的 cbw 以主席的身份在 8102 年统治全宇宙后开始了自己休闲的生活并邀请自己的好友每天都来和他做游戏。由于 cbw 想要显出自己平易近人所以 zhouwc 虽然是一个蒟蒻也有能和 cbw 玩游戏的机会。
## 题目描述
游戏是这样的
给定两个数 xy与一个模数 p。
cbw 拥有数 xzhouwc 拥有数 y。
第一个回合x-(xy)mod p。
第二个回合y-(xy)mod p。
第三个回合x-(xy)mod p。
第四个回合y-(xy)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。
解题思路
运用记忆化搜索用一个数组来保存对应的xy的结果。
代码
#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(xy)%p; //保存第一回合的值y1(x1y)%p; //第二回合的值if(x10)return g[x1][y]1;if(y10)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(z0;zt;z){scanf(%d%d,x,y);kdfs(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 130 points|s1| 15|s2| 5。 - Subtask 240 points|s1| 10^4|s2| 10^2。 - Subtask 330 points无特殊约定。
对于全部的测试点保证 1 |s1|,|s2| 10^6s1, 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,g1,j1);lenstrlen(g1);len2strlen(j1);for(x2;xlen2;x){yne[x-1];while(yj[y1]!j[x])yne[y];if(j[y1]j[x])ne[x]y1;elsene[x]0;}y0;for(x1;xlen;x){while(yg[x]!j[y1])yne[y];if(g[x]j[y1])y1;if(ylen2){printf(%d\n,x-len21);yne[y];}}for(x1;xlen2;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 d30,0 sumTime240)意义如上所述。
接下来 d 行每行两个数minTime_i,maxtime_i两个数之间有一个空格意义如上。(0 minTime_i maxTime_i8)
### 题目输出
如果有解在单独一行输出 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,mi0,ma0,x,y;int g[50][2];scanf(%d%d,d,sum);for(x0;xd;x){scanf(%d%d,g[x][0],g[x][1]);mig[x][0];mag[x][1];}if(summamisum){printf(YES\n);sum-mi;for(x0;xd;x){if(sum0){y0;if(g[x][1]-g[x][0]sum){printf(%d ,g[x][1]);sumsum-(g[x][1]-g[x][0]);}else{printf(%d ,g[x][0]sum);sum0;}}else{printf(%d ,g[x][0]);}}}elseprintf(NO\n);return 0;
}
