首页 > 其他分享 >Codeforces 1451F Nullify The Matrix

Codeforces 1451F Nullify The Matrix

时间:2024-02-26 20:36:07浏览次数:20  
标签:Nullify val 直线 int text Nim Codeforces 1451F oplus

因为保证了这个路径必须是向下和向右,就可以考虑每一条 \(i + j = x\) 的斜线上的点,因为一条路径经过的点对应的 \(i + j\) 一定是每次 \(+ 1\) 的。

考虑到因为对于同一条直线,每个点是独立的,因为一条路径至多经过这条直线上的一个点。
于是可以考虑用 \(\text{Nim}\) 的思想把这条直线上的点权 \(\oplus\) 上,记其为 \(val_x\)。
根据 \(\text{Nim}\) 游戏可以知道如果 \(val_x = 0\) 则说明对应其必败。
于是若每条直线的 \(val_x = 0\) 则说明后手必胜,否则先手必胜。

证明可以考虑 \(\text{Nim}\) 游戏的分析:
第一个限制,若存在直线 \(val_x \not = 0\),则可以通过一次操作使得所有直线 \(val_x = 0\)。
考虑找到最小的 \(x\) 满足 \(i + j = x\) 的点权 \(val_x \not = 0\),可以知道肯定存在 \(a_{i, j}\ge a_{i, j}\oplus val_x\),那么就可以把 \(a_{i, j}\) 替换为 \(a_{i, j}\oplus val_x\)。
对于 \(y > x\) 的直线,随便选取一个点 \(a_{i, j}\) 替换为 \(a_{i, j}\oplus val_y\) 即可,因为后面的点随便加减都可以。
第二个限制,若不全局为 \(0\),对于任意直线 \(val_x = 0\),则可以通过一次操作使得存在直线 \(val_x\not = 0\)。
随便选一个非 \(0\) 的点减小即可。

时间复杂度 \(O(nm)\)。

#include<bits/stdc++.h>
const int maxn = 2e2 + 10;
int val[maxn];
inline void solve() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n + m; i++) val[i] = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
        int x; scanf("%d", &x);
        val[i + j] ^= x;
    }
    bool f = 1;
    for (int i = 1; i <= n + m; i++) f &= ! val[i];
    puts(f ? "Jeel" : "Ashish"); 
}
int main() {
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}

标签:Nullify,val,直线,int,text,Nim,Codeforces,1451F,oplus
From: https://www.cnblogs.com/rizynvu/p/18035107

相关文章

  • CF1923 Educational Codeforces Round 162 (Rated for Div. 2)
    C.FindB给出一个数组A,对于q个询问,每个询问给出[l,r],对于A的子数组[l,r],问是否存在一个相同大小的数组B,使得两个数组的和相同,且任意相同下标的元素不同?Solution:A中任意一个大于1的元素,可以把他变成1,多余的那部分给到其他位置的元素上(如最后一个)对于等于1的元素,把......
  • CF1932 Codeforces Round 927 (Div. 3)
    E.FinalCountdown我愿称之为今年最傻逼的一次,思路很快想出来了,但是实现一直搞不对观察发现答案是n的所有前i位数相加(如12345,那么ans=12345+1234+123+12+1)要证明的话就是按照题目的Note那样算,(以12345为例,ans=(12345-1234-123-12-1)+21234+2123+212+21)然后傻逼的事情......
  • Educational Codeforces Round 162 (Rated for Div. 2)
    目录写在前面ABCDE写在最后写在前面比赛地址:https://codeforces.com/contest/1923。为唐氏儿的寒假带来了一个构式的结局,飞舞一个。天使骚骚不太行啊妈的,推了三条线了感觉剧情太白开水了,咖啡馆也是这个熊样子、、、A签到。显然最优的策略是不断地选择最右侧的1进行操作,每......
  • Codeforces Round 791 (Div. 2)
     C-RooksDefenders线段树模板,维护:1)v:个数,2)sum:v的个数是否大于0.//#include"bits/stdc++.h"#include"iostream"usingnamespacestd;constintN=2e5;structNode{intl,r,v,sum;}tr1[N*4],tr2[N*4];intn,q;voidbuild(Nodetr[],i......
  • Codeforces 587D Duff in Beach
    不难发现可以按长度为\(n\)分为段。考虑到\(l\)其实并没什么大用,只是说对于选出来的\(b_{1\simx}\)可以都整体移任意段,只需要保证在范围内就行了。进一步的,发现只需要看最后一个数的取值得到其最大可以在的段数即为\(d\),那么移动的方案数就为\(d-x+1\)。还有的一......
  • Codeforces Round 926 (Div. 2)
    A.升序排列再求和#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){intn;cin>>n;vector<int>a(n+1);for(inti=1;i<=n;i++)cin>>a[i];sort(a.b......
  • Educational Codeforces Round 162 (Rated for Div. 2)
    EducationalCodeforcesRound162(RatedforDiv.2)A-MovingChips解题思路:模拟一下,不难发现是\(1\)之间\(0\)的个数。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusin......
  • Codeforces 1025F Disjoint Triangles
    结论:如果两个三角形不相交,那么一定存在两条内公切线。于是可以考虑枚举这条内公切线的端点\(x,y\)。那么一个三角形的两个端点就会在\(x\toy\)这条线的同一侧,另外一个三角形的两个端点会在这条线的另一侧。同时这条线的一侧与其配对的端点可能是\(x\)也可能是\(y\)。......
  • Codeforces 486E LIS of Sequence
    考虑一个暴力的做法:建立一个超级起点\(a_0=0\)超级终点\(a_{n+1}=\inf\)。求出\(f_i\)代表\(1\simi\)且以\(i\)结尾的\(\text{LIS}\)长度。考虑\(f_i=\max\{f_j+1\}(j<i\landa_j<a_i)\)这个转移的式子,如果\(f_i=f_j+1(j<i\landa_j<a_i......
  • codeforces 1575M Managing Telephone Poles
    假设固定了\((x,y)\),考虑其和\((x',y')\)的距离\((x-x')^2+(y-y')^2=x^2-2xx'+x'^2+y^2-2yy'+y'^2=(x^2+y^2)+(-2xx'+x'^2)+(-2yy'+y'^2)\)。第一个括号内的式子是个定值,不用管;第二三个式子都是一次函数的形式......