组队训练记录（3）：2021ICPC南京

签到题 队友单开的

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
inline void solve(){int n, a, b; cin >> n >> a >> b;if(a - 1 <= n - a){for(int i = 1; i <= n - 1; i++) cout << 'U';if(b - 1 < n - b){for(int i = 1; i <= n - 1; i++) cout << 'L';for(int i = 1; i <= b - 1; i++) cout << 'R';for(int i = 1; i <= a - 1; i++) cout << 'D';} else {for(int i = 1; i <= n - 1; i++) cout << 'R';for(int i = 1; i <= n - b; i++) cout << 'L';for(int i = 1; i <= a - 1; i++) cout << 'D';}} else {for(int i = 1; i <= n - 1; i++) cout << 'D';if(b - 1 < n - b){for(int i = 1; i <= n - 1; i++) cout << 'L';for(int i = 1; i <= b - 1; i++) cout << 'R';for(int i = 1; i <= n - a; i++) cout << 'U';} else {for(int i = 1; i <= n - 1; i++) cout << 'R';for(int i = 1; i <= n - b; i++) cout << 'L';for(int i = 1; i <= n - a; i++) cout << 'U';}}
}
signed main(){ios_base::sync_with_stdio(false), cin.tie(0);int t = 1; // cin >> t;while(t--) solve();return 0;
}

每个点对答案的贡献是 $+1$ 或 $-1$ ，判断全正和全负和 $n==1$ 即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
int a[1000005];
inline void solve(){cin>>n;int fg=0,sum=0,minn=1e9,maxn=-1e9;for(int i=1;i<=n ;i++){cin>>a[i];sum+=abs(a[i]);minn=min(minn,a[i]);maxn=max(maxn,a[i]);if(a[i]<=0)fg=1;}if(n==1){cout<<a[1]<<endl;}else if(minn>0){cout<<sum-2*minn<<endl;}else if(maxn<0){cout<<sum+2*maxn<<endl;}else{cout<<sum<<endl;}
}signed main(){ios_base::sync_with_stdio(false), cin.tie(0);int t = 1; cin >> t;while(t--) solve();return 0;
}

考虑 枚举答案。 开桶存权值对应所有点下标，线段树单点插入单点删除即可。（题解好像是 $O(n)$ 的，但是nlogn暴力卡过去了）。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6 + 10;
namespace SegTree{#define ls rt << 1#define rs rt << 1 | 1#define lson ls, l, mid#define rson rs, mid + 1, rstruct Info{int lmax, rmax, sum, ans;friend Info operator+ (Info a, Info b){return Info{max(a.lmax, a.sum + b.lmax),max(b.rmax, b.sum + a.rmax),a.sum+b.sum,max({a.ans,b.ans,a.rmax+b.lmax})};}} tree[N << 2];void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }void update(int rt, int l, int r, int pos, int val){if(l == r){tree[rt] = Info{val, val, val, val};return;}int mid = l + r >> 1;if(mid >= pos) update(lson, pos, val);else update(rson, pos, val);push_up(rt);}
}
using SegTree::update;
vector<int> g[N << 1];
inline void solve(){int n, k, ans = 0; cin >> n >> k;for(int i = 1; i <= n; i++){int x; cin >>x;g[x + 1000000].emplace_back(i);}for(int i = 0; i <= 2000000; i++){ans = max((int)g[i].size(), ans);}if(k == 0){cout << ans << endl;return; }int ed=min(2000000, 2000000 + k);for(int i = max(0, k); i <= ed; i++){if(!g[i].size()||!g[i-k].size())continue;for(auto &pos : g[i]){update(1, 1, n, pos, -1);}for(auto &pos : g[i - k]){update(1, 1, n, pos, 1);}int res = SegTree::tree[1].ans + g[i].size();ans = max(res, ans);for(auto &pos : g[i]){update(1, 1, n, pos, 0);}for(auto &pos : g[i - k]){update(1, 1, n, pos, 0);}}cout << ans;
}
signed main(){ios_base::sync_with_stdio(false), cin.tie(0);int t = 1; // cin >> t;while(t--) solve();return 0;
}

容易发现 ，对于新增的数 分为两种情况

小于等于前缀最大值，则交换的增加次数为前缀的大于自身的数的种类数
大于前缀最大值，暴力更新前缀最大值。

权值线段树维护即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
int a[N];
namespace SegTree{#define ls rt << 1#define rs rt << 1 | 1#define lson ls, l, mid#define rson rs, mid + 1, rint tree[N << 2],fk[N<<2];void push_up(int rt){ fk[rt] = fk[ls] + fk[rs];tree[rt]=tree[ls]+tree[rs]; }void build(int rt, int l, int r){tree[rt] = fk[rt]=0;if(l == r) return;int mid = l + r >> 1;build(lson), build(rson);}void update(int rt, int l, int r, int pos, int val){if(l == r) return (void)(fk[rt] += val,tree[rt]=(fk[rt]!=0));int mid = l + r >> 1;if(mid >= pos) update(lson, pos, val);else update(rson, pos, val);push_up(rt);}int query(int rt, int l, int r, int L, int R){if(L > R) return 0;if(l >= L && r <= R) return tree[rt];int mid = l + r >> 1, ans = 0;if(mid >= L) ans += query(lson, L, R);if(mid < R) ans += query(rson, L, R);return ans;}
}
using SegTree::update;
using SegTree::query;
int dp[N];
inline void solve(){int n = 0; cin >> n;SegTree::build(1, 1, n);for(int i = 1; i <= n; i++) cin >> a[i], dp[i] = 0;int maxx = a[1],cnt=0,st=1;update(1, 1, n, a[1], 1);for(int i=2;i<=n;i++){update(1, 1, n, a[i], 1);if(a[i] <= maxx){dp[i] = dp[i - 1] + query(1, 1, n, a[i] + 1, n);} else {dp[i] = dp[st]+2;for(int j=st;j<i;j++){update(1, 1, n, a[j], -1);}for(int j=st+1;j<i;j++){dp[i]+=query(1, 1, n, a[j] + 1, n);update(1, 1, n, a[j], 1);}update(1,1,n,a[st],1);st=i;}maxx = max(maxx, a[i]);}for(int i = 1; i <= n; i++) cout << dp[i] << " \n"[i == n];
}
signed main(){ios_base::sync_with_stdio(false), cin.tie(0);int t = 1; cin >> t;while(t--) solve();return 0;
}

树dp
$f_u$ 表示以 $u$ 为根结点，不算 $u$ 的答案最大值，$g_u$ 表示访问了 $u$ 点之后立刻返回其父亲结点子树的最大值，暴力转移即可。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;const int N = 1e5 + 10;
int n;
int a[100005],t[100005];
vector<int>p[100005];
int f[200005],g[200005];
int pre[100005],nxt[100005];
void dfs(int u,int fa){if(fa!=0)p[u].erase(find(p[u].begin(),p[u].end(),fa));if(!p[u].size()){g[u]=a[u];return;}int fk=0;for(auto v:p[u]){dfs(v,u);g[u]+=f[v];fk=max(fk,a[v]);}if(p[u].size()==1){f[u]=f[p[u][0]]+a[p[u][0]];g[u]+=a[u];return;}for(int i=0;i<p[u].size();i++){if(i==0){pre[i]=(t[p[u][i]]==3)?a[p[u][i]]:0;}else{pre[i]=pre[i-1];if(t[p[u][i]]==3)pre[i]=max(pre[i],a[p[u][i]]);}}for(int i=p[u].size()-1;~i;i--){if(i+1==p[u].size()){nxt[i]=(t[p[u][i]]==3)?a[p[u][i]]:0;}else{nxt[i]=nxt[i+1];if(t[p[u][i]]==3)nxt[i]=max(nxt[i],a[p[u][i]]);}}f[u]=g[u]+fk;for(int i=0;i<p[u].size();i++){int v=p[u][i];if(i==0){f[u]=max(f[u],g[u]+nxt[i+1]+g[v]-f[v]);}else if(i+1==p[u].size()){f[u]=max(f[u],g[u]+pre[i-1]+g[v]-f[v]);}else{f[u]=max(f[u],g[u]+max(pre[i-1],nxt[i+1])+g[v]-f[v]);}}g[u]+=a[u];
}
inline void solve(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];p[i].clear();f[i]=g[i]=0;}for(int i=1;i<=n;i++){cin>>t[i];}for(int i=1;i<n;i++){int u,v;cin>>u>>v;p[u].push_back(v);p[v].push_back(u);}dfs(1,0);cout<<f[1]+a[1]<<endl;
}signed main(){ios_base::sync_with_stdio(false), cin.tie(0);int t = 1; cin >> t;while(t--) solve();return 0;
}

队友单切的 ，只知道是记搜。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;const int N=1e6+5;
int b[N], pr[N], tot=0;
void init()
{for(int i=2;i<=1e5;i++){if(!b[i]) pr[++tot]=i;for(int j=1;pr[j]*i<=1e5;j++){b[pr[j]*i]=1;if(i%pr[j]==0) break;}}
}
vector <int> g;
int sz[N];
unordered_map <int, int > mp; 
int dfs(int a, int d)
{if(mp[a*1e9+d]) return mp[a*1e9+d];if(a<=1) return 0;mp[a*1e9+d] = a-1;for(int x : g){int tx=pr[x];if(!sz[x] || d%tx) continue;int dd = a%tx;sz[x]--;if(dd+2<tx-dd+1){mp[a*1e9+d] = min(mp[a*1e9+d], dfs(a/tx,d/tx)+dd+1);}else if(dd+1>tx-dd+2){mp[a*1e9+d] = min(mp[a*1e9+d], dfs(a/tx+1,d/tx)+tx-dd+1);}else {mp[a*1e9+d] = min({mp[a*1e9+d], dfs(a/tx+1,d/tx)+tx-dd+1,dfs(a/tx,d/tx)+dd+1});}sz[x]++;}return mp[a*1e9+d];
}
inline void solve(){int a,b; cin>>a>>b;if(b<a) swap(a,b);int d=b-a;g.clear(); mp.clear();int tmp=d;for(int i=1;i<=tot;i++) sz[i]=0;for(int i=1;i<=tot;i++){if(pr[i]*pr[i]>tmp) break;int cnt=0;while(tmp%pr[i]==0){cnt++;tmp/=pr[i];}sz[i]=cnt;g.push_back(i);}if(tmp!=1) {g.push_back(100000);sz[100000]=1;pr[100000]=tmp;}int ans=dfs(a,d);cout<<ans<<"\n";
}signed main(){ios_base::sync_with_stdio(false), cin.tie(0);int t = 1;  cin >> t;init();//for(int i=1;i<=20;i++) cout<<pr[i]<<endl;while(t--) solve();return 0;
}