link
\(\textcolor{lightgreen}{A}-\textcolor{yellow}{B}-\textcolor{yellow}{C}-\textcolor{red}{D}-\textcolor{red}{E}-\color{red}{F}\)
A
给你一个数 n ，在给你一个数列 1~k，其中 x 不能用，然后用其他的数任意累加，如能得到 n ，输出所用数字数量和具体数列。
一眼分类。先分是否有 1，有 1 就皆大欢喜；
没 1，那就是可以用 2~k，此时就只要分两种情况：1. k=2，2. k>2 ;
为什么这样分？因为当 k>2 时，就可以用 2,3 组合成所有的数啦。 done.
#A code
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int t, n, k, x;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t --)
{
cin >> n >> k >> x;
if (k == 1 && x == 1) { cout << "NO" << endl; continue; }
if (x != 1) //1
{
cout << "YES" << endl << n << endl;
for (int i = 1; i <= n; i ++) cout << 1 << ' ';
cout << endl;
}
else
{
if (k == 2) //2
{
if (n % 2 != 0) cout << "NO" <<endl;
else
{
cout << "YES" << endl << n/2 << endl;
for (int i = 1; i <= n/2; i ++) cout << 2 << ' ';
cout << endl;
}
}
else //2 or 3
{
cout << "YES" << endl;
if (n % 2 == 0)
{
cout << n/2 <<endl;
for (int i = 1; i <= n/2; i ++) cout << 2 << ' ';
}
else
{
n -= 3;
cout << n/2+1 << endl;
for (int i = 1; i <= n/2; i ++) cout << 2 << ' ';
cout << 3 << endl;
}
}
}
}
return 0;
}
B
在 Oxy 的 Ⅰ 象限，给出三个不同的点 A，B，C，规定 A 为起点，其余为两个终点，求分别从起点到终点的两条最短路径的最大重合长度。
一开始受上题影响，且一眼没思路，我就又开始分类讨论，分出了四五种情况，越分越复杂......
然后我Q了一下 syz 大佬，发现自己还是一比赛就降智 qwq
两点最短距离就是 xa-xb，xa-xc（y同理，这个就叫做『曼哈顿距离』），
接下来就是分类讨论
然后考虑 A 在 B，C任意位置（xb≠xc，yb≠yc）下不同位置的性质
可以发现，+1 是所有答案的共有性质，即肯定重合在 A 点，
那么就是判断 x，y 分别是否异号即可（用相乘判断，注意开 long long ，一直被劝告，永远在忘记） done.
#B code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
struct node
{
ll x, y;
}a, b, c;
ll count(ll & beg, ll & end)
{
return beg - end;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t --)
{
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
ll lbx = count(a.x, b.x);
ll lby = count(a.y, b.y);
ll lcx = count(a.x, c.x);
ll lcy = count(a.y, c.y);
ll ans = 0;
if ((lbx * lcx) > 0) ans += min(abs(lbx), abs(lcx));
if ((lby * lcy) > 0) ans += min(abs(lby), abs(lcy));
cout << ++ ans << endl;
}
return 0;
}
C
给一个由 0~9 组成的字串 s、一个数 m、两个长度为 m 的字串 l,r ，求是否存在一个数满足在 [l,r] 范围内且不是 s 的子串（不一定是连续的）
- 首先想到肯定要枚举 l,r ，按从高到低数位 l -> r （不论是否连续，严格从左至右）
那对于 l -> r 的每一个数位，又肯定要在 s 上查询，看看能否找到；
没找到，那就说明肯定不是它的子串；
-
找到了，那就标记该位置，为什么嘞？其一是把 \(l[i] \rightarrow r[i]\) 中的所有被标记的位置找到，取其中的最大值，即最靠近 s 的尾巴，这样下一数位的数出现在 s 上的可能性就最小（别忘了严格从左至右，所以 s 标记处的左边就没有再遍历的意义了，所以我这样结论），这是一种贪心思想；
其二是也从刚刚的话看得出来，标记最远位置 x 后，下一位数就可以直接从 x+1 位开始查询； -
那么答案就从最大值这里切入，若是它的子串，最大值撑死了就是 s 的长度。
so，若不是子串，我们就可以给它赋一个极大值作为在 s 上找不到的标志（其实大于 s 的长度就可以。 done.
顺便提一嘴关于复杂度，Alex_Wei 大犇昨天在 帖子 里回答我说是 \(O(m*m*ls)\Rightarrow O(3*10^7)\) ，是我糊涂了吗（一定是）？，难道测试用例数量 t 不用算进去......
#C code
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int t, m;
string s, l, r;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t --)
{
cin >> s >> m >> l >> r;
int ls = s.size(), check = -1;
for (int i = 0; i < m ; i ++)
{
int k = check;
for (char c = l[i]; c <= r[i]; c ++)
{
int tmp = inf;
for (int j = check+1; j < ls; j ++)
{
if(s[j] == c)
{
tmp = j;
break;
}
}
k = max(k, tmp);
}
check = k;
}
cout << (check == inf ? "YES" : "NO") << endl;
}
return 0;
}
剩下 D,E,F ，不用看了，我有自知之明，肯定不会做 qwq
总结
这场比赛赛时实际上只过了 A ，但只花了 20min 左右，还是比较快的；
剩下的时间完全就耗在 B 上，思路蛮简单，但我的代码写得很......可以说凌乱，导致我一直能发现漏洞，一直调试，一直 wa ，不断堆砌代码，最后调不出来......
#B 凌乱的代码
#include<bits/stdc++.h>
using namespace std;
int t;
struct node
{
int x, y;
}a, b, c;
int count(int & beg, int & end)
{
return beg - end;
}
bool check()
{
if ((a.x >= b.x && a.x >= c.x && a.y >= b.y && a.y >= c.y) || (a.x <= b.x && a.x <= c.x && a.y <= b.y && a.y <= c.y)) return true;
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t --)
{
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
int lbx = count(a.x, b.x);
int lby = count(a.y, b.y);
int lcx = count(a.x, c.x);
int lcy = count(a.y, c.y);
int ans = 0;
bool ikun = false , IKUN = false;
if ((lbx ^ lcx) < 0) ans += 1;
else
{
ans += min(abs(lbx), abs(lcx));
if (check()) ikun = true;
}
if ((lby ^ lcy) < 0) ans += 1;
else
{
ans += min(abs(lby), abs(lcy));
if (check()) IKUN = true;
}
if (ikun && IKUN) ans ++;
cout << ans << endl;
}
return 0;
}
剩下没多少时间了，就懒得看 C 了。（直接开摆
但赛后看 C 还是蛮简单的。
标签：151,count,Educational,contest,int,ll,cin,abs,ans From： https://www.cnblogs.com/hi-zwjoey/p/17519336.html