CQNK信心赛(2019.8.20)

· · 个人记录

题目在此: 链接: https://pan.baidu.com/s/11E7Kj_zP0B7iy1MF6kWMRA 提取码: 9hgp

这场比赛打得还行,本来期望是140,结果因为C题的数据出得太水了,得了200分

A题

众所周知,机房里有 n(n\leqslant 2^{32})只鸽子。有一天,nudgd闲得发慌突发奇想,决定把这些鸽子全部赶到一起。已知,将数量分 别为 a只和b 只的两群鸽子赶到一起,需要花费 a\oplus b的时间,其中 \oplus为 C 与 C++ 中的 ^ 运算符,或 pascal 中的 xor 运算符。由于nudgd不想做PPT很闲,所以他想用尽可能多的时间来把所有鸽子赶到一起。他想知道最多需要多少时间,才能把所有鸽子都赶到一起。开始时,可以看作有n 群鸽子,每群仅有一只。

解:

一开始并没有想到如何去解,完全没有思路,然后就去打表。

怎么打表呢?其实就是正解的弱数据版

如果n\leqslant 100,那么我们很自然而然地可以想到用DP

设f[x][y]表示把[x,y]区间合并起来的最大时间,那么状态转移方程为:

f[x][y]=\max\{f[x][k]+f[k+1][y]+(k-x+1)\oplus(y-k)\}

其中x\leqslant k<y

然后答案就是f[1][n]

然后就可以打1\rightarrow20的表了。

观察可得:当n为奇数的时候:

ans=\lfloor\frac{n}{2}\rfloor\times n

当n为偶数的时候,我们感觉看不出什么。于是我们可以去看看f[1][n]是怎么来的。

设g[x][y]表示令f[x][y]最大的k

我们又可以发现当n为偶数的时候,g[1][n]=n-1

即:f[1][n]是从f[1][n-1]转移来的。

所以:

ans=\lfloor \frac{n-1}{2}\rfloor\times (n-1)+(n-1)\oplus 1

同时注意可能会溢出,所以要先除再乘

然后我们就可轻松愉快地A掉此题

时间复杂度O(1)

期望得分:100

实际得分:100

#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
using namespace std;
inline int Min(int a,int b)
{return a>b?b:a;}
inline int Max(int a,int b)
{return a>b?a:b;}
typedef long long ll;
template<typename T>
void rin(T &t)
{t=0;int k=1;char c=getchar();while(!isdigit(c)){if(c=='-')k=-1;c=getchar();}while(isdigit(c)){t=t*10+c-'0';c=getchar();}t*=k;}

int main()
{
    freopen("pigeon.in","r",stdin);
    freopen("pigeon.out","w",stdout);
    ll n;
    rin(n);
    ll ans=0;
    if(n&1)ans=n/2*n;
    else {ans=(n-1)/2*(n-1);ans=((n-1)^1)+ans;}
    printf("%lld",ans);
    return 0;
}

B题(CF521D)

nidgd终于像祝福中的那样,安度晚年去了。

晚年的nidgd闲来无事,玩起了卡牌游戏。

nidgd有n 张卡牌,第A_i 张卡牌上写有数字 。

nidgd会魔法,他有k种魔法,但是每种魔法只能用一次,并且只能使用其中m种魔法。

每种魔法有3个参数 。

若ty=1,则使用魔法后第x张卡牌上的数字变为y

若ty=2,则使用魔法后第x张卡牌上的数字增加y

若ty=3,则使用魔法后第x张卡牌上的数字乘上y

现在nidgd想求一种方案,使得使用完毕后所有卡牌的乘积最大。

乘积可能很大,请你输出排序后字典序最小的方案。关于最小字典序,见输出格式。

输入格式

第一行3个数n,k,m ,意义见题目描述。1\leqslant n\leqslant 10^5,1\leqslant m\leqslant k\leqslant 10^5

接下来一行 n个数,第 i个数为A_i 。1\leqslant A_i\leqslant 10^6

接下来 行,每行3个数 ty,x,y.

1\leqslant ty\leqslant 3,1\leqslant x\leqslant n,1\leqslant y\leqslant 10^6

输入格式:

第一行一个数 num表示实际使用的魔法个数。

接下来1行num个数,表示选取的魔法的编号。

如果有多种方案,优先选num小的,再优先选第1 个魔法编号尽量小的,再优先第2个......

解:

这道题用贪心。

我们很显然如果要选的话,我们的顺序一定是先用ty=1的,然后才是ty=2的,然后才是ty=3的。

首先一号操作可以转换为二号操作,我们贪心只用y>a[x]中最大的,否则就不用。

然后再考虑二号操作转换为三号操作,我们贪心先加大的。所以按这个顺序把它转换成乘法。

时间复杂度为O(klog_2k)

#include<stdio.h>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
inline ll Min(ll a,ll b)
{return a>b?b:a;}
inline ll Max(ll a,ll b)
{return a>b?a:b;}
template<typename T>
void rin(T &t)
{t=0;int k=1;char c=getchar();while(!isdigit(c)){if(c=='-')k=-1;c=getchar();}while(isdigit(c)){t=t*10+c-'0';c=getchar();}t*=k;}
const int maxn=1e5+5;
ll New[maxn],a[maxn],ty[maxn],x[maxn],y[maxn];
int n,k,m;
struct node
{
    ll id,u,v;
    node(ll x,ll y,ll z){id=x;u=y;v=z;}
};
bool cmp1(node a,node b)
{return a.u==b.u?a.v>b.v:a.u<b.u;}
bool cmp2(node aa,node bb)
{return aa.u*bb.v==bb.u*aa.v?aa.id<bb.id:aa.u*bb.v>bb.u*aa.v;}
vector<node> mg,b;
int main()
{
    rin(n);rin(k);rin(m);
    for(int i=1;i<=n;i++)rin(a[i]);
    for(int i=1;i<=k;i++)
    {
        rin(ty[i]);rin(x[i]);rin(y[i]);
        if(ty[i]==1)
        {
            if(y[New[x[i]]]<y[i]&&y[i]>a[x[i]])New[x[i]]=i;
        }
        if(ty[i]==2)mg.push_back(node(i,x[i],y[i]));
        if(ty[i]==3&&y[i]>1)b.push_back(node(i,y[i],1));
    }
    for(int i=1;i<=n;i++)if(y[New[i]]>a[i])mg.push_back(node(New[i],i,y[New[i]]-a[i]));
    sort(mg.begin(),mg.end(),cmp1);
    for(int i=0;i<mg.size();i++)
    {
        b.push_back(node(mg[i].id,a[mg[i].u]+mg[i].v,a[mg[i].u]));a[mg[i].u]+=mg[i].v;
    }
    sort(b.begin(),b.end(),cmp2);
    vector<int> ans;
    printf("%d\n",Min(b.size(),m));
    for(int i=0;i<Min(b.size(),m);i++)ans.push_back(b[i].id);
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)printf("%d ",ans[i]);
    return 0;
}

期望得分:0

实际得分:0

C题

信竞队的一号人才nadgd拥有很多特异功能,比如看一眼就能秒掉luogu上的黑题,AKIOI等.

但是蒟蒻faed很不服气他坚信是自己基因太弱了.

他花了数月时间学习了基因方面的知识并冒死采集到了nadgd的基因样本 蒟蒻faed于是便开始研究自己的基因S与nadgd的基因S_0的相似值

卧槽怎么这么长!!!

faed于是便自闭了把任务交给了你

faed定义如果他的基因改变最多k次后和nadgd的基因在某个位置是相同的那么相似值便加1

请你写一个代码来得出相似值

题意简述:求一个串在另一个串上的匹配次数,最多容忍k次失配

有多组测试

|S|\leqslant|S_0|\leqslant 10^5,k\leqslant 10,T\leqslant 3

解:

全场最不可思议的题,大部分都是打的暴力,结果数据水得太过了,很多人都得了大部分分。

我突然想起书上讲KMP算法的一句话:“对于随机数据,暴力算法表现得非常优秀”。(滑稽)

然而这道题跟KMP没有半毛钱的关系。

首先我们先来看暴力怎么打。

就是O(nm)匹配

其中O(n)的讨论,每一次讨论就要O(m)的匹配

我们可以优化O(m)的匹配,二分去查找他们的最长公共前缀,然后跨过它,继续。时间复杂度大概是O(log_2m)

那么总时间复杂度为O(nlog_2m)

#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
typedef unsigned long long ll;
const int maxn=1e5+5;
const ll seed=233;
ll a[maxn],b[maxn],bin[maxn];
char S[maxn],T[maxn];
int k,n,m;

inline ll gethash(ll *sum,int l,int r)
{
    return sum[r]-sum[l-1]*bin[r-l+1];
}

int lcp(int x,int y,int r)
{
    int l=1,mid,ans=0;
    while(l<=r)
    {
        mid=l+r>>1;
        if(gethash(a,x,x+mid-1)==gethash(b,y,y+mid-1)){ans=mid;l=mid+1;}
        else r=mid-1;
    }
    return ans;
}

bool isok(int pos)
{
    int r=pos+m-1;
    int x=pos,y=1;
    for(int i=1;i<=k;i++)
    {
        int tmp=lcp(x,y,m);
        x=x+tmp+1;
        y=y+tmp+1;
        if(y>m)return true;
    }
    return gethash(a,x,r)==gethash(b,y,m);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&k);
        scanf("%s%s",S+1,T+1);
        n=strlen(S+1);
        m=strlen(T+1);
        bin[0]=1;
        int ans=0;
        for(int i=1;i<=n;i++)bin[i]=bin[i-1]*seed;
        for(int i=1;i<=n;i++)a[i]=a[i-1]*seed+S[i];
        for(int i=1;i<=m;i++)b[i]=b[i-1]*seed+T[i];
        for(int i=1;i+m-1<=n;i++)
        if(isok(i))ans++;
        printf("%d\n",ans);
    }
    return 0;
}

期望得分:40

实际得分:90