CQNK信心赛(2019.8.20)
Huang_Yuhan · · 个人记录
题目在此: 链接: https://pan.baidu.com/s/11E7Kj_zP0B7iy1MF6kWMRA 提取码: 9hgp
这场比赛打得还行,本来期望是
A题
众所周知,机房里有
解:
一开始并没有想到如何去解,完全没有思路,然后就去打表。
怎么打表呢?其实就是正解的弱数据版
如果很自然而然地可以想到用
设
其中
然后答案就是
然后就可以打
观察可得:当
当
设
我们又可以发现当
即:
所以:
同时注意可能会溢出,所以要先除再乘
然后我们就可轻松愉快地
时间复杂度
期望得分:
实际得分:
#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有
nidgd会魔法,他有
每种魔法有3个参数 。
若
若
若
现在nidgd想求一种方案,使得使用完毕后所有卡牌的乘积最大。
乘积可能很大,请你输出排序后字典序最小的方案。关于最小字典序,见输出格式。
输入格式
第一行
接下来一行
接下来 行,每行
输入格式:
第一行一个数
接下来
如果有多种方案,优先选
解:
这道题用贪心。
我们很显然如果要选的话,我们的顺序一定是先用
首先一号操作可以转换为二号操作,我们贪心只用
然后再考虑二号操作转换为三号操作,我们贪心先加大的。所以按这个顺序把它转换成乘法。
时间复杂度为
#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;
}
期望得分:
实际得分:
C题
信竞队的一号人才nadgd拥有很多特异功能,比如看一眼就能秒掉
但是蒟蒻faed很不服气他坚信是自己基因太弱了.
他花了数月时间学习了基因方面的知识并冒死采集到了nadgd的基因样本
蒟蒻faed于是便开始研究自己的基因
卧槽怎么这么长!!!
faed于是便自闭了把任务交给了你
faed定义如果他的基因改变最多
请你写一个代码来得出相似值
题意简述:求一个串在另一个串上的匹配次数,最多容忍
有多组测试
解:
全场最不可思议的题,大部分都是打的暴力,结果数据水得太过了,很多人都得了大部分分。
我突然想起书上讲(滑稽)
然而这道题跟没有半毛钱的关系。
首先我们先来看暴力怎么打。
就是
其中
我们可以优化
那么总时间复杂度为
#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;
}
期望得分:
实际得分: