“字节跳动杯”2018中国大学生程序设计竞赛-女生专场

题解：
https://files.cnblogs.com/files/clrs97/2018CCPC%E5%A5%B3%E7%94%9F%E8%B5%9Bsol.pdf
Code：
1001. CCPC直播
#include
#include
int Case,n,i,x;char s[100];
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%s",s);
    n=strlen(s);
    for(i=0;i<3-n;i++)putchar(' ');
    printf("%s|",s);
    scanf("%s",s);
    n=strlen(s);
    printf("%s",s);
    for(i=0;i<16-n;i++)putchar(' ');
    scanf("%s",s);
    printf("|%s|[",s);
    scanf("%s",s);
    n=strlen(s);
    if(s[0]=='R'&&s[1]=='u'){
      scanf("%d",&x);
      for(i=0;i


1002. 口算训练

#include
#include
using namespace std;
const int N=100010;
int Case,n,m,i,x,L,R;vectorv[N];
inline void add(int n,int x){
  for(int i=2;i*i<=n;i++)while(n%i==0)v[i].push_back(x),n/=i;
  if(n>1)v[n].push_back(x);
}
inline bool ask(int x,int k){
  int l=0,r=v[x].size()-1,t=-1,mid;
  while(l<=r)if(v[x][mid=(l+r)>>1]>=L)r=(t=mid)-1;else l=mid+1;
  if(t<0)return 0;
  r=v[x].size()-1;
  while(k--){
    if(t>r)return 0;
    if(v[x][t]>R)return 0;
    t++;
  }
  return 1;
}
inline bool solve(int n){
  for(int i=2;i*i<=n;i++)if(n%i==0){
    int t=0;
    while(n%i==0)n/=i,t++;
    if(!ask(i,t))return 0;
  }
  if(n>1)return ask(n,1);
  return 1;
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(i=2;i


1003. 缺失的数据范围

#include
typedef long long ll;
int Case,a,b;ll K,l,r,mid,ans;
inline ll mul(ll a,ll b){
  if(!a||!b)return 0;
  if(a>(K+5)/b)return K+5;
  a*=b;
  return a>K+5?K+5:a;
}
inline ll getpow(ll a,int b){
  ll t=1;
  while(b--)t=mul(t,a);
  return t;
}
inline int getlog(ll n){
  ll o=n;
  while(o%2==0)o/=2;
  int t=0;
  while(n>1)n/=2,t++;
  if(o>1)t++;
  return t;
}
inline ll cal(ll n,int a,int b){
  return mul(getpow(n,a),getpow(getlog(n),b));
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d%lld",&a,&b,&K);
    l=2,r=K,ans=1;
    while(l<=r){
      mid=(l+r)>>1;
      if(cal(mid,a,b)<=K)l=(ans=mid)+1;else r=mid-1;
    }
    printf("%lld\n",ans);
  }
}



1004. 寻宝游戏

#include
#include
using namespace std;
const int N=55,M=25;
int Case,n,m,K,i,j,k,x,y,z,a[N][N],f[N][N][M][M],ans,s[N],cnt;//in out
inline bool cmp(int x,int y){return x>y;}
inline void up(int&a,int b){if(a


1005. 奢侈的旅行

#include
#include
#include
using namespace std;
typedef long long ll;
typedef pairP;
const int N=100010,M=200010;
const ll inf=1LL<<60;
int Case,n,m,i,g[N],v[M],a[M],b[M],nxt[M],ed;ll d[N];
priority_queue,greater >q;
inline void add(int x,int y,int A,int B){v[++ed]=y;a[ed]=A;b[ed]=B;nxt[ed]=g[x];g[x]=ed;}
int getlog(ll x){
  int t=0;
  while(x>1)x/=2,t++;
  return t;
}
inline void ext(int x,ll y){if(d[x]>y)q.push(P(d[x]=y,x));}
inline bool check(ll lv,ll a,ll b){return a/lv>=((1LL<


1006. 对称数

#include
#include
#include
using namespace std;
typedef unsigned long long ll;
const int N=200010,M=N*20;
int Case,n,m,i,x,y,z,a[N],g[N],v[N<<1],nxt[N<<1],ed;
int size[N],son[N],d[N],f[N],top[N],tot,root[N],l[M],r[M];
ll sum[M],ran[N],pre[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
int ins(int x,int a,int b,int c,ll d){
  int y=++tot;
  sum[y]=sum[x]^d;
  if(a==b)return y;
  int mid=(a+b)>>1;
  if(c<=mid){
    l[y]=ins(l[x],a,mid,c,d);
    r[y]=r[x];
  }else{
    l[y]=l[x];
    r[y]=ins(r[x],mid+1,b,c,d);
  }
  return y;
}
void dfs(int x,int y){
  f[x]=y;d[x]=d[y]+1;
  size[x]=1;son[x]=0;
  root[x]=ins(root[y],1,N,a[x],ran[a[x]]);
  for(int i=g[x];i;i=nxt[i])if(v[i]!=y){
    dfs(v[i],x);
    size[x]+=size[v[i]];
    if(size[v[i]]>size[son[x]])son[x]=v[i];
  }
}
void dfs2(int x,int y){
  top[x]=y;
  if(son[x])dfs2(son[x],y);
  for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]&&v[i]!=son[x])dfs2(v[i],v[i]);
}
inline int lca(int x,int y){
  while(top[x]!=top[y]){
    if(d[top[x]]>1;
    if((sum[l[A]]^sum[l[B]]^sum[l[C]]^sum[l[D]])!=(pre[mid]^pre[a-1])){
      b=mid;
      A=l[A];
      B=l[B];
      C=l[C];
      D=l[D];
    }else{
      a=mid+1;
      A=r[A];
      B=r[B];
      C=r[C];
      D=r[D];
    }
  }
  return a;
}
int main(){
  for(i=1;i


1007. 赛题分析

#include
#include
using namespace std;
int T,x,y,n,m,i,A,B;
int main(){
  scanf("%d",&T);
  for(x=1;x<=T;x++){
    scanf("%d%d",&n,&m);
    A=B=~0U>>1;
    for(i=1;i<=n;i++){
      scanf("%d",&y);
      A=min(A,y);
    }
    for(i=1;i<=m;i++){
      scanf("%d",&y);
      B=min(B,y);
    }
    printf("Problem %d:\n",x+1000);
    printf("Shortest judge solution: %d bytes.\n",A);
    if(m)printf("Shortest team solution: %d bytes.\n",B);
    else puts("Shortest team solution: N/A bytes.");
  }
}



1008. quailty算法

#include
const int N=300010,inf=~0U>>1;
int Case,n,i,a[N],b[N];long long ans;
void solve(int o,int l,int r){
  if(o<0||l>=r)return;
  int i,j,L=l-1,R=r+1;
  for(i=l;i<=r;i++)if(a[i]>>o&1)b[++L]=a[i];else b[--R]=a[i];
  for(i=l;i<=r;i++)a[i]=b[i];
  solve(o-1,l,L);
  solve(o-1,R,r);
  int cl=L-l+1,cr=r-R+1;
  if(!cl||!cr)return;
  if(cl>=3&&cr>=3)return;
  int k=1,A=inf,B=inf;
  if(cl<3&&cr<3)k++;
  for(i=l;i<=L;i++)for(j=R;j<=r;j++){
    int t=a[i]^a[j];
    if(t


1009. SA-IS后缀数组

#include
const int N=1000010;
int Case,n,i;char a[N],f[N];
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%s",&n,a+1);
    f[n]='>';
    for(i=n-1;i;i--){
      if(a[i]a[i+1])f[i]='>';
      else f[i]=f[i+1];
    }
    for(i=1;i


1010. 回文树

#include
#include
#include
using namespace std;
typedef pairP;
const int N=100010;
int Case,n,i,j,x,y,a[N],ans;vectorg[N];
void dfs(int x,int fx,int y,int fy){
  if(a[x]!=a[y])return;
  if(fx&&x==y)return;
  if(x<=y)ans++;
  for(int i=0,j=0,k=0;i


1011. 代码派对

#include
typedef long long ll;
const int N=100010,M=1010;
int Case,n,m,i,j,e[N][4],s[M][M];ll C3[N],ans;
ll solve(int dx,int dy){
  for(i=1;i<=m;i++)for(j=1;j<=m;j++)s[i][j]=0;
  for(i=1;i<=n;i++){
    int xl=e[i][0]+dx,yl=e[i][1]+dy,xr=e[i][2],yr=e[i][3];
    if(xl>xr||yl>yr)continue;
    s[xl][yl]++;
    s[xr+1][yl]--;
    s[xl][yr+1]--;
    s[xr+1][yr+1]++;
  }
  ll ret=0;
  for(i=1;i<=m;i++)for(j=1;j<=m;j++){
    s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    ret+=C3[s[i][j]];
  }
  return ret;
}
int main(){
  for(i=1;i
“字节跳动杯”2018中国大学生程序设计竞赛-女生专场

相关

标签
