总述
\(53+20+20+0=93\)，班上 \(rk9\)，太菜了。
考场 T1 特殊性质+暴力（可是没有打满），T2 特殊性质，T3 暴力。费时 \(40\) 分钟，剩下的时间写正解（没写出来）+摆烂。
感谢 cy 同志让我感受到了被题虐的感觉。
考场解法参见【部分分】部分。
T1. 匹配(2353)
简要题意
令两个区间 \([l,r],[x,y]\) 的节目效果值为：
\[\max_{a=l}^{r}\max_{b=x}^{y}|a-b| \]有 \(n\) 个区间 \([l_i,r_i]\)，你需要对它们两两分组，每组的节目效果值之和最大。输出最这个和。
\(2 \leq n \leq 10^{6},0 \leq l_i \leq r_i \leq 10^9\)，保证 \(n\) 为偶数。
部分分
Subtask #1(30pts)：\(n\leq 8\)，考虑直接暴力 DFS，时间复杂度 \(O(\textbf{玄学})\)。
namespace bf{
bool vis[1000005];
int grouped = 0;
int nowret = 0;
int result = 0;
void dfs(){
if(grouped>=n){
result=max(result,nowret);
return;
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
vis[i]=1;
for(int j=(i+1);j<=n;j++){
if(vis[j])continue;
vis[j]=1;
grouped += 2;
nowret += player_group_value(a[i],a[j]);
dfs();
grouped -= 2;
nowret -= player_group_value(a[i],a[j]);
vis[j]=0;
}
vis[i]=0;
}
}
int solve(){
dfs();
return result;
}
}
Subtask #3(20pts)：\(l_i=r_i\)，直接排序后贪心在左右两端取即可。时间复杂度 \(O(n\log n)\)。
namespace subtask3{
bool cmp(player x,player y){
return x.l<y.l;
}
int solve(){
int ret=0;
sort(a+1,a+n+1,cmp);
for(int l=1,r=n;l<r;l++,r--){
ret+=abs(a[l].l-a[r].l);
}
return ret;
}
};
Subtask #4(10pts)：\(r_i-l_i=r_j-l_j\)，也是排序后贪心取两端。时间复杂度 \(O(n\log n)\)。
namespace subtask4{
bool cmp(player x,player y){
return x.l<y.l;
}
int solve(){
int ret=0;
sort(a+1,a+n+1,cmp);
for(int l=1,r=n;l<r;l++,r--){
ret+=player_group_value(a[l],a[r]);
}
return ret;
}
}
正解
考虑一般化。其实我们可以给每一个区间分配一个 \(01\) 属性 \(t\)，当 \(t_i=1\) 时取 \(r_i\)，否则取 \(-l_i\)。那么我们其实要取 \(\frac{n}{2}\) 个 \(1\) 和 \(0\)。
先将所有的 \(t_i\) 设为 \(1\)，将其改为 \(0\)，答案需要加上 \(-r_i-l_i\)。将区间按照 \(l_i+r_i\) 排序，贪心改变前 \(\frac{n}{2}\) 个即可。
时间复杂度 \(O(n\log n)\)。本题卡常，需要使用快读。
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
#define T (1<<15)
char buf[T],*p1=buf,*p2=buf;
#define nc() (p1==p2&&(p2=buf+fread(p1=buf,1,T,stdin),p1==p2)?-1:*p1++)
ll rd(){
ll x=0;char c;bool s=0;
do c=nc();while(c!=45&&(c<48||c>57));
if(c==45)c=nc(),s=1;
do x=10*x+(c&15),c=nc();while(c>=48&&c<=57);
return s?-x:x;
}
#undef T
int n;
struct player{
int l,r;
bool operator<(const player &x) const {
return (r+l)<(x.r+x.l);
}
} p[1000005];
int ret=0;
signed main(){
// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
freopen("2353.in","r",stdin);
freopen("2353.out","w",stdout);
n=rd();
for(int i=1;i<=n;i++){
p[i].l=rd();p[i].r=rd();
}
sort(p+1,p+n+1);
for(int i=1;i<=n;i++)ret+=p[i].r;
for(int i=1;i<=(n>>1);i++)ret=ret-p[i].r-p[i].l;
printf("%lld",ret);
return 0;
}
T2. 狼人(2354)
简要题意
给你一个 \(n\) 个节点的树。每一个节点有一个权 \(c_i\) 你需要求出有多少个连通块，使得连通块中权组成的集合存在出现次数大于连通块节点数量的一半的权。答案对 \(998244353\) 取模。
\(1 \leq n \leq 3000,1 \leq c_i \leq n\)
部分分
Subtask #2(20pts)：树为 \(1\to 2\to\cdots\to n\) 的链。
链的情况就是连通块为区间，这道题就变成了给你一个序列求有多少个子区间的众数出现次数大于区间长度的一半。直接枚举区间用 std::map 维护众数即可。
时间复杂度 \(O(n^2\log n)\)，可以卡过。
int mm[3005];
int c[3005];
int ret=0;
for(int i=1;i<=n;i++){
memset(mm,0,sizeof(mm));
int zs=0;
for(int j=i;j<=n;j++){
mm[c[j]]++;
if(mm[zs]<mm[c[j]]){
zs=c[j];
}
if((2*mm[zs])>(j-i+1)){
ret++;
}
}
}
cout<<ret;
T3. 旅行(2355)
简要题意
有 \(n\) 个节点，对于任意的 \(i(1 \leq i \leq n-1)\)，有有向边 \((i,i+1),(i,i+2),\cdots,(i,i+T_i-1),(i,i+T_i)\)。（显然图为一个 DAG）
给定正整数 \(K\) 和自然数 \(D\)，如果沿着边 \((i,j)\) 从 \(i\) 到 \(j\)，需要花费代价为：
\[C_{i,j}=\lfloor \frac{j-i}{K} \rfloor \cdot D \]另外，每一个节点有一个权值 \(H_i\)。定义一条路径 \(P_1 \to P_2\to \cdots \to P_{m-1}\to P_m\)，那么这条路径的快乐程度为：
\[\sum_{i=1}^{n}{H_{P_i}}-\sum_{i=1}^{n-1}{C_{P_i,P_{i+1}}} \]即经过节点的权值总和与总花费的差。
定义 \(f_i\) 为从 \(i\) 出发到 \(n\) 的最大快乐程度。输出：
\[\operatorname{xor}\limits_{i=1}^{n}{f_i+i} \]\(1 \leq K \leq n \leq 2 \times 10^{6},0 \leq D,|H_i| \leq 10^{10},1 \leq T_i \leq n-i\)。
部分分
Subtask #1(20pts)：\(n \leq 3000\)，可以考虑暴力建出反图后从 \(n\) 开始 DP，每一个节点需要等到其入节点遍历完后开始遍历。则易得状态转移方程：
\[f_v=\max_{(u,v)\in\operatorname{Graph}}{f_u+H_v-\lfloor\frac{u-v}{K}\rfloor\cdot D} \]初始条件 \(f_n=H_n\)。
也可以在拓扑序上 DP，原理相同（想一想为什么）。
时间复杂度瓶颈在建图，时间复杂度为 \(O(n(\sum_{i=1}^{n-1}{T_i}))\)。
int n,k,d;
int cnt[N],in[N],f[N];
int h[N];
void dfs(int u){
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to;
cnt[v]++;
f[v]=max(f[v],f[u]+h[v]-((u-v)/k)*d);
if(cnt[v]>=in[v]){
dfs(v);
}
}
}
signed main(){
freopen("2355.in","r",stdin);
freopen("2355.out","w",stdout);
memset(f,0x8f,sizeof(f));
n=rd();k=rd();d=rd();
for(int i=1;i<=n;i++){
h[i]=rd();
}
for(int i=1,t;i<n;i++){
t=rd();
for(int j=(i+1);j<=(i+t);j++){
add(j,i);
in[i]++;
}
}
f[n]=h[n];
dfs(n);
int result=0;
for(int i=1;i<=n;i++){
result^=(f[i]+i);
}
printf("%lld",result);
return 0;
}