ZROI 提高十连测 Day1

　　第一天的提高模拟测考前特意睡了20min 还是歇菜了，果然自己菜是真实的。

题目质量海星但是我都不会这是真的...题目由于是花钱买的这里就不放了 LINK：problem 熟悉我的人应该都知道账号和密码...

但是总该叙述一下题意一个组两个人一个组长一个组员每个人都有两个属性w经验s工资要求w组长>=w组员有一部分人是组长一部分人是组员一部分是既可以是组长也可以是组员。

现在问要求组成k组的最小花费如果不可能的话输出-1.显然 2*k<=n...

而这里有点像一个二分图但是对于一部分既是组长又是组员的人很难判断究竟是组员还是组长通过以往的分析此时就应该上网络流了一个点两种选择然后网络流一跑求个最优但显然建图...建不出来图的费用流咕了.

考虑暴力这不就是爆搜的组合数么搜一发几个剪枝上去发现最致命的原因是无法判断方案的合法性想了一个贪心的做法每个A都选择一个较大的B 然后不够选再选一个较小的C 最后C再选B 看能把A B 集合都清空不能这样做（贪心感觉是正确的根据全局最优性原理好像也是可以证明的。不出意料的挂了我不知道哪写错了（贪心当时写的做法C是从大到小的但是我的答案小所以问题不出在 C上好像哪里写挂了贪心正确性也不好证明这个40分的做法于是也咕了.

考虑题解中的正解 dp 考虑一下对w排序从小到大按w排序排完序之后组长可以选择之前再其之前的组员设状态 f[i][j][k]表示前i个人形成了j组有k个组员的最小代价。

//#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cctype>

#include<utility>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<stack>

#include<string>

#include<cstring>

#define INF 1000000000000000ll

#define ll long long

#define db double

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)>(y)?(y):(x))

#define mp(x,y) make_pair(x,y)

using namespace std;

char *fs,*ft,buf[<<];

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getc();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getc();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getc();}

    return f<?-x:x;

}

const ll MAXN=,maxn=;

ll n,k;

struct wy

{

    ll w,s,op;

}t[MAXN];

inline ll cmp(wy a,wy b){return a.w==b.w?a.op<b.op:a.w<b.w;}

ll f[maxn][maxn];

int main()

{

    freopen("1.in","r",stdin);

    n=read();k=read();

    if(*k>n){puts("-1");return ;}

    for(ll i=;i<=n;++i)

    {

        ll w,s,op;

        w=read();s=read();op=read();

        t[i]=(wy){w,s,op};

        if(t[i].op==)t[i].op=;

        else

        {

            if(t[i].op==)t[i].op=;

            else if(t[i].op==)t[i].op=;

        }

    }

    sort(t+,t++n,cmp);

    for(ll i=;i<=k;++i)

        for(ll j=;j<=k;++j)

            f[i][j]=INF;

    f[][]=;

    for(ll i=;i<=n;++i)

    {

        for(ll j=k;j>=;--j)

            for(ll l=k;l>=;--l)

            {

                if(f[j][l]==INF)continue;

                //成为组长

                if(t[i].op!=)if(l->=&&j+<=k)f[j+][l-]=min(f[j+][l-],f[j][l]+t[i].s);

                //成为组员

                if(t[i].op!=)if(l+<=k)f[j][l+]=min(f[j][l+],f[j][l]+t[i].s);

            }

    }

    if(f[k][]!=INF)printf("%lld\n",f[k][]);

    else puts("-1");

    return ;

}

很不错的思路当时考试就顾着某个人和某个人的必要匹配了没有想到还是和具体匹配无关只要的到合法的人数就好了。

T2 看题目看的就一脸蒙蔽觉得非常不可写于是就弃疗看T3了。

T2 一个n*m的平面上每个点都有颜色每次可以选取一条直线对折要求对折的下半部分>=上半部分求最后对折出来最下层有多少种本质不同的结果，本质不同的定义：最下层在原方格纸中对应的区域不同。

看起来这个问题很难解决不妨来观察当n==1时的情况。先分析一下答案吧不动是一种然后对这一行采用manacher一下是必然的吧。。。(虽然我还没证明manacher本身的正确性但还是可以用的.

经过手动模拟之后我们发现最后的答案其实为 l~r 题目中就是让我们找有多少个不同的l~r 很迷其实 l~r可以当做最后的区间的话那么l~n和1~r也是可以当做最后的区间的，因为左折和右折是独立的。

多少个本质不同的l r 显然我们求出1~l之间的所有合法端点 * r[i]其是否能成为右端点我们定右端点求左端点和定左端点求右端点是是等效的。

怎么求 prei这个东西显然的是 pre[i]=pre[i-1]+x;x=pre[i-1]-pre[t];t=i-ansi-1;ansi=以i~i+1为中心的回文半径。这个式子的第一部分显然后一部分是当前点带来的贡献。落在i-ansi+1~i这个区间内的点都会使pre[i]得到贡献。

此时我们再求一个定点r即可。注意pre和buf数组的含义不尽相同。

//#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cctype>

#include<utility>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<stack>

#include<string>

#include<cstring>

#define INF 2000000000

#define ll long long

#define db double

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)>(y)?(y):(x))

#define mp(x,y) make_pair(x,y)

using namespace std;

char *fs,*ft,buf[<<];

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return f<?-x:x;

}

const ll MAXN=;

ll n,m,cnt;

ll p[MAXN<<],w[MAXN];

char a[MAXN],b[MAXN<<];

ll pre[MAXN],r[MAXN],suf[MAXN];

inline void manacher(ll len,char *c)

{

    ll mid=,mx=;

    for(ll i=;i<=len;++i)

    {

        p[i]=i<mx?min(p[(mid<<)-i],mx-i):;

        while(b[i-p[i]]==b[i+p[i]])++p[i];

        if(mx<p[i]+i)mid=i,mx=p[i]+i;

    }

    for(ll i=;i<=m;++i)w[i]=p[i<<|]>>;

}

inline ll calc(ll n,char *c)

{

    pre[]=;r[n]=;suf[n]=;

    for(ll i=;i<=n;++i)

    {

        ll t=i-w[i]-;

        ll x=pre[i-]-(t>=?pre[t]:);

        pre[i]=pre[i-]+(x>);

    }

    for(ll i=n-;i>=;--i)

    {

        ll t=i+w[i]+;

        ll x=suf[i+]-(t<=n?suf[t]:);

        suf[i]=suf[i+]+(r[i]=(x>));

    }

    ll ans=;

    for(ll i=;i<=n;++i)ans+=pre[i-]*r[i];

    return ans;

}

signed main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();

    if(n==)

    {

        scanf("%s",a+);

        b[]='&';b[]='#';cnt=;

        for(ll i=;i<=m;++i)b[++cnt]=a[i],b[++cnt]='#';

        manacher(cnt,b);

        printf("%lld\n",calc(m,a));

    }

}

考虑二维的折叠。发现横着叠竖着叠是不冲突的分别计算两个东西的方案数发现可以先横着叠再竖着叠或者先竖着叠再横着叠相乘即可。

//#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cctype>

#include<utility>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<stack>

#include<string>

#include<cstring>

#define INF 2000000000

#define mod 1000000007

#define P 131

#define ll long long

#define db double

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)>(y)?(y):(x))

#define mp(x,y) make_pair(x,y)

using namespace std;

char *fs,*ft,buf[<<];

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return f<?-x:x;

}

const ll MAXN=;

ll n,m,cnt;

ll p[MAXN<<],w[MAXN];

char a[MAXN];

ll b[MAXN<<];

ll pre[MAXN],r[MAXN],suf[MAXN],R[MAXN],C[MAXN];

inline void manacher(ll n,ll *c)

{

    b[]=-;b[]=-;

    ll len=;

    for(ll i=;i<=n;++i)b[++len]=c[i],b[++len]=-;

    ll mid=,mx=;

    for(ll i=;i<=len;++i)

    {

        p[i]=i<mx?min(p[(mid<<)-i],mx-i):;

        while(b[i-p[i]]==b[i+p[i]])++p[i];

        if(mx<p[i]+i)mid=i,mx=p[i]+i;

    }

    for(ll i=;i<=n;++i)w[i]=p[i<<|]>>;

}

inline ll calc(ll n,ll *c)

{

    manacher(n,c);

    pre[]=;r[n]=;suf[n]=;

    for(ll i=;i<=n;++i)

    {

        ll t=i-w[i]-;

        ll x=pre[i-]-(t>=?pre[t]:);

        pre[i]=pre[i-]+(x>);

    }

    for(ll i=n-;i>=;--i)

    {

        ll t=i+w[i]+;

        ll x=suf[i+]-(t<=n?suf[t]:);

        suf[i]=suf[i+]+(r[i]=(x>));

    }

    ll ans=;

    for(ll i=;i<=n;++i)ans+=pre[i-]*r[i];

    return ans;

}

signed main()

{

    //freopen("1.in","r",stdin);

    n=read();m=read();

    for(ll i=;i<=n;++i)

    {

        scanf("%s",a+);

        for(ll j=;j<=m;++j)

        {

            R[i]=(R[i]*P+a[j])%mod;

            C[j]=(C[j]*P+a[j])%mod;

        }

    }

    printf("%lld\n",calc(n,R)*calc(m,C));

    return ;

}

这题真的是精髓 manacher 的精髓还是折纸的精髓我估计理解不深所以写的慢吧以后要复习啊光这道题就写了4h 完蛋了GG了。

T3 此题好题思路非常的清奇 55分 n^2暴力 set维护维护一个偏移量就可以结局不过+1的情况查找的时候没思考清楚写挂了正解是把这些数字放到trie树中然后搞一些事情考虑+1的情况把trie树上链为111111这一条链上所有节点都交换左右儿子即可。

复杂度logn 由于%2^30 那么如果存在最后一位也交换的话相当于全部都变成0了符合取模。考虑^cnt在trie树上的体现普通对数字的体现是如果cnt的某一位是0那么这个数字当前位不变是1 的话这个数字当前位0 1 互换trie树上也是如此不过这个要考虑到所有的节点复杂度nlogn 因为是trie树每一个节点。trie树给我们带来的好处+1单次操作logn ^x这个操作nlogn 显然+法和^无法共存不妨+1直接修改^记全体偏移量。那么复杂的就是Qlogn+nlogn了

当然还有一个小问题 ^x)+1如何把1提到前面的问题这个要从 x上进行考虑x如果当前位为1的话那么trie树之上全为1的那一条链的对应位经过x异或应该是0我们此时+1累计到这个0上就好了因为这个0才是真正的1.那么我们真实的链是什么呢(2^30-1)一开始全为1

经过x异或如果对应位是1的话那么链应该是0对应位是0的话链应该是1 综上这条链为(2^30-1)^x 这条链就好了。

关于这样做的正确性：首先+1我们就是更改一条链交换其左右儿子^在前不妨假设^交换好了+1的话是刚才的链那么其实改变的就是cnt交换掉的东西我们直接改变cnt会交换掉的东西先+再^就显然成立了。

//#include<bits/stdc++.h>

#include<iostream>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<cctype>

#include<utility>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<deque>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<iomanip>

#include<stack>

#include<string>

#include<cstring>

#define INF 2000000000

#define ll long long

#define db double

#define max(x,y) ((x)>(y)?(x):(y))

#define min(x,y) ((x)>(y)?(y):(x))

#define mp(x,y) make_pair(x,y)

using namespace std;

char *fs,*ft,buf[<<];

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?:*fs++;

}

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return f<?-x:x;

}

const int MAXN=,mod=<<;

int n,Q,id,cnt;

int tag;//异或标记

int a[MAXN<<];

int t[MAXN<<][],sz[MAXN<<];

inline void insert(int x)

{

    int p=;x=x^tag;

    for(int i=;i<=;++i)

    {

        int tn=(x>>i)&;

        if(!t[p][tn])t[p][tn]=++id;

        p=t[p][tn];

    }

    ++sz[p];

}

inline void cancel(int x)

{

    int p=;x=x^tag;

    for(int i=;i<=;++i)

    {

        int tn=(x>>i)&;

        p=t[p][tn];

    }

    --sz[p];

}

inline void modify()//寻找最小的i使得trie树上一坨都是1

//如果tag==0 直接找就好了 考虑tag!=0

//如何把^tag)+1转换成+1)^tag 看起来非常的抽象 不妨观察前者的操作、

//其实就是tag^(mod-1) 这一条链

{

    int p=,qaq=tag^(mod-);

    for(int i=;i<=;++i)

    {

        int tn=(qaq>>i)&;

        swap(t[p][],t[p][]);

        p=t[p][tn^];

        if(!p)return;

    }

}

inline void solve(int p,int sum,int w)

{

    if(!p&&w!=)return;

    if(sz[p])

    {

        for(int i=;i<=sz[p];++i)a[++cnt]=sum^tag;

        return;

    }

    solve(t[p][],sum,w<<);

    solve(t[p][],sum|w,w<<);

    return;

}

int main()

{

    //freopen("1.in","r",stdin);

    n=read();Q=read();

    for(int i=;i<=n;++i)insert(read());

    for(int i=;i<=Q;++i)

    {

        int op,x;

        op=read();if(op!=)x=read();

        if(op==)insert(x);

        if(op==)cancel(x);

        if(op==)modify();

        if(op==)tag=tag^x;

    }

    solve(,,);

    sort(a+,a++cnt);

    for(int i=;i<cnt;++i)printf("%d ",a[i]);

    printf("%d\n",a[cnt]);

    return ;

}

巴特西

ZROI 提高十连测 Day1

最新文章

热门文章