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看到小艺酱可怜的样子，允许小艺酱免费占卜一次。
花瓣占卜：

1. 一瓣“在一起”，一瓣“不在一起”；开始的花瓣表示“在一起”。
2. 直到最后一个花瓣落地游戏结束。
3. 可以选择多朵花，选择撕一朵花就必须撕完。

以下为笔者补充大意（比赛时有，但《考试报告》中没有）：
最终结果为“在一起”。

题解

没看明白题意……
我的理解：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;
}