首页 > 其他分享 >CF 948 DIV.2 D. XORificator

CF 948 DIV.2 D. XORificator

时间:2024-05-29 17:34:21浏览次数:25  
标签:948 int CF DIV.2 XORificator mx

考虑对每个设置为1且唯一
那么我们发现对于所有的状态都是确定且唯一的
那么我们对于每个点假设它为1且为该列唯一
对于除它之外的点的状态进行存储
又由于这个值过于大
我们考虑使用哈希存储
那么出现次数最多的值即为答案

点击查看代码
map<ull,int>cnt;
map<ull,pii>pos;
void solve(){
    cnt.clear(),pos.clear();
    int n,m;cin>>n>>m;
    vector<vector<int>>a(n+1,vector<int>(m+1));
    string s;
    for(int i=1;i<=n;i++){
        cin>>s;
        for(int j=1;j<=m;j++)a[i][j]=s[j-1]-'0';
    }
    for(int j=1;j<=m;j++){
        ull H=0;
        for(int i=1;i<=n;i++)H=H*B+a[i][j];
        for(int i=1;i<=n;i++){
            ull H0=H;
            if(a[i][j]==0)H0+=pw[n-i];
            else H0-=pw[n-i];
            if(!cnt[H0])pos[H0]=make_pair(i,j);
            cnt[H0]++;
        }
    }
    int f1=0;ull mx=0;
    for(auto it:cnt){
        if(!f1){
            mx=it.first;
            f1=1;continue;
        }
        if(it.second>cnt[mx])mx=it.first;
    }
    cout<<cnt[mx]<<'\n';
    int x=pos[mx].first,y=pos[mx].second;
    for(int i=1;i<=n;i++){
        if((i==x)^a[i][y])cout<<1;
        else cout<<0;
    }
    cout<<'\n';
}
参考by https://www.luogu.com.cn/article/kwqplv51

标签:948,int,CF,DIV.2,XORificator,mx
From: https://www.cnblogs.com/archer233/p/18220745

相关文章

  • CF1975 记录
    一些吐槽考虑到我老是忘记自己做过什么题,而且这次打的实在太唐,就打算每次vp或者比赛完补完题写个总结,先说结论,D分讨了一年然后胃疼去睡觉,三题遗憾离场,赛后发现状态好冲到ForG问题不大,寄。A到C不标注数据范围。CF1975A给定一个序列,问是否能在若干次切断-交换操作后......
  • CF ROUND946 (DIV. 3)D:构造
    Ingenuity-2题面翻译你有两个机器人,分别是Rover(R)和Helicopter(H)。它们初始都在同一平面直角坐标系\(xOy\)的\((0,0)\)处。定义北为\(y\)轴正方向,东为\(x\)轴正方向。现有一串由以下四个字符指令组成的指令串\(s\):N向北移动一步,即\((x,y)\to(x,y+1)......
  • CF Div. 2 C
    CodeforcesRound948(Div.2)C.NikitaandLCM标签暴力枚举数据结构[[数学]]题目大意有长度为n的数组a,求a中最长子序列的长度,子序列要满足\(lcm(subArray(a))\notina\)\(1\len\le2000\),\(1\lea_i\le10^9\),对于t个测试案例,\(sum(n)\le2000\)思路1.......
  • CF1843E Tracking Segments
    题目链接:https://www.luogu.com.cn/problem/CF1843E思路:题目要求至少第几次修改后满足给定的一个区间是美丽区间.我们发现修改操作是有单调性的,随着修改次数的增加,那么满足的美丽区间数量一定会保持不变或增多.因此我们选择二分答案,二分修改次数.二分答案的check函数就根......
  • 大学生看过来:CCF-智谱清言-全国智能体开发比赛
    前言Al界的新话题——基于大模型(LLM)的智能体正在成为大学生日常工具,它们正式让人人都是产品经理变得有可能。它们模仿人类决策过程,拥有无限的应用潜力和强大功能。想要提升学习效率、丰富自己的课余生活、实现人机协同?智能体让你轻松搞定!只要能看到需求有痛点,就可以创作智......
  • CCF-CSP真题《202403-1 词频统计》思路+python满分题解
    哇q(≧▽≦q),第一次写博客,请大家多多关照○| ̄|_ 看到没啥人提供202403的第一题解题思路及python代码,刚好写完,心血来潮想分享解题思路,就写下了这篇博客,有其他的编码版本,欢迎大家一起探讨呀(虽然我是算法菜鸟┗(T﹏T)┛,但有问题,我会尽力回答的!!!)好了废话不多说,上解题思路!大概想了......
  • 「杂题乱刷」CF1977B
    题目链接CF1977B(luogu)CF1977B(codeforces)解题思路考虑通用做法。我们发现如果直接用二进制来表示的话这个数会只包含\(0,1\)这两个数字。发现这时阻碍我们构造的是连续的数字\(1\)。考虑消除连续的数字\(1\)。容易发现连续的数字\(1\)可以转化成将这一段最高位......
  • 「杂题乱刷」CF1977C
    题目链接CF1977C(luogu)CF1977C(codeforces)解题思路首先这题有一个简单的思路,就是当这个序列的LCM大于\(10^9\)时,显然取所有数字数字是合法的。然后我们接下来考虑LCM小于等于\(10^9\)的情况。发现这种情况LCM很小,且有一个简单的结论,就是你在序列中任选一个子......
  • 从CF1660F2看同余分组
    https://codeforces.com/contest/1660/problem/F2同余分组,树状数组维护逆序对先承继F1的做法,维护一个前缀和数组,让s[i]=='+'为\(1\),s[i]=='-'为\(-1\)。那么要满足两个条件:\(pre_r-pre_l\leq0\)要么加减号相同,要么减号更多(只有减号能减少)\(pre_r-pre_l......
  • 【最新区块链论文录用资讯】CCF A—INFOCOM 2024 共17篇
    Conference:IEEEInternationalConferenceonComputerCommunicationsCCFlevel:CCFACategories:计算机网络Year:2024Num:17AGenericBlockchain-basedSteganographyFrameworkwithHighCapacityviaReversibleGAN通过可逆GAN实现高容量的基于区块链的通用隐......