1.判断胜负（简单字符串）
题目
已知两个字符串A,B。 连续进行读入n次。 每次读入的字符串都为A|B（笔者注：意思是要么是A，要么是B）。 输出读入次数最多的字符串。
题解
比赛时想复杂了，记录每个字符串出现的次数，结果次数多的就是答案。
其实只需要记录第1个字符串，之后的字符串相同则计数+1，不同则记下字符串。计数大于n/2就输出第1个字符串，否则输出另一个字符串。
比赛时代码
其实有bug，每次A或B，可能只出现A或只出现B，代码会panic。实际数据没这种情况。
package main
import "fmt"
func solution(n int, arr []string) {
// TODO: 请在此编写代码
mp := make(map[string]int)
for _, s := range arr {
mp[s]++
}
if len(mp) != 2 {
panic(len(mp))
}
var s1, s2 string
var v1, v2 int
for s, v := range mp {
if s1 == "" {
s1, v1 = s, v
} else {
s2, v2 = s, v
}
}
if v1 < v2 {
s1 = s2
}
if v1 == v2 {
fmt.Println("dogfall")
} else {
fmt.Println(s1)
}
}
func main() {
var n int
fmt.Scan(&n)
arr := make([]string, n)
for i := 0; i < n; i++ {
fmt.Scan(&arr[i])
}
solution(n, arr)
}
2.买铅笔（简单算数）
题目
P老师需要去商店买n支铅笔作为小朋友们参加编程比赛的礼物。她发现商店一共有 3 种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。
为了公平起 见，P老师决定只买同一种包装的铅笔。 商店不允许将铅笔的包装拆开，因此P老师可能需要购买超过 n 支铅笔才够给小朋 友们发礼物。
现在P老师想知道，在商店每种包装的数量都足够的情况下，要买够至少 n 支铅笔最少需要花费多少钱。
题解
相当于要求在“包数乘每包铅笔数大于等于要求铅笔数”的情况下，“包数乘每包价格数”最低。
意味着算需要的包数需要上取整。
代码
package main
import "fmt"
func solution(n int, arr [3][2]int) {
// TODO: 请在此编写代码
ans := -1
//ans := (n+arr[0][0]-1)/arr[0][0]*arr[0][1]
for i := range arr {
if ans == -1 || ans > (n+arr[i][0]-1)/arr[i][0]*arr[i][1] {
ans = (n + arr[i][0] - 1) / arr[i][0] * arr[i][1]
}
}
fmt.Println(ans)
}
func main() {
var n int
var arr [3][2]int
fmt.Scan(&n)
for i := 0; i < 3; i++ {
for j := 0; j < 2; j++ {
fmt.Scan(&arr[i][j])
}
}
solution(n, arr)
}
3.拯救爱情（得分70%）
题目
小艺酱走到一个花之占卜店中。 店员小Q看到小艺酱可怜的样子，允许小艺酱免费占卜一次。
花瓣占卜：
- 一瓣“在一起”，一瓣“不在一起”；开始的花瓣表示“在一起”。
- 直到最后一个花瓣落地游戏结束。
- 可以选择多朵花，选择撕一朵花就必须撕完。
以下为笔者补充大意（比赛时有，但《考试报告》中没有）：
最终结果为“在一起”。
题解
没看明白题意……
我的理解：n朵花，每朵花有0个、1个或多个花瓣，选若干朵花，总花瓣数为奇数。
奇数花瓣的花的个数为奇数，全选；偶数个，不选最小的那个奇数。
比赛时代码
package main
import "fmt"
import "sort"
func solution(n int, a []int) {
// TODO: 请在此编写代码
ji := []int{}
ou := []int{}
sum := int64(0)
for _, v := range a {
sum += int64(v)
if v%2 == 0 {
ou = append(ou, v)
} else {
ji = append(ji, v)
}
}
sort.Ints(ou)
sort.Ints(ji)
if len(ji)%2 == 1 {
fmt.Println(sum)
} else {
if len(ji) != 0 {
fmt.Println(sum - int64(ji[0]))
} else {
//fmt.Println("")
//fmt.Println("0")
//fmt.Println("no")
//fmt.Println("NO")
//fmt.Println(-1)
/*ans := 0
for _, v := range ou{
if v!=0{
break
}
ans++
}
fmt.Println(ans)*/
}
}
}
func main() {
var n int
fmt.Scan(&n)
a := make([]int, n)
for i := 0; i < n; i++ {
fmt.Scan(&a[i])
}
solution(n, a)
}
4.拯救公主（中国剩余定理 或 模拟）
题目
在Flower Kingdom里，住着一位美丽的公主Ana，有一天Ana得了一种怪病，神医告知国王，在遥远的幽谷中有一种药能治愈Ana， 但是神医只有一份不完整的地图，地图的描述如下：
该地图的共有3行，第一行有m列，m为奇数，第二行有m+1列，第三行有m+2列；每一行用一个字符串表示，只有【两种字符】；‘.'表示草地，可以从它上面通过，‘*’表示岩石，每一行 最多 一个‘*’； 入口在左上角，由于在对角线方向上，因此即使对角线两边都有岩石，但是缝隙较大，人可以通过，故人可以向八个方向行走；
真实地图是由该地图的【每一行无限循环】得到的，这种神奇的药草就生长在第x行第y列的草地上,药草可能会在岩石上；
国王决定派遣勇敢的骑士David前去寻找拯救公主的解药； 现在聪明的你是否知道David能否找到该药？
以下为笔者补充大意：
t组数据，范围大概是m<=1000, t<=10
m>1
y的范围应该是1e8，记不清了。
比如输入数据是
..
.*.
..*.
代表的图是（无限列）
........................
.*..*..*..*..*..*..*..*.
..*...*...*...*...*...*.
题解
如果有1列中3行均是岩石，形成一列岩石，会把路挡住，让骑士无法向右走，导致取不到草药。
首先考虑药草不能在岩石上，否则直接返回NO。
其次，如果3行中至少1行没岩石，路不可能被挡住，返回YES。
否则，意味着药草不在岩石上，且3行均有岩石。
答案即判断图中是否存在一列岩石，如果存在是否在药草左侧（挡住路）。
假设岩石列号为p1,p2,p3，所有岩石位置为
(1, p1) (1, p1+1*m) (1, p1+2*m) ……
(2, p2) (2, p2+1*(m+1)) (2, p2+2*(m+1)) ……
(3, p3) (3, p3+1*(m+2)) (3, p3+2*(m+2)) ……
模拟
从左到右枚举每行岩石的位置，每次右移当前最左列的岩石。。
比如一开始是(1, p1) (2, p2) (3, p3)，第一步：
如果p1<=p2且p1<=p3，就将当前考虑位置变为(1, p1+m) (2, p2) (3, p3)
如果p2<=p1且p2<=p3，就将当前考虑位置变为(1, p1) (2, p2+(m+1)) (3, p3)
如果p3<=p2且p3<=p1，就将当前考虑位置变为(1, p1) (2, p2) (3, p3+(m+2))
以此类推。
直到min{p1+k1*m, p2+k2*(m+1), p3+k3*(m+2)}>=y 或 p1+k1*m==p2+k2*(m+1)==p3+k3*(m+2)之一成立。
若前者首先成立，意味着药草在最左的一列岩石左侧，不会被挡住。
若后者首先成立，意味着形成了一列岩石，挡住了药草。
中国剩余定理
（笔者不太熟悉数论……）
假设所有一列岩石为第L列，最左一列岩石为第L0列，则有：
L=p1 (mod m)
L=p2 (mod (m+1))
L=p3 (mod (m+2))
用中国剩余定理求，大概是如果m、m+1、m+2不互素，可能无解（？）
否则可以求出满足要求的最小的正数L0，进而有L=L0+k*LCM{ m, m+1, m+2 }
k为非负整数，LCM表示最小公倍数。
比较L0与y，可知骑士先遇到药草还是一列岩石。
比赛时代码
模拟部分是对的，其他部分实际没用到。
因为不会实现中国剩余定理，所以用的扩展欧几里得，有问题，大概能得70分。
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long
#define int long long
LL exgcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
LL g = exgcd(b, a % b, x, y);
LL tmp = y;
y = x - (a / b) * y;
x = tmp;
return g;
}
std::string solution(int m, int x, int y, std::vector<std::string> &vec) {
if (y <= 1e8) {
int pos[3] = {-1, -1, -1};
int sum[3] = {m, m + 1, m + 2};
for (int i = 0; i < 3; i++) {
for (int p = 0; p < sum[i]; p++) {
if (vec[i][p] == '*') {
pos[i] = p + 1;
break;
}
}
}
if ((y - pos[x - 1]) % sum[x - 1] == 0) {
return "NO";
}
if (pos[0] == -1 || pos[1] == -1 || pos[2] == -1) {
return "YES";
}
while (true) {
int minP = 0;
for (int i = 1; i <= 2; i++)if (pos[i] < pos[minP])minP = i;
if (pos[minP] >= y) {
return "YES";
}
if (pos[0] == pos[1] && pos[1] == pos[2]) {
return "NO";
}
pos[minP] += sum[minP];
}
} else {
std::string result;
int pos[3] = {};
int sum[3] = {m, m + 1, m + 2};
for (int i = 0; i < 3; i++) {
for (int p = 0; p < sum[i]; p++) {
if (vec[i][p] == '*') {
pos[i] = p + 1;
break;
}
}
}
if ((y - pos[x - 1]) % sum[x - 1] == 0) {
return "NO";
}
int k0, k1;
int g01 = exgcd(sum[0], -sum[1], k0, k1);
if ((pos[1] - pos[0]) % g01 != 0) {
return "NO";
}
k0 *= (pos[1] - pos[0]) / g01;
k1 *= (pos[1] - pos[0]) / g01;
int k0_, k2_;
int g02 = exgcd(sum[0], -sum[2], k0_, k2_);
if ((pos[2] - pos[0]) % g02 != 0) {
return "NO";
}
k0_ *= (pos[2] - pos[0]) / g02;
k2_ *= (pos[2] - pos[0]) / g02;
int d1, d2;
int gdd = exgcd(sum[1], -sum[2], d1, d2);
if ((k0_ - k0) % gdd != 0) {
return "NO";
}
d1 *= (k0_ - k0) / gdd;
d2 *= (k0_ - k0) / gdd;
//int kk0 = k0+d1*(m+1);
//int kk1 = k1+d1*m;
int kk2 = k2_ + d2 * m;
int pp = pos[0] + kk2 * m;
int ss = m * (m + 1) * (m + 2);
if (pp < 1) {
int f = (1 - pp + ss - 1) / ss;
pp += f * ss;
}
return pp > y ? "YES" : "NO";
}
/*int bs0 = (m+1)*(m+2);
int bs1 = m*(m+2);
int bs2 = m*(m+1);
if(kk0<1){
int f = (1-kk0 + bs0-1) / bs0;
kk0 += f*bs0;
kk1 += f*bs1;
kk2 += f*bs2;
}
if(kk1<1){
int f = (1-kk1 + bs1-1)/bs1;
kk0 += f*bs0;
kk1 += f*bs1;
kk2 += f*bs2;
}
if(kk2<1){
int f = (1-kk2+bs1-1)
}
return result;*/
}
#undef int
int main() {
#define int long long
int T;
std::cin >> T;
for (int i = 0; i < T; i++) {
int m;
int x;
int y;
std::vector<std::string> vec;
std::cin >> m;
std::cin >> x;
std::cin >> y;
std::string token;
for (size_t i = 0; i < 3; i++) {
std::cin >> token;
vec.push_back((token));
}
std::string result = solution(m, x, y, vec);
std::cout << result << std::endl;
}
return 0;
}
