T1-旅行家

给你 $ n $ 种能前进 $ A_i $ 步的装置，每种有 $ B_i $ 个
终点是用完装置到达的地方，现在限制了一些点，问你到达终点的方案数

解法

数据范围很小，直接状压dp

ac代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define mod 100000007
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);}
    template<typename T>void read(T &x)
    {
        x=0;char c=getchar_();
        for(;!isdigit(c);c=getchar_());
        for(;isdigit(c);c=getchar_())x=x*10+c-'0';
    }
    inline void write(ll x)
    {
        if(x>9)write(x/10);
        putchar_(x%10+'0');
    }
    inline void writeln(ll x)
    {
        write(x),putchar_('\n');
    }
};
using namespace fast_IO;
unordered_map<long long,bool>lm;
int n,m,a[10],b[10],p[10],ct[10],dp[5000000];
ll x;
ll calc()
{
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans+=1ll*a[i]*ct[i];
    return ans;
}
int main()
{
    freopen("traveller.in","r",stdin);
    freopen("traveller.out","w",stdout);
    read(n),p[0]=1;
    for(int i=1;i<=n;i++)
        read(a[i]),read(b[i]),
        p[i]=p[i-1]*(b[i]+1);
    read(m);
    for(int i=1;i<=m;i++)
        read(x),lm[x]=1;
    dp[0]=1;
    for(int i=0;i<p[n]-1;i++)
    {
        for(int j=1;j<=n;j++)ct[j]=i%p[j]/p[j-1];
        if(!lm.count(calc()))for(int j=1;j<=n;j++)
            (ct[j]<b[j])&&((dp[i+p[j-1]]+=dp[i])%=mod);
    }
    writeln(dp[p[n]-1]),flush();
    return 0;
}

T2-序列

给你 $ n $ 个区间，每次询问 $ 1-i $ 区间中满足 $ f(x \oplus y) \equiv 1 \pmod{2} $ 的无序数对 $ (x,y) $
$ f(x) $ 表示 $ x $ 的二进制分解中 $ 1 $ 的个数

解法

易得满足题意的数对 $ (x,y) $ 一定有 $ f(x) \mod 2 \not= f(y) \mod 2 $
所以我们统计区间里 $ f(x) $ 为奇数和偶数的个数
对于一个连续的区间，设 $ g(x) $ 表示 $ 1-x $ 中 $ f(x) $ 为奇数的个数
这怎么求呢，我们发现 $ 0,1,2,3,4,5... $ 每两个数有一个数的 $ f(x) $ 为奇数
我们只要检验多出来的一个数即可
对于不连续的区间，每次我们塞进去一个区间，用vector暴力合并即可

ac代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define fir first
#define sec second
#define mp make_pair
#define int long long 
using namespace std;
struct node
{
    int l,r,a,b;
    bool operator<(const node&x)const{return l<x.l;}
}tmp;
vector<node>p;
int n,l,r,a,b;
pair<int,int>operator+(pair<int,int>a,pair<int,int>b)
{
    return mp(a.fir+b.fir,a.sec+b.sec);
}
pair<int,int>operator-(pair<int,int>a,pair<int,int>b)
{
    return mp(a.fir-b.fir,a.sec-b.sec);
}
pair<int,int>f(pair<int,int>x)
{return mp(x.sec,x.fir);}
pair<int,int>spe(int x)
{
    int cnt=0;
    while(x)
        cnt+=x&1,x/=2;
    if(cnt&1)return mp(1,0);
    else return mp(0,1);
}
pair<int,int>calc(int x)
{
    if(x&1)return mp(x/2+1,x/2);
    else return mp(x/2+1,x/2)-spe(x+1);
}
void ins(int l,int r)
{
    tmp={l,r,0,0};
    int pos=lower_bound(p.begin(),p.end(),tmp)-p.begin();
    if(pos!=0&&p[pos-1].r>=tmp.l-1)
    {
        pos--;
        tmp.l=p[pos].l;
        if(p[pos].r>tmp.r)tmp.r=p[pos].r;
        a-=p[pos].a,b-=p[pos].b;
        p.erase(p.begin()+pos);
    }
    for(int i=pos;i<p.size();i++)
    {
        if(p[i].l>tmp.r+1)break;
        tmp.r=max(tmp.r,p[i].r);
        a-=p[i].a,b-=p[i].b;
        p.erase(p.begin()+i),i--;
    }
    pair<int,int>pp=calc(tmp.r)-calc(tmp.l-1);
    tmp.a=pp.fir,tmp.b=pp.sec;
    a+=tmp.a,b+=tmp.b;
    p.insert(p.begin()+pos,tmp);
}
signed main()
{
//  freopen("sequence.in","r",stdin);
//  freopen("sequence.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&l,&r),ins(l,r),printf("%lld\n",1ll*a*b);
    return 0;
}

T3-钢琴家

给你一个字符串 $ S $ 和一些模式串 $ s[i] $
改动一些字母使 $ S $ 成为 $ s[i] $ 的拼凑
改动字母越少越好，按顺序输出改完之后 $ s[i] $ 的拼凑方案

解法

暴力dp， $ f[i] $ 表示考虑到第 $ i $ 位，都能匹配的最少改动
再开一个数组记录方案就好了

ac代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
char a[1010],p[110][1010];
int n,m,x,t,l[110],f[1010],ue[1010];
inline int calc(int st,int s)
{
    int ans=0;
    for(int i=1;i<=l[s];++i)
        (a[st+i]!=p[s][i])&&(++ans);
    return ans;
}
inline void print(int nw)
{
    if(nw==0)return;
    print(nw-l[ue[nw]]);
    printf("%s\n",p[ue[nw]]+1);
}
int main()
{
    freopen("pianist.in","r",stdin);
    freopen("pianist.out","w",stdout);
    scanf("%s%d",a+1,&m),n=strlen(a+1);
    for(int i=1;i<=m;++i)
        scanf("%s",p[i]+1),l[i]=strlen(p[i]+1);
    for(int i=1;i<=10;++i)scanf("%d",&x);
    memset(f,0x3f,sizeof(f)),f[0]=0;
    for(int i=0;i<n;++i)for(int j=1;j<=m;++j)if(i+l[j]<=n)
        t=calc(i,j),(f[i]+t<f[i+l[j]])&&(f[i+l[j]]=f[i]+t,ue[i+l[j]]=j);
    print(n);
    return 0;
}

hgoi#20191106

原文：https://www.cnblogs.com/muronglin/p/hgoi-20191106.html