ACL Beginner Contest 总结——F多项式待补

A - Repeat ACL

签到题1

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=500010; int main() { IO; int T=1; //cin>>T; while(T--) { int n; cin>>n; string s="ACL"; while(n--) cout<<s; cout<<'\n'; } return 0; }

B - Integer Preference

签到题2

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; typedef long long ll; int main() { IO; int T=1; //cin>>T; while(T--) { ll a,b,c,d; cin>>a>>b>>c>>d; if(b<c||d<a) cout<<"No\n"; else cout<<"Yes\n"; } return 0; }

C - Connect Cities

简单并查集维护连通关系即可

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; const int N=500010; int n,m; int p[N]; int find(int x) { return x==p[x]?x:p[x]=find(p[x]); } int main() { IO; int T=1; //cin>>T; while(T--) { cin>>n>>m; for(int i=1;i<=n;i++) p[i]=i; while(m--) { int a,b; cin>>a>>b; p[find(a)]=find(b); } int res=0; for(int i=1;i<=n;i++) if(i==p[i]) res++; cout<<res-1<<'\n'; } return 0; }

D - Flat Subsequence

刚开始把相邻看成整个子序列绝对值差都不大于K，于是先做的E 值域线段树优化dp 状态表示：$f_i$考虑前$i$个数，且选择$a_i$作为子序列结尾的集合。 状态转移：$f_i=max(f_i,f_j+1)(|a_j-a_i|\le K)$ 考虑优化：能够更新$f_i$必须满足$a_i-K\le a_j\le a_i+K$，于是考虑权值线段树维护区间，每次把$a_i$打到权值线段树中，值为$f_i$，然后只需要求区间最值即可。单点修改、区间查询。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<iostream> #include<algorithm> using namespace std; const int N=300010; const ll mod=998244353; int f[N]; int n,k; int a[N]; struct node { int l,r;//值域 int val; }tree[N*4]; void pushup(int u) { tree[u].val=max(tree[u<<1].val,tree[u<<1|1].val); } void build(int u,int l,int r) { tree[u]={l,r,0}; if(l==r) return; int mid=l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); } void modify(int u,int pos,int val) { if(tree[u].l==tree[u].r) { tree[u].val=max(tree[u].val,val); return; } int mid=tree[u].l+tree[u].r>>1; if(pos<=mid) modify(u<<1,pos,val); else modify(u<<1|1,pos,val); pushup(u); } int query(int u,int l,int r) { if(tree[u].l>=l&&tree[u].r<=r) return tree[u].val; int mid=tree[u].l+tree[u].r>>1; int v=0; if(l<=mid) v=max(v,query(u<<1,l,r)); if(r>mid) v=max(v,query(u<<1|1,l,r)); return v; } int main() { IO; int T=1; //cin>>T; while(T--) { cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; build(1,0,300000); int res=0; for(int i=1;i<=n;i++) { int l=max(0,a[i]-k),r=min(300000,a[i]+k); f[i]=1+query(1,l,r); modify(1,a[i],f[i]); res=max(res,f[i]); } cout<<res<<'\n'; } return 0; }

E - Replace Digits

线段树维护十进制下的数即可（取模） 预处理num[][]数组，num[i][j]表示$iii\dots i(j个i)$，ten[]数组，ten[i]表示$10^i$，注意取模保存，有了这两个数组，区间合并就很好写了。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=200010; const ll mod=998244353; int n,m; struct node { int l,r; ll s; int lazy; }tree[N*4]; ll ten[N]; ll num[10][N]; void pushup(int u) { int lenr=tree[u<<1|1].r-tree[u<<1|1].l+1; tree[u].s=(tree[u<<1].s*ten[lenr]%mod+tree[u<<1|1].s)%mod; } void build(int u,int l,int r) { tree[u]={l,r,0,0}; if(l==r) { tree[u].s=1; return ; } int mid=l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r); pushup(u); } void pushdown(int u) { if(!tree[u].lazy) return; tree[u<<1].lazy=tree[u<<1|1].lazy=tree[u].lazy; tree[u<<1].s=num[tree[u].lazy][tree[u<<1].r-tree[u<<1].l+1]; tree[u<<1|1].s=num[tree[u].lazy][tree[u<<1|1].r-tree[u<<1|1].l+1]; tree[u].lazy=0; } void modify(int u,int l,int r,int x) { if(tree[u].l>=l&&tree[u].r<=r) { tree[u].s=num[x][tree[u].r-tree[u].l+1]; tree[u].lazy=x; return; } pushdown(u); int mid=tree[u].l+tree[u].r>>1; if(l<=mid) modify(u<<1,l,r,x); if(r>mid) modify(u<<1|1,l,r,x); pushup(u); } int main() { IO; int T=1; //cin>>T; while(T--) { cin>>n>>m; ten[0]=1; for(int i=1;i<=n;i++) ten[i]=10*ten[i-1]%mod; for(int i=1;i<=9;i++) { for(int j=1;j<=n;j++) num[i][j]=(num[i][j-1]*10%mod+i)%mod; } build(1,1,n); while(m--) { int l,r,x; cin>>l>>r>>x; modify(1,l,r,x); cout<<tree[1].s<<'\n'; } } return 0; }

F - Heights and Pairs

不会多项式，会了可能补

先贴个代码，搞会儿信号与系统晚上再补剩余的QaQ 要加油哦~