A. 斐波那契
周围大佬都说初中打过n遍,我一个菜鸡瑟瑟发抖。
把斐波那契数列写出来找了半天性质,用了半个多小时推出来
x兔子的父亲,就是x减去是在斐波那契数列中最大的小于x的数
举个栗子
13号兔子,应减去8,得到他的祖先5
10号兔子,应减去8,得到他的祖先2
预处理出斐波那契数列,然后让ab中较大的到他的祖先,a==b时输出答案,过程可以二分,但是因为菜还懒,发现减去的数一定越来越小,单调指针往前扫就行
那么为什么减去是正确的?他的含义是什么?
首先对斐波那契数列求前缀和,得到第i天有几只兔子,然后发现前缀和不用另算,实际就是斐波那契数列第i+2项,这么显然的东西我还是打表发现的,实际还是在斐波那契数列上,找到第一项大于等于x的,就是x在当天出生,减去前一项,得到k,就是x是当天第k只出生的兔子,而标号是按照父亲标号从小到大编号的,当天第i只出生的兔子的父亲就是k,所以减去最大的小于x的就是x的父亲。
#include<cstdio>
#include<cstring>
using namespace std;
long long fib[1005];
int main()
{
freopen("fibonacci2.in","r",stdin);
freopen("fibonacci.out","w",stdout);
int m;scanf("%d",&m);
fib[0]=1;fib[1]=1;fib[2]=1;
for(int i=3;i<=60;++i)fib[i]=fib[i-1]+fib[i-2];
for(int i=1;i<=m;++i){
long long a,b;scanf("%lld%lld",&a,&b);
int pa=60,pb=60;
while(a!=b){
if(a>b){
while(pa>=1&&fib[pa-1]>=a)pa--;
a-=fib[pa-1];
}else{
while(pb>=1&&fib[pb-1]>=b)pb--;
b-=fib[pb-1];
}
}
printf("%lld\n",a);
}
return 0;
}
B. 数颜色
没错,学数据数据结构学傻的就是我
记得做分块莫队时候看到过这题,于是就往分块想,于是喜提TLE
其实开个数组存一下第i种颜色位置的下标,每次二分查找指定区间内颜色个数就好,数组好像开不下?用vector
特判一下不存在的情况
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn=300005;
int c[maxn];
vector <int> a[maxn];
void ask(){
int l,r,col;scanf("%d%d%d",&l,&r,&col);
int p1=lower_bound(a[col].begin(),a[col].end(),l)-a[col].begin();
int p2=upper_bound(a[col].begin(),a[col].end(),r)-a[col].begin()-1;
if(p1>p2)printf("0\n");
else printf("%d\n",p2-p1+1);
}
void update(){
int x;scanf("%d",&x);
if(c[x+1]==c[x])return;
int p1=lower_bound(a[c[x]].begin(),a[c[x]].end(),x)-a[c[x]].begin();
a[c[x]][p1]++;
p1=lower_bound(a[c[x+1]].begin(),a[c[x+1]].end(),x+1)-a[c[x+1]].begin();
a[c[x+1]][p1]--;
swap(c[x],c[x+1]);
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&c[i]);
for(int i=1;i<=n;++i)a[c[i]].push_back(i);
for(int i=1;i<=m;++i){
int op;scanf("%d",&op);
if(op&1)ask();
else update();
}
return 0;
}
C. 分组
分类讨论,由于某些奇奇怪怪的原因还是菜想对了k=1的情况然而只得到了部分部分分。。。
k只有1、2两种取值,分类讨论即可
k=1时,用vis数组记录当前团体内有谁,每次加入新兔子时枚举所有平方数减去该兔子颜色,判断是否存在与之矛盾的兔子,如果有就重新分组,为了保证字典序最小,从后往前倒叙枚举,为了保证时间效率,令开数组rem记录那些位置有兔子,清零时清空rem对应位置即可
k=2时,仿照团伙那题,维护两个并查集,表示两个团体,令开数组记录与矛盾i的兔子在哪个集合,每次有一对新的矛盾关系i-j,判断这两个兔子是否在一个并查集中,在的话重新分组,不在就将i与j敌人所在团体合并,j与i所在团体合并,倒叙枚举。
实际上这玩意叫扩展域并查集,记录i敌人的数组相当于把i拆成两点中的虚拟点。领会精神吧。。
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn=301075;
int a[maxn],n,k,rem[maxn],cl[maxn];
bool flag[maxn];
void work1(){
int cnt=0,temp=0;
for(int i=n;i>=1;--i){
bool fl=0;
for(int j=512;j;--j){
if(j*j-a[i]<=0)break;
if(flag[j*j-a[i]]){fl=1;rem[++cnt]=i;break;}
}
if(fl){
while(temp)flag[cl[temp--]]=0;
}
cl[++temp]=a[i];
flag[a[i]]=1;
}
printf("%d\n",cnt+1);
for(int i=cnt;i>=1;--i)printf("%d ",rem[i]);
printf("\n");
}
vector<int>v[maxn];
int f[maxn],d[maxn];
int fx(int x){
if(f[x])return f[x]=fx(f[x]);
return x;
}
void hb(int x,int y){
x=fx(x);
y=fx(y);
if(x!=y)f[x]=y;
}
int up(int l,int r){
for(int i=l;i<=r;++i)
vector<int>().swap(v[a[i]]);
return l-1;
}
void work2(){
int cnt=0,fl=0,las=n;
for(int i=n;i>=1;--i){
//printf("%d ",i);
for(int j=512;j;--j){
if(j*j-a[i]<=0)break;
int ss=v[j*j-a[i]].size();
if(ss){
for(int k=0;k<ss;++k){
if(fx(i)==fx(v[j*j-a[i]][k])){
las=up(i+1,las);
rem[++cnt]=i;
break;
}
else{
if(!d[v[j*j-a[i]][k]])d[v[j*j-a[i]][k]]=i;
if(!d[i])d[i]=v[j*j-a[i]][k];
hb(d[v[j*j-a[i]][k]],i);
hb(d[i],v[j*j-a[i]][k]);
}
}
}
}
v[a[i]].push_back(i);
}
printf("%d\n",cnt+1);
for(int i=cnt;i>=1;--i)printf("%d ",rem[i]);
printf("\n");
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
if(k&1)work1();
else work2();
return 0;
}
这次考试最大收获(大雾)发现自己还是最菜的,学到了不少vector使用方法