首页 > 其他分享 >P5102 [JOI 2016 Final] 领地

P5102 [JOI 2016 Final] 领地

时间:2024-06-18 17:36:27浏览次数:31  
标签:kx return int P5102 ll pos ky 2016 Final

P5102 [JOI 2016 Final] 领地 模拟赛题,但是赛时挂在了取模上,就差一点啊啊啊啊啊啊。

记 \((x_i,y_i)\) 是移动了 \(i\) 次后的坐标。

肯定要从周期的方面考虑,每一组操作产生的点是上一组操作产生的点在 \(x\) 轴方向平移了 \(x_n\),\(y\) 轴方向平移了 \(y_n\) 得到的,即 \(\forall i\geq n,(x_i,y_i)=(x_{i\bmod n}+k x_n,y_{i\bmod n}+k y_n)\),其中 \(k=\lfloor \dfrac{i}{n} \rfloor\)。

那我们考虑将所有可以表示为 \((x'+kx_n,y'+ky_n)\) 的点分为一组,每个点也只会分到一组中。在一组中钦定唯一一个位置使其编号即 \(k\) 值为 \(0\),这样每个点都获得了一个编号。

那么我们现在有一个点编号为 \(p\),进行所有 \(K\) 组操作后,这个点覆盖的编号区间即 \([p,p+K-1]\)。我们可以直接在每组中做这个,然后取区间并,就得到了这组点中所有可以覆盖的地方。

现在我们对每组点同时做原问题,其实就相当于找到另外三组点,然后求它们覆盖的区间交。

初始点数是 \(O(n)\) 的,所以组数也是 \(O(n)\) 的,所以区间数也是 \(O(n)\) 的,中间需要一些排序,所以时间复杂度是 \(O(n\log n)\)。

再说一些细节。

\(x_n=y_n=0\) 要特别处理一下,也就是每个点单独是一组,一些写法可能要把 \(K\) 手动改成 \(1\)。

分组相当于每组点在一条直线上,每条直线的斜率也是一样的,所以可以通过截距找出每条直线。截距是 \(y-\dfrac{y_n}{x_n}x\),可以乘一个分母变成整数,同时防止除以 \(0\)。

但是每条直线不一定是一个组,同一截距每个 \(x\equiv x'\pmod {x_n}\) 是一组,\(x_n\) 为 \(0\) 时可以改为用 \(y\) 和 \(y_n\) 做,后面一些东西也是。注意取模的时候负数和正数的取模值是不一样的,要转一下。

这样每组对应一个截距和 \(x\bmod x_n\) 组成的二元组,可以用哈希表存一下。每组可以把第一个加进去的点的 \(k\) 值设为 \(0\)。求每个点 \((x,y)\) 对应的 \(k\) 值直接用 \(x\) 减去第一个点的横坐标再除一下 \(x_n\) 即可。

求区间交的时候,每组点编号并不统一,手动统一一下就行。比方说当前组 \(k=0\) 的点是 \((x,y)\),那么找到 \((x,y+1)\) 在他们组当中的 \(k\) 值 \(k'\),然后每个端点减去 \(k'\),就可以统一编号了。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
#define ll long long
using namespace std;
const int MAXN=1e5+10;
string s;int T,n,kx,ky,tot;ll ans;
unordered_map <ll,int> H;
struct ple{ll x,y,z;};vector <ple> v;
inline bool cmp(ple x,ple y)
    {return x.x!=y.x?x.x<y.x:x.z>y.z;}
inline bool ccmp(ple x,ple y)
    {return x.x!=y.x?x.x<y.x:x.y<y.y;}
struct node
{
    vector <ple> v,t,f;
    inline void work()
    {
        for(ple now:v) t.push_back({now.z,now.z+(T-1)});
        sort(t.begin(),t.end(),ccmp);ll l=t[0].x,r=t[0].y;
        for(int i=1;i<t.size();++i)
        {
            if(r>=t[i].x-1){r=max(r,t[i].y);continue;}
            f.push_back({l,r}),l=t[i].x,r=t[i].y;
        }
        f.push_back({l,r});return ;
    }
}t[MAXN];
inline ll M(ll x,ll y){y=abs(y);return (x%y+y)%y;}
inline ll pos(ll x,ll y)
{
    if(!kx&&!ky) return x*1000000+y;
    return (y*kx-x*ky)*100000+(kx?M(x,kx):M(y,ky));
}
inline ll F(ll x,ll y)
{
    if(!kx&&!ky) return 0;
    ll num=pos(x,y);int pos=H[num];
    ll prex=t[pos].v[0].x,prey=t[pos].v[0].y;
    return (kx?(x-prex)/kx:(y-prey)/ky);
}
inline void upd(ll x,ll y)
{
    ll num=pos(x,y);if(!H[num])
        H[num]=++tot,t[tot].v.push_back({x,y,0});
    else
    {
        if(!kx&&!ky) return ;
        int pos=H[num],prex=t[pos].v[0].x,prey=t[pos].v[0].y;
        if(kx) t[pos].v.push_back({x,y,(x-prex)/kx});
        else t[pos].v.push_back({x,y,(y-prey)/ky});
    }
}
signed main()
{
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>T>>s;
    for(char c:s)
    {
        if(c=='N') ++ky;if(c=='S') --ky;
        if(c=='E') ++kx;if(c=='W') --kx;
    }
    if(!kx&&!ky) T=1;upd(0,0);int x=0,y=0;
    for(int i=1;i<=n;++i)
    {
        char c=s[i-1];
        if(c=='N') ++y;if(c=='S') --y;
        if(c=='E') ++x;if(c=='W') --x;
        upd(x,y);
    }
    for(int i=1;i<=tot;++i) t[i].work();
    for(int i=1;i<=tot;++i)
    {
        ll x=t[i].v[0].x,y=t[i].v[0].y,s=0,pre;
        ll num1=pos(x,y+1);if(!H[num1]) continue;
        ll num2=pos(x+1,y);if(!H[num2]) continue;
        ll num3=pos(x+1,y+1);if(!H[num3]) continue;
        ll pos[4]={i,H[num1],H[num2],H[num3]};
        ll del[4]={0,F(x,y+1),F(x+1,y),F(x+1,y+1)};
        for(int o=0;o<4;++o) for(ple now:t[pos[o]].f)
            v.push_back((ple){now.x-del[o],o,1}),
            v.push_back((ple){now.y-del[o],o,0});
        sort(v.begin(),v.end(),cmp);
        for(ple now:v)
        {
            if(s==15) ans+=now.x-pre+1;
            s^=(1<<now.y),pre=now.x;
        }v.clear();
    }
    cout<<ans<<'\n';return 0;
}

标签:kx,return,int,P5102,ll,pos,ky,2016,Final
From: https://www.cnblogs.com/int-R/p/18254699/P5102

相关文章

  • FinalReference 如何使 GC 过程变得拖拖拉拉
    本文基于OpenJDK17进行讨论,垃圾回收器为ZGC。提示:为了方便大家索引,特将在上篇文章《以ZGC为例,谈一谈JVM是如何实现Reference语义的》中讨论的众多主题独立出来。FinalReference对于我们来说是一种比较陌生的Reference类型,因为我们好像在各大中间件以及JDK中......
  • Reflective Journal Final
    1.WhenIfirstventuredintotherealmofdigitalmultimodalcreation,Iinitiallybelievedthatcreationwassolelyconfinedtowords,relyingsolelyonvocabularyandgrammartoconveyinformation.However,asIdelveddeeperintomystudies,Igraduall......
  • Reflective Journal Final
    1.IbelievethattheevolutionofdigitalmultimodalcreationhasevolvedfromsimplePPTproductiontodiversefactorssuchasinsertingimagesandaudio,andthentocreatingyourownvideos,addingsubtitle,narration,stickers,andvisualeffects.As......
  • World Tour Finals 2022 Day2 E: Adjacent Xor Game
    考虑从高到低位做,不断贪心的一个过程。即假设把当前所有数\(a_i\)看成\(\lfloor\frac{a_i}{2^d}\rfloor\),有当前最优答案\(ans_d\);现在把所有数看成\(\lfloor\frac{a_i}{2^{d-1}}\rfloor\),推出下一步的答案\(ans_{d-1}\)。假设\(/2^d\)时,每一步xor完的序列是\(a_1......
  • 处理问题:windows server 2016由于没有远程桌面授权服务器可以提供许可证,远程会话被中
      windowsserver可以多用户同时登陆,默认最大远程登录数量为2,如果有更多人需要同时远程登录,则需要安装远程桌面授权服务,第一次安装后,免费期为120天,超过则无法正常远程登录。解决办法如下:Windowsserver2016服务器远程桌面登录时出现错误提示:“由于没有远程桌面授权服务器......
  • [lnsyoj166/luoguP2822/NOIP2016提高组] 组合数问题
    题意原题链接给定\(n,m,k\),对于所有的\(0\lei\len,0\lej\lemin\{i,m\}\),有多少对\((i,j)\)满足\(k|(^i_j)\)sol在解决组合数问题时,若遇到\(n,m\le2000\)的情况,可以使用递推法(杨辉三角)来进行\(O(n^2)\)的预处理,再\(O(1)\)直接调用递推法求组合数\[(^n_m)=(^{n-1}_m)+(......
  • 帮猪猪修修改的代码2016年的代码记录
    这是一个图片轮播的代码,但是它们的是css动画,当时代码运行不了,我花了二天才修改,现在记录一下,凭回忆用。<!DOCTYPEhtml><html><head><metacharset="utf-8"><title>网易科技</title><metaname="viewport"content="width=de......
  • F. Final Boss
    原题链接题解1.由于一回合可以使用多次技能,所以直接二分回合数即可2.回合数最多为\(4^{10}\)code#include<bits/stdc++.h>usingnamespacestd;#definelllonglonglla[200005],c[200005];llh,n;inlinevoidread(ll&x){x=0;llflag=1;char......
  • Java面试:final关键字有什么特点?
    final关键字在Java中有多种用途和特点,它可以用在类、方法和变量的声明中。以下是final关键字在不同上下文中的特点和用途:1.final类特点:当一个类被声明为final时,这个类不能被继承。不能创建这个类的子类,任何试图继承这个类的行为都会导致编译错误。示例:publicfinalc......
  • public、private、protected、package、final
    public关键字用于将类、方法或变量声明为公共的,意味着它们可以被所有类访问。无限制,全局可见。private关键字用于将类、方法或变量声明为私有的,意味着它们只能在声明它们的类内部访问。仅限于同一类。java支持嵌套类,如果一个类内部还定义了嵌套类,那么,嵌套类拥有访问private的权......