慕容琳的后花园
慕容琳的后花园
hgoi#20191111

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("%d\n",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],f[3010][3010],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],1ll*x[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++)
        f[0][0]+=a[i].g+1ll*(i-1)*a[i].s*d+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++)
    {
        f[i][0]=f[i-1][0],f[i][i]=f[i-1][i-1]-a[i].g-s[i+1]*d-1ll*(n-i)*(n-i)*d*d;
        for(int j=1;j<i;j++)
            f[i][j]=min(f[i-1][j],f[i-1][j-1]-a[i].g-1ll*(i-j)*a[i].s*d-s[i+1]*d-1ll*(n-j)*(n-j)*d*d);
    }
    for(int i=1;i<=n;i++)ans[i]=f[n][n-i];
    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 f[3010][3010],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++)
    {
        f[i][0]=f[i-1][0],f[i][i]=f[i-1][i-1]+1ll*(a[i].x+(i-1)*d)*(a[i].y+(i-1)*d);
        for(int j=1;j<i;j++)
            f[i][j]=min(f[i-1][j],f[i-1][j-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;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20191111
T1-文件改名 你现在有 $n$ 个文件名不同的文件,要更改这 $n$ 个文件的文件名 一次可以修改一个文件的文件名,要求中途不能有文件名相同 问最少修改几次 解法 可以发现,分三种情况 如…
扫描二维码继续阅读
2019-11-11
功能