Day 1
小菜鸡的第三天(没错,第二天咕咕咕了)
一、当日总结
昨天的题单是牛客训练赛74,3道签到题只做出来2题,讨论会的时候也没有遇到特别有感触的题就咕咕了,今天的题单是训练赛73,三道签到题磕磕碰碰ac了,什么时候才能突破啊!!!。
二、题目回顾
2.1CCA的数列
题意:n个数判断是否是等差数列、等比数列、等模数列中的一种
思路:非常常规,从前往后遍历加三个标记就行
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n;
bool fd=true,fq=true,fm=true;
ll a[N];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=1;i<n-1;i++)
{
if(fd&&2*a[i]!=a[i-1]+a[i+1]) fd=false;
if(fq&&a[i]*a[i]!=a[i-1]*a[i+1])fq=false;
if(fm&&a[i]%a[i-1]!=a[i+1]%a[i])fm=false;
if(!fd&&!fq&&!fm) break;
}
if(!fd&&!fq&&!fm) cout<<"NO";
else cout<<"YES";
return 0;
}
2.2CCA的字符串
题意:定义了一个字符串是“牛”的,当且仅当其有一个子串为“NowCoder”
转化一下也就是这个字符串有“NowCoder”子串。
问一个字符串有多少“牛”串
思路:以给定的字符串中的每个“NowCoder”为分界点,上至前一个分界点,后至末尾,乘积计数就行
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
typedef long long ll;
string s;
void solve()
{
int len=s.length(),st=-1;ll res=0;
for(int i=0;i<len-7;i++)
if(!s.compare(i,8,"NowCoder")){
res+=1ll*(i-st)*(len-(i+7));
st=i;
}
cout<<res;
}
int main()
{
cin>>s;
solve();
return 0;
}
2.3招生
问题:招生按高考成绩和校考成绩加权排名,前m个可被录取,问高考最低可以考多少
思路:算完分数只要考正好第m名的分就可以把第m个人挤下去,公式倒推即可。
要注意结果向上取整,分数最低为0
#include <iostream>
#include <algorithm>
using namespace std;
#define max(a, b) ((a) > (b) ? (a) : (b))
typedef long long ll;
const int N = 1e5 + 10;
int n,m,p;
ll a[N];
int main()
{
cin>>n>>m>>p;
for(int i=0;i<n;i++)
{
ll x,y;
cin>>x>>y;
a[i]=x*85+y*15;
}
sort(a,a+n);
cout<<max((a[n-m]-p*15+84)/85,0);
return 0;
}
2.4遥远的记忆
问题:在题述约束下a中最多有多少种数
思路:10绑定,记录有多少对10就行,对于头尾的不同情况举例就可以看出来
#include <iostream>
using namespace std;
const int N = 5e5 + 10;
int a[N],ans=1,n,c,k=1;
int main()
{
cin>>n>>c;
a[0]=c;
for(int i=1;i<n;i++)
{
cin>>c;
if(c^a[k-1]) a[k++]=c;
}
if(k%2) cout<<(k+1)/2;
else cout<<k/2+(a[0]+1)%2;
return 0;
}
2.5生涯回忆录
问题:遗憾为集合中最小不包含在集合内的正整数
对于给定的n个数的所有子集,问子集的遗憾之和为多少
思路:实际是一个排列组合问题
1)假设在n个数中有某个数k不存在,那么如果集合中前k-1个数都有,不管其他比k大的数是否存在,遗憾总是k
2)对于一组连续的数集,遗憾为k的可能情况为集合中包含小于k的每一个数,对于大于k的数不做要求
设计:用rest数组保存比k大的数
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const int Mod = 20000311;
int i=0,c=1,n,a[N],anum[N],rest[N],T[N]={
1};
ll ans=0;
void in()
{
// freopen("C.in","r",stdin);
for(int i=1;i<N;i++)
T[i]=(T[i-1]*2)%Mod;
cin>>n;rest[0]=n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
while(i<n)
if(a[i]>c&&anum[c]) rest[c]=rest[c-1]-anum[c],c++;
else if(a[i]==c) anum[c]++,i++;
else break;
if(i!=n)rest[c]=rest[c-1];
}
void solve()
{
i=1;
while(anum[i])
{
ll k=i;
for(int j=k-1;j>0;j--)
k=k*(T[anum[j]]-1)%Mod;
if(rest[i])k=k*T[rest[i]]%Mod;
ans=(ans+k)%Mod;
i++;
}
if(rest[i]==0)
{
ll k=i;
for(int j=k-1;j>0;j--)
k=k*(T[anum[j]]-1)%Mod;
ans=(ans+k)%Mod;
}
else
{
ll k=i;
for(int j=k-1;j>0;j--)
k=k*(T[anum[j]]-1)%Mod;
k=k*T[rest[i]]%Mod;
ans=(ans+k)%Mod;
}
cout<<ans;
}
int main()
{
in();
solve();
return 0;
}
VaQX·青
2021.01.25