2018.8.10Yukimai模拟Day1

这的确是最惨的一次模拟了……不会再惨了（10pts除非爆零orz）

总结一下吧……

T1 .章鱼

众所周知，雪舞喵有许多猫。由于最近的天气十分炎热，雪舞城的大魔法师雪月月根本不想出门，只想宅在家里打隔膜。大魔法师雪月月最近沉迷一个叫做社保2的隔膜，在这个隔膜的休闲对战模式中，雪月月和其他3个随机的玩家组队，与另外4个随机的玩家组成的队伍进行战斗。一场战斗中，两个队伍会被分配不同颜色的两种油漆，玩家需要操纵一个章鱼油漆工在有限的时间内往地图上刷油漆，时间结束时，地图上油漆所占面积较多的队伍将会获得胜利。雪月月在战斗的过程中会经常打开地图以查看自己的队伍是否处于优势(如果某一时刻的地图上，雪月月队伍的油漆所占面积多于敌方队伍的油漆所占面积，则雪月月认为自己的队伍处于优势)，以调整她下一步的战斗策略。然而雪月月的视力并不好，在大多数情况下她不能在短时间内分辨出己方是否处于优势，而在看地图时，地图会覆盖整个屏幕，雪月月不能及时发现敌人，就会被敌人消灭，因此雪月月经常输掉对战。虽然休闲模式的胜负并不会影响雪月月X等级的排位积分，但是输掉对战总是让猫很恼火，于是雪月月找来了雪舞喵的小猫雪萌萌，要求雪萌萌帮助她看地图，如果有雪萌萌帮她看地图她还输了，她就会拿雪萌萌来测试她最近发明的奇怪魔法。这样雪月月需要看地图的时候，只需打开地图0.1秒，让雪萌萌在1秒内告诉她她的队伍是否处于优势，这样就能方便的调整战斗策略而不会在看地图时被敌人偷袭了。然而只会卖萌的雪萌萌并不能在0.1秒内看清如此复杂的地图，更不能在1秒内算出雪月月的队伍是否处于优势。为了解决第一个问题，雪萌萌将地图划分成了的网格(每个格子的面积相等)，并在0.1秒内记住了网格中每个格子的大致情况。但就算是把地图划分成了网格，雪萌萌依然不能在1秒内算出答案，但是雪萌萌又相当不想被拿来测试奇怪的魔法，于是雪萌萌找到了你，请你在1秒内告诉她，雪月月的队伍有多大概率处于优势。

Input
输入包含多组数据，每组数据的第一行包含由1个空格分隔的两个正整数 n,m ，代表雪萌萌将地图分为 n行m 列的网格。
接下来的n 行，每行m有个字符代表雪萌萌记下的每个格子的大致情况。
输入数据以一组n = 0,m = 0 的不合法数据结束，你不必给出这组数据的答案。
字符代表的含义如下：
0 表示这一格里没有任何油漆
+ 表示这一格里充满了雪月月队伍的油漆
‐ 表示这一格里充满了敌方队伍的油漆
* 表示这一格里既有雪月月队伍的油漆，又有敌方队伍的油漆
根据数格子的国际惯例，对于同时存在双方队伍油漆的格子，若雪月月队伍的油漆所占面积大于等于格子的一半，则可以认为这个格子充满雪月月队伍的油漆，否则可以认为这个格子充满敌方队伍的油漆。
然而不幸的是，雪萌萌并没有记住这样的格子里雪月月队伍的油漆所占面积是否大于等于格子的一半，于是雪萌萌认为每个这样的格子中，雪月月队伍的油漆所占面积大于等于格子一半的概率是，小于格子一半的概率也是，且格子之间互不影响。
Output
对于每组数据，输出一行一个整数。
设雪月月获胜的概率为p ，可以证明 p*2^（n*m）是一个整数，请你输出其对取模后的结果。

是一道不算特别难的组合数题……不过当时自己特别傻……使用了一种错误的算法……就写错了……还debug不出来就特别伤。

首先我们计算一下，有一个加号，则tot++，有一个减号则tot--，如果有*就cur++。之后，如果tot+cur还小于0，则必然无法取胜，如果tot-cur还大于0，那就必然能取胜。

考虑一般情况。计算之后发现，我们至少需要cur - tot >> 1个不确定的格子被自己使用，才能确保自己是胜利的。（cur-tot>>1必然小于cur否则在前面的情况之中就已经被筛去了）

这样的话，雪月月在当前有i个格子时自己的的情况下获胜的概率是C（i，cur）也就是从cur个不确定的格子中选i个即可。那么总的获胜概率自然就是这些所有可行的概率之和。

注意因为答案要求的是概率再乘以2^(n*m)，所以我们先求逆元，以计算组合数（这里计算阶乘的逆元就可以，先顺着算一遍阶乘，再反着算一遍逆元），之后把结果乘以2^（n*m-cur）就行了。

（我当时以为自己发现了什么了不得的O（1）算法，就瞎写一通，不过后来发现自己是因为忘记乘组合数了）

看一下代码。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<cmath>

#include<set>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const ll p = 1e9 + 7;

const int M = 25000005;

ll read()

{

    ll ans = 0,op = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9')

    {

        if(ch == '-') op = -1;

        ch = getchar();

    }

    while(ch >= '0' && ch <= '9')

    {

        ans *= 10;

        ans += ch - '0';

        ch = getchar();

    }

    return ans * op;

}

ll qpow(ll a,ll b)

{

    ll q = 1;a %= p;

    while(b)

    {

        if(b & 1) q *= a,q %= p;

        a *= a,a %= p;

        b >>= 1;

    }

    return q % p;

}

ll sum[M+1],inv[M+1],n,m,tot,cur,ans,k;

char s[5005][5005];

void init()

{

    sum[0] = sum[1] = 1;

    inv[0] = inv[1] = 1;//inv[i]存i！的逆元

    rep(i,2,M-1) sum[i] = sum[i-1] * i % p;

    inv[M-1] = qpow(sum[M-1],p-2);

    per(i,M-2,2) inv[i] = inv[i+1] * (i+1) % p;

}

ll C(ll a,ll b)

{

    return sum[a] * inv[b] % p * inv[a-b] % p;

}

int main()

{

    init();

    while(1)

    {

        n = read(),m = read();

        if(!n && !m) break;

        tot = cur = 0;

        rep(i,1,n)

        {

            scanf("%s",s[i]);

            rep(j,0,m-1)

            {

                if(s[i][j] == '0') continue;

                if(s[i][j] == '+') tot++;

                if(s[i][j] == '-') tot--;

                if(s[i][j] == '*') cur++;

            }

        }

        ll ans = 0;

        if(tot + cur <= 0) printf("0\n");

        else if(tot - cur > 0) printf("%lld\n",qpow(2,n*m));

        else

        {

            rep(i,(cur - tot >> 1) + 1,cur)

            {

                ans += C(cur,i);

                if(ans > p) ans -= p;

            }

            ans *= qpow(2,n*m-cur),ans %= p;

            printf("%lld\n",ans);

        }

    }

    return 0;

}

T2.狒狒

Description
众所周知，雪舞喵有许多猫。
　由于最近的天气十分炎热，雪舞城的顶级工匠雪菲菲根本不想出门，只想宅在家里打隔膜。
顶级工匠雪菲菲一直沉迷一个叫做狒狒14的隔膜，狒狒14作为一个大型多人在线角色扮演隔膜，里面既有战斗职业也有生产和采集职业。雪菲菲作为雪舞城的顶级工匠在隔膜中自然也是顶级的，她在每个服务器上都有一个生产采集职业全部满级满装备的大号，更有数不清的小号，每个服务器中都有雪菲菲的至少套大型海景房，每天雪菲菲都会上街撒钱撒装备，抽取幸运的小伙伴赠送海景房，接受贫民的巴结和奉承，她对此感到十分快乐。
　然而好景不长，下周二雪菲菲即将迎来最忙的时间段，原因是下周二狒狒14将进行版本更新，版本更新会加入大量的新装备，导致雪菲菲的装备失去了统治地位，雪菲菲不得不焚膏继晷地刷各种各样的任务以获得用于换取顶级装备的货币，从而穿上一身新的顶级装备，以继续上述快乐的行为。
　　虽然任务是各种各样的，但它们的大致流程可以简化为以下3步：
1. 接任务
2. 搓一堆指定物品
3. 交任务
　　对于顶级工匠雪菲菲来说，搓东西完全不是问题，她闭着眼睛都能完成(这是她的原话)，然而顶级工匠雪菲菲对战斗没什么兴趣，所以她的所有账号中用来战斗的职业都只有 0级。而雪菲菲在地图上跑来跑去接任务和交任务的时候，有可能被野怪攻击，因为她的战斗职业都是0 级，如果被野怪攻击了，她就会凉凉。因此雪菲菲的大部分时间都浪费在躲避野怪上。
　　雪菲菲当然希望在最短时间内穿上神装，因此，为了尽可能的节省躲避野怪的时间，雪菲菲需要预先规划自己的路线。于是雪菲菲找到了雪舞城的电子专家雪花花，雪花花在解压了下个版本的补丁包后把所有的任务相关信息都告诉了雪菲菲，雪菲菲从中筛选出了她需要完成的任务。由于任务有cd，雪菲菲必须且仅能完成每个任务恰好一次。
　　狒狒14的地图可以大致划分为个地点，地点之间有条可以双向通行的通路，每条通路有一个长度代表通路的相对长度，一个危险程度代表这条路上野怪的密集程度。由于任意战斗职业等级达到20级才能解锁骑乘，雪菲菲只能在通路上步行。由于需要躲避野怪，雪菲菲步行通过一条通路花费的时间为。除此之外，有的地点还具有传送水晶，雪菲菲可以通过花费一些金币来读条传送到一个具有传送水晶的地点。虽然雪菲菲的金币可以认为是无限的，但传送的读条比较长，读条时还不能移动，在某些比较危险的地点读条传送就容易凉凉，因此在某些地点上雪菲菲不能发动传送。由于所有的通路都是危险的，雪菲菲也不能在通路上发动传送。一次读条传送将花费雪菲菲时间。保证通过通路和传送可以从地图上任意一点到达任意一点。
雪菲菲有q 个需要完成的任务，第 i个任务需要在si 点接任务，在ti 点交任务，雪菲菲需要保证，对于每个需要完成的任务，她的路线需要先后经过 si和ti ，具体来说，令雪菲菲路线上经过的点的序列为L ，则对于任意合法的i ，需满足序列 {si,ti}是L 的一个子序列。特别的，若si=ti ，则只需满足序列{si} 是L的一个子序列即可。
雪菲菲的路线在满足以上要求(即能完成所有任务)的条件下，可以从任意一个安全的点开始(即可以发动传送的地点)，进行若干次合法的步行或传送，到任意一个点结束。雪菲菲希望自己花费的时间最短。
然而雪菲菲并不擅长路径规划，于是雪菲菲又找来了雪舞喵的小猫雪萌萌，要求雪萌萌帮她规划路线，如果雪萌萌规划的路线不能让她满意，她就会拿雪萌萌来测试她最近制作的奇怪道具。
众所周知，雪萌萌只会卖萌，并不会什么路径规划。但是雪萌萌又相当不想被拿来测试奇怪的道具，于是雪萌萌找到了你，请你帮她规划雪菲菲的路线，你只需要告诉雪萌萌，雪菲菲需要花费的最短时间是多少。
Input
输入第一行包含由一个空格分隔的4个整数n,m,q,E
接下来的一行包含由一个空格分隔的 n个整数ci ， ci=1代表i 点有传送水晶
接下来的一行包含由一个空格分隔的n 个整数 vi， vi=1代表 i点是危险的(即路线不能从i 点开始，也
不能从i 点发动传送)
接下来行，每行包含由一个空格分隔的4个整数s,t,l,d 代表一条连接s 和t ，长度为l ，危险程度为d
的双向通路
接下来q 行，每行包含由一个空格分隔的2个整数si,ti 代表一个任务
Output
输出一行一个整数代表雪菲菲需要花费的最短时间。

这道题的数据范围非常的小……很明显是状压DP。

首先我们把图建出来，对于传送，只要符合条件，就建立一条边权为E的单向边。其他的路径就建一条边权为l*d的双向边。

这样之后，我们考虑如何进行状压DP。因为对于一个任务来说，只有三种状态，还没接，接了还没做完，已经做完了。而且任务只有不超过12个，所以我们使用一个长度为12的三进制串表示当前的状态。之后我们从当前状态出发，枚举每一个任务，当前的任务状态必须由上一次的转移过来。如果当前还没做，那么下一个节点就转移到此任务开始点，如果还没做完，转移到此任务结束点，做完了就不用管。

优先使用floyd处理每两个点之间的最短距离，同时要自己写函数计算三进制转换啥的……还有，一开始对于每个安全的节点都要压入队列，之后每次取队首元素进行更新，如果成功更新了，就把新的元素再压入队列。这样最后肯定会有一种状态无法继续被转移，即为所求。

看一下代码。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<iostream>

#include<queue>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = 1005;

typedef pair<ll,ll> pr;

ll read()

{

    ll ans = 0,op = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9')

    {

        if(ch == '-') op = -1;

        ch = getchar();

    }

    while(ch >= '0' && ch <= '9')

    {

        ans *= 10;

        ans += ch - '0';

        ch = getchar();

    }

    return ans * op;

}

struct mis

{

    ll a,b;

}mi[20];

ll n,m,q,e,g[30][30],s,t,l,d;

ll dp[30][700000],st[30];

bool c[30],v[30],vis[30][700000];

queue <pr> pq;

void floyd()//floyd处理最短距离

{

    rep(k,1,n)

    rep(i,1,n)

    rep(j,1,n)

    g[i][j] = min(g[i][j],g[i][k] + g[k][j]);

}

void build()

{

    memset(g,127/3,sizeof(g));

    memset(dp,127/3,sizeof(dp));

    n = read(),m = read(),q = read(),e = read();

    rep(i,1,n) c[i] = read(),g[i][i] = 0;

    rep(i,1,n) v[i] = read();

    rep(i,1,m)

    {

        s = read(),t = read(),l = read(),d = read();

        g[s][t] = min(g[s][t],d*l);

        g[t][s] = min(g[t][s],d*l);//使用邻接矩阵以用floyd

    }

    rep(i,0,q-1) mi[i].a = read(),mi[i].b = read();

    rep(i,1,n)

    {

        if(!v[i])

        {

            dp[i][0] = 0;//第一维表示枚举的任务，第二维表示状态

            pq.push(make_pair(i,0));//如果安全就压入

            rep(j,1,n) if(c[j]) g[i][j] = min(g[i][j],e);//建立单向边

        }

    }

    floyd();

}

void cal(ll x)

{

    rep(i,0,q-1) st[i] = x % 3,x /= 3;//将状态转化为三进制串

}

ll lac()

{

    ll res = 0;

    per(i,q-1,0) res *= 3,res += st[i];//三进制串转化回去

    return res;

}

void update(int i,ll val)

{

    st[i]++;

    ll pos = lac();

    st[i]--;

    ll c;

    if(st[i] == 0) c = mi[i].a;

    else c = mi[i].b;

    dp[c][pos] = min(dp[c][pos],val);//更新距离

    if(!vis[c][pos]) vis[c][pos] = 1,pq.push(make_pair(c,pos));

//记录一下此状态已经被走过

}

int main()

{

    build();

    ll r = 100000000000000;

    while(!pq.empty())

    {

        pr c = pq.front();

        pq.pop();

        cal(c.second);

        bool ret = 1;

        rep(i,0,q-1)

        {

            if(st[i] < 2)//如果当前任务没做完

            {

                ret = 0;

                if(st[i] == 0)

                update(i,dp[c.first][c.second] + g[c.first][mi[i].a]);

                else update(i,dp[c.first][c.second] + g[c.first][mi[i].b]);//更新即可

            }

        }

        if(ret) r = min(r,dp[c.first][c.second]);//全做完了就更新答案

    }

    printf("%lld\n",r);

    return 0;

}

/*

5 4 2 1

1 0 0 0 0

0 1 1 1 0

1 2 1 2

2 3 0 2000

3 4 2 2

4 5 4 2

3 1

4 5

*/

T3.辣鸡

（本题题目描述过长……所以上图吧……）

这题真难写……

其实算法并不是很难想。我们用三棵线段树分别维护每种稀有度的卡在一个区间内出现的次数和喜爱程度。之后对于每个新加入的区间，记录其下标和喜爱度的期望值。把它们放到set里面维护。重载一下小于号每次直接取堆首元素就行。

然后对于删除操作，我们可以选择记录一下下标所对应的值和左右端点，直接在set里面erase就好。

至于修改操作……我一开始以为这是个丧心病狂的操作因为我以为他要同时修改好多个区间的值，不过显然不是这样……题目描述已经保证没有一张卡属于两个即以上区间啦……（还是加粗的字体呢）

所以我们可以再开一个set记录左右端点（要按左端点排序），之后直接用upperbound在set里面以左端点为关键字就能把这个元素找到，再进行一些操作就非常的简单。

话虽这么说……不过代码其实不是很好写…有好多细节（主要是你写到一半觉得题太长就想放弃）

上代码。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<iostream>

#include<set>

#include<vector>

#include<utility>

#include<map>

#define rep(i,a,n) for(int i = a;i <= n;i++)

#define per(i,n,a) for(int i = n;i >= a;i--)

#define enter putchar('\n')

using namespace std;

typedef long long ll;

const int M = 500005;

ll read()

{

    ll ans = 0,op = 1;

    char ch = getchar();

    while(ch < '0' || ch > '9')

    {

        if(ch == '-') op = -1;

        ch = getchar();

    }

    while(ch >= '0' && ch <= '9')

    {

        ans *= 10;

        ans += ch - '0';

        ch = getchar();

    }

    return ans * op;

}

ll n,q,ra[M],xl[M],a,b,x,cnt,keyl[M],keyr[M];

double key[M];

struct node//存储左右端点和下标

{

    ll dl,dr,id;

    bool operator < (const node &g) const

    {

        return dl < g.dl;

    }

};

struct card//存储卡池的情况，按题目要求重载，之后直接取堆首

{

    double v;

    ll pos;

    bool operator < (const card &g) const

    {

        if(v == g.v) return pos < g.pos;

        return v > g.v;

    }

};

set <node> nq;

set <card> cq;

struct seg

{

    ll sum[M<<2],exp[M<<2];

    void update(ll p)

    {

        sum[p] = sum[p<<1] + sum[p<<1|1];

        exp[p] = exp[p<<1] + exp[p<<1|1];

    }

    void build(ll p,ll l,ll r,ll num)

    {

        if(l == r) //建树的时候要对应稀有度

        {

            if(num == ra[l]) sum[p] = 1,exp[p] = xl[l];

            return;

        }

        ll mid = l+r >> 1;

        build(p<<1,l,mid,num);

        build(p<<1|1,mid+1,r,num);

        update(p);

    }

    void modify(ll p,ll l,ll r,ll pos,ll val)//常规修改

    {

        if(l == r)

        {

            exp[p] = val;

            return;

        }

        ll mid = l+r >> 1;

        if(pos <= mid) modify(p<<1,l,mid,pos,val);

        else modify(p<<1|1,mid+1,r,pos,val);

        exp[p] = exp[p<<1] + exp[p<<1|1];

    }

    double query1(ll p,ll l,ll r,ll kl,ll kr)//找喜爱度

    {

        if(l == kl && r == kr) return (double)exp[p];

        ll mid = l + r >> 1;

        if(kr <= mid) return query1(p<<1,l,mid,kl,kr);

        else if(kl > mid) return query1(p<<1|1,mid+1,r,kl,kr);

        else return query1(p<<1,l,mid,kl,mid) + query1(p<<1|1,mid+1,r,mid+1,kr);

    }

    double query2(ll p,ll l,ll r,ll kl,ll kr)//找个数

    {

        if(l == kl && r == kr) return (double)sum[p];

        ll mid = l + r >> 1;

        if(kr <= mid) return query2(p<<1,l,mid,kl,kr);

        else if(kl > mid) return query2(p<<1|1,mid+1,r,kl,kr);

        else return query2(p<<1,l,mid,kl,mid) + query2(p<<1|1,mid+1,r,mid+1,kr);

    }

}t[4];

double calc(ll l,ll r)//丧心病狂的计算（注意这里是从0开始的否则会出错）

{

    double ans = 0;

    ans += 10.0 * (9.0 / 10.0 * t[0].query1(1,1,n,l,r) / t[0].query2(1,1,n,l,r));

    ans += 10.0 * (9.0 / 100.0 * t[1].query1(1,1,n,l,r) / t[1].query2(1,1,n,l,r));

    ans += 10.0 * (t[2].query1(1,1,n,l,r) / t[2].query2(1,1,n,l,r) / 100.0);

    ans += 9.0 / 10.0 * t[1].query1(1,1,n,l,r) / t[1].query2(1,1,n,l,r);

    ans += t[2].query1(1,1,n,l,r) / t[2].query2(1,1,n,l,r) / 10.0;

    return ans;

}

int main()

{

    n = read(),q = read();

    rep(i,1,n) ra[i] = read();

    rep(i,1,n) xl[i] = read();

    rep(i,0,2) t[i].build(1,1,n,i);

    key[0] = calc(1,n),keyl[0] = 1,keyr[0] = n;//记录下标对应的值，左右端点的位置

//    printf("%.4lf\n",key[0]);

    cq.insert((card){key[0],0});

    nq.insert((node){1,n,0});

    rep(i,1,q)

    {

        set <card> :: iterator it1;

//        for(it1 = cq.begin();it1 != cq.end();it1++) printf("%.4lf %lld\n",it1->v,it1->pos);

        char c = getchar();

        if(c == '1')//使用字符读入处理……当然有其他方式

        {

            a = read(),b = read();

            key[++cnt] = calc(a,b),keyl[cnt] = a,keyr[cnt] = b;//新建卡池并插入堆中

            cq.insert((card){key[cnt],cnt});

            nq.insert((node){a,b,cnt});

        }

        else if(c == '2')//把卡池删了

        {

            x = read();

            cq.erase((card){key[x],x});

            nq.erase((node){keyl[x],keyr[x],x});

        }

        else if(c == '3')

        {

            a = read(),b = read();

            t[ra[a]].modify(1,1,n,a,b);

            cq.erase((card){key[0],0});

            key[0] = calc(1,n);

            cq.insert((card){key[0],0});//先改基础卡池

            set <node> :: iterator it = nq.upper_bound((node){a,233,233});//找到要改的

//            printf("#%lld\n",(*it).id);

            if(it == nq.begin()) continue;//如果是基础卡池就不改

            it--;

            ll k = (*it).id;

//            printf("#%lld\n",k);

//            if((*it).dr < x) continue;//这里很奇怪，不删70，删了AC

            cq.erase((card){key[k],k});

            key[k] = calc(keyl[k],keyr[k]);

            cq.insert((card){key[k],k});//删除，修改，重新插入

        }

        else

        {

            card now = *(cq.begin());

            printf("%lld\n",now.pos);//否则直接输出堆首元素，下面是处理K以外的字符的

            c = getchar(),c = getchar(),c = getchar();

        }

    }

    return 0;

}

写完此题要由衷的赞美STL……

哎……以后还是要注意考试策略……orz

巴特西

2018.8.10Yukimai模拟Day1

最新文章

热门文章