jyt回寝室

题意

在一个$n\ast mn*m$的f(1,1)=1，对于每一行，,对于每行第一个格子，的矩阵中。

做法

对于矩阵中每一个2*2矩阵从左上到右下来说

如上图所示蓝线走法最为优秀。

所以对于任何一种如上图从左上到右下的走法（蓝线）都可以优化成先走到右上（绿线）。

可以证明，任何一种矩阵，先直线走到右上然后从右上走到右下最为优秀。

如图

时间复杂度O(n+m)

关键代码

long long ans = 0 , i;
for(i = 1 ; i <= m ; i ++) ans += i;
for(i = 2 ; i <= n ; i ++) ans += m * i;
printf("%lld\n", ans);

jyt的序列1

题意

在一个$[l,r][l,r]$的序列中，你可以对这个序列进行k次操作。

每次操作可以选两个数，将这两个数从序列中删除并将这两个数的乘积插回序列中。

问能否在k次操作后使得序列中所有数的最大公约数（gcd）不等于1。

做法

设对于任何一个gcd为m （m!=1）的结果，最优的办法是将对所有不为m的倍数的数与为m的倍数的数进行操作，这样使得序列中没有数不为m的倍数，gcd为m的倍数。

如果序列中存在m的倍数（即$\frac{r}{m}-\frac{l-1}{m}>0\backslash frac\{r\}\{m\}-\backslash frac\{l-1\}\{m\}>0$），那么非m的倍数的个数(即最少操作数)为$\mathrm{（}r-l+1)-(\frac{r}{m}-\frac{l-1}{m})（r-l+1)-(\backslash frac\{r\}\{m\}-\backslash frac\{l-1\}\{m\})$,可证m越小越好，所以m=2时，所需操作数最少。

所以只需判断奇数个数是否不大于k。

时间复杂度O(T)

关键代码

int f = 0;
if(r == l && l != 1) f = 1;//当序列个数为1且这个数不为1时同样符合要求
if(((r - l + 1 ) - ( r / 2 - ( l - 1 ) / 2)) <= k) f = 1;
if(f == 1) printf("YES\n");
else printf("NO\n");

jyt的序列2

题意

构造一个从1到n的序列，使得这个序列相邻两个数之间的差大于1且小于4.

做法

本题提供一种简单的构造方法。

设q为小于等于n的最大偶数，设p为小于等于n 的最大奇数

q  q-2  q-4 ..... 8  6        3  1  4  2        5  7 ..... p-4  p-2  p

反向也可

时间复杂度O(n)

关键代码

for(i = n - n % 2 ; i >= 6 ; i -= 2) printf("%d ", i);
printf("3 1 4 2 ");
for(i = 5 ; i <= n ; i += 2) printf("%d ", i);

jyt和wtr的博弈

题意

对于两个序列，两个人打算轮流从序列删除一些数，每次只能删掉其中一个序列开头的位置的数，且每次删的数必须比上一个人删的数大。 如果有人删不了，那么这个人输，另一个人赢。

两个人绝对聪明

做法

首先我们将找出两个序列中起始最长连续上升段（从头开始的连续单调递增最长序列）的长度，我们后面简称为上升段长度。

我们将起始点大的称之为大路，小的称之为小路（如果相等谁都可以）。

对于先手来说，先手拿走大路的第一个点，那么小路第一个点就拿不走，小路作废，

如果大路上升段长度为奇数，那么这个上升段将正好被先手拿完，后手没法拿，先手胜。

如果大路上升段长度为偶数，先手不会傻到先拿大路起始点，那么先手会去拿小路第一个点，如果小路上升段长度也为偶数，此时两个路都为偶数，无论先手怎么拿，后手只需紧随先手，先手拿哪条路，后手就拿哪条路。可以始终保持两个路为偶数，最后后手会先拿完某一路的上升段，后手胜。

如果小路上升段为奇数，那么先手先拿小路，然后两条路同时变成偶数，对于后手来说，如同刚才讨论先手拿两个偶数路一样，后手拿哪条路，先手就拿哪条路，最后先手拿完，先手胜。

通过讨论可知，如果任意一条路为奇数，那么先手胜，否则后手胜。

时间复杂度O(n)

关键代码

int f = 1, g = 1, cnt1 = 0, cnt2 = 0, i , last , x;
for (i = 1, last = -1; i <= n; i ++) {
    scanf("%d", &x);
    if(f && x > last) cnt1 ++, last = x;
    else f = 0;
}
f = 1;
for (i = 1, last = -1; i <= m; i ++) {
    scanf("%d", &x);
    if(f && x > last) cnt2 ++, last = x;
    else f = 0;
}

if(cnt1 % 2 || cnt2 % 2) printf("jyt is win!\n");
else printf("wtr is win!\n");