VP记录:Codeforces Round 865 (Div. 2) A~C

传送门:CF

难受了,本来想写到D题的,但是D题是一道交互题,只能作罢,提前润了

A题:A. Ian Visits Mary

简单的数学题,发现只要控制矩阵的宽为1就不可能在途中经过格点,直接实现即可(具体看代码)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int main() {int T=read();while(T--) {int a=read(),b=read();cout<<2<<endl;cout<<a-1<<" "<<1<<endl;cout<<a<<" "<<b<<endl;}return 0;
}

B题:B. Grid Reconstruction

一道构造题.需要找一下性质.
首先发现首尾必然应该放最大的两个数字,也就是2n,2n-1,原因显然.
我们需要让最小值最大.观察一下样例以及优美的平均思想,不难发现我们只需将所有的$2\ast k-1,2\ast k$填在斜对角即可(并且一大一小的进行填),举个栗子,也就是:

10 1 7 3 5 
2  8 4 6 9

为什么这样干是正确的呢,首先我们显然需要将小的数填在减的位置,然后将大的数字放在加的位置,这样才能保证最大.所以我们一大一小的进行填.
假设现在我们现在处于1的位置,我们有两个选择,可以走右边,也可以走下面,诶,此时我们发现走右边比走下面小加了一个1,但是我们此时又会发现走右边的话接下来走3又会少减了1,这样就平均了.这个证明可能不太严谨,但是这就是平均的优美之处!!,严谨证明应该也不难证明,但是限于篇幅此处暂略(\doge)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x = 0, w = 1;char ch = getchar();for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') w = -1;for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';return x * w;
}
#define maxn 1000000
const double eps = 1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int ans[3][maxn];
int main() {int T = read();while (T--) {int n = read();ans[1][1]=2*n;ans[2][n]=2*n-1;int l=1,r=2*n-3;for(int j=2;j<=n;j++) {if(j&1) {ans[1][j]=r;r-=2;}else {ans[1][j]=l;l+=2;}}l=2,r=2*n-2;for(int j=1;j<=n-1;j++) {if(j&1) {ans[2][j]=l;l+=2;}else {ans[2][j]=r;r-=2;}}for(int i=1;i<=2;i++) {for(int j=1;j<=n;j++) {printf("%d ",ans[i][j]);ans[i][j]=0;}printf("\n");}}return 0;
}

C题:C. Ian and Array Sorting

诶,又是一道大胆猜测的题目.
我们可以将连续的两个数加一或者减一.简单把玩一下就会发现存在这样的一个性质.假设我们有三个数$a,b,c$连续,我们可以将$a-1,c+1$或者$a+1,c-1$这两种操作是由尚需操作转化而来的,证明显然.
我们需要将原来的序列转化成一个不下降的序列,贪心的来想就需要将前面的数字改的小一点就行,也就是对于每一位数字来说,我们都要在满足大于其前面的所有数字的前提下尽量的变得更小.诶,此时我们大胆猜测,我们直接使用上述两种操作,将前面的数字都改为$0$(当然可以是任意一个数,不一定为0).也就是对于第$i$位来讲,假设对于第$i$位之前的所有数字我们都是0,我们此时将$a[i]$也变为0,将差值使用前面的转化方法加到$a[i+2]$上.这样的话,我们最终数列就变成了这样的一个数列,前$n-2$项都是0,最后两项是所有的奇数项之和以及所有的偶数项之和.所以此时只需要判断这两个数即可.因为对于相邻的两个数来说我们并不能改变他们的差值(仅当n为偶数时).
但是对于n为奇数的情况就不同了,我们可以将前$n-1$同时减小,这样就可以小于最后一个数了.也就是对于n为奇数的时候必然是满足题意的.

赛场上直接猜就完了,但是写博客不就是为了让别人知道为什么这样做是对的吗,所以此处简单证明一下:
基于上述的结论,考虑使用反证法来证明当n为偶数时,当前仅当所有奇数位和<=偶数位和时有解.那么假设当n为偶数时,当前仅当所有奇数位和>偶数位和时依旧存在解.为了方便起见将最终满足题意的奇数位记为$a1,a2,a3,a\mathrm{4....}ak$,偶数位记为$b1,b2,b\mathrm{3...}bk$
并且我们此时有$\sum a_i>=\sum b_i$,根据题意还应该有:
$a1<=b1<=a2<=b2<=...<=ak<=bk$,显然我们会发现$\sum a_i<=\sum b_i$,与已知矛盾.所以证毕.
上述证明了必要性,至于充分性应该显然,此处就不在赘述了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];
signed main() {int T=read();while(T--) {int n=read();for(int i=1;i<=n;i++) {a[i]=read();}if(n&1) {puts("YES");continue;}int sum1=0,sum2=0;for(int i=1;i<=n;i++) {if(i&1) sum1+=a[i];else sum2+=a[i];}if(sum1<=sum2) puts("YES");else puts("NO");}return 0;
}