传送门: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
∗
k
−
1
,
2
∗
k
2*k-1,2*k
2∗k−1,2∗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,b,c
a,b,c连续,我们可以将
a
−
1
,
c
+
1
a-1,c+1
a−1,c+1或者
a
+
1
,
c
−
1
a+1,c-1
a+1,c−1这两种操作是由尚需操作转化而来的,证明显然.
我们需要将原来的序列转化成一个不下降的序列,贪心的来想就需要将前面的数字改的小一点就行,也就是对于每一位数字来说,我们都要在满足大于其前面的所有数字的前提下尽量的变得更小.诶,此时我们大胆猜测,我们直接使用上述两种操作,将前面的数字都改为
0
0
0(当然可以是任意一个数,不一定为0).也就是对于第
i
i
i位来讲,假设对于第
i
i
i位之前的所有数字我们都是0,我们此时将
a
[
i
]
a[i]
a[i]也变为0,将差值使用前面的转化方法加到
a
[
i
+
2
]
a[i+2]
a[i+2]上.这样的话,我们最终数列就变成了这样的一个数列,前
n
−
2
n-2
n−2项都是0,最后两项是所有的奇数项之和以及所有的偶数项之和.所以此时只需要判断这两个数即可.因为对于相邻的两个数来说我们并不能改变他们的差值(仅当n为偶数时).
但是对于n为奇数的情况就不同了,我们可以将前
n
−
1
n-1
n−1同时减小,这样就可以小于最后一个数了.也就是对于n为奇数的时候必然是满足题意的.文章来源:https://www.toymoban.com/news/detail-431296.html
赛场上直接猜就完了,但是写博客不就是为了让别人知道为什么这样做是对的吗,所以此处简单证明一下:
基于上述的结论,考虑使用反证法来证明当n为偶数时,当前仅当所有奇数位和<=偶数位和时有解.那么假设当n为偶数时,当前仅当所有奇数位和>偶数位和时依旧存在解.为了方便起见将最终满足题意的奇数位记为
a
1
,
a
2
,
a
3
,
a
4....
a
k
a1,a2,a3,a4....ak
a1,a2,a3,a4....ak,偶数位记为
b
1
,
b
2
,
b
3...
b
k
b1,b2,b3...bk
b1,b2,b3...bk
并且我们此时有
∑
a
i
>
=
∑
b
i
\sum{a_i}>=\sum{b_i}
∑ai>=∑bi,根据题意还应该有:
a
1
<
=
b
1
<
=
a
2
<
=
b
2
<
=
.
.
.
<
=
a
k
<
=
b
k
a1<=b1<=a2<=b2<=...<=ak<=bk
a1<=b1<=a2<=b2<=...<=ak<=bk,显然我们会发现
∑
a
i
<
=
∑
b
i
\sum{a_i}<=\sum{b_i}
∑ai<=∑bi,与已知矛盾.所以证毕.
上述证明了必要性,至于充分性应该显然,此处就不在赘述了.文章来源地址https://www.toymoban.com/news/detail-431296.html
#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;
}
到了这里,关于VP记录:Codeforces Round 865 (Div. 2) A~C的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!