hgoi#20191111

muronglin
muronglin 2019年11月11日
  • 在其它设备中阅读本文章

T1- 文件改名

你现在有 $n$ 个文件名不同的文件,要更改这 $n$ 个文件的文件名 一次可以修改一个文件的文件名,要求中途不能有文件名相同 问最少修改几次

解法

可以发现,分三种情况 如果是自环,啥都不用改 如果不在环上,顺着直接改就好了 如果在环上,需要先改一次使环断开

ac 代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define M1 19260817
#define M2 20040220
#define N 100010
using namespace std;
map<pii,int>P;
pii tmp;
int n,cnt,l,tmp1,tmp2,tg,ans,a[N],b[N],vis[N],rd[N],id[N<<1];
char str1[20],str2[20];
int dfs(int u)
{
    if(vis[u])tg=1;
    else
        cnt++,vis[u]=1,(id[b[u]])&&(dfs(id[b[u]]));
}
int main()
{
    freopen("files.in","r",stdin);
    freopen("files.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s%s",str1+1,str2+1);
        tmp1=tmp2=0,l=strlen(str1+1);
        for(int i=1;i<=l;i++)
            tmp1=(tmp1*233ll+str1[i])%M1,
            tmp2=(tmp2*2333ll+str1[i])%M2;
        tmp=mp(tmp1,tmp2);
        (!P.count(tmp))&&(P[tmp]=++cnt);
        a[i]=P[tmp],id[P[tmp]]=i;
        tmp1=tmp2=0,l=strlen(str2+1);
        for(int i=1;i<=l;i++)
            tmp1=(tmp1*233ll+str2[i])%M1,
            tmp2=(tmp2*2333ll+str2[i])%M2;
        tmp=mp(tmp1,tmp2);
        (!P.count(tmp))&&(P[tmp]=++cnt);
        b[i]=P[tmp];
    }
    for(int i=1;i<=n;i++)
        (id[b[i]])&&(rd[id[b[i]]]=1);
    for(int i=1;i<=n;i++)
        (!rd[i])&&(cnt=0,dfs(i),ans+=cnt);
    for(int i=1;i<=n;i++)
        (!vis[i]&&a[i]!=b[i])&&(tg=cnt=0,dfs(i),ans+=cnt+tg);
    printf("%dn",ans);
    return 0;
}

T2- 怪物猎人

有 $n$ 个怪物,每个怪物有两个属性 $A_i,B_i$ 杀死一个怪物需要 $A_i*B_i$ 的血量 现在给你 m 个人,每个人分别有 $h_i$ 的血量 每杀死一个怪物,其它怪物的两个属性都会上升 $d$ 问你每个人最多能杀死多少怪物

解法

杀死一个怪物的耗血 $H=(A+kd)(B+kd)=AB+kd(A+B)+k^2d^2$
所以杀一堆怪时,最优策略是先杀 $A_i+B_i$ 较大的
我们根据 $A_i+B_i$ 来排序
设 $f_{i,j}$ 表示考虑到第 i 个怪物,有 j 个怪物不杀
需要的最少血量,转移的话推一下删掉一个怪物会减少的血量即可

还有一种更好的 DP(其实是我考场上想假掉惹 QWQ)
设 $f_{i,j}$ 表示考虑到第 i 个怪物,取 j 个怪物需要的最少血量
那么 $f_{i,j}=min(f_{i-1,j},f_{i-1,j-1}+(A_i+(j-1)d)(B_i+(j-1)d))$
代码懒得写了,放过我吧 QAQ划掉,我把代码写出来了嘤嘤嘤~

ac 代码

//第一种DP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    int s;ll g;
    bool operator<(const node&a)const{return s>a.s;}
}a[3010];
int n,m,d,x[3010],y[3010];
ll s[3010],ans[3010],f3010,h[300010];
int main()
{
    freopen("hunter.in","r",stdin);
    freopen("hunter.out","w",stdout);
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1;i<=n;i++)scanf("%d",&x[i]);
    for(int i=1;i<=n;i++)scanf("%d",&y[i]);
    for(int i=1;i<=n;i++)a[i]={x[i]+y[i],1llx[i]y[i]};
    for(int i=1;i<=m;i++)scanf("%lld",&h[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        f0+=a[i].g+1ll(i-1)a[i].sd+1ll(i-1)(i-1)d*d;
    for(int i=n;i>=1;i--)s[i]=s[i+1]+a[i].s;
    for(int i=1;i<=n;i++)
    {
        fi=fi-1,fi=fi-1-a[i].g-s[i+1]d-1ll(n-i)(n-i)d*d;
        for(int j=1;j<i;j++)
            fi=min(fi-1,fi-1-a[i].g-1ll(i-j)a[i].sd-s[i+1]d-1ll(n-j)(n-j)dd);
    }
    for(int i=1;i<=n;i++)ans[i]=fn;
    for(int i=1;i<=m;i++)
        printf("%d ",lower_bound(ans+1,ans+n+1,h[i])-ans-1);
    return 0;
}
//第二种DP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
    int x,y;
    bool operator<(const node&a)const{return x+y>a.x+a.y;}
}a[3010];
int n,m,d;
ll f3010,h[300010];
int main()
{
    freopen("hunter.in","r",stdin);
    freopen("hunter.out","w",stdout);
    scanf("%d%d%d",&n,&m,&d);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].x);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].y);
    for(int i=1;i<=m;i++)scanf("%lld",&h[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
    {
        fi=fi-1,fi=fi-1+1ll(a[i].x+(i-1)d)(a[i].y+(i-1)d);
        for(int j=1;j<i;j++)
            fi=min(fi-1,fi-1+1ll(a[i].x+(j-1)d)(a[i].y+(j-1)d));
    }
    for(int i=1;i<=m;i++)
        printf("%d ",lower_bound(f[n]+1,f[n]+n+1,h[i])-f[n]-1);
    return 0;
}

T3- 魔法帽游戏

你有一个长度为 $n$ 的数组,初始时 $A_i=i$ 你还有一个长度为 $m$ 的操作序列,每次操作 $a_i,b_i$ 表示交换这两个位置上的数 你有 $q$ 个询问,每次询问 $x,l,r$ 表示顺序做了 $[l,r]$ 区间内的操作后数 $x$ 在哪里

解法

看到这个题,前几天学的莫队终于有用了! 这不就是莫队的板子题吗~ 嘤嘤嘤~
关于莫队,详见 学习笔记 #莫队
那么指针移动所带来的影响是什么呢 对于 l 指针,不管是左移还是右移,都是交换一次 那交换什么呢,我们考虑到这是一开始就做的交换 所以要对于值交换,也就是将当前状态中值为 $a_l,b_l$ 的数交换 对于 r 指针,不管左移右移,也是交换一次 因为是最后做的交换,所以直接对位置交换即可 具体为将当前状态中位置为 $a_r,b_r$ 的数交换 然后用莫队暴力搞一下就愉快的 AC 啦 正解竟然是 O(n+m+q)的,什么神仙啊

ac 代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define N 200010
#define reg register
using namespace std;
namespace fast_IO
{
    const int IN_LEN = 10000000, OUT_LEN = 10000000;
    char ibuf[IN_LEN], obuf[OUT_LEN], ih = ibuf + IN_LEN, oh = obuf, lastin = ibuf + IN_LEN, lastout = obuf + OUT_LEN - 1;
    inline char getchar_(){return (ih == lastin) && (lastin = (ih = ibuf) + fread(ibuf, 1, IN_LEN, stdin), ih == lastin) ? EOF : *ih++;}
    inline void putchar_(const char x){if(oh == lastout) fwrite(obuf, 1, oh - obuf, stdout), oh = obuf; *oh ++= x;}
    inline void flush(){fwrite(obuf, 1, oh - obuf, stdout);}
    inline void read(reg int&x)
    {
        char c=getchar_();
        for(;!isdigit(c);c=getchar_());
        for(;isdigit(c);c=getchar_())x=x*10+c-'0';
    }
    inline void write(reg int x){if(x>9)write(x/10);putchar_(x%10+'0');}
    inline void writeln(reg int x){write(x),putchar_('n');}
};
using namespace fast_IO;
int n,m,q,K,l,r,x[N],y[N],T[N],g[N],p[N],ans[N];
struct node
{
    int q,l,r,id;
    inline void init(reg int i){read(q),read(l),read(r),id=i;}
    bool operator<(const node&a)const
        {return T[l]==T[a.l]?((T[l]&1)?r<a.r:r>a.r):l<a.l;}
}a[200010];
inline void upd1(reg int i){swap(p[x[i]],p[y[i]]),swap(g[p[x[i]]],g[p[y[i]]]);}
inline void upd2(reg int i){swap(g[x[i]],g[y[i]]),swap(p[g[x[i]]],p[g[y[i]]]);}
int main()
{
    freopen("magic.in","r",stdin);
    freopen("magic.out","w",stdout);
    read(n),read(m),read(q),K=sqrt(m);
    for(reg int i=1;i<=n;++i)g[i]=p[i]=i;
    for(reg int i=1;i<=m;++i)
        read(x[i]),read(y[i]),T[i]=(i-1)/K+1;
    for(reg int i=1;i<=q;++i)a[i].init(i);
    sort(a+1,a+q+1),l=1,r=0;
    for(reg int i=1;i<=q;++i)
    {
        while(l>a[i].l)upd1(--l);
        while(r<a[i].r)upd2(++r);
        while(l<a[i].l)upd1(l++);
        while(r>a[i].r)upd2(r--);
        ans[a[i].id]=p[a[i].q];
    }
    for(reg int i=1;i<=q;++i)writeln(ans[i]);
    flush();return 0;
}