dc_y's Blog

JSOI2015终于考完辣

然而这次题目极其蛋疼（还不如考JSOI。。）

所以还是决定不订正辣（谁让这套题巧妙地避开了我的知识范围）

要题目戳这

要题解戳这

T1

通项公式还是挺水的

然而不会求Σ怎么破。。

先打个20分再说

后面那p<=1000的20分好像可做

似乎有循环诶

好的40分到手

T2

听说神(S)犇(B)桢错误贪心拿了18分，略不爽

T3

看到300行代码直接弃疗

听说这是JSOI2015Day2

本蒟蒻再次滚粗。。

Orz NiroBC 230

Orz Gold_7 220

Orz Chrysanthemum 220

本蒟蒻2、3两题炸飞，100收场

T1 

表示被题目吓到了，模拟了下样例，还是看不出什么。。

此时桢神(S)犇(B)吼道：这是傻逼题啊卧槽。。

貌似是结论题，窝这种蒟蒻只好猜结论了→_→

好像是答案是2^nk。。嗯过大样例了。。

#include<cstdio>
#define p 1000000007
long long ans,n,m,k;
long long mi(long long x,long long y)
{
	long long mi=1;
	while (y>0){
		if (y%2==1) mi=mi*x%p;
		y/=2;
		x=x*x%p;
	}
	return(mi);
}
int main()
{
	freopen("subset.in","r",stdin);
	freopen("subset.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	k=mi(2,n);
    ans=mi(k,m);
    printf("%lld\n",ans);
	
}

T2

这个K真是不明觉厉。。

打个20分暴力吧。。

诶爆0了。。原来是没写using namespace std; (刚转C勿喷)

正解是二分

如果存在更优解，则有：

对于len=l的情况，单调队列维护取最优解即可。

对于len∈(l,r],最优解必为M(i,j)=a[i],m(i,j)=a[j]或M(i,j)=a[j],m(i,j)=a[i]。

那么将分母乘过去，就有：a[i]+b*i-(a[j]+b*j)>b*K或a[j]-b*j-(a[i]-b*i)>b*K。

然后两个单调队列维护即可。

#include<cstdio>
int n,m,k,cas,l,r,head,tail,h,t;
int q[100000],p[100000],a[100000];
double ans,ans2;
double erfen(double x,double y)
{
    if (y-x<1e-6) return(x);
    double z=(x+y)/2;
    head=1;tail=0;q[1]=0;
     
    for (int i=l;i<=n;i++){
        if (i>l){
            while ((q[head]<=i-r)&&(head<tail)) head++;
            if (a[q[head]]+z*q[head]-a[i]-i*z>z*k) return(erfen(z,y));
        }
        int m=i-l+1;
        while ((a[m]+m*z>a[q[tail]]+z*q[tail])&&(tail>=head)) tail--;
        q[++tail]=m;
    }
    head=1;tail=0;q[1]=0;
    for (int i=l;i<=n;i++){
        if (i>l){
            while ((q[head]<=i-r)&&(head<tail)) head++;
            if (-a[q[head]]+z*q[head]+a[i]-i*z>z*k) return(erfen(z,y));
        }
        int m=i-l+1;
        while ((a[m]-m*z<a[q[tail]]-z*q[tail])&&(tail>=head)) tail--;
        q[++tail]=m;
    }
    return(erfen(x,z));
}
int main()
{
    scanf("%d",&cas);
    while (cas-->0)
    {
        scanf("%d%d%d%d",&n,&k,&l,&r);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        ans=0;
        ans=erfen(0,1000);
        head=1;tail=0;q[1]=0;
        h=1;t=0;p[1]=0;
        ans2=0;
        for (int i=1;i<=n;i++){
            while ((a[i]>a[q[tail]])&&(tail>=head)) tail--;
            q[++tail]=i;
            while ((a[i]<a[p[t]])&&(t>=h)) t--;
            p[++t]=i;
            if (i>=l){
                while ((q[head]<=i-l)&&(head<tail)) head++;
                while ((p[h]<=i-l)&&(h<t)) h++;
                if ((double)(a[q[head]]-a[p[h]])/(l-1+k)>ans2) ans2=(double)(a[q[head]]-a[p[h]])/(l-1+k);
            }
        }
        if (ans>ans2) printf("%.4lf\n",ans);
        else printf("%.4lf\n",ans2);
    }
}

T3

听说是可持久化trie树，然而我脑补了个hash做法。

l-r的前缀个数为根节点到l的个数+根节点到r的个数-2*根节点到lca(l,r)的个数。只要dfs时更新hash数组P，可O(1)询问。

注意hash冲突，概率蛮大的。。窝写了三个hash才过。。

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 310000
#define P 19999999
#define P1 19999981
#define P2 19999963
#define M 211
int nu,x,y,n,m,num,k,s,l;
long long w;
int e[N],d[N],c[N],ans[N],head2[N],next2[N],vet2[N],flag[N],f[N],lca[N],head[N],next[N],vet[N],head1[N],next1[N],vet1[N],cost1[N],p2[21000000],p[21000000],p1[21000000];
int cost[N][11][3],cost2[N][3];
char ch[11];
 
int add(int a,int b)
{
    next[++num]=head[a];
    head[a]=num;
    vet[num]=b;
}
int addd(int a,int b,int c)
{
    next1[++num]=head1[a];
    head1[a]=num;
    vet1[num]=b;
    cost1[num]=c;
}
int ad(int a,int b,int c,int d,int e)
{
    next2[++nu]=head2[a];
    head2[a]=nu;
    vet2[nu]=b;
    cost2[nu][0]=c;
    cost2[nu][1]=d;
    cost2[nu][2]=e;
}
int find(int x)
{
    if (f[x]!=x) f[x]=find(f[x]);
    return(f[x]);
}
int df(int u,int fa)
{
    int v=0;
    flag[u]=1;
    for (int e=head1[u];e!=0;e=next1[e]){
        v=vet1[e];
        if (flag[v]=1) lca[cost1[e]]=v;
        if (flag[v]=2) lca[cost1[e]]=find(v);
    }
    for (int e=head[u];e!=0;e=next[e]){
        v=vet[e];
        if (v!=fa) df(v,u);
    }
    f[u]=fa;
    flag[u]=2;
}
int dfs(int u,int fa)
{
    int v=0;
    int shit;
    for (int e=head2[u];e!=0;e=next2[e]){
        v=vet2[e];
        if (e<=2*m) shit=1;
        else shit=-2;
        if (cost2[e]!=0)
        ans[v]=ans[v]+shit*min(min(p[cost2[e][0]],p1[cost2[e][1]]),p2[cost2[e][2]]);
    }   
    for (int e=head[u];e!=0;e=next[e]){
        v=vet[e];
        if (v!=fa){
            for (int i=0;i<=9;i++) {p[cost[e][i][0]]++;p1[cost[e][i][1]]++;p2[cost[e][i][2]]++;}
            dfs(v,u);
            for (int i=0;i<=9;i++) {p[cost[e][i][0]]--;p1[cost[e][i][1]]--;p2[cost[e][i][2]]--;}
        }
    }
}   
int main()
{
    scanf("%d",&n);
    for (int i=1;i<n;++i){
        scanf("%d%d%s",&x,&y,ch);
        add(x,y);
        add(y,x);
        w=0;
        long long ww=0;
        long long w2=0;
        for (int j=0;j<=9;j++){
            if (ch[j]<97) break;
            w=(w*M+ch[j])%P;
            ww=(ww*M+ch[j])%P1;
            w2=(w2*M+ch[j])%P2;
            cost[num-1][j][0]=cost[num][j][0]=w;
            cost[num-1][j][1]=cost[num][j][1]=ww;
            cost[num-1][j][2]=cost[num][j][2]=w2;
        }
    }
    num=0;
    for (int i=1;i<=n;i++) f[i]=i;
    scanf("%d",&m);
    for (int i=1;i<=m;i++){
        scanf("%d%d%s",&x,&y,ch);
        w=0;
        long long ww=0;
        long long w2=0;
        for (int j=0;j<=9;j++){
            if (ch[j]<97) break;
            w=(w*M+ch[j])%P;
            ww=(ww*M+ch[j])%P1;
            w2=(w2*M+ch[j])%P2;
        }
        c[i]=w;
        d[i]=ww;
        e[i]=w2;
        addd(x,y,i);
        ad(x,i,c[i],d[i],e[i]);
        ad(y,i,c[i],d[i],e[i]);
        addd(y,x,i);
    }
    df(1,0);
    for (int i=1;i<=m;i++) ad(lca[i],i,c[i],d[i],e[i]);
    dfs(1,0);
    for (int i=1;i<=m;i++) printf("%d\n",ans[i]);    
}