头部背景图片
星之所幸,尘之所哀。 |
星之所幸,尘之所哀。 |

ModularPowerEquation!!

2019-03-26

ModularPowerEquation!!

题目描述

  Q次询问,给出A和P,求正整数x满足Axx(modP)A^x\equiv x(mod P)

输入格式

  第一行一个整数Q表示询问次数。

  第Q行每行两个数a和P代表一次询问。

输出格式

  第i行代表第i次询问。

样例

input

7
2 4
3 8
9 6
10 7
177 168
2028 88772
123456789 987654321

output

4
11
9
2
7953
234831584
471523108231963269

Hint

1q4001\leq q\leq 400

1n,x1091\leq n,x\leq 10^9

题解:

Axx(mod p){A}^x\equiv x(mod\ p)

AA%φ(p)+φ(p)x(mod p){A}^{A\%\varphi(p)+\varphi(p)}\equiv x(mod\ p)x>φ(P)x>\varphi(P)

t=x%φ(p)+φ(p)t=x\%\varphi(p)+\varphi(p)

AtAxx(mod p)A^t\equiv A^x\equiv x(mod\ p)

tx(mod φ(p))t\equiv x(mod\ \varphi(p))

Atx(mod p)A^t\equiv x(mod\ p)

tAt(mod gcd(p,φ(p)))t\equiv A^t(mod\ \gcd(p,\varphi(p)))

这样就转成了子问题,当p等于1时可直接返回1。

将问题转化成已知t如何求x

AtAxx(mod p)A^t\equiv A^x\equiv x(mod\ p)

tx(mod φ(p))t\equiv x(mod\ \varphi(p))

可得

x=t+Xφ(x)x=t+X\varphi(x)

x=At+Ypx=A^t+Yp

列不定方程

Xφ(p)Yp=Att{X}\varphi(p)-Yp=A^t-t

用exgcd任意解出一组即可,再将xx保持在φ(p)\varphi(p)之上即可。

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long x,long long y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
long long exgcd(long long a,long long b,long long &x,long long &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    long long d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
long long phi(long long x){
    int ans=1;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            ans*=(i-1);
            x/=i;
            while(x%i==0)x/=i,ans*=i;
        }
    }
    if(x!=1)ans*=(x-1);
    return ans;
}
long long power(long long x,long long k,long long P){
    long long ans=1;
    while(k){
        if(k&1)(ans*=x)%=P;
        (x*=x)%=P;
        k>>=1;
    }
    return ans;
}
long long solve(long long a,long long m){
    if(m==1)return 1;
    long long M=phi(m);
    long long d=gcd(M,m);
    long long t=solve(a,d);
    long long At=power(a,t,m);
    long long x,y;
    exgcd(M/d,m/d,x,y);
    long long A=((At-t%M)/d*x)%m;
    long long ans=t%M+A*M;
    ans%=m/d*M;
    ans+=m/d*M;
    ans%=m/d*M; 
    ans+=m/d*M; 
    return ans;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        long long x,m;
        scanf("%lld%lld",&x,&m);
        long long ans=solve(x,m);
        printf("%lld %lld %lld\n",ans,ans%m,power(x,ans,m));
    }
}

超现实数 Surreal numbers

超现实数

上段石碑文字:

    In the beginning, everything was void,and J.H.W.H Conway began to create numbers.Conway said,"Let there be two rules which bring forth all numbers large and small.This shall be the first rule: Every number corresponds to two sets of previously created numbers,such that no member of the left set is greater than or equal to any member of the right set.And the second rule shall be this:One number is less than or equal another number if and only if no member of the first number’s left if greater than or equal to the the second number, and no member of the second number’s right set is less than or equal to the first number."And Conway examined there two rules he had made,and behold! They were very good.And the first number was created from the void left set and the void right set.Conway called this number"zero,"and said that it shall be a sign to separate positive numbers from negative numbers.Conway proved that zero was less than or equal to zero,and he saw that it was good.And the evening and the morning were the day of zero.On the next day,two more numbers were created,one with zero as its left set and one with zero as its right set.And Conway called "minus one."And he proved that minus one is less than but not equal to zero and zero is less than but not equal to one.And the evening …

翻译:

    初,万物混沌茫然,随后J.H.W.H.Conway始创数。Conway曰,"创生二道,大小诸数盖由此出。其一曰:凡数,皆合于前创二数之集,其位左者,无一大于或等于右者。其二曰:甲数小于或等于乙数,当且仅当甲数之左集中无一大于或等于乙数,且乙数之右集中无一小于或等于甲数。"Conway检视二道,连呼妙哉!此二道真绝妙。

    元初之数,左右皆空。Conway名之曰"零",命其为正负两界分野之符。Conway证得,零小于或等于零,此间妙也。夜去昼来,是为零日。次日,又得二数。其一以零为左集,其一以零为右集。Conway名前者曰"一",后者曰“负一”,Conway证得,负一小于而不等于零,零小于而不等于一。是夜…

Day1:

0={:}0=\{ \emptyset:\emptyset \}

1={0:}1=\{0:\emptyset\}

1={:0}-1=\{\emptyset:0\}

规则

(1)x=(XL,XR),XLXRx=(X_L,X_R),X_L\ngeq X_R

(2)xyx\leq y意味着XLyX_L\ngeq yxYRx\ngeq Y_R

定理

    显然根据规则(2)在比较大小关系上x{max(AXL):max(BXR)}x\equiv \{max(A\in X_L):max(B \in X_R)\}

T1:若xyx\leq yyzy\leq z,则xzx\leq z

证明:设有三数x,y,z满足

    xyx\leq y,且yzy\leq z,且xzx\nleq z

    则称他们为坏数(x,y,z)

    根据规则2我们可以得知yzy\leq z,(zXLz\leq X_LZRxZ_R\leq x),yXLy\nleq X_L

    当XLzX_L\geq z时,(y,z,XL)(y,z,X_L)是坏数。

    当ZRxZ_R\leq x时,(ZR,x,y)(Z_R,x,y)是坏数。

    设置函数d(x)d(x)表示xx被创造出来的日子。显然d(x)<d(XL),d(x)<d(XR)d(x)<d(X_L),d(x)<d(X_R)

    那么d(x)+d(y)+d(z)=nd(x)+d(y)+d(z)=n,而他们能拓展的坏数的d总和要小于他们,归纳可知所有坏数的存在都必须有一个(xk,yk,zk)(x_k,y_k,z_k)d(xk)+d(yk)+d(zk)=3d(x_k)+d(y_k)+d(z_k)=3。而day1的三个数并不存在这样的关系,反证可得T1成立。

T2:XLxX_L\leq xxXRx\leq X_R

证明:

XLxX_L\nleq x实质上是在说xxLx\leq x_L,因为能得到xxLLx\leq x_{LL},xLLx_{LL}\leq

xxLx\leq x_L不成立,因为这意味着XLxLX_L\ngeq x_L,用T3可得xLxLx_L\leq x_L,所以不成立。同理xXRx\leq X_R

T3:xxx\leq x

证明:这 意味着XLxX_L\ngeq xxXRx\ngeq X_R

即要证明xxLx\leq x_L不成立,而这意味着xLxLx_L\ngeq x_L,根据上文用到的归纳法可证明不成立。

根据T2可证明所有的数都相关,即

T4:若xyx\nleq y即,yxy\leq x

未完待续…

string[BZOJ某题加强版]

2018-11-19

题目:

img

题解:

    用排除法,一个SabT,我们枚举abT,查找有多少个S能接上a。即abT与fail[abT]之间的差就是能接上的最短距离。而Sab T这种分段方式则会在枚举到bT的时候枚举到,因此每个只需与fail取差的那段即可。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 1200000
using namespace std;
char s[N];
int ch[N][27],n,d[N],c[N],siz[N],tot,q[N],fail[N];
long long ans;
int build_trie(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        int m=strlen(s+1);
        int now=0;
        for(int i=1;i<=m;i++){
            if(ch[now][s[i]-'a'+1]==0)ch[now][s[i]-'a'+1]=++tot;
            d[ch[now][s[i]-'a'+1]]=d[now]+1;
            now=ch[now][s[i]-'a'+1];
        }
    }
}
int build_AC(){
    int head=0,tail=1;
    q[1]=0;
    while(head<tail){
        int now=q[++head];
        for(int i=1;i<=26;i++){
            int v=ch[now][i];
            if(v==0)continue;
            int x;
            for(x=fail[now];x&&!ch[x][i];x=fail[x]);
            if(now!=x)fail[v]=ch[x][i];
            q[++tail]=v;
        }
    }
    for(int i=tail;i;i--){
        siz[q[i]]++;
        siz[fail[q[i]]]+=siz[q[i]];
    }
}
int dfs(int x){
    if(fail[x]){
        int o=d[x]-d[fail[x]];
        if(o!=0)ans-=siz[c[o]]-1;
    }
    c[d[x]]=x;
    for(int i=1;i<=26;i++)if(ch[x][i])dfs(ch[x][i]);
}
int main(){
    int T;
    scanf("%d",&T);
    build_trie(); 
    ans=1LL*tot*tot;
    build_AC();
    dfs(0);
    printf("%lld\n",ans);
}

「雅礼集训 2018 Day10」贪玩蓝月

2018-10-25

题目:「雅礼集训 2018 Day10」贪玩蓝月

题解:

    维护两个栈,插入就直接插入,删除就出栈,如果其中一个栈清空了,那么就直接从另外那个栈暴力取一半来重构。

    统计答案就用线段树来暴力求最大值。(不知道为什么输入数据里有点的编号qwq)。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 120000
using namespace std;
int P;
long long h[520],n,A,B,c[520];
struct illyasviel{
    int w,v;
    illyasviel(int _w=0,int _v=0){w=_w,v=_v;}
}a[N],b[N],d[N];
struct node{
    long long f[520];
    int clear(){
        memset(f,-1,sizeof(f));
        f[0]=0;
    }
    int add(int v,int w){
        memset(h,-1,sizeof(h));
        h[0]=0;
        for(int i=0;i<P;i++)if(f[i]!=-1)h[(i+v)%P]=max(h[(i+v)%P],f[i]+w);
        for(int i=0;i<P;i++)f[i]=max(f[i],h[i]);
    }
}g[N],f[N];
char s[10];
int add1(int v,int w){
    A++;
    a[A].v=v;
    a[A].w=w; 
    f[A]=f[A-1];
    f[A].add(v,w);
}
int add2(int v,int w){
    B++;
    b[B].v=v;
    b[B].w=w;
    g[B]=g[B-1];
    g[B].add(v,w);
}
int rebuild(){
    int cnt=0;
    for(int i=A;i>=1;i--)d[++cnt]=a[i];
    for(int i=1;i<=B;i++)d[++cnt]=b[i];
    A=cnt/2;
    B=cnt-A;
    int o=0;
    for(int i=A;i>=1;i--)a[i]=d[++o];
    for(int i=1;i<=A;i++)f[i]=f[i-1],f[i].add(a[i].v,a[i].w);
    for(int i=1;i<=B;i++)b[i]=d[++o];
    for(int i=1;i<=B;i++)g[i]=g[i-1],g[i].add(b[i].v,b[i].w);
}
int del1(){
    if(A==0)rebuild();
    if(A==0)B--;
    else A--;
}
int del2(){
    if(B==0)rebuild();
    if(B==0)A--;
    else B--;
}
namespace seg{
    long long t[5000];
    int build(int i,int l,int r){
        if(l==r)return t[i]=c[l];
        int mid=(l+r)/2;
        build(i*2,l,mid);
        build(i*2+1,mid+1,r);
        t[i]=max(t[i*2],t[i*2+1]); 
    }
    long long query(int i,int l,int r,int x,int y){
        if(x<=l&&y>=r)return t[i];
        int mid=(l+r)/2;
        long long ans=-100000000000LL;
        if(x<=mid)ans=max(ans,query(i*2,l,mid,x,y));
        if(y>mid)ans=max(ans,query(i*2+1,mid+1,r,x,y));
        return ans;
    }
}
long long cal(int x,int y){
    for(int i=0;i<P;i++)c[i+1]=f[A].f[i];
    for(int i=1;i<=P;i++)if(c[i]==-1)c[i]=-10000000000000LL; 
    long long ans=-1;
    seg::build(1,1,P);
    for(int i=0;i<P;i++){
        if(g[B].f[i]==-1)continue;
        int l=x-i,r=y-i;
        if(l<0)l+=P;
        if(r<0)r+=P;
        if(l<=r)ans=max(ans,g[B].f[i]+seg::query(1,1,P,l+1,r+1));
        else ans=max(ans,g[B].f[i]+max(seg::query(1,1,P,1,r+1),seg::query(1,1,P,l+1,P)));
    }
    return max(ans,-1LL);
}
int main(){
    int T;
    scanf("%d",&T);
    scanf("%d%d",&n,&P);
    int tot=1,cnt=0;
    f[0].clear();
    g[0].clear();
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        if(s[1]=='I'){
            int v,w;
            scanf("%d%d",&v,&w);
            v%=P;
            if(s[2]=='F')add1(v,w);
            if(s[2]=='G')add2(v,w);
        }
        if(s[1]=='D'){
            if(s[2]=='F')del1(); 
            if(s[2]=='G')del2();
        }
        if(s[1]=='Q'){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",cal(x,y));
        }
    }
}

BZOJ4676 Xor-Mul棋盘

2018-10-09

题目:

img

img

题解:

    考虑每个二进制位是相对独立的,那么就可以枚举每一行的状态然后暴力转移,预处理一些东西后,复杂度大概是O(22nmlog2106)O(2^{2n}m\log_{2}{10^6})。差不多是两亿。(之前有道题六亿longlong带取模2.3s能过,就没去思考进一步的复杂度了(还能通过类似插头DP的转移方式将其中2n2^n变为n)

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 12000
using namespace std;
long long f[N][(1<<5)+10];
int a[6][N],b[6][N],you[6][N],xia[6][N];
int A[N][(1<<5)+10],B[N][(1<<5)+10],C[N][(1<<5)+10];
int p[6][N];
int n,m,q[10];
int cal1(int i,int j){
    int ans=0;
    for(int k=1;k<=n;k++)q[k]=(j&(1<<(k-1)))>0;
    q[n+1]=q[1];
    for(int k=1;k<=n;k++)if(q[k]!=q[k+1])ans+=xia[k][i];
    return ans;
}
int cal2(int i,int j){
    int ans=0;
    for(int k=1;k<=n;k++)q[k]=(j&(1<<(k-1)))>0;
    q[0]=q[n];
    for(int k=1;k<=n;k++)if(q[k])ans+=you[k][i];
    return ans;
}
int cal3(int i,int j){
    int ans=0;
    for(int k=1;k<=n;k++)q[k]=(j&(1<<(k-1)))>0;
    q[0]=q[n];
    for(int k=1;k<=n;k++)ans+=(p[k][i]^q[k])*b[k][i];
    return ans;
}
long long cal(int x){
    memset(f,0x7f,sizeof(f));
    long long ans=f[0][0];
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)p[i][j]=(a[i][j]&(1<<x))>0;
    for(int i=1;i<=m;i++)for(int j=0;j<(1<<n);j++)A[i][j]=cal1(i,j);//竖着的 
    for(int i=1;i<m;i++)for(int j=0;j<(1<<n);j++)B[i][j]=cal2(i,j);//横着的 
    for(int i=1;i<=m;i++)for(int j=0;j<(1<<n);j++)C[i][j]=cal3(i,j);//本身的 
    for(int i=0;i<(1<<n);i++)f[1][i]=C[1][i]+A[1][i];
    for(int i=1;i<=m;i++){
        for(int j=0;j<(1<<n);j++){
            for(int k=0;k<(1<<n);k++){
                int l=j^k;
                f[i+1][l]=min(f[i][j]+B[i][k]+A[i+1][l]+C[i+1][l],f[i+1][l]);
            }
        }
    }
    for(int i=0;i<(1<<n);i++)ans=min(ans,f[m][i]);
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)scanf("%d",&you[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)scanf("%d",&xia[i][j]);
    long long ans=0;
    for(int i=0;i<=20;i++)ans+=cal(i)<<i;
    printf("%lld\n",ans);
}

BZOJ4675 点对游戏

2018-10-09

题目:

img

题解:

    考虑每个幸运点对都是相对独立的,就可以通过计算每个点对的概率来得到答案。

    统计幸运点对个数并乘上概率就是答案了。

官方题解:

题目来源:原创

考察要点:树的基于点/边的分治、概率与期望

涉及要点:动态规划、广度优先搜索

解题报告:

    对于某位玩家,其占据每个点的概率是相同的(因为点与点之间没有区别)。同样,其占据某对点对的概率也是固定的。不妨设这位玩家最终占据了n个点中的x个点,因为三人轮流选取的顺序固定,所以x可以简单求得。则该玩家占据某对点对的概率可以这么计算:

    该玩家从n个点中选取x个点的方案数为C(n,x)。

    在这些方案中,选取了某对点对的方案数为C(n-2,x-2)。

    与前面分析类似,易得每个方案的概率是相等的,故该玩家占据某对点对的概率为C(n2,x2)C(n,x)=x(x1)n(n1)\frac{C(n-2,x-2)}{C(n,x)}= \frac{x(x-1)}{n(n-1)}

    故问题转换为求距离为某个幸运数的点对对数,将其乘以x(x1)n(n1)\frac{x(x-1)}{n(n-1)}即为答案。

    对于数据点1,n <= 1000,bfs即可。

    对于数据点2、3、4,第i个幸运数为i,因为幸运数<=10,故可以使用树形动态规划求解。F[x][1…10]表示子树x中与节点x距离为1…10的点数,转移略。

    如果在bfs中加入剪枝优化(距离超过最大的幸运数后就不再搜索),亦可通过这三个数据点。

    对于数据点5、6、7,n为3的倍数,三人答案相同,方便选手计算。

    对于所有数据点,3 <= n <= 50000,m <= 10,幸运数大小 <= n,使用树的基于点/边的分治求解。其中树的基于边的分治需要重建树以防止星形图(数据点7和数据点10)时复杂度退化。另外在不开编译优化的情况下,使用vector等STL存图的程序也容易在这两个数据点超时。

出题思路:

    本题要求选手对期望与概率的独立性有最基本的认识,分析出藏在轮流选取背后的是每个点对相同的概率。之后本题的题目模型考察选手的硬编程实力,在所有树分治题目中,本题属于最简单的一类,熟练掌握的选手应可以在半小时至一小时内(关于这个表示赞同)解决。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 120000
using namespace std;
int tot,Next[N],v[N],h[N];
int l[N],q[N],siz[N],dep[N];
int p[N],son[N],O,ill,cnt;
int m,luck[20],n;
long long ans;
int add(int x,int y){
    tot++;
    Next[tot]=h[x];
    v[tot]=y;
    h[x]=tot;
}
int get_siz(int x,int fa){
    siz[x]=1;
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1)continue;
        if(v[i]==fa)continue;
        get_siz(v[i],x);
        siz[x]+=siz[v[i]];
    }
}
int get_son(int x,int fa,int OO){
    son[x]=OO-siz[x];
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1)continue;
        if(v[i]==fa)continue;
        get_son(v[i],x,OO);
        son[x]=max(son[x],siz[v[i]]);
    }
    if(son[x]<son[O])O=x;
}
int get_son(int x){
    son[O]=10000000;
    O=0;
    get_siz(x,0);
    get_son(x,0,siz[x]);
    return O;
}
int lfs(int x,int fa){
    dep[x]=dep[fa]+1;
    if(dep[x]>ill)l[++ill]=0;
    if(dep[x]>cnt)q[++cnt]=0;
    l[dep[x]]++;
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1)continue;
        if(v[i]==fa)continue;
        lfs(v[i],x);
    }
}
int solve(int x){
    p[x]=1;
    cnt=0,ill=0;
    dep[x]=0;
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1)continue;
        ill=0;
        lfs(v[i],x);
        for(int j=1;j<=m;j++)if(luck[j]<=ill)ans+=l[luck[j]];
        for(int j=1;j<=ill;j++)
            for(int k=1;k<=m;k++)
                if(luck[k]>j&&luck[k]-j<=cnt)ans+=1LL*q[luck[k]-j]*l[j];
        for(int j=1;j<=ill;j++)q[j]+=l[j];
    }
     
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1)continue;
        int o=get_son(v[i]);
        solve(o);
    }
}
int cal(long double x){
    long double k=ans;
    printf("%.2Lf\n",k*(x/n)*((x-1)/(n-1)));
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d",&luck[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    solve(1);
    cal(n/3+(n%3>=1));
    cal(n/3+(n%3>=2));
    cal(n/3+(n%3>=3));
}

BZOJ4695 最假女选手

题目:

img

img

题解:

    吉利线段树板子题,利用父亲信息每次更新子节点,然后利用势能分析能证明其时间复杂度是O(nlog22n)O(nlog_2^2n)的(全靠脑补的我就写出了7k的代码(我无法用更短的代码表示我对这题的喜爱x。

    明明不是第一次写吉利线段树但我怎么一点印象都没有qwq。

    复制一时爽,调试火葬场(因为连着把一个错误复制了好多次导致重构代码。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 520000
using namespace std;
int a[N],n,m;
namespace seg{
    int mx[N*4],mi[N*4],mii[N*4],mxx[N*4],tag[N*4];
    int siz_min[N*4],siz_max[N*4];
    long long sum[N*4];
    int q[10];
    int down(int i,int l,int r){
        mii[i]+=tag[i];
        mi[i]+=tag[i];
        mxx[i]+=tag[i];
        mx[i]+=tag[i];
        sum[i]+=1LL*tag[i]*(r-l+1);
        if(l==r)return tag[i]=0;
        tag[i*2]+=tag[i];
        tag[i*2+1]+=tag[i];
        tag[i]=0;
    }
    int pushdown(int i,int l,int r){
        down(i,l,r);
        int mid=(l+r)/2;
        if(l!=r&&tag[i*2]!=0)down(i*2,l,mid);   
        if(l!=r&&tag[i*2+1]!=0)down(i*2+1,mid+1,r);
        if(l!=r){
            if(mi[i]==mx[i]){
                long long a=mi[i];
                siz_min[i]=siz_max[i]=r-l+1;
                siz_min[i*2]=siz_max[i*2]=mid-l+1;
                siz_min[i*2+1]=siz_max[i*2+1]=r-mid;
                mi[i*2]=a;
                mx[i*2]=a;
                mxx[i*2]=a;
                mii[i*2]=a;
                sum[i*2]=1LL*a*(mid-l+1);
                mi[i*2+1]=a;
                mx[i*2+1]=a;
                mxx[i*2+1]=a;
                mii[i*2+1]=a;
                sum[i*2+1]=1LL*a*(r-mid);
                return 0;
            }
            if(mi[i*2]==mx[i*2]){
                int mid=(l+r)/2;
                long long a=0;
                if(mi[i]>mi[i*2])a=mi[i];
                if(mx[i]<mx[i*2])a=mx[i];
                if(mi[i]<=mi[i*2]&&mx[i]>=mx[i*2])a=mi[i*2];
                mi[i*2]=a;
                mx[i*2]=a;
                mxx[i*2]=a;
                mii[i*2]=a;
                sum[i*2]=1LL*a*(mid-l+1);
                siz_min[i*2]=siz_max[i*2]=mid-l+1;
            }else{
                if(mi[i]>mi[i*2])sum[i*2]+=1LL*(mi[i]-mi[i*2])*siz_min[i*2];
                if(mx[i]<mx[i*2])sum[i*2]+=1LL*(mx[i]-mx[i*2])*siz_max[i*2];
                mx[i*2]=min(mx[i],mx[i*2]);
                mi[i*2]=max(mi[i],mi[i*2]);
                mxx[i*2]=max(mxx[i*2],mi[i*2]);
                mii[i*2]=min(mii[i*2],mx[i*2]);
            }
            if(mi[i*2+1]==mx[i*2+1]){
                int mid=(l+r)/2;
                int a=0;
                if(mi[i]>mi[i*2+1])a=mi[i];
                if(mx[i]<mx[i*2+1])a=mx[i];
                if(mi[i]<=mi[i*2+1]&&mx[i]>=mx[i*2+1])a=mx[i*2+1];
                mi[i*2+1]=a;
                mx[i*2+1]=a;
                mxx[i*2+1]=a;
                mii[i*2+1]=a;
                sum[i*2+1]=1LL*a*(r-mid);
                siz_min[i*2+1]=siz_max[i*2+1]=r-mid;
            }else{
                if(mi[i]>mi[i*2+1])sum[i*2+1]+=1LL*(mi[i]-mi[i*2+1])*siz_min[i*2+1]; 
                if(mx[i]<mx[i*2+1])sum[i*2+1]+=1LL*(mx[i]-mx[i*2+1])*siz_max[i*2+1]; 
                mx[i*2+1]=min(mx[i],mx[i*2+1]);
                mi[i*2+1]=max(mi[i],mi[i*2+1]);
                mxx[i*2+1]=max(mxx[i*2+1],mi[i*2+1]);
                mii[i*2+1]=min(mii[i*2+1],mx[i*2+1]);
            }
         }
    }
    int update(int i,int l,int r){
        int mid=(l+r)/2;
    //  pushdown(i,l,r);
        pushdown(i*2,l,mid);
        pushdown(i*2+1,mid+1,r);
        sum[i]=sum[i*2]+sum[i*2+1];
        q[1]=mi[i*2];
        q[2]=mi[i*2+1];
        q[3]=mx[i*2];
        q[4]=mx[i*2+1];
        q[5]=mii[i*2];
        q[6]=mii[i*2+1];
        q[7]=mxx[i*2];
        q[8]=mxx[i*2+1];
        sort(q+1,q+1+8);
        mi[i]=q[1];
        for(int j=2;j<=8;j++)if(q[j]!=q[1]){mii[i]=q[j];break;}
        if(q[8]==q[1])mii[i]=mi[i];
        mx[i]=q[8];
        for(int j=7;j>=1;j--)if(q[j]!=q[8]){mxx[i]=q[j];break;}
        if(q[8]==q[1])mxx[i]=mx[i];
        siz_min[i]=0;
        siz_max[i]=0;
        if(mi[i*2]==mi[i])siz_min[i]+=siz_min[i*2];
        if(mi[i*2+1]==mi[i])siz_min[i]+=siz_min[i*2+1];
        if(mx[i*2]==mx[i])siz_max[i]+=siz_max[i*2];
        if(mx[i*2+1]==mx[i])siz_max[i]+=siz_max[i*2+1];
        sum[i]=sum[i*2]+sum[i*2+1];
    }
    int build(int i,int l,int r){
        if(l==r){
            mx[i]=a[l];
            mxx[i]=a[l];
            mi[i]=a[l];
            mii[i]=a[l];
            sum[i]=a[l];
            siz_max[i]=1;
            siz_min[i]=1;
            return 0;
        }
        int mid=(l+r)/2;
        build(i*2,l,mid);
        build(i*2+1,mid+1,r);
        update(i,l,r);
    }
    int insert(int i,int l,int r,int x,int y,int a){
        pushdown(i,l,r);
        if(x<=l&&y>=r){
            tag[i]+=a;
            pushdown(i,l,r);
            return 0;
        }
        int mid=(l+r)/2;
        if(x<=mid)insert(i*2,l,mid,x,y,a);
        if(y>mid)insert(i*2+1,mid+1,r,x,y,a);
        update(i,l,r);
    }
    int insert_min(int i,int l,int r,int x,int y,int a){
        pushdown(i,l,r);
        if(x<=l&&y>=r){
            if(a>=mx[i])return 0;
            if(a<mi[i]){
                mx[i]=mi[i]=mxx[i]=mii[i]=a;
                sum[i]=1LL*a*(r-l+1);
                siz_max[i]=siz_min[i]=(r-l+1);
                return 0;
            }
            if(a>mxx[i]&&a<mx[i]){
                sum[i]-=1LL*mx[i]*siz_max[i];
                sum[i]+=1LL*a*siz_max[i];
                mx[i]=a;
                mii[i]=min(mii[i],a);
                mxx[i]=min(mxx[i],a);
                mx[i]=min(mx[i],a);
                return 0;
            }
            if(l==r)return 0;
            int mid=(l+r)/2;
            if(x<=mid)insert_min(i*2,l,mid,x,y,a);
            if(y>mid)insert_min(i*2+1,mid+1,r,x,y,a);
            update(i,l,r);
        }
        int mid=(l+r)/2;
        if(x<=mid)insert_min(i*2,l,mid,x,y,a);
        if(y>mid)insert_min(i*2+1,mid+1,r,x,y,a);
        update(i,l,r);
    }
    int insert_max(int i,int l,int r,int x,int y,int a){
        pushdown(i,l,r);
        if(x<=l&&y>=r){
            if(a<=mi[i])return 0;
            if(a>mx[i]){
                mx[i]=mi[i]=mxx[i]=mii[i]=a;
                sum[i]=1LL*a*(r-l+1);
                siz_max[i]=siz_min[i]=(r-l+1);
                return 0;
            }
            if(a<mii[i]&&a>mi[i]){
                sum[i]-=1LL*mi[i]*siz_min[i];
                sum[i]+=1LL*a*siz_min[i];
                mi[i]=a;
                mii[i]=max(mii[i],a);
                mxx[i]=max(mxx[i],a);
                mx[i]=max(mx[i],a);
                return 0;
            }
            if(l==r)return 0;
            int mid=(l+r)/2;
            if(x<=mid)insert_max(i*2,l,mid,x,y,a);
            if(y>mid)insert_max(i*2+1,mid+1,r,x,y,a);
            update(i,l,r);
        }
        int mid=(l+r)/2;
        if(x<=mid)insert_max(i*2,l,mid,x,y,a);
        if(y>mid)insert_max(i*2+1,mid+1,r,x,y,a);
        update(i,l,r);
    }
    long long query(int i,int l,int r,int x,int y){
        pushdown(i,l,r);
        if(x<=l&&y>=r)return sum[i];
        long long ans=0;
        int mid=(l+r)/2;
        if(x<=mid)ans+=query(i*2,l,mid,x,y);
        if(y>mid)ans+=query(i*2+1,mid+1,r,x,y);
//      printf("%d %d %d\n",max(l,x),min(y,r),ans);
        return ans;
    }
    int query_min(int i,int l,int r,int x,int y){
        pushdown(i,l,r);
        if(x<=l&&y>=r)return mi[i];
        int ans=0x7fffffff;
        int mid=(l+r)/2;
        if(x<=mid)ans=min(ans,query_min(i*2,l,mid,x,y));
        if(y>mid)ans=min(ans,query_min(i*2+1,mid+1,r,x,y));
        return ans;
    }
    int query_max(int i,int l,int r,int x,int y){
        pushdown(i,l,r);
        if(x<=l&&y>=r)return mx[i];
        int ans=-0x7fffffff;
        int mid=(l+r)/2;
        if(x<=mid)ans=max(ans,query_max(i*2,l,mid,x,y));
        if(y>mid)ans=max(ans,query_max(i*2+1,mid+1,r,x,y));
        return ans;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    seg::build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int type;
        scanf("%d",&type);
        if(type==1){
            int x,y,a;
            scanf("%d%d%d",&x,&y,&a);
            seg::insert(1,1,n,x,y,a);
        }
        if(type==2){
            int x,y,a;
            scanf("%d%d%d",&x,&y,&a);
            seg::insert_max(1,1,n,x,y,a);
        }
        if(type==3){
            int x,y,a;
            scanf("%d%d%d",&x,&y,&a);
            seg::insert_min(1,1,n,x,y,a);
        }
        if(type==4){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",seg::query(1,1,n,x,y));
        }
        if(type==5){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",seg::query_max(1,1,n,x,y));
        } 
        if(type==6){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%d\n",seg::query_min(1,1,n,x,y));
        }
    }
}

「雅礼集训 2017 Day2」线段游戏

2018-10-07

题意:

    给出若干条线段,用 (x1,y2)(x_1,y_2) , (x2,y2)(x_2,y_2)表示其两端点坐标,现在要求支持两种操作:

    0,x1,y1,x2,y20,x_1,y_1,x_2,y_2 表示加入一条新的线段 (x1,y2)(x_1,y_2) , (x2,y2)(x_2,y_2)

    11 , x0x_0 询问所有线段中,xx坐标在 x0x_0 处的最高点的yy坐标是什么,如果对应位置没有线段,则输出 00

题解:

    线段树维护区间中位数值最大,可易证最终答案一定是线段树上某个区间的最大值。(注意数据中有竖线

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 1200000
#define O 320000
#define inf 10000000000
#define get(x,k,b) (x*k+b) 
using namespace std;
int n,m;
namespace seg{
	long double tk[N],tb[N],ans;
	int build(int i,int l,int r){
		tb[i]=-inf;
		if(l==r)return 0;
		int mid=(l+r)/2;
		build(i*2,l,mid);
		build(i*2+1,mid+1,r);
	}
	int insert(int i,int l,int r,long double k,long double b,int x,int y){
		if(x<=l&&y>=r){
			int mid=(l+r)/2;
			if(get(l,tk[i],tb[i])<get(l,k,b)&&get(r,tk[i],tb[i])<get(r,k,b)){
				tk[i]=k;
				tb[i]=b;
				return 0;
			}
			if(get(l,tk[i],tb[i])>get(l,k,b)&&get(r,tk[i],tb[i])>get(r,k,b))return 0;
			long double ll=get(mid,k,b);
			long double rr=get(mid,tk[i],tb[i]);
			if(ll>rr){
				if(l==r)return 0;
				if(k>tk[i])insert(i*2,l,mid,tk[i],tb[i],x,y);
				else insert(i*2+1,mid+1,r,tk[i],tb[i],x,y);
				tk[i]=k;
				tb[i]=b;
				return 0;
			}else{
				if(l==r)return 0;
				if(k>tk[i])insert(i*2+1,mid+1,r,k,b,x,y);
				else insert(i*2,l,mid,k,b,x,y);
				return 0;
			}
			return 0;
		}
		int mid=(l+r)/2;
		if(x<=mid)insert(i*2,l,mid,k,b,x,y);
		if(y>mid)insert(i*2+1,mid+1,r,k,b,x,y);
	}
	int query(int i,int l,int r,int x){
		if(i==1)ans=-inf;
		ans=max(ans,get(x,tk[i],tb[i]));
		if(l==r)return 0;
		int mid=(l+r)/2;
		if(x<=mid)query(i*2,l,mid,x);
		else query(i*2+1,mid+1,r,x);
	}
}
int insert(){
	int xa,ya,xb,yb;
	scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
	xa++;
	xb++;
	if(xa>xb){
		swap(xa,xb);
		swap(ya,yb);
	}
	long double k=(long double)(yb-ya+0.0)/(xb-xa);
	long double b=ya-k*xa;
	if(xa==xb)k=0,b=max(ya,yb);
	xa=max(1,xa);
	xa=min(xa,O);
	xb=max(1,xb);
	xb=min(xb,O);
	seg::insert(1,1,O,k,b,xa,xb);
}
int main(){
	scanf("%d%d",&n,&m);
	seg::build(1,1,O);
	for(int i=1;i<=n;i++)insert();
	for(int i=1;i<=m;i++){
		int type;
		scanf("%d",&type);
		if(type==0)insert();
		if(type==1){
			int x;
			scanf("%d",&x);
			x++;
			seg::query(1,1,O,x);
			if(seg::ans<=-inf+1){
				printf("0.0000000\n");
				continue;
			}
			printf("%5Lf\n",seg::ans);
		}
	}
} 

K相等

2018-10-07

题目:img

题解:

    大分类讨论加上大人类智慧(大概就是用人类智慧锁定哪k位不变,再用人类智慧来找后继,最后再上下波动搜索一下就能解决。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
long long n,k,bns;
long long cal(long long x){
    long long ans=0;
    while(x){
        long long o=x%10;
        if(o==4||o==7)ans++;
        x/=10;
    }
    return ans;
}
long long check(long long x,long long y){
    for(long long i=1;i<=k;i++){
        if(cal(x)!=cal(y))return 0;
        x++;
        y++;
    } 
    return 1;
}
long long Next(long long x,int p){
    long long y=x+1;
    long long o=cal(y)-cal(x)+p;
    if(x==0&&p!=0)return 10000;
    if(o==0)return y;
    if(o>0){
        long long z=y,k=1;
        while(z){
            long long p=z%10;
            if(p!=0)
                return y+k;
            k*=10;
            z/=10;
        }
    }
    if(o<0){
        int flag=0;
        if(x%10<4&&p<=-1)return x-x%10+4;
        if(x%10<7&&p<=-1)return x-x%10+7;
        if(x%10==4)return x-x%10+7;
        if(x%10==7)flag=1;
        long long Ans=Next(x/10,p-flag+1)*10+4;
        long long Bns=Next(x/10,p-flag)*10;
        if(cal(Bns)!=cal(x))return Ans;
        return min(Ans,Bns);
        return Ans;
    }
}
long long a[20];
int solve(){
    scanf("%lld%lld",&n,&k);
    long long m=n+k-1,l=1,L=0,c=n,flag=0,cns,o=0,O=0,f=k;
    bns=0;
    while(m>0){
        long long x=n%10,y=m%10;
        if(y!=0)flag=1;
        if(x!=y){
            L=l; 
            O=o;
        }
        bns=bns+l*x;
        o++;
        a[o]=x;
        n/=10;
        m/=10;
        l*=10;
        if(l>k)break;
    }
    L=max(1LL,L);
    n=c/L;
    k=(c+f-1)/L-(c)/L+1;
    if(f<=10&&f>=3&&(c%10==4||c%10==7)){
        k=1;
        for(int i=c-c%10+10;i<=c+f;i++)if(cal(i/10)!=cal(c/10))k=2;
        n=c/10;
        O++;
    }
    long long A=0,tot=0;
    for(long long i=Next(n,0);i;i=Next(i,0)){
        tot++;
        if(check(i,n)){
            A=i;
            for(long long i=O;i>=1;i--)A=A*10+a[i];
            k=f;
            for(int i=max(c+1,A-40);i<=A;i++)if(k<=100&&check(i,c)){
                printf("%lld\n",i);
                return 0;
            }
            printf("%lld\n",A);
            return 0;
        }
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--)solve();
}

Illyasviel的图游戏

2018-10-05

题意:

    Alice和Bob在玩游戏。

    他们有一张n个点m条边的带正权的简单无向图,其中除了1号点和n号点每个点度数小于等于2。

    Alice和Bob轮流操作,Alice先手,每次操作的人可以选择一条仍然存在的边,并且使得边权减一。如果有一条边边权减为了零,它会立即消失。

    在这张图上有一只Illyasviel想要从1号点走到n号点,如果在某个时刻Illyasviel不能从1号点走到n号点,他会十分生气并且判定上一个操作的玩家输。

    假设Alice和Bob都采取最优策略,请输出Alice是否可以获胜,是输出“Yes”, 否则输出“No”

题解:

    题目中对于图的限制可以看做 1 到 n 的所有简单路径互不相交。在结束游戏前的最后一步一定是剩下一条 1 到 n 的路径,并且路径上的权值全都是一。如果剩下的最后一条路径确定了,游戏的总步数也确定了,那么先后手的胜负也确定了。那么双方的策略就使尽可能使最后留下的路径是使自己必胜的路径,即尽可能切断使对方必胜的路径。切断一条路径需要的步数是这条路径上的权值的最小值。我们只需要比较双方切断对方必胜的路径所需要的步数即可。(此处是官方题解)

#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 720000
using namespace std;
int tot,Next[N],v[N],h[N],w[N];
int n,p[N],m,bns;
long long L,R;
long long ans;
int add(int x,int y,int z){
    tot++;
    Next[tot]=h[x];
    v[tot]=y;
    w[tot]=z;
    h[x]=tot;
    return 0;
}
int dfs(int x,int a,int len){//L 奇 R 偶
    if(x==n){
        if(len&1)L+=a;
        else R+=a;
        return 1;
    }
    p[x]=1;
    int flag=0;
    for(int i=h[x];i;i=Next[i]){
        if(p[v[i]]==1&&v[i]!=n)continue;
        dfs(v[i],min(a,w[i]),len+1);
    }
    return flag;
}
int main(){
    tot=1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
        ans+=z;
    }
    dfs(1,0x7fffffff,0);
    if((((ans-1)&1)&&(L>=R))||(((ans)&1)&&(R>=L)))printf("Yes\n");
    else printf("No\n");
}

题目链接:Illyasviel的图游戏