BruceJay's Blog

Bruce之NOIP模拟考梦靥系列二

| Comments

扯淡

然而这就是水平的体现,Bruce快垫底了。

Day1

permutations

[Description]

给定2个1~n的全排列a,b。每次可以把a中最后一个元素取出,插入a的任意位置,求最少操作多少次可以使a变成b。

[Hint]

[Solution]

标记a中每个元素在b中出现的位置,找出从1开始的最长的上升序列1~x,n-x+1就是答案。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200100;
int a[N]; int pos[N]; int n;

inline int read()
{
    int x=0,t=1; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int main()
{
    freopen("permutations.in","r",stdin);
    freopen("permutations.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) pos[read()]=i;
    for(int i=1;i<=n;i++)
        if(pos[a[i]]<pos[a[i-1]]) {printf("%d",n-i+1);break;}
    return 0;
}

stone

[Description]

给定n堆石子,第i堆石子数a[i]。可以将第i堆石子并入第j堆石子,第i堆消失,第j堆变成a[i]+a[j],代价为a[i]。
有q个询问,每个询问有个限制k,表示每堆石子最多只能并入k堆石子,求最小代价。

[Hint]

[Solution]

这题的合并过程可以抽象地画成一棵树,v是u的儿子表示第v堆石子在合并了其儿子后,合并到第u堆中。推倒不难发现,一个节点的子节点最多k个,合并总代价为每个节点深度与权值的乘积之和。贪心求出深度为0,1,2....的点即可。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 100100;
bool cmp(const int &x,const int &y)
{return x>y;}
ll a[N]; ll sum[N];
int n,q,k; ll ans=0;

inline int read()
{
    int x=0,t=1; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

ll Solve(ll k)
{
    if(k==1) return ans;
    ll res=0,now=1,tmp=k;
    while(now<n){
        res+=sum[n]-sum[now];
        now+=tmp; tmp*=k;
    }
    return res;
}

int main()
{
    freopen("stone.in","r",stdin);
    freopen("stone.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++) ans+=sum[n]-sum[i];
    q=read();
    while(q--) k=read(),printf("%lld ",Solve(k));
    return 0;
}

rock

[Description]

路口有n个红绿灯,在第0秒左右灯变绿,持续g秒,又变红,持续r秒。第i个红绿灯到前一个红绿灯的距离为li。 终点到第n个红绿灯的距离为l[n+1]。
有q个询问,每个询问有个t[i],求第t[i]秒出发第多少秒能到终点。(速度1个单位每秒)

[Hint]

[Solution]

如果走到某个红绿灯时显示的是红灯,无论在红灯的哪一秒,离开这个红绿灯后走到终点的时间是一样的,也就是说,可以标记t[i]为在第i个红绿灯首次被停下来,离开这个红绿灯后走到终点还需要花费的时间。这个配合着模拟过程求出就是了。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 50100;
ll l[N]; ll f[N]; ll t[N];
ll g,r,d; int n,q;

inline int read()
{
    int x=0,t=1; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

int main()
{
    freopen("rock.in","r",stdin);
    freopen("rock.out","w",stdout);
    n=read()+1; g=read(); r=read(); d=g+r;
    for(int i=1;i<=n;i++) l[i]=read();
    q=read();
    while(q--){
        f[0]=read(); int tag=0;
        for(int i=1;i<=n;i++){
            f[i]=f[i-1]+l[i];
            if(i<n && f[i]%d>=g){
                f[i]+=d-f[i]%d;
                if(t[i]) {f[n]=f[i]+t[i]; break;}
                if(!tag) tag=i;
            }
        }
        if(tag) t[tag]=f[n]-f[tag];
        printf("%lld\n",f[n]);
    }
    return 0;
}

Day2

hello

[Description]

给定l,r,求区间[l,r]内首位数字等于末尾数字的数的个数。

[Hint]

[Solution]

设f[i]表示1~i中满足条件的数的个数。先处理位数比i的位数小的数(预处理)。标记first为i的首位数字,last为i的末尾数字,x为i的位数。在1~i中,所有与i的位数相同的数中,以1~first-1开头的,首末位数字相等的数都满足条件,一共有种,再考虑开头为first的,假设i去头去尾中间的数(一个x-2位的正整数)为mid,方案数有mid+1种(但对于first>last的情况要减去一种)。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 20;
ll a[N]; ll s[N]; ll bin[N];
ll l,r;

void prework()
{
    a[1]=a[2]=9;
    for(int i=3;i<=18;i++) a[i]=a[i-1]*10;
    for(int i=1;i<=18;i++) s[i]=s[i-1]+a[i];
    bin[0]=1;
    for(int i=1;i<=18;i++) bin[i]=bin[i-1]*10;
}

ll Solve(ll x)
{
    int y=18;
    for(int i=1;i<=18;i++) if(bin[i]>x) {y=i;break;}
    ll first=x/bin[y-1],last=x%10,mid=(x-first*bin[y-1])/10;
    return s[y-1]+(first-1)*bin[max(0,y-2)]+mid+(first<=last);
}

int main()
{
    freopen("hello.in","r",stdin);
    freopen("hello.out","w",stdout);
    prework();
    scanf("%lld%lld",&l,&r);
    printf("%lld",Solve(r)-Solve(l-1));
    return 0;
}

fraction

[Description]

如下形式给定一个分数A/B:
分子A=a1*a2*...*an;
分母B=b1*b2*...*bm。
同样形式输出另一个分数C/D:
分子C=c1*c2*...*cp;
分母D=d1*d2*...*dq。
要求gcd(C,D)=1,p<=100000,q<=100000。

[Hint]

[Solution]

不难想到这题的方向是质因数分解,线性筛出内的素数,再标记每个数的最小质因子(便于分解质数)。先将A,B分解,用桶来标记数对每个质数的幂次,可以求出gcd(A,B),再用桶模拟A,B除以gcd(A,B)的过程,构造出的解一定满足条件。

[Code]

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int NUM = 1e7+1;
const int SIZE = 1e5+1;
int suma[NUM]; int sumb[NUM];
int prime[NUM]; int kill[NUM];
bool del[NUM];
int a[SIZE]; int b[SIZE];
int n,m,cnt=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Linear_Shaker()
{
    for(int i=2;i<NUM;i++){
        if(!del[i]) prime[++cnt]=i,kill[i]=i;
        for(int j=1;j<=cnt && i*prime[j]<NUM;j++){
            del[i*prime[j]]=true;
            kill[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
}

void Div(int x,int sum[])
{
    while(x!=1){
        sum[kill[x]]++;
        x/=kill[x];
    }
}

int Solve(int x,int sum[])
{
    int y=x;
    while(x!=1){
        if(sum[kill[x]]){
            y/=kill[x];
            sum[kill[x]]--;
        }
        x/=kill[x];
    }
    return y;
}

int main()
{
    freopen("fraction.in","r",stdin);
    freopen("fraction.out","w",stdout);
    Linear_Shaker();
    n=read(); m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++) b[i]=read();
    for(int i=1;i<=n;i++) Div(a[i],suma);
    for(int i=1;i<=m;i++) Div(b[i],sumb);
    for(int i=1;i<NUM;i++) suma[i]=min(suma[i],sumb[i]);
    memcpy(sumb,suma,sizeof(suma));
    for(int i=1;i<=NUM;i++) sumb[i]=suma[i];
    printf("%d %d\n",n,m);
    for(int i=1;i<=n;i++) printf("%d ",Solve(a[i],suma));
    puts("");
    for(int i=1;i<=m;i++) printf("%d ",Solve(b[i],sumb));
    return 0;
}

match

[Description]

给定两个由大写字母组成的长度为n的字符串a,b。
从a,b中分别拿出子串x,y(x,y长度相等),定义f(x,y)为串x和串y对应位置相等的个数。
对每个子串抽取的概率相等。求f(x,y)的期望。

[Hint]

[Solution]

显然要O(n)的算法。
不难求出取子串x和y的总方案数为
如果a[i]==b[j],那么只要在a,b上取的区间[x,x+l-1]和[y,y+l-1]能保证i-x==j-y,那么a[i]和b[j]就会对答案产生贡献。a[i]与b[j]对答案产生的贡献g(i,j)为满足,,的(x,y,l)的数量,看似复杂,其实不难求:
$$g[i][j]=i*(n-j+1),i<=j$$
$$g[i][j]=(n-i+1)*j,i>j$$
我们可以正反各进行一遍扫描,分别处理两种情况(具体看代码就懂啦)。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 2000100;
char s[N]; int a[N]; int b[N];
ll f[30]; ll g[30];
int n; double ans=0; ll tot;

int main()
{
    freopen("match.in","r",stdin);
    freopen("match.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) tot+=(ll)i*i;
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) a[i]=s[i]-'A'+1;
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) b[i]=s[i]-'A'+1;
    for(int i=1;i<=n;i++){
        f[b[i]]+=(ll)i; ans+=(double)(n-i+1)*f[a[i]]/tot;
    }
    for(int i=n;i;i--){
        ans+=(double)i*g[a[i]]/tot; g[b[i]]+=(ll)n-i+1;
    }
    printf("%.6lf",ans);
    return 0;
}

Comments

comments powered by Disqus