1005.Little-W-and-Contest

算法标签：并查集、组合数

因为可行的组合只有2、2、1和2、2、2两种
那么每次合并时统计两个集合中1和2的个数，并计算出“因这次合并而减少的组合”数量即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5,MOD=1e9+7;

int T,n,m,p,x;

int FA[N],sz[N][2];

int getFa(int x)
{
    if (FA[x]==x) return x;
    else return FA[x]=getFa(FA[x]);
}
int cnt[2],u,v;
int inv[N];

int qpower(int x,int p)
{
    int ret=1;
    for (int base=x;p;p>>=1,base=(1ll*base*base)%MOD)
        if (p&1==1) ret=(1ll*ret*base)%MOD;
    return ret;
}
int Com(int n,int m)
{
    int ret=1;
    for (int i=1;i<=m;i++)
    {
        ret=(1ll*ret*(n-i+1))%MOD;
        ret=(1ll*ret*inv[i])%MOD;
    }
    return ret;
}
int main()
{
    for (int i=1;i<=N-1;i++) inv[i]=qpower(i,MOD-2);
    cin>>T;
    while(T--)
    {
        cin>>n;
        cnt[0]=cnt[1]=0;
        for (int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            FA[i]=i;
            sz[i][0]=sz[i][1]=0;
            sz[i][x-1]=1;
            cnt[x-1]++;
        }
        ll ans=(Com(cnt[1],3)+(1ll*Com(cnt[1],2)*cnt[0])%MOD)%MOD;
        printf("%lld\n",ans);
        for (int i=1;i<=n-1;i++)
        {
            scanf("%d%d",&u,&v);
            u=getFa(u),v=getFa(v);
            int l0=cnt[0]-sz[u][0]-sz[v][0];
            int l1=cnt[1]-sz[u][1]-sz[v][1];
            ans=(ans-(((1ll*sz[u][1]*sz[v][1])%MOD)*(cnt[1]+cnt[0]-sz[u][1]-sz[u][0]-sz[v][1]-sz[v][0]))%MOD+MOD)%MOD;
            ans=(ans-(((1ll*sz[u][1]*sz[v][0]+1ll*sz[u][0]*sz[v][1])%MOD)*(cnt[1]-sz[u][1]-sz[v][1]))%MOD+MOD)%MOD;
            printf("%lld\n",ans);
            FA[v]=u;
            sz[u][0]+=sz[v][0];
            sz[u][1]+=sz[v][1];
        }
    }
    return 0;
}

1007.Tokitsukaze-and-Rescue

标签：最短路、随机数据

这题需要对随机数据比较敏感，因为给出的是完全图，边值又是随机的，所以从1到n的最短路所经过的边数的期望值一定很小，而k又是<=5的，所以直接跑最短路+暴力删去最短路上的边就能过了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=50+5;

const int INF=0x3f3f3f3f;

struct Edge{
    int from,to,val,nxt;
}e[2500];

int head[N];

int n,m,s,edgeN,ans;

int dis[N],pre[N];

vector<int>path[8];

int T,u,v,w,k;

void addEdge(int u,int v,int w)
{
    edgeN++;
    e[edgeN].from=u;
    e[edgeN].to=v;
    e[edgeN].val=w;
    e[edgeN].nxt=head[u];
    head[u]=edgeN;
}

struct Node{
    int dis,key;
    friend bool operator <(const Node &x,const Node &y)
    {
        return x.dis>y.dis;
    }
};

void dijkstra(int x)
{
    priority_queue<Node>Q;
    bool vis[N]={0};
    for (int i=1;i<=n;i++) dis[i]=INF;
    dis[1]=0;
    pre[1]=-1;
    Q.push({0,1});
    while(!Q.empty())
    {
        Node top=Q.top();
        Q.pop();
        int now=top.key;
        if (vis[now]) continue;
        vis[now]=1;
        for (int i=head[now];~i;i=e[i].nxt)
        {
            int to=e[i].to;
            if (dis[to]>dis[now]+e[i].val)
            {
                pre[to]=i;
                dis[to]=dis[now]+e[i].val;
                if (!vis[to]) Q.push({dis[to],to});
            }
        }
    }
    if (x!=0)
    {
        int now=n;
        while(pre[now]!=-1)
        {
            path[x].push_back(pre[now]);
            now=e[pre[now]].from;
        }
    }
}

void dfs(int l)
{
    if (l==0)
    {
        dijkstra(l);
        ans=max(ans,dis[n]);
        return;
    }
    path[l].clear();
    dijkstra(l);
    for (auto x:path[l])
    {
        int sv=e[x].val;
        e[x].val=INF;
        e[x^1].val=INF;
        dfs(l-1);
        e[x].val=sv;
        e[x^1].val=sv;
    }
}
void init()
{
    ans=0;
    memset(head,-1,sizeof(head));
    edgeN=-1;
}
void solve()
{
    cin>>n>>k;
    init();
    for (int i=1;i<=n*(n-1)/2;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);addEdge(v,u,w);
    }
    dfs(k);
    printf("%d\n",ans);
}

int main()
{
    cin>>T;
    while(T--) solve();
    return 0;
}

1008.Triangle-Collision

标签：思维，点和向量旋转后的坐标变换

把小球在反射视作“穿入了镜子中的世界”是最关键的思考点。于是小球不再发生反射，而是产生了无数个边相邻的三角形。
接着考虑二分答案，计算出给定时间内小球穿过的边的个数。
实际上只要计算出小球穿过的平行于x轴的那条边的个数，然后把小球的位置和速度绕着三角形重心旋转两次，分别计算即可。
比较有价值的是点和向量旋转后的坐标变换公式。

假设对图片上任意点(x,y)，绕一个坐标点(rx0,ry0)逆时针旋转a角度后的新的坐标设为(x0, y0)，有公式：
x0=(x-rx0)*cos(a)-(y-ry0)*sin(a)+rx0;
y0=(x-rx0)*sin(a)+(y-ry0)*cos(a)+ry0;
向量(x,y)逆时针旋转a角度后新的向量为(x0,y0)，有公式:
x0=x*cos(a)-y*sin(a);
y0=x*sin(a)+y*cos(a);

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;
const double eps=1e-6,pi=4.0*atan(1.0);

int T,k;

double L,X,Y,VX,VY,x,y,vx,vy,H;

void Rotate(double &x,double &y,double &vx,double &vy,double x0,double y0,double a)
{
    double x_,vx_,y_,vy_;
    x_=(x-x0)*cos(a)-(y-y0)*sin(a)+x0;
    vx_=vx*cos(a)-vy*sin(a);
    y_=(x-x0)*sin(a)+(y-y0)*cos(a)+y0;
    vy_=vx*sin(a)+vy*cos(a);
    x=x_,y=y_,vx=vx_,vy=vy_;
}

double cal(double x,double y,double vx,double vy,double t)
{
    double len;
    if (vy<0) len=-t*vy-y;
    else len=t*vy-(H-y);
    if (len>=0) return floor(len/H)+1;
    else return 0;
}
ll check(double t)
{
    ll sum=0;
    double len;
    x=X,y=Y,vx=VX,vy=VY;
    sum+=cal(x,y,vx,vy,t);

    Rotate(x,y,vx,vy,0,H/3,2*pi/3);
    sum+=cal(x,y,vx,vy,t);

    x=X,y=Y,vx=VX,vy=VY;
    Rotate(x,y,vx,vy,0,H/3,4*pi/3);
    sum+=cal(x,y,vx,vy,t);
    return sum;
}

int main()
{
    //freopen("a.in","r",stdin);
    cin>>T;
    while(T--)
    {
        scanf("%lf%lf%lf%lf%lf%d",&L,&X,&Y,&VX,&VY,&k);
        H=sqrt(3)*L/2;
        x=X,y=Y,vx=VX,vy=VY;
        double l=0,r=1e9;
        check(2);
        while(r-l>eps)
        {
            double mid=(l+r)/2;
            if (check(mid)>=k) r=mid;
            else l=mid;
        }
        printf("%.8lf\n",(l+r)/2);
    }
    //fclose(stdin);
    return 0;
}

1006.X-Number

标签：数位dp、组合数

这题让我对数位dp有了一些新的理解。。如果某些状态能够通过数学方法快速计算，那么不一定要通过dp转移，而是直接计算出结果就可以了。

那么对于这道题，什么情况下可以直接计算呢？假设前k位的情况已经确定了，并且

第k+1位的取值范围没有限制（即数位dp中的limit为0）
最高位已经确定了（前k位不全为0）

那么就可以通过另一个dp+组合数的方法计算出合法的方案数了。具体看代码中的dp0。

对于除此之外的情况，因为不能直接计算，所以像正常的数位dp一样进行转移即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

map<array<int,10>,ll>dp[20][2];

array<int,10>status={0};

int T,d,digit[20];

ll l,r,cc[20][20],dp0[20];

ll C(int n,int m)
{
    ll res=1;
    if (m>n-m) m=n-m;
    if (~cc[n][m]) return cc[n][m];
    for (int i=1;i<=m;i++)
        res*=(n-m+i),res/=i;
    return cc[n][m]=res;
}

ll dfs(int pos,bool limit,bool f)
{
    if (!limit && dp[pos][f].find(status)!=dp[pos][f].end()) return dp[pos][f][status];
    if (pos==0)
    {
        for (int i=0;i<=9;i++)
        {
            if (i==d) continue;
            if (status[i]>=status[d]) return dp[pos][f][status]=0;
        }
        return dp[pos][f][status]=1;
    }
    int up=limit?digit[pos]:9;
    ll sum=0;
    if (!limit && f)
    {
        for (int i=0;i<=pos;i++)
        {
            for (int i0=0;i0<=pos-i;i0++) dp0[i0]=0;
            dp0[pos-i]=C(pos,i);
            for (int i0=0;i0<10;i0++)
            {
                if (i0==d) continue;
                if (status[i0]>=status[d]+i)
                {
                    dp0[0]=0;
                    break;
                }
                for (int i1=0;i1<=pos-i;i1++)
                    for (int i2=1;i2<=min(i1,status[d]+i-status[i0]-1);i2++)
                        dp0[i1-i2]+=C(i1,i2)*dp0[i1];
            }
            sum+=dp0[0];
        }
    }
    else
    {
        for (int i=0;i<=up;i++)
        {
            if (i||f)
            {
                status[i]++;
                sum+=dfs(pos-1,limit&&(i==up),1);
                status[i]--;
            }
            else sum+=dfs(pos-1,limit&&(i==up),0);
        }
    }
    return limit?sum:dp[pos][f][status]=sum;
}

ll div(ll tmp)
{
    int p=0;
    while(tmp) digit[++p]=tmp%10,tmp/=10;
    return dfs(p,1,0);
}

void solve()
{
    cin>>l>>r>>d;
    for (int i=0;i<20;i++) for (int j=0;j<2;j++) dp[i][j].clear();
    printf("%lld\n",div(r)-div(l-1));
}

int main()
{
    cin>>T;
    memset(cc,-1,sizeof(cc));
    while(T--) solve();
    return 0;
}