闲话
第一场CF div3，T2读错题了...T3构造乱搞没搞出来...在此深刻反思。
A
Translate
我们可以任意将一个数组拆成两部分，分别求出这两部分的和，是否有一种拆分方式使得这两部分和的奇偶性相同？
Analysis
根据小学数学我们得知
- 奇数+奇数 = 偶数
- 奇数+偶数 = 奇数
- 偶数+偶数 = 偶数
考虑如何分组，对于一个奇数，她有两种情况：
- 和奇数分为一组
- 和偶数分为一组
我们先考虑和偶数分为一组是什么情况。
先考虑如果一组内有奇数个奇数，那么第二组必须也有奇数个奇数。也就是说题目中必须有偶数个奇数。
再考虑如果一组内有偶数个奇数，那么这一组的和一定是偶数，第二组也必须有偶数个奇数（0也是偶数）。因为偶数+偶数=偶数，所以题目中必须有偶数个奇数。
我们再来考虑奇数和奇数分为一组，偶数和偶数分为一组。
容易发现这种分组方式必须有偶数个奇数。
归纳一下，上述分组方案中原题都必须有偶数个奇数，因此，我们只需要统计一下原数组中奇数个数，最后看看是否有偶数个奇数即可。
反思：比赛的时候口胡了一个奇数和奇数分为一组的性质就交了，没考虑这么多，如果是OI赛制需要验证算法正确性。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 10010
using namespace std;
int T;
int a[N];
int main()
{
// freopen("input.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) cin>>a[i];
int sum1=0,sum2=0;
for(int i=1;i<=n;i++)
{
if(a[i]%2 != 0) sum1++;
}
if(sum1%2 == 0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
B
Translate
给定一个自然数 \(x\)，你可以对这个数的各个数位进行如下操作（可以不操作或操作多次）：
- 将其四舍五入至这一位，即，如果这个数位的更低一位大于等于 \(5\)，那么这个数位加上 \(1\)（逢十则进一），并将这个数位的所有更低的数位变成 \(0\)。
问操作后的 \(x\) 的最大值可能是多少。本题有多测，共 \(t\) 组数据。
\(1\le t \le 10^4, 0\le x < 10^{2\times 10^5}\)。
Analysis
我们发现本题牵扯到了进位操作，这启发我们从小到大进行处理进位。
此外，本题允许进行多次“四舍五入”操作，我们肯定是要尽可能的多进位，所以我们从低位到高位看每一位能否进位，如果能进则肯定进，如果不能进就是无效操作了。
每完成一次进位操作后标记一下当前位置，因为每次操作后该位后面都变成 \(0\) ，显然不会影响下一步的进位，于是我们可以最后一块处理。显然最后一次标记后面就必须全是 \(0\) 了。起到了一个很好的优化
虽然题面说最大是多少，但实际上就是个模拟题。
中间实现的时候需要注意一些细节，见代码注释
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
int T;
int main()
{
// freopen("input.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
string s,s1;
cin>>s1;
s = "0"+s1; //补全前导0
int pos = 0;
for(int i=s.size()-1;i>0;i--) //从低位到高位
{
if(s[i] == '9'+1) //处理进位
{
s[i] = '0';
s[i-1] ++;
}
if(s[i] >= '5') //处理“五入”
{
s[i-1] ++;
pos = i; //标记一下当前位置后面的都位0
}
}
for(int i=0;i<s.size();i++)
{
if(i == 0 && s[i] == '0') continue; //前导0不输出
if(i == pos) //到达标记点后面的都是0
{
for(int j = pos;j<s.size();j++) cout<<"0";
break;
}
cout<<s[i];
}
cout<<endl;
}
}
反思：题意需要读明白再写，看清楚这是一个什么题，例如本题就是一个简单的模拟。
C
Translate
有一个长度为 \(n\) 序列 \(A\) 和一个序列 \(B\)。\(B\) 为 \(A\) 中任意两数的最小值。那么，\(B\) 的长度为 \(\dfrac{n(n-1)}2\)。现将 \(B\) 随机打乱，请求出相对应的 \(A\)。只需输出一种方案。
Analysis
很有意思的构造题。
对于这种构造题，一般是开启spj，也就是任意一种符合题目要求的构造均可。我们可以找一些特殊性质来启发我们。
我们发现若 \(a\) 数组是从小到大排好序的，定义 \(ans_i\) 表示第 \(i\) 个数与后面 \(n-i\) 个数两两比较的最小值，则显然 \(ans_1 = a_1,ans_2 = a_2,ans_3 = a_3...\) 。
简要证明:
已知 \(a\) 数组单调不减，以 \(ans_1\) 为例，第 \(1\) 个数一定比后面 \(n-1\) 个数小。同理，第 \(2\) 个数一定比后面 \(n-2\) 个数小......以此类推，得证。
至于最后一个数输出 INF 即可。需要注意 INF 最大是1e9，否则会超出题目范围导致WA on test 1
类似于构造题我们可以手搓数据，可以构造一点特殊性质例如排好序，找出规律，推结论。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#define INF 1e9
#define N 1000005
using namespace std;
int T;
int a[N];
int main()
{
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n*(n-1)/2;i++) scanf("%d",&a[i]);
sort(a+1,a+n*(n-1)/2+1);
int now = 0;
int minn = INF;
for(int i=1;i<=n;i++)
{
for(int j=i;j<n;j++) //每一组
{
now++;
if(j == i) cout<<a[now]<<" "; //由于已经排好序输出每一组的首位即可
}
}
cout<<minn<<endl;
}
}
待更...