训练赛链接：https://vjudge.net/contest/410049#problem/D

Gym - 102861B

题意：

在一个二维平面上，给你一个船，问你在这个二维平面上有没有船重叠。有的话输出N，否则输出Y

D、L、R、C确定一个船在二维平面上的位置，D为0表示船平行于X轴放置，为1平行y轴放置。L表示船得长度。（R，C）表示船头所在位置

题解：

模拟判断就行，数据不大

代码：

1 #include
2 using namespace std;
3
4 int mp[110][110];
5
6 int main()
7 {
8 int n, flag = 1;
9 scanf("%d", &n);
10 for (int i = 1; i <= n; i++) 11 { 12 int d, l, r, c; 13 scanf("%d %d %d %d", &d, &l, &r, &c); 14 if (d == 0) 15 { 16 if (c + l - 1 > 10)
17 flag = 0;
18 else
19 {
20 for (int j = c; j <= c + l - 1; j++) 21 { 22 if (mp[r][j]) 23 flag = 0; 24 else 25 mp[r][j] = 1; 26 } 27 } 28 } 29 else 30 { 31 if (r + l - 1 > 10)
32 flag = 0;
33 for (int j = r; j <= r + l - 1; j++)
34 {
35 if (mp[j][c])
36 flag = 0;
37 else
38 mp[j][c] = 1;
39 }
40 }
41 }
42 if (flag)
43 puts("Y");
44 else
45 puts("N");
46 }

Gym - 102861F

题意：

给你一个由S、R、Q字符组成的字符串，这个字符串用来描述两个人的比赛信息。比赛采取三局两胜制，每一局获胜条件如下：

1、一个人的得分大于等于10

2、一个人得分大于等于5，且要比对手多两分

3、一局由多轮游戏构成，每一轮游戏有一个发球人和一个接球人构成

刚开始由左边的人发球，之后每一轮由上一轮赢的人发球（谁赢了就得一分）

字符串中S表示发球人得一分，R表示接球人得分。Q表示宣布一下当前比赛情况

输出格式：

1、如果现在已经有人赢了两局就输出“GL - GR”，GL表示左边人赢了几局，GR表示右边人赢了几局。并在获胜者一方加上“(winner)”

2、如果没有人赢了两局，输出"GL (PL) - GR (PR)"，GL、GR解释如上，PL表示左边人当前局得分，PR表示右边人当前局得分

样例解释：

SRSSQSSSSQRRSS

1、因为最开始左边人发球，且第一个字符为S，那么发球人得分，也就是左边的人得一分

2、之后左边继续发球，第二个字符为R，所以接球人得分，也就是右边的人得一分

3、之后右边发球，第三个字符为S，所以接球人得分，也就是右边的人得一分

4、之后右边发球，第四个字符为S，所以接球人得分，也就是右边的人得一分

5、出现Q，输出比赛信息

6、后面就不说了

题解：

模拟

代码：

1 /*
2 * @Author: hesorchen
3 * @Date: 2020-11-21 17:26:53
4 * @LastEditTime: 2020-11-26 16:23:35
5 * @Description: 栽种绝处的花
6 */
7 #include
8 using namespace std;
9 typedef long long ll;
10 const int maxn = 5e6 + 5;
11 const ll mod = 1e9 + 7;
12 char s[maxn];
13 int main()
14 {
15 scanf("%s",s+1);
16 int len=strlen(s+1);
17 int xian=0,num_0=0,num_1=0,win_0=0,win_1=0,flag=0;
18 for(int i=1;i<=len;++i) 19 { 20 if(s[i]!='Q') 21 { 22 if(flag) continue; 23 if(xian==0) 24 { 25 if(s[i]=='S') 26 { 27 num_0++; 28 } 29 else 30 { 31 xian=1-xian; 32 num_1++; 33 } 34 } 35 else 36 { 37 if(s[i]=='S') 38 { 39 num_1++; 40 } 41 else 42 { 43 xian=1-xian; 44 num_0++; 45 } 46 } 47 if(num_0==10 || num_1==10) 48 { 49 50 if(num_0==10) 51 { 52 win_0++; 53 //win_1=0; 54 } 55 else 56 { 57 win_1++; 58 //win_0=0; 59 } 60 num_0=num_1=0; 61 } 62 else if(abs(num_0-num_1)>=2 && max(num_0,num_1)>=5)
63 {
64 if(num_0-num_1>0)
65 {
66 win_0++;
67 //win_1=0;
68 }
69 else
70 {
71 win_1++;
72 //win_0=0;
73 }
74 num_0=num_1=0;
75 }
76 if(win_0>=2 || win_1>=2)
77 {
78 flag=1;
79 }
80 }
81 else
82 {
83 if(flag)
84 {
85 if(win_0==2)
86 {
87 printf("%d (winner) - %d\n",win_0,win_1);
88 }
89 else
90 {
91 printf("%d - %d (winner)\n",win_0,win_1);
92 }
93 }
94 else
95 {
96 if(xian==0)
97 printf("%d (%d*) - %d (%d)\n",win_0,num_0,win_1,num_1);
98 else printf("%d (%d) - %d (%d*)\n",win_0,num_0,win_1,num_1);
99 }
100 }
101 }
102 return 0;
103 }
104 /*
105 SSSSSQRSSSSQSSSSSQ
106 */

Gym - 102861G

题意：

找到前缀和最大的数，如果最大的数为负数就直接输出100，否则就加上100输出

代码：

1 /*
2 * @Author: hesorchen
3 * @Date: 2020-11-21 17:26:53
4 * @LastEditTime: 2020-11-26 13:07:25
5 * @Description: 栽种绝处的花
6 */
7 #include
8 using namespace std;
9
10 int s[110];
11 int a[110];
12 int main()
13 {
14 int n;
15 scanf("%d", &n);
16 for (int i = 1; i <= n; i++)
17 scanf("%d", &a[i]);
18 int ans = 0;
19 for (int i = 1; i <= n; i++)
20 {
21 s[i] = s[i - 1] + a[i];
22 ans = max(s[i] + 100, ans);
23 }
24 printf("%d\n", max(100, ans));
25 }

Gym - 102861L

题意：

给你一个n行m列由字母组成的方格，后面给你k个字符串si。

对于字符串si排列组合得到的所有新字符串（例如给你abc，你就可以得到abc、acb、bac、bca、cab、cba），看看这些所有新字符串可不可以在输入的n行m列的

方格中找到（找到是指横竖斜三种方向能找到这个字符串就可以），可以的话就标记。

如果某个方格被两个字符串si，sj（i!=j）的全排列标记到了，那么这个方格位置就是特殊的方格，最后输出特殊方格数量

样例：

4 5
XBOIC
DKIRA
ALBOA
BHGES
3
BOLA
CASA
BOI

题解：

模拟

代码：

1 #include
2 using namespace std;
3
4 char mp[100][100];
5 int col[100][100];
6 string s[100];
7 int main()
8 {
9 int n, m;
10 scanf("%d %d", &n, &m);
11 for (int i = 1; i <= n; i++) 12 scanf("%s", mp[i] + 1); 13 int k = 0; 14 scanf("%d", &k); 15 for (int i = 1; i <= k; i++) 16 { 17 cin >> s[i];
18 sort(s[i].begin(), s[i].end());
19 }
20 for (int i = 1; i <= n; i++)
21 {
22 for (int j = 1; j <= m; j++)
23 {
24 for (int l = 1; l <= k; l++)
25 {
26 int len = s[l].size();
27 string temp;
28 temp = "";
29 for (int o = 0; o < len; o++)
30 temp += mp[i][j + o];
31 sort(temp.begin(), temp.end());
32 if (temp == s[l])
33 for (int o = 0; o < len; o++)
34 {
35 if (col[i][j + o] == -1)
36 continue;
37 else if (col[i][j + o] == 0)
38 col[i][j + o] = l;
39 else if (col[i][j + o] != l)
40 col[i][j + o] = -1;
41 }
42
43 temp = "";
44 for (int o = 0; o < len; o++)
45 temp += mp[i + o][j];
46 sort(temp.begin(), temp.end());
47 if (temp == s[l])
48 for (int o = 0; o < len; o++)
49 {
50 if (col[i + o][j] == -1)
51 continue;
52 else if (col[i + o][j] == 0)
53 col[i + o][j] = l;
54 else if (col[i + o][j] != l)
55 col[i + o][j] = -1;
56 }
57 temp = "";
58 for (int o = 0; o < len; o++)
59 temp += mp[i + o][j + o];
60 sort(temp.begin(), temp.end());
61 if (temp == s[l])
62 for (int o = 0; o < len; o++)
63 {
64 if (col[i + o][j + o] == -1)
65 continue;
66 else if (col[i + o][j + o] == 0)
67 col[i + o][j + o] = l;
68 else if (col[i + o][j + o] != l)
69 col[i + o][j + o] = -1;
70 }
71
72 temp = "";
73 for (int o = 0; o < len; o++)
74 temp += mp[i - o][j + o];
75 sort(temp.begin(), temp.end());
76 if (temp == s[l])
77 for (int o = 0; o < len; o++)
78 {
79 if (i - o < 0)
80 continue;
81 if (col[i - o][j + o] == -1)
82 continue;
83 else if (col[i - o][j + o] == 0)
84 col[i - o][j + o] = l;
85 else if (col[i - o][j + o] != l)
86 col[i - o][j + o] = -1;
87 }
88 }
89 }
90 }
91 int ans = 0;
92 for (int i = 1; i <= n; i++)
93 for (int j = 1; j <= m; j++)
94 {
95 ans += (col[i][j] == -1 ? 1 : 0);
96 }
97 printf("%d\n", ans);
98 return 0;
99 }

Gym - 102861N

题意：

题目说了好多都没用，大致意思就是给你一个二分图，左边点是M集合，右边点是N集合，M集合的每一个点mi都由一个pi表示，保证pi是素数

N集合的每一个点ni可以用ci来表示，把这个ci分解质因数，例如ci=12，那么ci的质因数为2，3，那么ci就和pi==2和pi==3的M集合里面的点相连

且和pi==2的点相连权值为2，因为2*2*3=12

现在不给你pi，给出所有ci，让你对pi排序之后输出

题解：

说了这么多，其实就是找出来ci的所有质因子，去重之后输出就可以了。。。。。

大质数分解板子

代码：

1 /*
2 * @Author: hesorchen
3 * @Date: 2020-11-21 17:26:53
4 * @LastEditTime: 2020-11-26 18:08:55
5 * @Description: 栽种绝处的花
6 */
7 #include
8 using namespace std;
9 #define LL long long
10 set s;
11 // void f(long long x)
12 // {
13 // for (int i = 2; i <= sqrt(x); i++) 14 // { 15 // if (x % i == 0) 16 // { 17 // while (x % i == 0) 18 // { 19 // s.insert(i); 20 // x /= i; 21 // } 22 // } 23 // } 24 // if (x > 1)
25 // s.insert(x);
26 // }
27 const int maxn = 50005;
28 const int INF = 0x3f3f3f3f;
29 const int Times = 10;
30 const int N = 5500;
31 LL ct, cnt;
32 LL fac[N];
33
34 LL gcd(LL a, LL b)
35 {
36 return b ? gcd(b, a % b) : a;
37 }
38 LL multi(LL a, LL b, LL m)
39 {
40 LL ans = 0;
41 a %= m;
42 while (b)
43 {
44 if (b & 1)
45 {
46 ans = (ans + a) % m;
47 b--;
48 }
49 b >>= 1;
50 a = (a + a) % m;
51 }
52 return ans;
53 }
54
55 LL pow(LL a, LL b, LL m)
56 {
57 LL ans = 1;
58 a %= m;
59 while (b)
60 {
61 if (b & 1)
62 {
63 ans = multi(ans, a, m);
64 b--;
65 }
66 b >>= 1;
67 a = multi(a, a, m);
68 }
69 return ans;
70 }
71
72 bool Miller_Rabin(LL n)
73 {
74 if (n == 2)
75 return true;
76 if (n < 2 || !(n & 1)) 77 return false; 78 LL m = n - 1; 79 int k = 0; 80 while ((m & 1) == 0) 81 { 82 k++; 83 m >>= 1;
84 }
85 for (int i = 0; i < Times; i++) 86 { 87 LL a = rand() % (n - 1) + 1; 88 LL x = pow(a, m, n); 89 LL y = 0; 90 for (int j = 0; j < k; j++) 91 { 92 y = multi(x, x, n); 93 if (y == 1 && x != 1 && x != n - 1) 94 return false; 95 x = y; 96 } 97 if (y != 1) 98 return false; 99 } 100 return true; 101 } 102 103 LL pollard_rho(LL n, LL c) 104 { 105 LL i = 1, k = 2; 106 LL x = rand() % (n - 1) + 1; 107 LL y = x; 108 while (true) 109 { 110 i++; 111 x = (multi(x, x, n) + c) % n; 112 LL d = gcd((y - x + n) % n, n); 113 if (1 < d && d < n) 114 return d; 115 if (y == x) 116 return n; 117 if (i == k) 118 { 119 y = x; 120 k <<= 1; 121 } 122 } 123 } 124 125 void find(LL n, int c) 126 { 127 if (n == 1) 128 return; 129 if (Miller_Rabin(n)) 130 { 131 fac[ct++] = n; 132 return; 133 } 134 LL p = n; 135 LL k = c; 136 while (p >= n)
137 p = pollard_rho(p, c--);
138 find(p, k);
139 find(n / p, k);
140 }
141
142 int main()
143 {
144 int n, m, K;
145 long long x;
146 scanf("%d %d %d", &n, &m, &K);
147 for (int i = 1; i <= m; i++)
148 {
149 scanf("%lld", &x);
150 ct = 0;
151 find(x, 120);
152 sort(fac, fac + ct);
153 int k = 1;
154 for (int j = 1; j < ct; j++)
155 {
156 if (fac[j] == fac[j - 1])
157 continue;
158 else
159 {
160 fac[k++] = fac[j];
161 }
162 }
163 cnt = k;
164 for (int j = 0; j < cnt; j++)
165 s.insert(fac[j]);
166 }
167 while (K--)
168 {
169 int a, b, c;
170 scanf("%d %d %d", &a, &b, &c);
171 }
172 for (auto it = s.begin(); it != s.end(); it++)
173 {
174 cout << *it << ' ';
175 }
176 puts("");
177 }

Gym - 101968C

题意：

模拟下面一段程序

f(l,r):
if l is equal to r then return a[l]
s = 0
for i = l to r: s = s + a[i]
return s + f(l+1,r) + f(l,r-1)

给你n个数ai，让你求f(1,n)%1e9+7

题解：

很明显就是让你求对于一个位置x(1<=x<=n)，这个位置最后计算了多少次，设这个次数为wi，最后输出Σn1ai*wi

打表求出来每一个位置的贡献，找规律，规律和杨辉三角很相似，最后是一个排列组合

代码：

1 /*
2 * @Author: hesorchen
3 * @Date: 2020-11-21 17:26:53
4 * @LastEditTime: 2020-11-26 15:39:57
5 * @Description: 栽种绝处的花
6 */
7 #include
8 using namespace std;
9 typedef long long ll;
10 const int maxn = 1e6 + 5;
11 const ll mod = 1e9 + 7;
12 ll ksm(ll a, ll b)
13 {
14 ll res = 1;
15 while (b)
16 {
17 if (b & 1)
18 {
19 res = (res * a) % mod;
20 }
21 b >>= 1;
22 a = (a * a) % mod;
23 }
24 return res;
25 }
26 ll fac[maxn], inv[maxn];
27 void init()
28 {
29 fac[0] = inv[0] = 1;
30 for (int i = 1; i <= maxn - 1; i++)
31 {
32 fac[i] = (i * fac[i - 1]) % mod;
33 inv[i] = (inv[i - 1] * ksm(i, mod - 2)) % mod;
34 }
35 }
36 ll C(int n, int m)
37 {
38 return ((fac[n] * inv[m]) % mod) * inv[n - m] % mod;
39 }
40 int main()
41 {
42 init();
43 int t, n;
44 scanf("%d", &t);
45 while (t--)
46 {
47 ll sum = 0, x;
48 scanf("%d", &n);
49 for (int i = 1; i <= n; i++)
50 {
51 scanf("%lld", &x);
52 sum = (sum + ((C(n + 1, i) - 1) * x % mod)) % mod;
53 }
54 printf("%lld\n",sum);
55 }
56
57 return 0;
58 }

Gym - 101968D

题意：

给你两个序列a，b，如果对a序列中一个数加上[-k,k]，然后对a序列排序，对b序列排序之后两个序列相等就可以了

题解：

unordered_map弄一下就可以了

之前输入还没结束我们就break，导致出现ILE错误，一脸懵

代码：

1 /*
2 * @Author: hesorchen
3 * @Date: 2020-11-21 17:26:53
4 * @LastEditTime: 2020-11-26 17:16:06
5 * @Description: 栽种绝处的花
6 */
7 #include
8 using namespace std;
9
10 unordered_map mp;
11
12 // inline int get(int x)
13 // {
14 // return x * 13331 + 1000000007;
15 // }
16
17 void read(int &v)
18 {
19 int k = 1;
20 v = 0;
21 int c = getchar();
22 while (c < '0' || c > '9')
23 {
24 if (c == '-')
25 k = 0;
26 c = getchar();
27 }
28 while (c >= '0' && c <= '9') 29 v = (v << 3) + (v << 1) + (c - 48), c = getchar(); 30 if (k == 0) 31 v = -v; 32 } 33 int get(int x) 34 { 35 return (x * 1333331 + 1000000007) % 1000000007; 36 } 37 int main() 38 { 39 int t; 40 read(t); 41 while (t--) 42 { 43 mp.clear(); 44 int n, k; 45 long long sum = 0; 46 read(n), read(k); 47 for (int i = 1; i <= n; i++) 48 { 49 int temp; 50 read(temp); 51 sum += temp; 52 mp[get(temp)]++; 53 } 54 int num1 = -1, num2 = -1, flag = 1; 55 for (int i = 1; i <= n; i++) 56 { 57 int temp; 58 read(temp); 59 if (flag == -1) 60 continue; 61 if (mp[get(temp)] > 0)
62 {
63 sum -= temp;
64 mp[get(temp)]--;
65 }
66 else if (flag)
67 {
68 flag = 0;
69 num2 = temp;
70 }
71 else if (!flag)
72 {
73 flag = -1;
74 // break;
75 }
76 }
77 if (flag == 1)
78 {
79 puts("YES");
80 }
81 else if (flag == -1)
82 {
83 puts("NO");
84 }
85 else
86 {
87 long long temp = sum - (long long)num2;
88 if (abs(temp) <= k)
89 puts("YES");
90 else
91 puts("NO");
92 }
93 }
94 }