2020杭电多校联合训练(第四场)
in 杭电多校多校训练 with 0 comment

2020杭电多校联合训练(第四场)

in 杭电多校多校训练 with 0 comment

摘要

/ABCDEFGHIJKL
场上
zyj
wrf
lmj

题目

A.Anti-AK Problem

题意

题解

代码


B.Blow up the Enemy

lmj (00:15:50) +1

题意

一个人从n种武器中选一种,另一个人在n种武器中随机选一种,每种武器有攻击力和攻击完的冷却时间,每个人的血量为100,如果同时死亡那么胜率为50%,求最高胜率。

题解

观察题目性质,由于两人的初始血量都为100,所以对于每种武器 i,都能算出击杀对方的时间。具体来说,$\left\lceil\frac{100+a_{i}-1}{a_{i}}\right\rceil$ 就是需要的攻击次数,那么$\left(\left[\frac{100+a_i-1}{a_{i}}\right]-1\right) \cdot d_{i}$ 就是最早击杀对方的时间。
显然,你的最优决策是选择击杀时间最早的那一种武器,再枚举对方的选择计算胜利的概率即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
void work()
{
    int n;
    scanf("%d",&n);
    int cnt=0;
    int ans=1e8;
    for(int i=1;i<=n;i++){
        int a,d;
        scanf("%d%d",&a,&d);
        int tmp=(100+a-1)/a-1;
        tmp*=d;
        if(ans>tmp){
            ans=tmp;
            cnt=0;
        }
        if(ans==tmp){
            cnt++;
        }
    }
    double sum=0;
    sum=(n-cnt)+0.5*cnt;
    //printf("%d %f\n",cnt,sum);
    printf("%.10f\n",sum/n);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.Contest of Rope Pulling

lmj (03:39:26) +2

题意

两个班级,每个人有体重和颜值两个属性,要求从两个班中各选几个人使得选出的两个集合体重和相等且两个集合的颜值和最大。

题解

卡常假题,直接$n^3$dp加指令集优化可以卡过,以下是正解。

先转化题意:有 $n + m$ 个物品,每个物品用一对数 $\left(w_{i}, v_{i}\right)\left(-10^{3} \leq w_{i} \leq 10^{3},-10^{9} \leq v_{i} \leq 10^{9}\right)$ 描述。选择一个物品子集 $S$,满足 $\sum_{i \in S} w_{i}=0$ ,最大化$\sum_{i \in S} v_{i}$。
这是一个经典的 01 背包问题,通过 DP 可以做到 $\mathcal{O}\left((n+m)^{2} \cdot \max \left\{w_{i}\right\}\right)$ 的时间复杂度。
单个物品的 $w_i$ 最大只有 $10^{3}$,但是 DP 过程中$\sum w_{i}$ 的最大值可能达到$10^{6}$。这无疑是极大的浪费。
如果我们以一种相对随机的方式安排物品的加入顺序,那么可以发现,最优解在每一阶段对应的状态都在 0 附近振荡。设最优解的子集为 $S$,在物品全集的加入顺序被等概率重排之后,子集 $S$ 的加入顺序也被等概率重排。我们只需要设一个足够大的上界 $T$,只考虑 $[-T, T]$ 的$\sum w_{i}$,做原来的 DP 即可。

代码

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=1e6+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll dp[N];
ll dp2[N];
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int sum1=0;
    for(int i=1;i<=n;i++){
        int w,v;
        scanf("%d%d",&w,&v);
        for(int j=sum1;j>=0;j--){
            if(dp[j]+v>dp[j+w]){
                dp[j+w]=dp[j]+v;
            }
        }
        sum1+=w;
    }
    int sum2=0;
    for(int i=1;i<=m;i++){
        int w,v;
        scanf("%d%d",&w,&v);
        for(int j=sum2;j>=0;j--){
            if(dp2[j]+v>dp2[j+w]){
                dp2[j+w]=dp2[j]+v;
            }
        }
        sum2+=w;
    }
    ll ans=0;
    int minn=min(sum1,sum2);
    for(int i=1;i<=minn;i++){
        ans=max(ans,dp[i]+dp2[i]);
    }
    printf("%lld\n",ans);
    for(int i=1;i<=sum1;i++){
        dp[i]=-1e15;
    }
    for(int i=1;i<=sum2;i++){
        dp2[i]=-1e15;
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    for(int i=1;i<=1e6;i++){
        dp[i]=-1e15;
        dp2[i]=-1e15;
    }
    //cin>>T;
    while(T--){
        work();
    }
}

D.Deliver the Cake

zyj (01:09:41) +0

题意

给出一张无向连通图,点分为$L$和$R$两类,你需要从$S$走到$T$,并且要求经过点时人的状态和点的类型一样,过程中可以转变人的状态,花费$x$秒,问从$S$走到$T$的最短时间。

题解

容易证明贪心地走是最优的,也就是说,我们跑最短路松弛时,可以根据当前人的状态和下一个村庄的状态改变松弛边的边权,然后在起点根据点$S$的状态跑一次到两次就可以了。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
typedef pair<ll,pair<int,int> > pii;
ll dis[maxn][2];int vis[maxn][2];
int n,m,s,t,x;
char op[maxn];
struct Edge{
    int v;ll w;int nxt;
}g[maxn<<1];
int head[maxn],edge_tot;
const ll INF=(ll)1e15;
void init(){rep(i,0,n) head[i]=0;edge_tot=1;}
void addedge(int u,int v,ll w=1){g[edge_tot]={v,w,head[u]};head[u]=edge_tot++;}
void dijkstra(int s,int cnt){
    priority_queue<pii,vector<pii>,greater<pii> > Q;
    rep(i,1,n) dis[i][0]=dis[i][1]=INF,vis[i][0]=vis[i][1]=0; dis[s][cnt]=0;
    Q.push({dis[s][cnt],{s,cnt}});
    if(op[s]=='L'&&cnt==1) return;
    if(op[s]=='R'&&cnt==0) return;
    while(!Q.empty()){
        pii tmp=Q.top();Q.pop();
        int u=(tmp.second).first,opc=(tmp.second).second;
        if(vis[u][opc]) continue; vis[u][opc]=1;
        for(int i=head[u];i;i=g[i].nxt){
            int v=g[i].v,cc=opc;ll w=g[i].w;
            if(opc==0&&op[v]=='R') w+=x,cc=1;
            if(opc==1&&op[v]=='L') w+=x,cc=0;
            if(dis[v][cc]>dis[u][opc]+w){
                dis[v][cc]=dis[u][opc]+w;
                Q.push({dis[v][cc],{v,cc}});
            }
        }
    }
}
void solve(){
    scanf("%d%d%d%d%d",&n,&m,&s,&t,&x);init();
    scanf("%s",op+1);
    rep(i,1,m){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,1ll*w);addedge(v,u,1ll*w);
    }
    ll ans=INF;
    dijkstra(s,0);
    ans=min({ans,dis[t][0],dis[t][1]});
    // printf("%lld\n",ans);
    dijkstra(s,1);
    ans=min({ans,dis[t][0],dis[t][1]});
    printf("%lld\n",ans);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

E.Equal Sentences

zyj+lmj (00:44:13) +2

题意

我们定义两个句子几何相似为:
1.连句子的单词集相等。
2.对于每个单词,其在$S$中第i次出现的下标和在$T$中第i次出现的下标相差小于等于1。

给出句子$S$,问你有多少句子和$S$相似。

题解

尝试分析题目所述的条件,找到与之等价的条件。假设句子 $S$ 与 $T$ 几乎相等,取最大的 $k$ 满足$S[1: k]=T[1: k]$,如果$k \neq n$,必然有$S[k+1] \neq T[k+1]$ 。由于需要满足题目所述的条件,所以一定会有$S[k+1]=T[k+2], S[k+2]=T[k+1]$,我们可以将$T[k+1] \text { 与 } T[k+2]$交换,继续执行操作。
由此可以发现,对于任意一个与 $S$ 几乎相等的句子 $T$,都能唯一对应若干个不交的交换操作。同样地,任意一组不交的交换操作,也能唯一对应一个与 $S$ 几乎相等的句子 $T$。需要注意,这里不交的交换操作$(i, i+1)$应满足$S[i] \neq S[i+1]$。
接下来可以用$DP$来解决这个问题。令 $f(i)$ 表示与$S[1: i]$几乎相等的句子个数。转移到 $i$ 的时候,考虑 $i$ 与 $i − 1$ 是否进行交换操作即可(交换需满足$S[i-1] \neq S[i]$)。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n;
ll dp[maxn];
string s[maxn];
void solve(){
    cin>>n;
    ll ans=0;
    rep(i,1,n){
        cin>>s[i];
    }
    dp[0]=1;
    dp[1]=1;
    for(int i=2;i<=n;i++){
        if(s[i]==s[i-1])dp[i]=dp[i-1];
        else dp[i]=(dp[i-1]+dp[i-2])%mod;
    }
    cout<<dp[n]<<endl;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int T;cin>>T;
    while(T--) solve();
}

F.Fake Photo

题意

题解

代码


G.Go Running

zyj (03:24:04) +5

题意

有一条跑到,初始时有学生在跑步,每个学生可以选择一个初位置和初始方向,以固定$1m/s$的速度跑自定义的时间。有一个监视器,可以报告指定时间制定位置有至少一个人,现在给出n个监视器信息,求最少多少学生在跑步。

题解

由一个监视器信息$(t_i,x_i)$可以得知,这个信息可能由$(x_i - t_i ,R)$或$(x_i +t_i ,L)$得到,其中$L,R$表示初方向。那么现在问题就变成了,选定最少的初位置,使得每个监视器都能被覆盖到。那么我们把$L$和$R$看成左部和右部的点,监视器看成边,这就变成了一个最大点匹配问题。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n;
struct DINIC{
    #define maxn (int)1e6
    #define maxe (int)3e6+10
    const ll inf=(ll)1e17;
    int dep[maxn],head[maxn],cur[maxn],tot;
    struct EDGE{int v,nxt;ll val;}g[maxe];
    void add(int u,int v,ll w){g[tot]={v,head[u],w};head[u]=tot++;}
    void init(){tot=0;memset(head,-1,sizeof(head));}
    void addedge(int u,int v,ll w){add(u,v,w);add(v,u,0);}
    bool bfs(int s,int t){
        memset(dep,0,sizeof(dep));
        queue<int> Q;Q.push(s); dep[s]=1;cur[s]=head[s];
        while(!Q.empty()){
            s=Q.front();Q.pop();
            for(int i=head[s],v;~i;i=g[i].nxt){
                if(g[i].val>0&&!dep[v=g[i].v]){
                    dep[v]=dep[s]+1;cur[v]=head[v];
                    if(v==t) return true;
                    Q.push(v);
                }
            }
        } return false;
    }
    ll dfs(int s,int t,ll flow){
        if(s==t||flow<=0) return flow;
        ll rest=flow;
        for(int &i=cur[s];~i;i=g[i].nxt){
            int v=g[i].v;
            if(g[i].val>0&&dep[v]==dep[s]+1){
                ll tmp=dfs(v,t,min(rest,g[i].val));
                if(tmp<=0) dep[v]=0;
                rest-=tmp;
                g[i].val-=tmp;g[i^1].val+=tmp;
                if(rest<=0) break;
            }
        }
        return flow-rest;
    }
    ll maxflow(int s,int t){
        ll ans=0;
        while(bfs(s,t)) ans+=dfs(s,t,inf);
        return ans;
    }
    //先init(),再addedge,最后flow.maxflow(s,t);
}dinic;
map<ll,int> mp[2];
int p1,p2;
set<pair<int,int> > ck;
#define addedge dinic.addedge
void solve(){
    scanf("%d",&n);dinic.init();
    rep(i,0,1) mp[i].clear();
    ck.clear();
    p1=0,p2=0;
    rep(i,1,n){
        ll t,x;scanf("%lld%lld",&t,&x);
        ll l=x-t,r=x+t;
        if(!mp[0].count(l)) mp[0][l]=++p1;
        if(!mp[1].count(r)) mp[1][r]=++p2;
        int c1=mp[0][l],c2=mp[1][r];
        if(ck.find({c1,c2})==ck.end()){
            addedge(c1,n+c2,1);ck.insert({c1,c2});
            // printf("!!%d %d\n",p1,p2);
        }
    }
    // printf("$$%d %d\n",p1,p2);
    int S=n+p2+1,T=S+1;
    rep(i,1,p1) addedge(S,i,1);
    rep(i,1,p2) addedge(i+n,T,1);
    ll f=dinic.maxflow(S,T);
    printf("%lld\n",f);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

H.Head Maker

题意

题解

代码


I.Imperative Meeting

题意

题解

代码


J.Joyful Party

题意

题解

代码


K.Kindergarten Physics

lmj (01:00:47) +0

题意

给出两物体的质量和距离,给出万有引力公式,求经过$t_0$时间后两物体的距离。

题解

观察到质量的单位是$kg$,距离的单位是$km$,很明显万有引力的值很小,可以忽略不计,因此输出原距离即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
double G=6.6743*1e-11;
void work()
{
    int a,b,d,t;
    scanf("%d%d%d%d",&a,&b,&d,&t);
    d=d*1000;
    double ans=0;
    double v=0;
    for(int i=1;i<=t;i++){
        double A=(a+b)*G/(d-ans)/(d-ans);
        ans+=(v+A+v)/2;
        v+=A;
    }
    printf("%.20f\n",(d-ans)/1000);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

L.Last Problem

lmj (04:03:23) +0

题意

给出一种放数的方法:要放一个数x,他四周必须要是$(x-1,x-2,x-3,x-4)$,负数忽略,请你给出一种构造出n的方案。

题解

容易发现爆搜虽然理论是$n^3$步的,但是会有很多点可以重用,可以在$4e4$步内完成。

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
map<pair<int,int>,int>m;
//int cnt=0;
void dfs(int x,int y,int n)
{
    if(n<=0)return;
    if(m[{x,y-1}]!=n-4){
        dfs(x,y-1,n-4);
    }
    if(m[{x-1,y}]!=n-3){
        dfs(x-1,y,n-3);
    }
    if(m[{x+1,y}]!=n-2){
        dfs(x+1,y,n-2);
    }
    if(m[{x,y+1}]!=n-1){
        dfs(x,y+1,n-1);
    }
    //cnt++;
    printf("%d %d %d\n",x,y,n);
    m[{x,y}]=n;
}
void work()
{
    int n;
    scanf("%d",&n);
    dfs(0,0,n);
    //printf("%d\n",cnt);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}
Responses