Gym - 102861B 、Gym - 102861F、Gym 102861G、Gym 102861L、Gym 102861N、Gym 101968C、Gym 101968D
2024-09-05 09:13:52
训练赛链接：https://vjudge.net/contest/410049#problem/D
题意：
在一个二维平面上，给你一个船，问你在这个二维平面上有没有船重叠。有的话输出N，否则输出Y
D、L、R、C确定一个船在二维平面上的位置，D为0表示船平行于X轴放置，为1平行y轴放置。L表示船得长度。（R，C）表示船头所在位置
题解：
模拟判断就行，数据不大
代码：
1 #include <bits/stdc++.h>
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 }
题意：
给你一个由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 <bits/stdc++.h>
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 */
题意：
找到前缀和最大的数，如果最大的数为负数就直接输出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 <bits/stdc++.h>
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 }
题意：
给你一个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 <bits/stdc++.h>
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 }
题意：
题目说了好多都没用，大致意思就是给你一个二分图，左边点是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 <bits/stdc++.h>
8 using namespace std;
9 #define LL long long
10 set<long long> 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 }
题意：
模拟下面一段程序
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 <bits/stdc++.h>
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 }
题意：
给你两个序列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 <bits/stdc++.h>
8 using namespace std;
9
10 unordered_map<int, int> 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 }
最新文章
- BufferedOutputStream的学习
- smartstore-net
- jquery重置html form
- [转]Responsive Tables Demo
- [错误代码：0x80070002]IIS7及以上伪静态报错404
- SCOI2009生日快乐
- html5生成柱状图（条形图）
- 【转】国内较快的maven镜像
- tabhost中setup()和setup(LocalActivityManager activityGroup)
- Git查看、删除、重命名远程分支和tag
- swift 学习资源 大集合
- Linux常用命令(第二版) --Shell应用技巧
- 杭电ACM2020--绝对值排序
- String.matches()的用法
- 利用div绘制细线居中
- java线程学习之Sleep方法
- python 发送163邮件
- Android优化指南
- has invalid type <class 'numpy.ndarray'>, must be a string or Tensor
- .NET分布式缓存Memcached从入门到实战