• 欢迎光临~

2022HDU多校第三场

开发技术 开发技术 2022-07-29 次浏览

2022HDU多校第三场

过程

开场1h速切2签到,但吉吉卡到了第三个签到12,同时我也卡到了02,这波属于双双坐牢。02我一眼想到了二分时间加状压dp,然后帧的时间从0开始也被对面二聪提醒,但是状压怎么写一直困扰,一直在纠结当在一个状态中加入技能时,这个技能该如何安排,一直想不通,然后一直坐牢,没打代码。但赛后把别人代码一看,突然发现自己竟一直在与空气斗智斗勇,因为状压dp的写法就不需要考虑这个问题(补题0.5h就补了),当时应该第一时间打代码,不能让队友闲着,至少应该把框架搭起来,也让队友好调试。最后我又返回看12这个第三个签到,交了发dfs结果爆栈RE,改成bfs结果TLE,但正确性应该没问题,最后吉吉魔改减少了dfs的深度然后过了。接下来吉吉光速切掉11,4题结束,但02属实有点可惜,属于是我不自信了,思维不够开放,把吉吉演了。

总结

1.签到卡30min以上就换人看,不要再纠结。
2.知道题目大概写法,且手头开不出其他题时,可以先把准备工作写好,大不了扔给队友。

补题

02

一看n为18,就在暗示状态压缩dp,然后因为要最小时间,可以联想到耳二分判断,接下来就是状压转移方程。

我们令(dp[S])表示技能使用状态(S)下在规定时间内可达到的最大伤害。这里看上去因为技能有作用时间需要考虑使用顺序,但dp转移的过程中保证了一个新的状态,一定是从以前的某个最优状态转移来的,因此,对于新加的技能,默认最后一个发动,因其不在最后一个发动的情况已经被其他状态所包含。

需要注意的是,因为技能有作用时间,所以在规定时间内技能伤害不一定能打满,所以需要判断是否能释放该技能,且释放该技能后伤害能打出多少。
状态压缩转移为以下形式,详见完整代码

   rep(i,0,(1<<n)-1){
      rep(j,0,n-1){
         if(i&1<<j){
            int last=i^(1<<j);
            if(last状态已经超时) continue;
            if(last状态时间 + 技能伤害时间<= 规定时间) 
               dp[i]=max(dp[last]+伤害打满);
            else dp[i]=maX(dp[last]+打部分伤害);
         }
      }
   }
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rpe(i,a,b) for(int i=a;i>=b;--i)
#define pts putchar('n')
#define ptc putchar(' ')
#define pb push_back 
#define pty puts("YES")
#define ptn puts("NO")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int N=2e5;
const int maxn=2*N+9;
const int inf=0x7f7f7f7f;
const ll linf=1e18;
const int maxm=1000*N+9;
const int mod=1e9+7;
const int base=31;
const double eps=1e-4;
int n;
ll h;
ll t[maxn],tt[20],len[maxn];
ll d[20][maxn];
ll dp[maxn];
bool check(int tim){
    rep(i,0,(1<<n)-1){
        dp[i]=0;
        rep(j,0,n-1){
            if(i&(1<<j)){
                int last=i^(1<<j);
                if(t[last]>=tim) continue;
                if(t[last]+len[j+1]<=tim) 
                  dp[i]=max(dp[i],dp[last]+d[j+1][len[j+1]]);
                else dp[i]=max(dp[i],dp[last]+d[j+1][tim-t[last]]);
            }
        }
        if(dp[i]>=h) return 1;
    }
    return 0;
}
void solve(){
    cin>>n>>h;
    rep(i,1,n){
        scanf("%lld %lld",&tt[i],&len[i]);
        rep(j,1,len[i]) {
            scanf("%lld",&d[i][j]);
            d[i][j]+=d[i][j-1];
        }
    }
    ll tmp=0;
    rep(i,1,n){
        tmp+=d[i][len[i]];
    }
    if(tmp<h) {puts("-1");return;}
    rep(i,0,(1<<n)-1){
        t[i]=0;
        rep(j,0,n-1){
            if(i&(1<<j)){
                t[i]+=tt[j+1];
            }
        }
    }
    int l=1,r=2e6;int ans=r;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("%dn",ans-1);
}
int main (){
    int T;cin>>T;
    while(T--){
        solve();
    }
   return 0;
} 

03

签到,注意getline(cin,s)的使用即可

09

签到,每次在ddl处完成当前积累的任务,知道没有ddl,同时能多拿就多拿。

11

本题与曼哈顿距离有关,当不存在(w_i)限制时,求最远曼哈顿距离,我们可以按照(x+y,x-y)将原有点排序,对于每一个点求其曼哈顿距离最大,即与最大或最小的(x+y,x-y)的点的距离。此处可以扩展至(k)维,每次求解复杂度为(n*2^k)
然而本题有(w_i)的限制,相当于对于每一个询问点,如果里第(i)个给定点太远,则距离为(w_i),否则即为曼哈顿距离。
那么对于一个询问点,我们需要知道哪个给定点找到其距离最远且满足(w_i)限制,这里我们按照(x+y,x-y)排序后,我们枚举所求点,用指针枚举给定点,随着所求点(x+y)递增时,其与指针所指向给定点的距离一定递增,当满足指针所指向给定点的(w_i)时,该所求点答案与当前两点间距离取最大值,同时当两点间距离大于(w_i)时,用一个临时变量表示所有两点距离大于(w_i)的最大值,所求点的答案也对该临时变量取最大值。
再对(x+y)倒序来一遍,(x-y)排序同理,即可求得答案,复杂第(O(nlogn+q))

同时题解做法也很精妙,采用在线做法,将所有给定点按照(w_i)从小到大排序,然后分别按照(x+y,x-y,-x+y,-x-y)来来预处理出后缀距离最大值,就可以在线性时间内求出询问点到后缀给定点的最大距离。
选取按(w_i)排序后的第k个城镇,(O(1))求出所求点((x',y'))到第(k..n)个城镇的最大距离(d),有两种情况:
1. (w_k<d),那么第(k...n)个城镇对答案的贡献至少为(w_k)。用(w_k)更新答案,且(1...k)城镇的(w)值均不超过(w_k),因此它们不可能更新答案,考虑范围([k+1,n])
2. (w_k>=d),那么第(k...n)个城镇对答案贡献为(d),用d更新答案,缩小范围([1,k-1])
那么此时二分即可,复杂度(O((n+q)logn))

//队友做法
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rpe(i,a,b) for(int i=a;i>=b;--i)
#define pts putchar('n')
#define ptc putchar(' ')
#define pb push_back 
#define pty puts("YES")
#define ptn puts("NO")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int N=3e5;
const int maxn=2*N+9;
const int inf=0x7f7f7f7f;
const ll linf=1e18;
const int maxm=1000*N+9;
const int mod=1e9+7;
const int base=31;
const double eps=1e-4;

int n,m;
struct node{
 int x,y;
 int z;
};
node p[maxn],q[maxn];
int ans[maxn];
bool cmp1(node a,node b){return a.x+a.y<b.x+b.y;}
bool cmp2(node a,node b){return a.x-a.y<b.x-b.y;}
inline int dist(node a,node b){return abs(a.x-b.x)+abs(a.y-b.y);}
void solve(){
 cin>>n>>m;
 rep(i,1,n) scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].z);
 rep(i,1,m) scanf("%d %d",&q[i].x,&q[i].y),q[i].z=i;
 sort(p+1,p+1+n,cmp1);sort(q+1,q+1+m,cmp1);
 //x+y
 int now=1,tmp=0;
 rep(i,1,m){
  int dis=q[i].x+q[i].y-p[now].x-p[now].y;;
  while(dis>p[now].z&&now<=n){
   tmp=max(tmp,p[now].z);
   now++;dis=q[i].x+q[i].y-p[now].x-p[now].y;
  }
  if(now<=n)ans[q[i].z]=max(ans[q[i].z],max(tmp,dis));
  else ans[q[i].z]=max(ans[q[i].z],tmp);
 }
 now=n,tmp=0;
 rpe(i,m,1){
  int dis=p[now].x+p[now].y-q[i].x-q[i].y;
  while(dis>p[now].z&&now>0){
   tmp=max(tmp,p[now].z);
   now--;dis=p[now].x+p[now].y-q[i].x-q[i].y;
  }
  if(now>0)ans[q[i].z]=max(ans[q[i].z],max(tmp,dis));
   else ans[q[i].z]=max(ans[q[i].z],tmp);
 }
 //x-y
 sort(p+1,p+1+n,cmp2);sort(q+1,q+1+m,cmp2);
 now=1,tmp=0;
 rep(i,1,m){
  int dis=q[i].x-q[i].y-(p[now].x-p[now].y);
  while(dis>p[now].z&&now<=n){
   tmp=max(tmp,p[now].z);
   now++;dis=q[i].x-q[i].y-(p[now].x-p[now].y);
  }
  if(now<=n)ans[q[i].z]=max(ans[q[i].z],max(tmp,dis));
  else ans[q[i].z]=max(ans[q[i].z],tmp);
 }
 now=n,tmp=0;
 rpe(i,m,1){
  int dis=p[now].x-p[now].y-(q[i].x-q[i].y);
  while(dis>p[now].z&&now>0){
   tmp=max(tmp,p[now].z);
   now--;dis=p[now].x-p[now].y-(q[i].x-q[i].y);
  }
  if(now>0)ans[q[i].z]=max(ans[q[i].z],max(tmp,dis));
  else ans[q[i].z]=max(ans[q[i].z],tmp);
 }
 rep(i,1,m) printf("%dn",ans[i]);
 //clear
 rep(i,1,m) ans[i]=0;
}
int main (){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
 return 0; 
} 
//std
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005,inf=2100000000;
int Case,n,m,i,x,y,a[N],b[N],c[N],d[N];
struct E{int x,y,w;}e[N];
inline bool cmp(const E&a,const E&b){return a.w<b.w;}
inline void up(int&a,int b){a<b?(a=b):0;}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
    sort(e+1,e+n+1,cmp);
    a[n+1]=b[n+1]=c[n+1]=d[n+1]=-inf;
    for(i=n;i;i--){
      a[i]=max(a[i+1],-e[i].x-e[i].y);
      b[i]=max(b[i+1],-e[i].x+e[i].y);
      c[i]=max(c[i+1],e[i].x-e[i].y);
      d[i]=max(d[i+1],e[i].x+e[i].y);
    }
    while(m--){
      scanf("%d%d",&x,&y);
      int l=1,r=n,mid,tmp,ans=0;
      while(l<=r){
        mid=(l+r)>>1;
        tmp=x+y+a[mid];
        up(tmp,x-y+b[mid]);
        up(tmp,-x+y+c[mid]);
        up(tmp,-x-y+d[mid]);
        if(e[mid].w<tmp){
          l=mid+1;
          up(ans,e[mid].w);
        }else{
          r=mid-1;
          up(ans,tmp);
        }
      }
      printf("%dn",ans);
    }
  }
}

12

我盲猜状态甚少,暴力dfs一波,然后爆栈了,改成bfs然后T了,随后队友在dfs中优化一波卡时限过了。

而正解是(dp),设(f_{i,j})表示P前i项匹配上了S,且(P_i)匹配(S)中数字(P_i)第j次出现的位置时,有多少种合法的方案,由于S中每个数字出现次数都为2,因此状态数(O(n))。转移时枚举(P_{i+1})匹配哪个位置,那么(P_i)匹配的位置与(P_{i+1})匹配的位置中间的那段连续子串需要完全匹配(Q)中对应的字符串,使用字符串hash可以(O(n))判断。

//暴力优化,卡过了
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rpe(i,a,b) for(int i=a;i>=b;--i)
#define pts putchar('n')
#define ptc putchar(' ')
#define pb push_back 
#define pty puts("YES")
#define ptn puts("NO")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int N=3e5;
const int maxn=2*N+9;
const ll inf=(1LL<<30);
const ll linf=1e18;
const int maxm=1000*N+9;
const int mod=998244353;
const int base=31;
const double eps=1e-4;
int n;
int p[maxn],q[maxn],s[maxn];
int read(){
    int a=1,b=0;char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') a=-1;c=getchar();}
    while(c<='9'&&c>='0'){b=(b<<3)+(b<<1)+c-'0';c=getchar();}
    return a*b;
}
map<ll,int>mp;
ll dfs(int a,int b){
    if(a==n+1&&b==n+1) return 1;
    if(mp[a*inf+b]) return mp[a*inf+b];
    ll tmp=0;
    if(a==n+1){
        while(q[b]==s[n+b]&&b<=n) b++;
        if(b!=n+1) tmp=0;
        else tmp=1;
    }
    else if(b==n+1){
        while(p[a]==s[n+a]&&a<=n) a++;
        if(a!=n+1) tmp=0;
        else tmp=1;
    }   
    else if(p[a]==s[a+b-1]&&q[b]==s[a+b-1]) {
        tmp=(dfs(a+1,b) + dfs(a,b+1));
    }
    else if(p[a]==s[a+b-1]){
        int aa=a;
        while(p[aa]==s[aa+b-1]&&q[b]!=s[aa+b-1]&&aa<=n) aa++;
        tmp=dfs(aa,b);
    }
    else if(q[b]==s[a+b-1]){
        int bb=b;
        while(q[bb]==s[a+bb-1]&&p[a]!=s[a+bb-1]&&bb<=n) bb++;
        tmp=dfs(a,bb);
    }
    while(tmp>=mod) tmp-=mod;
    mp[a*inf+b]=tmp;
    return tmp;
}
void solve(){
    mp.clear();
    cin>>n;
    rep(i,1,n) p[i]=read();
    rep(i,1,n) q[i]=read();
    rep(i,1,n<<1) s[i]=read();
    printf("%lldn",dfs(1,1));
}
int main (){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
 return 0; 
} 

待补08

计算几何,共50条线段,故(O(C(100,3)*100)枚举检查,时间复杂度O(n^4)),需要特判所有点共线情况。

程序员灯塔
转载请注明原文链接:2022HDU多校第三场
喜欢 (0)