Preface
啊啊啊为什么我老是被简单题卡啊！
A. Treasure Chest
A 题题面这么长吓我一跳。
分类讨论，钥匙在前面可以拿了钥匙直接到箱子那里；箱子在前面就尽量把箱子往钥匙搬，让折回的距离尽量小。
点击查看代码
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
int T; scanf("%d",&T);
while(T--)
{
int x,y,k; scanf("%d%d%d",&x,&y,&k);
if(y<=x) printf("%d\n",x);
else
{
x=min(x+k,y);
printf("%d\n",y+(y-x));
}
}
return 0;
}
B. Points and Minimum Distance
所求为曼哈顿距离，途中肯定不能走回头路（所以需要排序），所以距离只与起点和终点的坐标有关。
把点位排个序然后以前一半为横坐标，后一半为纵坐标，这样可以让起点和终点的曼哈顿距离最小且不走回头路。
证明不来，打出来发现样例对了我就直接交了，详细证明可以在这里找找，有好几篇有详细证明的。
点击查看代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=105;
int n,a[N<<1];
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n<<1;i++)
scanf("%d",&a[i]);
sort(a+1,a+(n<<1)+1);
printf("%d\n",(a[n]-a[1])+(a[n<<1]-a[n+1]));
for(int i=1;i<=n;i++)
printf("%d %d\n",a[i],a[n+i]);
}
return 0;
}
C. Torn Lucky Ticket
不知道是什么做法的题。
因为位数较小，所以可以对于每个数都枚举位数并查找和。
具体来说，设 \(c(i,j)\) 表示长度为 \(i\)，和为 \(j\) 的数的数量。
对于某个数 \(x\)，设长度为 \(len_x\)，\(sum_x(i)\) 表示右 \(i\) 个数位的和。
如果 \(x\) 要和在左侧拼上一个 \(y\) ，设 \(x\) 的右边 \(i\) 位要作为新数的右边部分，那么 \(x\) 左边还剩下 \((len_x-i)\) 位，新数左右两侧数位数量相等，所以 \(len_y+(len_x-i)=i\)，解得 \(len_y=i-(len_x-i)\)。
此时右半部分的和为 \(sum_x(i)\)，左侧剩下 \(sum_x(len_x)-sum_x(i)\)，所需 \(y\) 的数位总和就为 \(sum_x(i)-(sum_x(len_x)-sum_x(i))\)。
所以此时合法的 \(y\) 的数量就为：
\[c ( i-(len_x-i), sum_x(i)-(sum_x(len_x)-sum_x(i)) ) \]同理，要在 \(x\) 右边拼上一个 \(y\)，合法的 \(y\) 的数量就为：
\[c ( (len_x-i)-i, (sum_x(len_x)-sum_x(i))-sum_x(i) ) \]所以答案就为：
\[\sum_{x=1}^{n}\left( \sum_{i=1}^{len_x} c(i-(len_x-i), sum_x(i)-(sum_x(len_x)-sum_x(i))) + \sum_{i=1}^{len_x} c((len_x-i)-i, (sum_x(len_x)-sum_x(i))-sum_x(i)) \right) \]化简一下（\(sum_x\) 表示 \(sum_x(len_x)\)）：
\[\sum_{x=1}^{n} \sum_{i=1}^{len_x} (c(2i-len_x,2sum_x(i)-sum_x)+c(len_x-2i,sum_x-sum_x(i))) \]#include<cstdio>
using namespace std;
const int N=2e5+5;
int n,a[N];
int cnt[15][105];
int num[N][10],sum[N][10],len[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
int t=a[i];
while(t)
{
num[i][++len[i]]=t%10; t/=10;
sum[i][len[i]]=sum[i][len[i]-1]+num[i][len[i]];
}
cnt[len[i]][sum[i][len[i]]]++;
}
long long ans=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=len[i];j++)
{
//sum[j]=?+(sum[len]-sum[j]); j=?+(len-j)
int nd_len=j-(len[i]-j),nd_sum=sum[i][j]-(sum[i][len[i]]-sum[i][j]);
if(nd_len>0&&nd_sum>0) ans+=cnt[nd_len][nd_sum];
}
for(int j=1;j<=len[i];j++)
{
//sum[j]+?=sum[len]-sum[j]; j+?=len-j
int nd_len=(len[i]-j)-j,nd_sum=(sum[i][len[i]]-sum[i][j])-sum[i][j];
if(nd_len>0&&nd_sum>0) ans+=cnt[nd_len][nd_sum];
}
}
printf("%lld\n",ans);
return 0;
}
D. XOR Construction
好题。
如果知道了 \(b_1\) 其它的 \(b\) 也都能一下推出来（\(b_i=b_{i-1} \oplus a_{i-1}\)）。
枚举 \(b_1\)，通过二进制建立 \(a\) 前缀异或和的 01-Trie，插入 \(b_1\) 查找最大异或值，判断是否小于 \(n\) 即可。
这里有很多我这种做法的详解。
#include<cstdio>
#include<bitset>
using namespace std;
const int N=2e5+5,LogN=20;
int n,a[N],sum[N],b[N];
int trie[N<<1][2],idx=1;
void insert(bitset<LogN+5> x)
{
int p=1;
for(int i=LogN;i>=0;i--)
{
bool t=x[i];
if(!trie[p][t]) trie[p][t]=++idx;
p=trie[p][t];
}
return;
}
bool check(bitset<LogN+5> x)
{
int p=1,now=0;
for(int i=LogN;i>=0;i--)
{
bool t=x[i];
if(trie[p][!t]) //可以异或出1
{
p=trie[p][!t];
now=(now<<1)+1;
}
else
{
p=trie[p][t];
now=(now<<1)+0;
}
}
return now<n;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]^a[i];
insert(sum[i]);
}
for(b[1]=0;b[1]<n;b[1]++)
if(check(b[1])) break;
printf("%d ",b[1]);
for(int i=2;i<=n;i++)
printf("%d ",sum[i-1]^b[1]);
return 0;
}