题目链接 戳我
先给翻译
A
给你n个点
找出特殊点的个数
特殊点:上下左右都有其他点的点
B
给你n和k
找到一个最小的v使得
v+v/k+v/k^2+v/k^3+……>=n
C
给你一个01串问你多少子串包含恰好k个1
D
貌似是给你一棵树,开始所有的边是黑色
3种操作
xy之间的边染黑
xy之间的边染白
询问2点距离,中间有白边输出-1
E
给你n个数
对于每个数你要在剩下的中间找一个数使得
a&b=0
然后输出
A
暴力
#include <cstdio> #include <algorithm> using namespace std; int a,b,c,d,e,f,g,h,i,j,k,l,m,n; int x[205],y[205]; int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]); for(i=1;i<=n;i++){ g=0; for(j=1;j<=n;j++){ if(x[i]==x[j]&&y[i]<y[j])g|=1; if(x[i]==x[j]&&y[i]>y[j])g|=2; if(x[i]<x[j]&&y[i]==y[j])g|=4; if(x[i]>x[j]&&y[i]==y[j])g|=8; } if(g==15)h++; } printf("%d\n",h); return 0; }
B
二分然后判断
#include <cstdio> #include <algorithm> using namespace std; int n,k,l,r,mid; bool check(int x){int s=0;while(x>0){s=s+x;x/=k;}return s>=n;} int main(){ scanf("%d%d",&n,&k); l=1;r=n;mid=(l+r)>>1; for(;l<r;mid=(l+r)>>1){ if(check(mid))r=mid; else l=mid+1; } printf("%d\n",l); return 0; }
C
找到每个1的位置
每连续k个1算一下左右多少0然后计算答案
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; int a[1000005],b,c,d,e,f,g,i,j,k,l,m,n,r; char s[1000005]; long long h; int main(){ scanf("%d",&k); scanf("%s",s+1); l=strlen(s+1); if(k==0){ for(i=1;i<=l;i++) if(s[i]=='0'){ for(j=i;s[j]=='0';j++); h=h+1ll*(j-i)*(j-i+1)/2; i=j; } printf("%I64d",h); return 0; } for(i=1;i<=l;i++) if(s[i]=='1'){ a[++n]=i; } a[n+1]=l+1; if(k>n){printf("0");return 0;} for(l=1,r=k;r<=n;l++,r++){ h=h+1ll*(a[l]-a[l-1])*(a[r+1]-a[r]); } printf("%I64d\n",h); return 0; }
D
直接树链剖分。。。。。
#include <cstdio> #include <algorithm> #define N 200005 using namespace std; int a,b,c,d,e,g,h,i,j,k,l,m,n,sum,tot; int f[N],dis[N],T[N],fa[N],top[N],size[N],son[N]; int wa[N],ne[N],la[N]; void make(int a,int b){ wa[++tot]=b;ne[tot]=la[a];la[a]=tot; wa[++tot]=a;ne[tot]=la[b];la[b]=tot; } void ch(int a,int b,int c){ if(dis[a]<dis[b])a=b; for(i=T[a];i<=n;i+=i&(-i))f[i]+=c*2-1; } int calc(int a,int b){ int s=0; for(i=a;i;i-=i&(-i))s-=f[i]; for(i=b;i;i-=i&(-i))s+=f[i]; return s; } void dfs(int x){ size[x]=1; for(int i=la[x];i;i=ne[i]) if(wa[i]!=fa[x]){ fa[wa[i]]=x; dis[wa[i]]=dis[x]+1; dfs(wa[i]); size[x]+=size[wa[i]]; if(size[wa[i]]>son[x])son[x]=wa[i]; } } void dfs2(int x,int Top){ top[x]=Top; T[x]=++sum; if(son[x])dfs2(son[x],Top); for(int i=la[x];i;i=ne[i]) if(wa[i]!=fa[x]&&wa[i]!=son[x]){ dfs2(wa[i],wa[i]); } } int main(){ scanf("%d",&n); for(i=1;i<n;i++){ scanf("%d%d",&a,&b); make(a,b); } dfs(1); dfs2(1,1); scanf("%d",&m); for(;m;m--){ scanf("%d",&a); if(a==1){ scanf("%d",&b); ch(wa[b*2-1],wa[b*2],0); } else if(a==2){ scanf("%d",&b); ch(wa[b*2-1],wa[b*2],1); } else{ scanf("%d%d",&c,&d);h=0;a=c;b=d; for(;top[a]!=top[b];){ if(dis[top[a]]<dis[top[b]])swap(a,b); h=h+calc(T[top[a]]-1,T[a]); a=fa[top[a]]; } if(dis[a]>dis[b])swap(a,b); h=h+calc(T[a],T[b]); if(h)printf("-1\n"); else printf("%d\n",dis[c]+dis[d]-dis[a]*2); } } return 0; }
E
定义f[i]表示i的答案
显然对于每个j属于i(j&i=j)
f[j]都是可以=f[i]的
然后从大到小转移一下
#include <cstdio> #include <algorithm> #define m 23 using namespace std; int a[1000005],b,c,d,e,f[10000005],g,h,i,j,k,l,n; int main(){ scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]); for(i=1;i<=n;i++){ f[a[i]^((1<<m)-1)]=a[i]; } for(i=(1<<m)-1;i>=0;i--){ for(j=0;j<m;j++)if(f[i|(1<<j)])f[i]=f[i|(1<<j)]; } for(i=1;i<=n;i++)if(f[a[i]])printf("%d ",f[a[i]]);else printf("-1 "); return 0; }
2024年1月21日 20:12
The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. <a href="https://boardmodelpaper.com/">boardmodelpaper.com</a> Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.
2024年1月21日 20:13
The Board model paper" typically refers to a sample or model question paper that is designed by educational boards or institutions for various exams. These papers serve as practice material for students preparing for exams, providing them with an idea of the question format, difficulty level, and the type of content that may be covered in the actual examination. boardmodelpaper.com Model papers are usually created for specific subjects or courses. They cover a range of topics and chapters that students are expected to have studied during the academic term. Students often use these educational board model papers as an integral part of their exam preparation strategy, helping them familiarize themselves with the exam pattern and refine their understanding of the subject matter.