本场链接:Codeforces Round #706 (Div. 2)
闲话
状态低迷，手速场被干了。E题正在路上，D题感觉比较难扯，讲不太清楚。
A. Split it!
手动模拟一下题意，可以发现这个题大概上就是要从两边做回文，但是中间一小段可以作为(a_{k+1})从而不受回文约束。那么直接从两侧向中间求最多相同的个数再看和(k)的关系即可。
特判：偶数长度且完全消完的时候事实上(a_{k+1})就被删掉了，必须保证有一个存在。
代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
int main()
{
Angel_Dust;
int T;cin >> T;
while(T--)
{
int n,k;cin >> n >> k;
string s;cin >> s;
if(k == 0) cout << "YES
";
else
{
int l = 0,r = n - 1;
while(l < r)
{
if(s[l] != s[r]) break;
++l;
--r;
}
if(n % 2 == 0 && l == r + 1) --l;
if(l >= k) cout << "YES
";
else cout << "NO
";
}
}
return 0;
}
B. Max and Mex
不难注意到，如果出现了已经有的数，此后整个序列里面不同的数的个数必然不会再发生改变。而(mex)的更新直觉上不会太多，暴力直接做就可以了。但是有例外情况：每次加入的数如果构成递推的形式，那么就会导致暴力TLE。此时特判(mex=max+1)即可。
代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int N = 1e5+7;
ll a[N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,k;scanf("%d%d",&n,&k);
set<ll> st;
forn(i,1,n) scanf("%lld",&a[i]),st.insert(a[i]);
ll mex = 0,cir = 0;
while(st.count(mex)) ++mex;
while(k--)
{
int maxv = (*--st.end());
if(mex == maxv + 1)
{
cir = 1;
break;
}
int nxt = (mex + (*--st.end()) + 1) / 2;
if(st.count(nxt)) break;
st.insert(nxt);
while(st.count(mex)) ++mex;
}
ll ans = (int)st.size();
if(cir) ans += k + 1;
printf("%lld
",ans);
}
return 0;
}
C. Diamond Miner
标准的贪心题，比A简单。
猜想：由于距离的形式一定是(sqrt(x^2+y^2))，那么自然的就有两种方案：较小的(x)对应较小的(y)或是较小的(x)对应较大的(y)。
证明：假设答案序列(p)，那么交换其中两对((x,y))的选择不会对其他的产生影响。设为(x_1 leq x_2,y_1 leq y_2)。接下来证明顺序摆放的代价一定不劣于逆序摆放即可。对距离平方再展开做差可以得到顺序代价-逆序代价的值必然(leq 0)。则顺序摆放一定不劣。
将坐标按绝对值大小排序，再顺序求距离即可。
代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int N = 1e5+7;
ll x[N],y[N];
bool cmp(ll x,ll y)
{
return abs(x) < abs(y);
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
int idx_x = 0,idx_y = 0;
forn(i,1,2 * n)
{
int a,b;scanf("%d%d",&a,&b);
if(a == 0) y[++idx_y] = b;
else x[++idx_x] = a;
}
sort(x + 1,x + n + 1,cmp);
sort(y + 1,y + n + 1,cmp);
double res = 0;
forn(i,1,n) res += sqrt(x[i] * x[i] + y[i] * y[i]);
printf("%.15lf
",res);
}
return 0;
}
D. Let's Go Hiking
两个人一定是在单调的段上移动，由于在较短的上走一定不如较长的上走，先求出单调段最长的长度(l)以及长度是(l)的单调段的个数。当(c>2)的时候显然无解，因为先手必然先取一个。当(c=1)的时候也无解，因为对手总能放在相邻位置阻拦先手。那么只有可能是在(c=2)的时候有可能先手必胜。
若(c=2)且两段不相邻，先手必败。因为后手换一边即可胜利。那么只可能是两段拼接在一起。若两段都是单调递增单调递减的，则不可能拼接在一起。两段的单调关系只能是不同的。若连接点向两侧移动分别是单调递增的，同样先手必败，因为先手只能放在边角位置，而后手一定能放在身边导致先手输掉。
只剩一种情况：两段拼接在一起并且从连接点向两侧递减，显然(x)必取连接点。此时若(l\%2=0)则先手必败，后手只需放在边角即可。最后只有当(l%2=1)时先手必胜。
求解时，预处理(L[i])表示从左到(i)为结尾的最长上升段的长度，(R[i])对称处理。只有当最大值出现的位置都唯一且恰好相同的时候，先手必胜，其余情况先手均必败。
代码
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int N = 1e5+7;
int a[N],L[N],R[N];
int main()
{
int n;scanf("%d",&n);
forn(i,1,n) scanf("%d",&a[i]);
forn(i,1,n) if(a[i] > a[i - 1]) L[i] = L[i - 1] + 1;else L[i] = 1;
forr(i,1,n) if(a[i] > a[i + 1]) R[i] = R[i + 1] + 1;else R[i] = 1;
int maxL = 0,pos = 0;
forn(i,1,n) maxL = max({maxL,L[i],R[i]});
forn(i,1,n)
{
if(L[i] != maxL) continue;
if(pos) return puts("0"),0;
pos = i;
}
forn(i,1,n)
{
if(R[i] != maxL) continue;
if(pos && pos != i) return puts("0"),0;
pos = i;
}
if(L[pos] == R[pos] && L[pos] % 2 == 1) puts("1");
else puts("0");
return 0;
}
E. Garden of the Sun
考虑简单构造：一个粗暴的想法肯定是直接把一列涂满。如果隔着一个列涂的话很容易构成环，但是可以隔两个。题目保证每个初始空格都不相邻，所以暴力的隔两列涂满至少不会产生环，只是可能不联通。当(m\%3=0)时，每三个为一组涂满中间一列。当(m\%3=1)的时候会恰好多出一列来，这时可以把所有涂满的列往左挪动一列，那么最后一列自然也就涂满了。剩下一种情况两种构造方案都不会有问题。
剩下一个问题：这样构造的形状可能是不连通的，那么现在在两个格子的距离里面加一些点使之联通：如果只有一行或者第二行完全为空，那么把第一行两个涂起来就可以了；否则填第二行。样例的第二个可以说明暴力填第一行会形成一个大小为四的正方形。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int N = 505;
char s[N][N];
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n,m;scanf("%d%d",&n,&m);
forn(i,1,n) scanf("%s",s[i] + 1);
for(int i = 1 + (m % 3 == 0);i <= m;)
{
forn(j,1,n) s[j][i] = 'X';
i += 3;
if(i > m) break;
int pos = 2;
if(n == 1 || (s[2][i - 1] != 'X' && s[2][i - 2] != 'X')) pos = 1;
else pos = 2;
s[pos][i - 1] = s[pos][i - 2] = 'X';
}
forn(i,1,n) printf("%s
",s[i] + 1);
}
return 0;
}