2022暑期hdu4

暑期hdu4"/>

2022暑期hdu4

1 Link with Bracket Sequence 2

题解

区间DP，设 表示 为合法括号序列且 上括号相互匹配的方案数， 表示 区间形成一 个合法括号序列的方案数，转移为：

• 枚举i, j 位置上填写的内容，如果形成匹配的括号对，则：f_{i,j} = k*g_{i+1,j-1}，其中k为使得i,j上括号相匹配的方案数
• 一般地，g_{i,j}=g_{i,k}+f_{k+1,j}

答案取g_{1,n}即可

复杂度O(n^3)

标程

#include <cstdio>
#include <cstring>
#define MN 500using ll = long long;const int mod = 1000000007;int n,m;
int a[MN+5];
int f[MN+5][MN+5],g[MN+5][MN+5];void solve(){memset(f,0,sizeof(f));memset(g,0,sizeof(g));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}if(n&1){puts("0");return;}for(int i=0;i<=n;i++){g[i+1][i] = 1;}for(int len=2;len<=n;len+=2){for(int l=1;l+len-1<=n;l++){int r = l+len-1;if(a[l]>=0&&a[r]<=0){int e;if(a[l]==0&&a[r]==0){e = m;}else if(a[l]==0||a[r]==0){e = 1;}else if(a[l]+a[r]==0){e = 1;}else{e = 0;}f[l][r] = (ll)g[l+1][r-1]*e%mod;}for(int nl=l;nl<=r;nl+=2){g[l][r] = (g[l][r]+(ll)g[l][nl-1]*f[nl][r])%mod;}}}printf("%d\n",g[1][n]);
}int main(){int T;scanf("%d",&T);//T = 1;while(T--) solve();
}

1002 Link with Running

题解

 整体思路：在最短路图上跑最长路。

先用dijkstra在第一个权值上跑出最短路图来，并求出第一个答案（最短路图的边权为第二个权 值）。 注意到第一个权上可能为0，因此它并不一定是个DAG，需要用trajan将强连通分量缩起来。 获得了DAG之后，只需要在DAG上求最长路即可得到第二个答案。

标程

#include <cstdio>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <vector>
#define MN 100000using std::min;
using std::max;
using std::function;
using std::greater;
using std::swap;
using std::stack;
using std::queue;
using std::priority_queue;
using std::vector;using ll = long long;const ll INF = 1e18;struct Edge{int v,w1,w2;
};namespace GetSpg{ll dis[MN+5];vector<Edge> e[MN+5];void clear(int n){for(int i=1;i<=n;i++){e[i].clear();}}void addEdge(int u,int v,int w1,int w2){e[u].push_back({v,w1,w2});}void dijkstra(int n,int S){using pii = std::pair<ll,int>;priority_queue<pii,vector<pii>,greater<pii>> pq;for(int i=1;i<=n;i++){dis[i] = INF;}pq.push({dis[S]=0,S});while(!pq.empty()){int u = pq.top().second;ll d = pq.top().first;pq.pop();if(d!=dis[u]) continue;for(Edge edge:e[u]){int v = edge.v;int w = edge.w1;if(dis[u]+w<dis[v]){dis[v] = dis[u]+w;pq.push({dis[v],v});}}}}void solve(int n,function<void(int,int,int,int)> addEdge){dijkstra(n,1);for(int u=1;u<=n;u++){if(dis[u]==INF) continue;for(Edge edge:e[u]){if(dis[u]+edge.w1==dis[edge.v]){addEdge(u,edge.v,edge.w1,edge.w2);}}}}}namespace GetDag{vector<Edge> e[MN+5];stack<int> s;bool ins[MN+5];int low[MN+5],dfn[MN+5],scc[MN+5];int dfnCnt=0,sccCnt=0;void clear(int n){for(int i=1;i<=n;i++){e[i].clear();ins[i] = false;dfn[i] = low[i] = scc[i] = 0;}dfnCnt = 0;sccCnt = 0;while(!s.empty()) s.pop();}void addEdge(int u,int v,int w1,int w2){e[u].push_back({v,w1,w2});}void tarjan(int u){dfn[u] = ++dfnCnt;low[u] = dfn[u];s.push(u);ins[u] = true;for(Edge edge:e[u]){int v = edge.v;if(dfn[v]){if(ins[v]){low[u] = min(low[u],dfn[v]);}}else{tarjan(v);low[u] = min(low[u],low[v]);}}if(low[u]==dfn[u]){int v;++sccCnt;do{v = s.top();s.pop();ins[v] = false;scc[v] = sccCnt;}while(u!=v);}}void solve(int& n,function<void(int,int,int,int)> addEdge,bool isLoop[]){for(int i=1;i<=n;i++){if(!dfn[i]){tarjan(i);}}for(int u=1;u<=n;u++){for(Edge edge:e[u]){int v = edge.v;if(scc[u]==scc[v]){if(edge.w2>0){isLoop[scc[u]] = true;}}else{addEdge(scc[u],scc[edge.v],edge.w1,edge.w2);}}}}}namespace GetLp{int din[MN+5];bool isLoop[MN+5];vector<Edge> e[MN+5];struct Dis{ll d;Dis(ll d=0){this->d = d;}Dis operator + (const Dis& that)const{if(d==-INF||that.d==-INF) return Dis(-INF);if(d==INF||that.d==INF) return Dis(INF);return Dis(d+that.d);}bool operator < (const Dis& that)const{return this->d < that.d;}};Dis f[MN+5];void clear(int n){for(int i=1;i<=n;i++){din[i] = 0;isLoop[i] = false;e[i].clear();}}void addEdge(int u,int v,int w1,int w2){e[u].push_back({v,w1,w2});din[v]++;}void solve(int n,int S){for(int i=1;i<=n;i++){f[i] = -INF;}f[S] = 0;queue<int> q;for(int i=1;i<=n;i++){if(din[i]==0) q.push(i);}while(!q.empty()){int u = q.front();q.pop();if(isLoop[u]) f[u] = f[u]+INF;for(Edge edge:e[u]){int v = edge.v;int w = edge.w2;f[v] = max(f[v],f[u]+w);if(--din[v]==0){q.push(v);}}}}
}void solve(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v,w1,w2;scanf("%d%d%d%d",&u,&v,&w1,&w2);GetSpg::addEdge(u,v,w1,w2);}GetSpg::solve(n,GetDag::addEdge);GetDag::solve(n,GetLp::addEdge,GetLp::isLoop);GetLp::solve(GetDag::sccCnt,GetDag::scc[1]);printf("%lld %lld\n",GetSpg::dis[n],GetLp::f[GetDag::scc[n]].d);GetSpg::clear(n);GetDag::clear(n);GetLp::clear(n);
}int main(){int T;scanf("%d",&T);while(T--) solve();
}

1004 Link with Equilateral Triangle

题解

输出一堆No即可。

证明： 对于一个合法的解，应当满足不存在同时包含0,1,2的三角形，下面我们证明这样的三角形一定存在。 左下角必然是1，右下角必然是0，底边不能含有2，则底边上必然有奇数条1-0的边，这些边都属于一个 小三角形。考虑其他的0-1边，由于不在两个斜边上，其他的0-1边必然属于两个三角形。因此“每个三角 形内0-1边的数量”的和必然为奇数。 但是，假设不存在0-1-2的三角形，则所有三角形都必然包含0条或2条的0-1边，产生了矛盾。 因此一定存在0-1-2的三角形

标程

#include <cstdio>void solve(){int n;scanf("%d",&n);puts("No");
}int main(){int T;scanf("%d",&T);while(T--) solve(); 
}

5 Link with level Editor II

题解

考虑用双指针求解，用矩阵的方式维护1~m的路径数量。 发现矩阵并非全部可逆，难以进行删除操作，使用对顶栈的技巧规避掉删除操作即可。 复杂度O(nm^3)。

标程

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MN 5000
#define MM 20using std::max;using ll = long long;const int INF = 1000000001;namespace GTI
{char gc(void){const int S = 1 << 16;static char buf[S], *s = buf, *t = buf;if (s == t) t = buf + fread(s = buf, 1, S, stdin);if (s == t) return EOF;return *s++;}ll gti(void){ll a = 0, b = 1, c = gc();for (; !isdigit(c); c = gc()) b ^= (c == '-');for (; isdigit(c); c = gc()) a = a * 10 + c - '0';return b ? a : -a;}int gts(char *s){int len = 0, c = gc();for (; isspace(c); c = gc());for (; c != EOF && !isspace(c); c = gc()) s[len++] = c;s[len] = 0;return len;}int gtl(char *s){int len = 0, c = gc();for (; isspace(c); c = gc());for (; c != EOF && c != '\n'; c = gc()) s[len++] = c;s[len] = 0;return len;}
}
using GTI::gti;
using GTI::gts;
using GTI::gtl;int n,m,k;struct Matrix{int a[MM+2][MM+2];Matrix(int x=0){memset(a,0,sizeof(a));for(int i=1;i<=m;i++){a[i][i] = x;}}Matrix operator * (const Matrix& that)const{Matrix ret;for(int i=1;i<=m;i++){for(int j=1;j<=m;j++){for(int k=1;k<=m;k++){ret.a[i][j] = limit(ret.a[i][j]+(ll)this->a[i][k]*that.a[k][j]);}}}return ret;}static int limit(ll x){if(x>=INF) return INF;else return x;}};Matrix d[MN+5],b[MN+5];bool check(const Matrix& lhs,const Matrix& rhs){int ans = 0;for(int i=1;i<=m;i++){ans = Matrix::limit(ans+(ll)lhs.a[1][i]*rhs.a[i][m]);}return ans<=k;
}void solve(){n = gti();m = gti();k = gti();for(int i=1;i<=n;i++){int l = gti();d[i] = 1;while(l--){int u = gti();int v = gti();d[i].a[u][v] = 1;}}int ans = 0;Matrix csuf = 1;b[0].a[1][m] = INF;for(int r=1,l=0,lim=0;r<=n;r++){csuf = csuf*d[r];while(!check(b[l],csuf)){l++;if(l>lim){b[r] = d[r];for(int i=r-1;i>lim;i--){b[i] = d[i]*b[i+1];}lim = r;csuf = 1;}}ans = max(ans,r-l+1);}printf("%d\n",ans);
}int main(){int T = gti();while(T--) solve();
}

6 BIT Subway

题解

签到题，阅读理解题。 真实的情况很容易算，DLee的价格实际上是一个关于总原票价 的分段函数：

ans=

• x (0<=x<100)
• (x-100)*0.8+100 (100<=x<225)
• (x-225)*0.5 +200 (225<=x)

标程

#include<bits/stdc++.h>
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define Fill(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf=2139062143;
const int MOD=998244353;
const int MAXN=200100;
inline int read()
{int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}return x*f;
}
inline ll readll()
{ll x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}return x*f;
}
namespace CALC
{inline int pls(int a,int b){return a+b>=MOD?a+b-MOD:a+b;}inline int mns(int a,int b){return a-b<0?a-b+MOD:a-b;}inline int mul(int a,int b){return (1LL*a*b)%MOD;}inline void inc(int &a,int b){a=pls(a,b);}inline void dec(int &a,int b){a=mns(a,b);}inline void tms(int &a,int b){a=mul(a,b);}inline int qp(int x,int t,int res=1){for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);return res;}inline int Inv(int x){return qp(x,MOD-2);}
}
using namespace CALC;
int n;
db c1,c2,a[MAXN];
int main()
{rep(T,1,read()){n=read();c1=c2=0;rep(i,1,n) {a[i]=read();db x=0;if(c2>=200) c2+=0.5*a[i];else if(c2>=100) c2+=0.8*a[i];else c2+=a[i];if(c1<100) x=min(a[i],100-c1),c1+=x,a[i]-=x;if(a[i]>0&&c1<200) x=min(a[i]*0.8,200-c1),c1+=x,a[i]-=x/0.8;if(a[i]>0&&c1>=200) c1+=a[i]*0.5;//cout<<c1<<" "<<c2<<endl;}printf("%.3lf %.3lf\n",c1,c2);}
}

7 Climb Stairs

题解

比较签的题。 由于题目要求必须把所有怪物打完，所以跳过的怪物还必须得走回去打败才行。我们要从当前位置 ， 找到一个右端点 ，使得可以按照 的顺序打败这一段的怪物。不难看出 更小的 时候不会更劣。直接暴力维护当前想要先到达的右端点（满足 ），用线段树维护一下 的 能 力 值 血 量 ，一旦扩展到r位置，就将 区间加 。找到最小的满足要求的r就可以继续更新位置， 更新位置后，相当于实际上完成了击杀 的过程，所以将后面的区间加上相应的值。由于每 个右端点只会被计算一次，所以时间复杂度是 的。

标程

#include<bits/stdc++.h>
#define rep(i,s,t) for(int i=(s),i##end=(t);i<=i##end;++i)
#define dwn(i,s,t) for(int i=(s),i##end=(t);i>=i##end;--i)
#define ren for(int i=fst[x];i;i=nxt[i])
#define Fill(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int inf=2139062143;
const int MOD=998244353;
const int MAXN=200100;
inline int read()
{int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}return x*f;
}
inline ll readll()
{ll x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}return x*f;
}
namespace CALC
{inline int pls(int a,int b){return a+b>=MOD?a+b-MOD:a+b;}inline int mns(int a,int b){return a-b<0?a-b+MOD:a-b;}inline int mul(int a,int b){return (1LL*a*b)%MOD;}inline void inc(int &a,int b){a=pls(a,b);}inline void dec(int &a,int b){a=mns(a,b);}inline void tms(int &a,int b){a=mul(a,b);}inline int qp(int x,int t,int res=1){for(;t;t>>=1,x=mul(x,x)) if(t&1) res=mul(res,x);return res;}inline int Inv(int x){return qp(x,MOD-2);}
}
using namespace CALC;
int n,a[MAXN],k,las,cur,l,r;
pair<ll,int> q[MAXN];
ll sum[MAXN],f[MAXN],mxf[MAXN];
ll mn[MAXN<<2];
void build(int k,int l,int r)
{if(l==r) {mn[k]=f[l];return ;}int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);mn[k]=min(mn[k<<1],mn[k<<1|1]);
}
int res=inf;
void query(int k,int l,int r,int a,int b,int w)
{if(a<=l&&r<=b){if(mn[k]>w||res!=inf) return ;if(l==r) {res=l;return ;}int mid=l+r>>1;if(mn[k<<1]<=w) query(k<<1,l,mid,a,b,w);else if(mn[k<<1|1]<=w) query(k<<1|1,mid+1,r,a,b,w);return ;}int mid=l+r>>1;if(a<=mid) query(k<<1,l,mid,a,b,w);if(b>mid) query(k<<1|1,mid+1,r,a,b,w);
}
int solve()
{n=read(),a[0]=sum[0]=read(),k=min(read(),n);rep(i,1,n) a[i]=read(),sum[i]=sum[i-1]+a[i];f[0]=sum[0]<<1;rep(i,1,n) f[i]=max(sum[i]+a[i],f[i-1]);rep(i,0,n) f[i]=f[i]-sum[i];//rep(i,0,n) cout<<f[i]<<" ";puts("");build(1,1,n);las=-1,cur=0;while(cur!=n){res=inf;query(1,1,n,cur+1,min(las+k+1,n),sum[cur]);//cout<<las<<" "<<cur<<" "<<res<<endl;if(res==inf) return 0;las=cur,cur=res;}return 1;
}
int main()
{rep(T,1,read()) puts(solve()?"YES":"NO");
}