A.Altruistic Amphibians

    一个挺有意思的题目。首先考虑这样的问题：倘若要让尽可能多的青蛙能够逃跑，则显然罗汉最好叠得尽可能的高（这才能使得那些不能一次性跳出的青蛙能够逃离）。

    而显然，对于那些体重最大的青蛙，他们显然不能叠在其他青蛙上，因此我们首先对青蛙的重量从大到小进行排序，其次我们考虑第i个青蛙的重量对于其他重量小的重量的青蛙的状态的转移。

    我们设dp[i]为重量为i的青蛙最高能够跳的高度，而对于第i个重量为w[i]的青蛙，不难想到最多一定会有个w[i]个重量小于w[i]的青蛙能够跳到它的上面，故可得有状态转移方程（dp[j-w[i]]=max(dp[j-w[i]],dp[j]+h[i]）(w[i]<=j<=2*w[i])

#include 
      
       #define maxn 100000005using namespace std;int dp[maxn];struct Node{    int l,w,h;    bool operator <(const Node &b)const{        return w>b.w;    }}q[100005];int main(){    int n,d;    scanf("%d%d",&n,&d);    for(int i=0;i
       
        d) res++;        for(int j=q[i].w;j
       
      

 

---

 B.Baby Bites

    温暖的签到题

#include
      
       using namespace std;string str;int change(string s){    int len=s.size();    int ret=0;    for(int i=0;i
       
        >n;    int flag=0;    for(int i=1;i<=n;i++){        cin>>str;        if(str[0]>='0'&&str[0]<='9'){            int num=change(str);            if(num!=i) flag=1;        }    }    if(flag) cout<<"something is fishy"<
       
      

 

---

C.Code Cleanups

    题意相当奇怪的签到题。实际的题意为：给你若干个操作，每个操作的序号id都是递增的。在第id天一定会进行该次操作。每次进行一次操作，肮脏值就会+1（最开始肮脏值为0），肮脏值每天都累计，直到在某一天，累计的肮脏值大于20，则将所有的肮脏值清零，现在问你最小的清零的次数。

    这个题明白题意后就是一个很简单的题目了

#include
      
       using namespace std;int mp[400];int main(){    int n;    scanf("%d",&n);    int tmp;    for(int i=1;i<=n;i++){        scanf("%d",&tmp);        mp[tmp]=1;    }    tmp=0;    int sum=0;    int ans=0;    for(int i=1;i<=365;i++){        if(mp[i]) tmp+=1;        sum+=tmp;        if(sum>=20){            ans++;            tmp=sum=0;        }    }    if(sum) ans++;    printf("%d\n",ans);    return 0;}
      

---

 

D.Delivery Delays

 因为要找最大值最小，所以考虑二分，但是如何很快地check。送货员在跑的时候一定会沿最短路跑，所以先做一下多源的最短路。题目说送货员会按照下单顺序送货，所以送货员送货的过程将会是分成几段出去回来的过程。所以check的时候就看一下是否有一个分段的方案使得答案可行。dp[i]表示前i个送完回到1号点的最小时间，有了dp[i]就可以更新假如后面一个长度为len的区间出去一次就连续送完的答案，需要判断这一个区间如果出去一次就送完是否可行，这就需要找到送货远最早以及最晚什么时间出发，判断要更新的时间是否落在这个时间段内，如果满足方可更新。

1 #include
      
        2 using namespace std; 3 typedef long long ll; 4 typedef pair
       
        pll; 5 const int maxn=1005; 6 const int maxm=5005; 7 const long long inf=0x3f3f3f3f3f3f3f3f; 8 long long dp[maxn]; 9 ll s[maxn],t[maxn];10 int p[maxn];11 int n,m,k;12 struct edge{13     int to,nxt;14     ll d;15 }e[maxm<<1];16 int head[maxn];17 long long dis[maxn][maxn];18 int ecnt;19 void add_edge(int u,int v,ll d){20     e[ecnt].to=v;21     e[ecnt].d=d;22     e[ecnt].nxt=head[u];23     head[u]=ecnt++;24 }25 void ins(int u,int v,ll d){26     add_edge(u,v,d);27     add_edge(v,u,d);28 }29 void dij(int id,int u){30     priority_queue
        
         
          ,greater
          
            >q;31     for(int i=1;i<=n;i++) dis[id][i]=inf;32     dis[id][u]=0;33     q.push(make_pair(dis[id][u],u));34     while(!q.empty()){35         long long tmp=q.top().first;36         u=q.top().second;37         q.pop();38         if(dis[id][u]
           
            dis[id][u]+e[i].d){42 dis[id][v]=dis[id][u]+e[i].d;43 q.push(make_pair(dis[id][v],v));44 }45 }46 }47 }48 bool check(long long x){49 memset(dp,inf,sizeof(dp[0])*(n+2));50 dp[0]=0;51 for(int i=0;i
            
             >n>>m;72 int u,v;73 long long w;74 memset(head,-1,sizeof(head[0])*(n+2));75 for(int i=1;i<=m;i++){76 cin>>u>>v>>w;77 ins(u,v,w);78 }79 for(int i=1;i<=n;i++){dij(i,i);}80 cin>>k;81 for(int i=1;i<=k;i++)82 cin>>s[i]>>p[i]>>t[i];83 long long l=0,r=inf;84 long long ans=l;85 while(l<=r){86 long long mid=(l+r)>>1;87 if(check(mid)){ans=mid;r=mid-1;}88 else l=mid+1;89 }90 cout<
             
              <
             
            
           
          
         
        
       
      

 

---

E.Delivery Delays

    首先我们可以发现，因为每个士兵的血量最大为6，且敌我双方的士兵数均为5，因此我们考虑可以用搜索的方法去解决。

    因为士兵的总血量的状态比较少，因此我们可以考虑用一个12位的long long的每一位去存储每一种血量的个数。此时，这每一个12位的long long整型就唯一代表了一种状态。而又因为在搜索的过程中，每一种曾经访问过的状态所对应的概率必定是唯一的，因此我们只需要用记忆化的形式对曾经出现过的结果记进行记录，以达到剪枝的作用。

    因为我们要记录的是敌军死亡的概率，因此，我们可以优先将敌军的6种血量置于12位long long的高位，这样，当我们访问到的状态值<1000000，则代表已经敌军已经已经死亡，即可直接跳出递归（又一个剪枝）。

    最后只需要将相应的概率相乘并相加即为答案。

#include 
      
       using namespace std;typedef unsigned long long ll;int mp[2][10];unordered_map
       
        dp;//充当记忆化数组ll GetSta(){
    //获取状态    ll res=0;    for(int i=1;i<=6;i++) res*=10,res+=mp[1][i];    for(int i=1;i<=6;i++) res*=10,res+=mp[0][i];    return res;}double dfs(ll sta,int limit){    if(dp.count(sta)) return dp[sta];//如果该状态曾经访问过，则直接调用结果    if(sta<1000000) return 1;//如果该状态的值<1000000，则证明敌人已死，返回1    if(limit==0) return 0;    int cnt=0;    for(int i=0;i<2;i++)//获取总人数        for(int j=1;j<=6;j++) cnt+=mp[i][j];    double res=0;    for(int i=0;i<2;i++){        for(int j=1;j<=6;j++){            if(!mp[i][j]) continue;            mp[i][j]--;            mp[i][j-1]++;            ll newsta=GetSta();            double tmp=dfs(newsta,limit-1);//dfs求解下一层的答案            dp[newsta]=tmp;             mp[i][j]++;//回溯            mp[i][j-1]--;             res+=1.0*mp[i][j]/cnt*tmp;//统计概率        }    }    return res;}int main(){    int n,m,d,num;    scanf("%d%d%d",&n,&m,&d);    for(int i=0;i
       
      

---

F.Firing the Phaser

---

G.Game Scheduling

---

H.House Lawn

    为了保证对于任意的T而言，T周一定能够完成T项任务，因此我们只需要对每一件商品枚举周期T(0<=T<=间隔+工作时间)，判断是否能在某个整周期完成至少一次工作即可。

#include
      
       using namespace std;const int maxn=105;double eps=1e-8;int sgn(double x){    if(fabs(x)
       
        x.id;        return p>x.p;    }}d[maxn];int main(){    //freopen("in.txt","r",stdin);    //freopen("out.txt","w",stdout);    scanf("%d%d",&n,&m);    priority_queue
        q;    for(int i=1;i<=m;i++){        getchar();        char ch=getchar();        while(ch!=','){d[i].s+=ch;ch=getchar();}        scanf("%d,%d,%d,%d",&d[i].p,&d[i].c,&d[i].t,&d[i].r);        d[i].id=i;    }    for(int i=1;i<=m;i++){        bool flag=0;        for(int T=1;T<=d[i].t+d[i].r;T++){            if(flag) break;            long long sum1=10080*T;            long long sum=0;            long long tmp=sum1/(d[i].r+d[i].t);            tmp*=d[i].t;            long long tmp1=sum1%(d[i].r+d[i].t);            tmp1=min(tmp1,1LL*d[i].t);            sum+=(tmp+tmp1)*d[i].c;            if(sum<1LL*n*T) flag=1;        }        if(!flag) q.push(d[i]);    }    if(q.empty()){puts("no such mower");return 0;}    data u=q.top();    q.pop();    cout<
         
          <
         
       
      

---

I.Intergalactic Bidding

     题目说了从大到小排完序后所有人的赌注都大于后面那个人的两倍，所以题解就是高精度排序，然后高精度减法，减到最后判断最后那个数是否为0就行。

 

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn=1500;struct bigint{    int len;    int  a[maxn];    bigint (){        len=0;        memset(a,0,sizeof a);    }    bool operator <(const bigint &b)const {        if (len
         
          b.len) return 0;        for (int i=len-1;i>=0;i--)            if (a[i]>b.a[i]) return 0;            else if (a[i]
          
           =0;i--)        c.a[c.len++]=s[i]-'0';    return c;}struct S{    int id;    char s[maxn];    bigint a;    bool operator <(const S &b)const {        return b.a
           
            >n>>s; m=change(s); for (int i=1;i<=n;i++) { cin>>f[i].s>>s; f[i].a=change(s); } sort(f+1,f+n+1); for (int i=1;i<=n;i++){ if (f[i].a
           
          
         
        
       
      

 

---

J.Jumbled String

　　构造题，我们可以先根据a和d，算出我们需要的0和1的数量，如果算不出来，impossible；接着我们可以判断一下0和1的个数相乘是否为b+c，如果不等，impossible；如果相等，最后就是根据b和c调整0和1的位置输出即可。

　　要注意特判一下几种特殊情况，a、b、c、d都为0时，不是impossible，要输出一个0或1；

　　当a=b=c=0,d!=0或b=c=d=0,a!=0时，要输出对应全0或全1的序列，不行则impossible。

#include
      
       using namespace std;bool check(long long x,long long ans){    if(x*(x-1)/2<=ans) return 1;    return 0;}int main(){  //  freopen("in.txt","r",stdin); //   freopen("out.txt","w",stdout);    long long  a,b,c,d;    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);    if (a==0&&b==0&&c==0&&d==0) {        printf("0\n");        return 0;    }    long long l=1,r=1e9;    long long ans=0;    while(l<=r){        int mid=(l+r)>>1;        if(check(mid,a)) {l=mid+1;ans=mid;}        else r=mid-1;    }    long long ans1=0;    l=1,r=1e9;    while(l<=r){        int mid=(l+r)>>1;        if(check(mid,d)) {l=mid+1;ans1=mid;}        else r=mid-1;    }  //  cout<
       
        <<' '<
        
         <
        
       
      

---

K.King's Colors

　　给你一棵树，问用恰好k种颜色将其涂成两个相邻点颜色不同的方法有多少种。题目告诉你是一棵树了，你涂根节点有k种方法，在接下去的n-1个点的涂法就都是（k-1）种，所以答案为k*(k-1)^(n-1)。仔细想想就会发现怎么涂和树的形状没有关系，所以不用理会。接着，题目说的是要恰好k种，明显我们上面的式子不是恰好k种，所以我们要容斥一下，容斥系数就是一个组合数，把恰好(k-1)种的情况减去，把恰好(k-2)种的情况加上…… 最后就是答案了。

#include 
      
       using namespace std;typedef long long ll;const int mod=1e9+7;const int maxn=2507;ll inv[maxn],f[maxn],finv[maxn];ll powm(ll x,ll n){    ll res=1;    while (n){        if (n&1) res=res*x%mod;        n>>=1;        x=x*x%mod;    }    return res;}void init(){    inv[1]=1;    for (int i=2;i
       
        n) return 0;    return f[n]*finv[m]%mod*finv[n-m]%mod;}int main(){    init();    ios::sync_with_stdio(false);    cin.tie(0);    int n,k;    cin>>n>>k;    ll ans=0;    for (int i=0,f=1;i