测试成果
非常寄
35+56+0+8=99
基本上把能犯的错误都犯了
T1 记得 dp 数组初始化 \(-\infty\)！！！！
T2 记得认真暴搜，不要乱记录访问状态
T3 记得把调试删掉！！！！！
T4 记得开 long long ！！
红日学长很会写题目名称，让我看着很想打原神（
可惜挂大分，上次题目名称是 arcaea 的时候也挂大分了
A 风与牧歌的城邦 (mondstadt)
没有温迪的后果就是写不出第一题 \(\dots\)
题目大意
给定序列 \(\{a_n\},\{b_n\}\)，保证 \(a_1, a_2, \dots, a_n\) 两两不同。
对于 \(\forall 1 \le l \le r \le n\)，定义区间 \([l, r]\) 的权值如下：设 \(a_p = \max\{a_l, a_{l + 1}, \dots, a_r\}\)，则 \([l, r]\) 的权值为 \(b_p\)。
你需要将 \(1 \sim n\) 划分为若干段，求每一段的权值之和的最大值。
对于所有测试数据，保证 \(1 \le n \le 5 \times 10 ^ 5\)，\(1 \le a_i \le n\)，\(- 10 ^ 9 \le b_i \le 10 ^ 9\)，保证 \(a_1, a_2, \dots, a_n\) 是 \(1 \sim n\) 的一个排列。
题解
dp 方程不够优（）
\(O(n^2)\) 做法
\(f_{i}\) 表示 \(1\sim i\) 最大值.
\(\displaystyle{f_i=\max_{prv_i\le j<i}\{f_j+w(j+1,i-1)\}}\)
其中 \(\displaystyle{w(L,R)=b_k,\max_{i\in[L,R]}\{a_i\}=a_k}\)
\(prv_i=\max_{k}\{a_k>a_i\}\)
这个不好优化，我们考虑调教式子
变成这样
\[f_i=\max_{j} \begin{cases} \begin{align*} &f_{prv_i}&,prv_i\ne 0\\ &\max_{prv_i\le k<i}\{f_k\}+b_i &,prv_i\ne0\\ &\max\{0,\max_{1\le k<i}\{f_k\}\}+b_i &,prv_i=0\\ \end{align*} \end{cases} \]\(O(n\log n)\) 做法
单调栈处理 \(prv_i\)，线段树处理 \(f_i\) 最大值
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5+5;
const ll inf = 1e18;
int n,a[N],b[N];
int st[N],tp,prv[N];
ll f[N];
struct Sagiri
{
int l,r;
ll mx;
} t[N<<2];
#define ls (p<<1)
#define rs (p<<1)|1
void build(int p, int l, int r)
{
t[p].l=l,t[p].r=r;
if(l==r) { t[p].mx=-inf; return ; }
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
t[p].mx=max(t[ls].mx,t[rs].mx);
}
void change(int p, int x, ll v)
{
if(t[p].l==t[p].r) { t[p].mx=v; return ; }
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid) change(ls,x,v);
else change(rs,x,v);
t[p].mx=max(t[ls].mx,t[rs].mx);
}
ll query(int p, int l, int r)
{
if(t[p].l==l and t[p].r==r) return t[p].mx;
int mid=(t[p].l+t[p].r)>>1;
if(r<=mid) return query(ls,l,r);
else if(l>mid) return query(rs,l,r);
else return max(query(ls,l,mid),query(rs,mid+1,r));
}
int main()
{
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=n; i++) scanf("%d",&b[i]);
for(int i=1; i<=n; i++)
{
while(tp and a[st[tp]]<a[i]) tp--;
if(tp>0) prv[i]=st[tp];
st[++tp]=i;
}
for(int i=1; i<=n; i++) f[i]=-inf;
build(1,1,n);
for(int i=1; i<=n; i++)
{
if(prv[i]) f[i]=f[prv[i]];
if(i==1) f[i]=b[i];
else if(prv[i]) f[i]=max(f[i],query(1,prv[i],i-1)+b[i]);
else f[i]=max(f[i],max(0ll,query(1,1,i-1))+b[i]);
change(1,i,f[i]);
}
printf("%lld\n",f[n]);
return 0;
}
我只能说我为什么想不出来，甚至暴力写挂，呜呜呜 \(\dots\)
B 岩与契约的海港 (liyue)
虽然有钟离，可是还是挂分了
题目大意
给定 \(n\) 个蛋糕，每块蛋糕有一个美味值 \(w_i\)。蛋糕的两面分别涂有一种奶油 \(a_i\), \(b_i\)，奶油共有四种类型，分别以 \(\texttt{X}\)，\(\texttt{Y}\)，\(\texttt{Z}\)，\(\texttt{W}\) 表示。
蛋糕 A 能叠放在蛋糕 B 上当且仅当蛋糕 A 底面的奶油与蛋糕 B 顶面的奶油是同一种。其中底面和顶面可以任意指定，即可以对蛋糕进行翻转。
你需要从 \(n\) 个蛋糕中选择若干个，并将它们以任意方向、任意顺序叠在一起。求所选蛋糕的美味度之和的最大值。
题解
很好转化成图论模型.
把 \(\texttt{W}\)，\(\texttt{X}\)，\(\texttt{Y}\)，\(\texttt{Z}\) 看做四个点，把一个蛋糕看做一条边
我们就是要找一条路径，每一条边只经过一次，边权和的最大值.
注意到如果重边数大于 \(2\)，可以在经过它的时候，多走一个来回.
所以最多少走一条边（一定是最小的那条）
于是对于每两个点重边，记录他边数的奇偶，边权和，边权最小值.
现在图中最多 \(12\) 条边，轻松暴搜完成.
可惜不知道为什么写挂了，测试完改改就过了，不知道错哪了（
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 5e5+5;
int n;
int sum[6][6],cnt[6][6],mn[6][6];
int tmp[6][6];
int vt[6];
int st[10],tp;
int dfs(int u, int cur)
{
if(cur>13) return 0;
st[++tp]=u;
int res=0;
for(int i=1; i<=4; i++) vt[i]=0;
for(int i=1; i<=tp; i++) vt[st[i]]=1;
for(int i=1; i<=4; i++) if(vt[i]) res+=sum[i][i];
for(int i=1; i<=4; i++) for(int j=1; j<=4; j++) tmp[i][j]=0;
for(int i=1; i<tp; i++)
{
int u=st[i],v=st[i+1];
if(u>v) swap(u,v);
tmp[u][v]++;
}
int flag=0;
for(int i=1; i<=4; i++)
for(int j=i+1; j<=4; j++)
{
if(tmp[i][j]>=3) flag=1;
else if(tmp[i][j]==2 and cnt[i][j]<2) flag=1;
else if(tmp[i][j]==2 and (cnt[i][j]&1)) res+=sum[i][j]-mn[i][j];
else if(tmp[i][j]==2) res+=sum[i][j];
else if(tmp[i][j]==1 and cnt[i][j]<1) flag=1;
else if(tmp[i][j]==1 and (cnt[i][j]&1)) res+=sum[i][j];
else if(tmp[i][j]==1) res+=sum[i][j]-mn[i][j];
}
if(flag) { tp--; return 0; }
for(int i=1; i<=4; i++)
{
if(u==i) continue;
res=max(res,dfs(i,cur+1));
}
tp--; return res;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
int w; string a,b;
for(int i=1; i<=n; i++)
{
cin>>w>>a>>b;
int u=a[0]-'W'+1,v=b[0]-'W'+1;
if(u>v) swap(u,v); cnt[u][v]++,sum[u][v]+=w;
if(mn[u][v]) mn[u][v]=min(mn[u][v],w);
else mn[u][v]=w;
}
int ans=0;
for(int i=1; i<=4; i++) ans=max(ans,dfs(i,1));
printf("%d\n",ans);
return 0;
}
C 雷与永恒的群岛 (inazuma)
虽然刚打完稻妻任务，但是我没删调试，虽然是正解
题目大意
给定序列 \(\{a_{2n}\}\)。你需要选出 \(n\) 个位置 \(1 \le b_1 < b_2 < \dots < b_n \le 2n\)，求 \(\gcd(a_{b_1}, a_{b_2}, \dots, a_{b_n})\) 的最大值。
对于所有测试数据，保证 \(1 \le n \le 10 ^ 5\)，\(1 \le a_i \le 10 ^ {12}\)。
题解
\(O(na_i)\) 做法
枚举 \(\gcd\)，看看够不够 \(n\) 个 \(\gcd\) 的倍数
随机化乱搞 \(O(\operatorname{can}\ AC)\) 做法
- 随机两个位置，求 \(gcd\)，塞进一个 set 里
- set 里随机两个位置，求 \(gcd\)，塞进 set 里
2 这个操作重复三次.
我也不知道为什么是对的，但是没有 2 可以构造出反例
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5;
int n,m,ng;
ll a[N<<1];
set<ll> st,st2;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r)
{
assert(r>=l);
return uniform_int_distribution<>(l,r)(rng);
}
int main()
{
scanf("%d",&n); m=n<<1;
for(int i=1; i<=m; i++) scanf("%lld",&a[i]);
int T=100;
ll ans=0;
for(int i=1; i<=T; i++)
{
int pos1=random(1,m),pos2=random(1,m);
st.insert(__gcd(a[pos1],a[pos2]));
}
for(int t=1; t<=3; t++)
{
st2.clear();
for(int u:st) for(int v:st) st2.insert(__gcd(u,v));
for(int u:st2) st.insert(u);
}
for(ll d:st)
{
int cnt=0;
for(int i=1; i<=m; i++) if(a[i]%d==0) cnt++;
if(cnt>=n) ans=max(ans,d);
}
printf("%lld\n",ans);
return 0;
}