2022“杭电杯”中国大学生算法设计超级联赛（4）

本文主要是介绍2022“杭电杯”中国大学生算法设计超级联赛（4），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接

\(Link with Bracket Sequence II\)

为了方便去重，我们令 \(f_{i,j}\) 表示 \(i\) ~ \(j\) 组成的两端括号匹配的合法括号序列方案数，\(g_{i,j}\) 表示 \(i\) ~ \(j\) 组成的合法括号序列方案数，答案为 \(g_{1,n}\) 。
转移 \(g_{i,j} -> f_{i-1,j+1}\)，\(g_{i,j}=\sum\limits_{k=i}^{j-1}g_{i,k} \cdot f_{k+1,j}\) 。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=5e2+3,p=1e9+7;
int n,m,f[N][N],g[N][N],a[N];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL int mod(int x){return x>=p?x-p:x;}
IL void solve(){
    memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
    n=in(),m=in();
    for(int i=1;i<=n;++i) a[i]=in();
    for(int i=1;i<=n+1;++i) g[i][i-1]=1;
    for(int l=2;l<=n;++l)
      for(int i=1;i+l-1<=n;++i){
          int j=i+l-1;
          if(!a[i]&&!a[j]) f[i][j]=1ll*g[i+1][j-1]*m%p;
          else if((a[i]>0&&!a[j])||(!a[i]&&a[j]<0)||(a[i]>0&&!(a[i]+a[j]))) f[i][j]=g[i+1][j-1];
          else f[i][j]=0;
          g[i][j]=f[i][j];
          for(int k=i;k<j;++k) g[i][j]=mod(g[i][j]+1ll*g[i][k]*f[k+1][j]%p);
      }
    printf("%d\n",g[1][n]);
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

\(Link with Running\)

先求出最短路图，因为有 \(0\) 边，所以有环，可以卡 \(spfa\) 。故先 \(tarjan\) 缩点再拓扑排序求值。

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define pb push_back
using namespace std;
const int N=1e5+3;
struct hh{
    int to,e,p;
};
struct kk{
    int id;LL dis;
    bool operator<(const kk &a) const{
    return dis>a.dis;}
};
vector<hh>e1[N],e2[N],e3[N];
priority_queue<kk>q;
int n,m,vis[N],num,dfn[N],low[N],col[N],Col,sta[N],tp,deg[N];
LL d1[N],f[N];
IL int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL void dij(){
    memset(d1+1,63,8*n),memset(vis+1,0,4*n);
    q.push((kk){1,0}),d1[1]=0;
    while(q.size()){
        kk u=q.top();q.pop();
        if(vis[u.id]) continue;
        vis[u.id]=1;
        for(hh v:e1[u.id])
          if(d1[v.to]>d1[u.id]+v.e){
              d1[v.to]=d1[u.id]+v.e;
              q.push((kk){v.to,d1[v.to]});
          }
    }
}
void tarjan(int u){
    dfn[u]=low[u]=++num,sta[++tp]=u;
    for(hh v:e2[u])
      if(!dfn[v.to]) tarjan(v.to),low[u]=min(low[u],low[v.to]);
      else if(!col[v.to]) low[u]=min(low[u],dfn[v.to]);
    if(low[u]==dfn[u]){
        ++Col;
        while(sta[tp+1]^u) col[sta[tp--]]=Col;
    }
}
IL void topo(){
    memset(deg+1,0,4*n),memset(f+1,-63,8*n),f[col[1]]=0;
    for(int i=1;i<=n;++i)
      for(hh u:e2[i])
        if(col[i]^col[u.to])
          e3[col[i]].pb((hh){col[u.to],u.e,u.p}),++deg[col[u.to]];
    for(int i=1;i<=Col;++i) if(!deg[i]) sta[++tp]=i;
    while(tp){
        int u=sta[tp--];
        for(hh v:e3[u]){
            f[v.to]=max(f[v.to],f[u]+v.p);
            if(!--deg[v.to]) sta[++tp]=v.to;
        }
          
    }
}
IL void solve(){
    int x,y,e,p;
    n=in(),m=in();
    for(int i=1;i<=n;++i)
      e1[i].clear(),e2[i].clear(),e3[i].clear();
    for(int i=1;i<=m;++i)
      x=in(),e1[x].pb((hh){in(),in(),in()});
    dij();
    for(int i=1;i<=n;++i)
      for(hh u:e1[i])
        if(d1[i]+u.e==d1[u.to])
          e2[i].pb(u);
    num=tp=Col=0,memset(dfn+1,0,4*n),memset(low+1,0,4*n),memset(col+1,0,4*n);
    tarjan(1),topo();
    printf("%lld %lld\n",d1[n],f[col[n]]);
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

\(Magic\)

差分约束模板题。

#define IL inline
#define LL long long
using namespace std;
const int N=1e4+3;
struct hh{
    int to,nxt,w;
}e[N*3];
int n,m,k,num,fir[N],vis[N],cnt[N];
LL dis[N];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
IL void add(int x,int y,int w){e[++num]=(hh){y,fir[x],w},fir[x]=num;}
queue<int>q;
void spfa(){
    while(q.size()) q.pop();
    memset(dis,-63,8*(n+1));
    memset(cnt,0,4*(n+1));
    memset(vis,0,4*(n+1));
    dis[0]=0,q.push(0);
    while(!q.empty()){
        int u=q.front();q.pop();vis[u]=0;
        for(int i=fir[u],v;v=e[i].to,i;i=e[i].nxt)
          if(dis[v]<dis[u]+e[i].w){
              dis[v]=dis[u]+e[i].w;
              cnt[v]=cnt[u]+1;
              if(cnt[v]>=n+1){puts("-1");return;}
              if(!vis[v]) q.push(v),vis[v]=1;
          }
    }
    printf("%lld\n",dis[n]);
}
void solve(){
    int l,r,x;
    memset(fir,0,4*(n+1));
    n=in(),k=in(),num=0;
    for(int i=1;i<=n;++i) add(max(1,i-k+1)-1,min(n,i+k-1),in());
    for(int i=1;i<=n;++i) add(i-1,i,0);
    m=in();
    for(int i=1;i<=m;++i){
        l=in(),r=in(),x=in();
        add(r,l-1,-x);
    }
    spfa();
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

\(Link with Level Editor II\)

注意到 \(m\) 很小，我们可以用矩阵来储存边快速计算情况，用线段树快速求一段的方案情况，双指针跑即可。
蹲一个对顶栈做法。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N = 5e3 + 3, M = 21;
int n, Max, m, k, flag;
struct Martix {
    int r, c;
    LL a[M][M];
    IL void init(int r, int c) {
        this->r = r, this->c = c;
        for (int i = 1; i <= r; ++i)
            for (int j = 1; j <= c; ++j)
                a[i][j] = 0;
    }
    Martix operator*(const Martix &b) const {
        Martix d;
        d.init(r, b.c);
        for (int i = 1; i <= r; ++i)
            for (int j = 1; j <= b.c; ++j)
                for (int k = 1; k <= c; ++k)
                    d.a[i][j] += a[i][k] * b.a[k][j];
        for (int i = 1; i <= r; ++i)
            for (int j = 1; j <= b.c; ++j)
                if (d.a[i][j] > k)
                    d.a[i][j] = k + 1;
        return d;
    }
    IL int chk() { return a[1][m] <= k; }
} S[N], A, B;
struct segment {
#define ls k << 1
#define rs k << 1 | 1
    Martix s[N << 2];
    void build(int k, int l, int r) {
        if (l == r) {
            s[k] = S[l];
            return;
        }
        int mid = l + r >> 1;
        build(ls, l, mid), build(rs, mid + 1, r);
        s[k] = s[ls] * s[rs];
    }
    Martix query(int k, int l, int r, int ll, int rr) {
        if (l >= ll && r <= rr)
            return s[k];
        int mid = l + r >> 1;
        if (rr <= mid)
            return query(ls, l, mid, ll, rr);
        if (ll > mid)
            return query(rs, mid + 1, r, ll, rr);
        return query(ls, l, mid, ll, rr) * query(rs, mid + 1, r, ll, rr);
    }
} T;
IL int pd(int len) {
    for (int i = len; i <= n; ++i) {
        int j = i - len + 1;
        if (T.query(1, 1, n, j, i).chk())
            return 1;
    }
    return 0;
}
void solve() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; ++i)
        S[i].init(m, m);
    for (int i = 1; i <= n; ++i) {
        int l, x, y;
        scanf("%d", &l);
        while (l--)
            scanf("%d %d", &x, &y), S[i].a[x][y]++;
        for (int j = 1; j <= m; ++j)
            S[i].a[j][j]++;
    }
    T.build(1, 1, n);
    int l = 1, r = 1, ans = 1;
    A = S[1];
    for (; l <= n; ++l, A = T.query(1, 1, n, l, r)) {
        while (r < n && (B = A * S[r + 1], B.chk()))
            ++r, A = B;
        ans = max(ans, r - l + 1);
        if (r == n) break;
    }
    printf("%d\n", ans);
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--)
        solve();
    return 0;
}

\(BIT Subway\)

签到题，写一个分段函数即可（但赛时我智障惹）。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define LF double
using namespace std;
const int N=1e5+3;
const LF p1=0.8,p2=0.5;
int n,a[N];
IL LL in(){
	char c;int f=1;
	while((c=getchar())<'0'||c>'9')
	  if(c=='-') f=-1;
	LL x=c-'0';
	while((c=getchar())>='0'&&c<='9')
	  x=x*10+c-'0';
	return x*f;
}
IL LF ask1(LF x,LF y){
	if(x<100&&x+y>=100) return 100-x+ask1(100,y+x-100);
	if(x<200&&x+0.8*y>=200) return 200-x+(y-(200-x)/0.8)*0.5;
	if(x<100) return y;
	if(x<200) return 0.8*y;
	return 0.5*y;
}
IL LF ask2(LF x,LF y){
	if(x<100) return y;
	if(x<200) return 0.8*y;
	return 0.5*y;
}
void solve(){
	n=in();LF ans1=0,ans2=0;
	for(int i=1;i<=n;++i) a[i]=in();
	for(int i=1;i<=n;++i) ans1+=ask1(ans1,a[i]),ans2+=ask2(ans2,a[i]);
	printf("%.3lf %.3lf\n",ans1,ans2);
}
int main()
{
	int T=in();
	while(T--) solve();
	return 0;
}

\(Climb Stairs\)

假设我们在 \(now\) 层，我们必然是跳到 \(now+x\) 层，再往下走到 \(now+1\) 层，显然每次跳的楼层尽可能少会更优。
我们先求出到 \(now+1\) 层的必要条件，即假设我们跳到某 \(now+x\) 层再向下可以全吃掉能否在 \(now+1\) 层时能够打败怪物，这个可以二分求出。
但我们是默认 \(now+2\) 到 \(now+x\) 层是可以全吃掉的，事实上我们并不知道，所以我们需要再对这些层也进行上述操作，直到满足条件。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
#define LF double
using namespace std;
const int N=1e5+3;
int n,k,a[N];
LL pre[N],st;
IL LL in(){
	char c;int f=1;
	while((c=getchar())<'0'||c>'9')
	  if(c=='-') f=-1;
	LL x=c-'0';
	while((c=getchar())>='0'&&c<='9')
	  x=x*10+c-'0';
	return x*f;
}
IL int get(LL s,int pos){
	int l=pos,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(s+pre[mid]-pre[pos]>=a[pos]) r=mid;
		else l=mid+1;
	}
	return l;
}
void solve(){
	n=in(),st=in(),k=in();
	for(int i=1;i<=n;++i) a[i]=in(),pre[i]=a[i]+pre[i-1];
	int now=0,up=0;
	while(up<n){
		int Max=up+1,i=up;
		while(i<Max){
			int to=get(st,++i);
			if(st+pre[to]-pre[i]<a[i]){puts("NO");return;}
			Max=max(Max,to);
		}
		if(Max>now+k){puts("NO");return;}
		st+=pre[Max]-pre[up],now=up+1,up=Max;
	}
	puts("YES");
}
int main()
{
	int T=in();
	while(T--) solve();
	return 0;
}

\(Fall with Full Star\)

嫖一位学长的博客，里面讲得很详细。
链接

\(Link is as bear\)

如果序列中有连续的两个 \(0\) ，最终序列可以是任意数的异或和。
如果我们要不选这两个 \(0\) 旁边的数，我们可以连续进行两次操作把那个数也变成 \(0\)，如果要选择，我们可以通过操作把那个数移到一边，再把要删去的数删去。
于是，如果我们记要选的数标记为 \(1\)，不选的标记为 \(0\) 。
若有两个相连的 \(0\) ，我们可以把它们的数值变为 \(0\)。
若有多个相连的 \(1\) ，我们可以把它们合并到一个位置中，并产生相连的 \(0\)。
对于 \(0,1\) 相间的情况，因为存在 \(i<j\) ，\(a_i=a_j\) ，我们可以任意决定 \(i,j\) 的取法使得这种情况不存在。
线性基求出最大异或和即可。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=1e5+3;
int n,a[N];
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
struct LB{
    LL a[64];
    IL void clear(){memset(a,0,sizeof(a));}
    IL void ins(LL x){
        for(int i=63;~i;--i)
          if(x>>i&1){
              if(a[i]) x^=a[i];
              else{a[i]=x;return;}
          }
    }
    IL LL get_Max(){
        LL Max=0;
        for(int i=63;~i;--i)
          if((Max^a[i])>Max) Max^=a[i];
        return Max;
    }
}B;
void solve(){
    n=in();B.clear();
    while(n--) B.ins(in());
    printf("%lld\n",B.get_Max());
}
int main()
{
    int T=in();
    while(T--) solve();
    return 0;
}

这篇关于2022“杭电杯”中国大学生算法设计超级联赛（4）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

2022“杭电杯”中国大学生算法设计超级联赛（4）

链接

\(Link with Bracket Sequence II\)

\(Link with Running\)

\(Magic\)

\(Link with Level Editor II\)

\(BIT Subway\)

\(Climb Stairs\)

\(Fall with Full Star\)

\(Link is as bear\)

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯