1. 云图网首页
  2. 技术专区
  3. 编程笔记

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;
}

原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/278828.html

赞 (0)
0
上一篇 2022年8月4日
下一篇 2022年8月4日

相关推荐

发表回复

登录后才能评论