汉阳区建设局网站,网站制作关键字排名,阿里巴巴代加工平台,建湖人才网手机版传送门:CF
难受了,本来想写到D题的,但是D题是一道交互题,只能作罢,提前润了 A题:A. Ian Visits Mary
简单的数学题,发现只要控制矩阵的宽为1就不可能在途中经过格点,直接实现即可(具体看代码)
#include bits/stdc.h
using namespace std;
typedef long long ll;
#de…传送门: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 rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int main() {int Tread();while(T--) {int aread(),bread();cout2endl;couta-1 1endl;couta bendl;}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 rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|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 l1,r2*n-3;for(int j2;jn;j) {if(j1) {ans[1][j]r;r-2;}else {ans[1][j]l;l2;}}l2,r2*n-2;for(int j1;jn-1;j) {if(j1) {ans[2][j]l;l2;}else {ans[2][j]r;r-2;}}for(int i1;i2;i) {for(int j1;jn;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,c1 a−1,c1或者 a 1 , c − 1 a1,c-1 a1,c−1这两种操作是由尚需操作转化而来的,证明显然. 我们需要将原来的序列转化成一个不下降的序列,贪心的来想就需要将前面的数字改的小一点就行,也就是对于每一位数字来说,我们都要在满足大于其前面的所有数字的前提下尽量的变得更小.诶,此时我们大胆猜测,我们直接使用上述两种操作,将前面的数字都改为 0 0 0(当然可以是任意一个数,不一定为0).也就是对于第 i i i位来讲,假设对于第 i i i位之前的所有数字我们都是0,我们此时将 a [ i ] a[i] a[i]也变为0,将差值使用前面的转化方法加到 a [ i 2 ] a[i2] a[i2]上.这样的话,我们最终数列就变成了这样的一个数列,前 n − 2 n-2 n−2项都是0,最后两项是所有的奇数项之和以及所有的偶数项之和.所以此时只需要判断这两个数即可.因为对于相邻的两个数来说我们并不能改变他们的差值(仅当n为偶数时). 但是对于n为奇数的情况就不同了,我们可以将前 n − 1 n-1 n−1同时减小,这样就可以小于最后一个数了.也就是对于n为奇数的时候必然是满足题意的.
赛场上直接猜就完了,但是写博客不就是为了让别人知道为什么这样做是对的吗,所以此处简单证明一下: 基于上述的结论,考虑使用反证法来证明当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 a1b1a2b2...akbk a1b1a2b2...akbk,显然我们会发现 ∑ a i ∑ b i \sum{a_i}\sum{b_i} ∑ai∑bi,与已知矛盾.所以证毕. 上述证明了必要性,至于充分性应该显然,此处就不在赘述了.
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define int long long
#define maxn 1000000
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];
signed main() {int Tread();while(T--) {int nread();for(int i1;in;i) {a[i]read();}if(n1) {puts(YES);continue;}int sum10,sum20;for(int i1;in;i) {if(i1) sum1a[i];else sum2a[i];}if(sum1sum2) puts(YES);else puts(NO);}return 0;
}
