lyzlyz?lyzlyz!

有幸膜到了贵省的题目，感到不明觉厉，于是水了一发题解来骗访客量。

T1

求图的不同最小割数，仿佛就是ZJOI2011搬的原题。（然而我并没有做过）

最小割树定理告诉窝萌：n个点的图的不同最小割数最多有n-1个。（我也不会证明）

所以可以分治，对于集合S中的点，随机选出两个点跑最小割将集合划分成X和Y，然后对X和Y递归求解即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
const int inf=1000000007;
int n,m,i,x,y,z,edgenum,S,T,cnt,ans;
int head[M],vet[M],next[M],size[M],A[M],a[M],b[M],dis[M],h[M],flag[M];
void addedge(int x,int y,int z){
    vet[++edgenum]=y;
    next[edgenum]=head[x];
    head[x]=edgenum;
    size[edgenum]=z;
    vet[++edgenum]=x;
    next[edgenum]=head[y];
    head[y]=edgenum;
    size[edgenum]=z;
}
int bfs(){
    for (int i=1;i<=n;i++)dis[i]=-1;
    int l=1,r=1;
    dis[S]=0;h[l]=S;
    while (l<=r){
        int u=h[l];
        for (int e=head[u];e;e=next[e]){
            int v=vet[e];
            if (size[e]&&dis[v]<0){
                dis[v]=dis[u]+1;
                h[++r]=v;
            }
        }
        l++;
    }
    if (dis[T]<0)return 0;else return 1;
}
int dfs(int u,int aug){
    if (u==T)return aug;
    int flow=0;
    for (int e=head[u];e;e=next[e]){
        int v=vet[e];
        if (size[e]&&dis[v]==dis[u]+1){
            int tmp=dfs(v,min(aug-flow,size[e]));
            flow+=tmp;
            size[e]-=tmp;
            size[e^1]+=tmp;
            if (flow==aug)return flow;
        }
    }
    if (!flow)dis[u]=-1;
    return flow;
}
void Dfs(int u){
    flag[u]=1;
    for (int e=head[u];e;e=next[e]){
        int v=vet[e];
        if (size[e]&&!flag[v])Dfs(v);
    }
}
void rebuild(){
    for (int i=2;i<=edgenum;i+=2)size[i]=size[i^1]=size[i]+size[i^1]>>1;
}
void solve(int l,int r){
    if (l==r)return;
//  printf("%d %d\n",l,r);
    rebuild();S=a[l];T=a[r];
    int tmp=0;
    while (bfs())tmp+=dfs(S,inf);
    for (int i=1;i<=n;i++)flag[i]=0;
    Dfs(S);
    A[++cnt]=tmp;
    int L=l,R=r;
    for (int i=l;i<=r;i++)
        if (flag[a[i]])b[L++]=a[i];
            else b[R--]=a[i];
    for (int i=l;i<=r;i++)a[i]=b[i];
    solve(l,L-1);solve(R+1,r);
}
int main(){
    edgenum=1;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)a[i]=i;
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);
    }
    solve(1,n);
    sort(A+1,A+cnt+1);
    ans=unique(A+1,A+cnt+1)-A-1;
    printf("%d\n",ans);
}

T2

求平面上欧氏距离第k小的点对。

先用k-d tree求出每个点的最近点，然后每次取出距离最近的点对(x,y)，暴力求满足dis(x,z)>dis(x,y)且dis(x,z)最小的z，做k次即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<ll,int> PII;
const int M=100010;
int n,k,i,j,root,b[M];
ll ans,dist[M];
struct node{ll x,y,minx,maxx,miny,maxy;int l,r;}a[M];
bool cmp1(node x,node y){return x.x<y.x;}
bool cmp2(node x,node y){return x.y<y.y;}
priority_queue<PII>q;
void pushup(int x,int y){
    a[x].minx=min(a[x].minx,a[y].minx);
    a[x].maxx=max(a[x].maxx,a[y].maxx);
    a[x].miny=min(a[x].miny,a[y].miny);
    a[x].maxy=max(a[x].maxy,a[y].maxy);
}
void update(int x){
    int l=a[x].l,r=a[x].r;
    if (l)pushup(x,l);
    if (r)pushup(x,r);
}
void build(int l,int r,int flag,int &p){
    if (l>r){p=0;return;}
    int mid=l+r>>1;p=mid;
    if (flag)nth_element(a+l,a+mid+1,a+r+1,cmp1);
        else nth_element(a+l,a+mid+1,a+r+1,cmp2);
    a[p].minx=a[p].maxx=a[p].x;
    a[p].miny=a[p].maxy=a[p].y;
    build(l,mid-1,flag^1,a[p].l);
    build(mid+1,r,flag^1,a[p].r);
    update(p);
}
ll dis(ll x,ll y,ll z,ll w){
    return (x-y)*(x-y)+(z-w)*(z-w);
}
ll solve(int x,int y){
    if (!x)return 0;
    return max(max(dis(a[x].minx,a[y].x,a[x].miny,a[y].y),dis(a[x].minx,a[y].x,a[x].maxy,a[y].y)),max(dis(a[x].maxx,a[y].x,a[x].miny,a[y].y),dis(a[x].maxx,a[y].x,a[x].maxy,a[y].y)));
}
void query(int x,int p){
    if (!p)return;
    ans=max(ans,dis(a[x].x,a[p].x,a[x].y,a[p].y));
    ll d1=solve(a[p].l,x),d2=solve(a[p].r,x);
    if (d1>d2){
        if (d1>ans)query(x,a[p].l);
        if (d2>ans)query(x,a[p].r);
    }else{
        if (d2>ans)query(x,a[p].r);
        if (d1>ans)query(x,a[p].l);
    }
}
int main(){
    scanf("%d%d",&n,&k);
    k*=2;
    for (i=1;i<=n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);
    build(1,n,1,root);
    for (i=1;i<=n;i++){
        ans=0;
        query(i,root);
        q.push(MP(ans,i));
    }
    for (i=1;i<=n;i++)b[i]=n;
    for (i=1;i<k;i++){
        int x=q.top().second;q.pop();
        b[x]--;
        for (j=1;j<=n;j++)dist[j]=dis(a[x].x,a[j].x,a[x].y,a[j].y);
        nth_element(dist+1,dist+b[x],dist+n+1);
        q.push(MP(dist[b[x]],x));
    }
    printf("%lld\n",q.top().first);
}

T3

SB数位dp，送分题。

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
int a[110];
ll x,y,dp[15][10][10][2][2][2][2];
ll solve(ll x){
    int n=0,i,j,k,l,I,J,K,p,q,r;
    while (x){
        a[++n]=x%10;
        x/=10;
    }
    if (n!=11)return 0;
    for (i=1;i<=n/2;i++)swap(a[i],a[n-i+1]);
    memset(dp,0,sizeof dp);
    for (i=1;i<a[1];i++)
        for (j=0;j<=9;j++){
            if (i==4||j==4)p=1;else p=0;
            if (i==8||j==8)q=1;else q=0;
            dp[2][i][j][p][q][0][0]=1;
        }
    for (j=0;j<a[2];j++){
        if (a[1]==4||j==4)p=1;else p=0;
        if (a[1]==8||j==8)q=1;else q=0;
        dp[2][a[1]][j][p][q][0][0]=1;
    }
    if (a[1]==4||a[2]==4)p=1;else p=0;
    if (a[1]==8||a[2]==8)q=1;else q=0;
    dp[2][a[1]][a[2]][p][q][0][1]=1;
    for (i=2;i<n;i++)
        for (j=0;j<=9;j++)
            for (k=0;k<=9;k++)
                for (I=0;I<=1;I++)
                    for (J=0;J<=1;J++)
                        for (K=0;K<=1;K++)
                            for (l=0;l<=9;l++){
                                if (l==4)p=1;else p=I;
                                if (l==8)q=1;else q=J;
                                if (l==j&&l==k)r=1;else r=K;
                                dp[i+1][k][l][p][q][r][0]+=dp[i][j][k][I][J][K][0];
                                if (l<a[i+1])dp[i+1][k][l][p][q][r][0]+=dp[i][j][k][I][J][K][1];
                                    else if (l==a[i+1])dp[i+1][k][l][p][q][r][1]+=dp[i][j][k][I][J][K][1];
                            }
    ll ans=0;
    for (i=0;i<=9;i++)
        for (j=0;j<=9;j++)
            for (k=0;k<=1;k++)
                ans+=dp[n][i][j][0][0][1][k]+dp[n][i][j][1][0][1][k]+dp[n][i][j][0][1][1][k];
    return ans;
}
int main(){
    scanf("%lld%lld",&x,&y);
    printf("%lld\n",solve(y)-solve(x-1));
}

T4

数论大杂烩，大概要实现：大数求因子、求逆元、快速幂。

用pollard-rho、exgcd随便乱搞一通就行了。

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
int i,j,cnt,A;
ll c,d,e,n,p,q,r,shit;
int ss[10000010],prime[2000010];
ll quickcheng(ll x,ll y,ll mod){
    ll ans=0;
    while (y){
        if (y&1)ans=(ans+x)%mod;
        x=(x+x)%mod;
        y>>=1;
    }
    return ans;
}
ll quickmi(ll x,ll y,ll mod){
    ll ans=1;
    while (y){
        if (y&1)ans=quickcheng(ans,x,mod);
        x=quickcheng(x,x,mod);
        y>>=1;
    }
    return ans;
}
ll gcd(ll x,ll y){
    if (!y)return x;else return gcd(y,x%y);
}
ll Abs(ll x){if (x<0)return -x;else return x;}
ll f(ll x){return (quickcheng(x,x,n)+A)%n;}
void pollard_rho(ll n){
    A=rand()%1000+1;
    ll a=2,b=2;
    while (1){
        a=f(a);
        b=f(f(b));
        ll tmp=gcd(Abs(b-a),n);
        if (tmp>1){p=tmp;q=n/tmp;return;}
        if (a==b)break;
    }
    pollard_rho(n);
}
void exgcd(ll a,ll b,ll &c,ll &d){
    if (!b){
        c=1;d=0;return;
    }
    exgcd(b,a%b,d,c);
    d=d-a/b*c;
}
int main(){
    for (i=2;i<=10000000;i++){
        if (!ss[i])prime[++cnt]=i;
        for (j=1;j<=cnt&&i*prime[j]<=10000000;j++){
            ss[i*prime[j]]=1;
            if (!(i%prime[j]))break;
        }
    }
    scanf("%lld%lld%lld",&e,&n,&c);
    pollard_rho(n);
    r=(p-1)*(q-1);
    exgcd(e,r,d,shit);
    d=(d+r)%r;
    printf("%lld %lld\n",d,quickmi(c,d,n));
}

T5

用trie树维护时间，然后每个询问用一个单调栈来维护即可。（然而我一开始强行套了个set被卡常了）

#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
char S[10];
int n,i,pointnum,cnt,d,l,r,top,stack[110],trie[20000010][2],mn[20000010];
ll x,y,z,w;
int main(){
    scanf("%d",&n);
    while (n--){
        scanf("%s",S);
        if (S[0]=='A'){
            scanf("%lld.%lld.%lld.%lld/%d",&x,&y,&z,&w,&d);
            x=(x<<24)+(y<<16)+(z<<8)+w;
            int u=0;
            for (i=31;i>=32-d;i--){
                int p=x&(1ll<<i);
                if (p)p=1;
                if (!trie[u][p])trie[u][p]=++pointnum;
                u=trie[u][p];
            }
            if (!mn[u])mn[u]=++cnt;
        }else{
            scanf("%lld.%lld.%lld.%lld %d %d",&x,&y,&z,&w,&l,&r);
            x=(x<<24)+(y<<16)+(z<<8)+w;
            int tmp=32,u=0;
            for (i=31;i>=0;i--){
                int p=x&(1ll<<i);
                if (p)p=1;
                if (!trie[u][p])break;
                    else{
                        u=trie[u][p];
                        if (mn[u]&&mn[u]<l)tmp=i;
                    }
            }
            u=0;
//          printf("tmp=%d\n",tmp);
            for (i=31;i>=tmp;i--){
                int p=x&(1ll<<i);
                if (p)p=1;
                if (!trie[u][p])break;else u=trie[u][p];
            }
            top=0;
            for (i=tmp-1;i>=0;i--){
                int p=x&(1ll<<i);
                if (p)p=1;
                if (!trie[u][p])break;
                    else{
                        u=trie[u][p];
                        if (mn[u]&&mn[u]<=r){
                            while (top&&mn[u]<stack[top])top--;
                            stack[++top]=mn[u];
                        }
                    }
            }
            printf("%d\n",top);
        }
    }
}

T6

仿佛要可并堆？我不会啊……

先挖个坑，待填。