现在每天的考试策略就是优先切掉所有一眼题然后暴力打满然后摆。
为了查证 T3 题目背景的真实性，我看了看 nflsoj。结果：6。
感觉不如原神。
玩水
一场考试不能没有一道签到题。
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m,sum[1010][1010];
char s[1010][1010];
bool v[1010][1010];
int query(int l1,int r1,int l2,int r2){
return sum[l1-1][l2-1]+sum[r1][r2]-sum[l1-1][r2]-sum[r1][l2-1];
}
bool check(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(v[i][j]&&(v[i][j-1]||v[i-1][j]||v[i+1][j]||v[i][j+1]||query(i+1,n,j+1,m)))return true;
}
}
return false;
}
int main(){
int tim;scanf("%d",&tim);
while(tim--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]==s[i+1][j-1])v[i+1][j]=true,sum[i+1][j]++;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)sum[i][j]+=sum[i][j-1];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)sum[i][j]+=sum[i-1][j];
}
puts(check()?"1":"0");
memset(v,0,sizeof(v));
memset(sum,0,sizeof(sum));
}
return 0;
}
假人
首先我们有一个朴素的背包。设 \(dp_{i,j}\) 为前 \(i\) 组选 \(j\) 长度的最大值。
然后我们神秘地把下标变成 \(0\) 开始标号。这时候长度范围是 \([0,4]\)，最小公倍数是 \(12\)。
然后我们非常神秘地发现把 dp 数组按照模 \(12\) 的余数分类，每一组都是凸的。也就是它满足
\[dp_{i,j}-dp_{i,j-12}\ge dp_{i,j+12}-dp_{i,j} \]因为元素范围在 \([0,4]\) 之间且元素和为 \(24\) 的所有可重集都能分成两个 \(12\)。证明爆搜。
那么每组分治然后闵可夫斯基和合并凸包。不管从哪方面来说都很神秘。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define int long long
using namespace std;
int n,a[100010][10],len[100010];
struct node{
vector<int>v[12];
vector<int>& operator[](int pos){
return v[pos];
}
};
void merge(node &a,node &b,node &ans){
for(int i=0;i<12;i++)if(!a[i].empty()){
for(int j=0;j<12;j++)if(!b[j].empty()){
int del=(i+j>=12),pos=(i+j)%12,x=0,y=0;
while(1){
ans[pos][x+y+del]=max(ans[pos][x+y+del],a[i][x]+b[j][y]);
if(x==a[i].size()-1&&y==b[j].size()-1)break;
else if(x==a[i].size()-1)y++;
else if(y==b[j].size()-1)x++;
else ++((a[i][x+1]-a[i][x]>b[j][y+1]-b[j][y])?x:y);
}
}
}
}
node solve(int l,int r){
node ans;
if(l==r){
for(int i=1;i<=a[l][0];i++)ans[(i-1)%12].push_back(a[l][i]);
return ans;
}
int L=len[r]-len[l-1],mid=(l+r)>>1;
node a=solve(l,mid),b=solve(mid+1,r);
for(int i=0;i<12;i++){
for(int j=i;j<=L;j+=12)ans[i].push_back(-1);
}
merge(a,b,ans);
return ans;
}
signed main(){
scanf("%lld",&n);int sum=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i][0]);len[i]=len[i-1]+a[i][0]-1;
for(int j=1;j<=a[i][0];j++)scanf("%lld",&a[i][j]);
}
node ans=solve(1,n);
for(int i=0;i<=len[n];i++)printf("%lld ",ans[i%12][i/12]);
return 0;
}
切题
首先这是个最大流。然后赛时上了个 dinic，获得 10 分。
有个东西叫 Gale-Ryser 定理：
对于两边点数分别为 \(n,m\) 的二分图，两个序列 \(a,b\) 可能为其度数序列，当且仅当：和相等，且对 \(a_i\) 降序排序之后，\(\forall k\in[1,n],\sum\limits_{i=1}^ka_i\le \sum\limits_{i=1}^m\min(b_i,k)\)。
然后你对 \(b_i\ge k\) 的 \(b_i\) 记录个个数叫 \(c_k\)，那么变成 \(\sum_{i=1}^k(c_i-a_i)\ge 0\)。那先处理出来建线段树，如果全局最小值非负就合法。
然后关于修改。以操作 \(1\) 为例，修改 \(a\) 的时候由于是降序排列，需要找到相同一段 \(a\) 中最前面的给它加上，然后把后边一段的全局最小值减 \(1\)。操作 \(2\) 就是找到最后边的然后加 \(1\)。
修改 \(b\) 就随便区间修改一下就行了。反正是对 \(b\) 值域开的。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
int n,m,q,a[250010],b[250010],c[250010],sum[250010],a2[250010];
struct node{
int min,lz;
}tree[1000010];
void pushup(int rt){
tree[rt].min=min(tree[lson].min,tree[rson].min);
}
void pushtag(int rt,int val){
tree[rt].min+=val;tree[rt].lz+=val;
}
void pushdown(int rt){
if(tree[rt].lz){
pushtag(lson,tree[rt].lz);pushtag(rson,tree[rt].lz);
tree[rt].lz=0;
}
}
void build(int rt,int l,int r){
if(l==r){
tree[rt].min=sum[l];return;
}
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
pushup(rt);
}
void update(int rt,int L,int R,int l,int r,int val){
if(l<=L&&R<=r){
pushtag(rt,val);return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)update(lson,L,mid,l,r,val);
if(mid<r)update(rson,mid+1,R,l,r,val);
pushup(rt);
}
bool cmp(int a,int b){
return a>b;
}
int main(){
scanf("%d%d",&n,&m);int mx=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)scanf("%d",&b[i]),c[b[i]]++,mx=max(mx,b[i]);
for(int i=mx;i>=0;i--)c[i]+=c[i+1];
for(int i=1;i<=n;i++)a2[i]=a[i];
sort(a2+1,a2+n+1,cmp);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+c[i]-a2[i];
build(1,1,n);scanf("%d",&q);
while(q--){
int od,x;scanf("%d%d",&od,&x);
if(od==1){
int pos=lower_bound(a2+1,a2+n+1,a[x],cmp)-a2;
a[x]++;a2[pos]++;
update(1,1,n,pos,n,-1);
}
else if(od==2){
int pos=upper_bound(a2+1,a2+n+1,a[x],cmp)-a2-1;
a[x]--;a2[pos]--;
update(1,1,n,pos,n,1);
}
else if(od==3){
b[x]++;c[b[x]]++;
update(1,1,n,b[x],n,1);
}
else if(od==4){
update(1,1,n,b[x],n,-1);
c[b[x]]--;b[x]--;
}
puts(tree[1].min>=0?"1":"0");
}
return 0;
}
天下第一
上次看到这句话还是在中国象棋那题。就是棋盘放炮的方案数那个。当然不是洛谷的，是 nflsoj 上边 \(n,m\le 100000\) 的。有一说一其实可以开到 \(10^9\)，使用一个广为人知的 \(O(\sqrt n\log n)\) 方法。
算了扯远了。
考虑一个图是链的条件：
- 点度数 \(\le 2\)
- 无环
- 点数减边数为 \(1\)
一个个考虑条件。首先度数 \(\le 2\)，可以双指针一下。每次右端点扩展的时候，加入所有右端点连的 \([l,r]\) 的边，并判断度数是否超过 \(2\)，如果超过就右移左端点并断边。
然后无环。这个是个 LCT 经典问题。也是双指针扫一下。
最后是第三个条件。可以扫描线，每次扫到 \(r\)，线段树节点保存每个 \([i,r]\) 区间所有边都加入后点数减边数的值。
细节相当多。建议∑。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
int n,m,d[250010],pos[250010];
vector<int>g[250010];
namespace LCT{
#define lson tree[x].son[0]
#define rson tree[x].son[1]
struct node{int fa,son[2],val,sum;bool lz;}tree[250010];
bool isroot(int x){return tree[tree[x].fa].son[0]!=x&&tree[tree[x].fa].son[1]!=x;}
bool get(int x){return tree[tree[x].fa].son[1]==x;}
void pushup(int x){tree[x].sum=tree[lson].sum^tree[rson].sum^tree[x].val;}
void rev(int x){swap(lson,rson);tree[x].lz^=1;}
void pushdown(int x){if(tree[x].lz){if(lson)rev(lson);if(rson)rev(rson);tree[x].lz=false;}}
void rotate(int x){int y=tree[x].fa,z=tree[y].fa,tmp=get(x);if(!isroot(y))tree[z].son[tree[z].son[1]==y]=x;tree[y].son[tmp]=tree[x].son[tmp^1];
if(tree[x].son[tmp^1])tree[tree[x].son[tmp^1]].fa=y;tree[x].son[tmp^1]=y;tree[y].fa=x;tree[x].fa=z;pushup(y);pushup(x);}
void pushall(int x){if(!isroot(x))pushall(tree[x].fa);pushdown(x);}
void splay(int x){pushall(x);for(int i;i=tree[x].fa,!isroot(x);rotate(x)){if(!isroot(i))rotate(get(i)==get(x)?i:x);}}
void access(int x){for(int p=0;x;p=x,x=tree[x].fa){splay(x);rson=p;pushup(x);}}
void makert(int x){access(x);splay(x);rev(x);}
int findrt(int x){access(x);splay(x);pushdown(x);while(lson)x=lson,pushdown(x);splay(x);return x;}
void split(int x,int y){makert(x);access(y);splay(y);}
void link(int x,int y){makert(x);if(findrt(y)!=x)tree[x].fa=y;}
void cut(int x,int y){makert(x);if(findrt(y)==x&&tree[y].fa==x&&!tree[y].son[0]){tree[y].fa=tree[x].son[1]=0;pushup(x);}}
#undef lson
#undef rson
}
namespace seg{
#define lson rt<<1
#define rson rt<<1|1
struct node{
int ans,cnt,lz;
}tree[1000010];
node pushup(node x,node y){
x.lz=y.lz=0;
if(x.ans==y.ans)return{x.ans,x.cnt+y.cnt,0};
else return x.ans<y.ans?x:y;
}
void pushtag(int rt,int val){
tree[rt].ans+=val;tree[rt].lz+=val;
}
void pushdown(int rt){
if(tree[rt].lz){
pushtag(lson,tree[rt].lz);pushtag(rson,tree[rt].lz);tree[rt].lz=0;
}
}
void build(int rt,int l,int r){
tree[rt].cnt=1;
if(l==r)return;
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
tree[rt]=pushup(tree[lson],tree[rson]);
}
void update(int rt,int L,int R,int l,int r,int val){
if(l<=L&&R<=r){
pushtag(rt,val);return;
}
pushdown(rt);
int mid=(L+R)>>1;
if(l<=mid)update(lson,L,mid,l,r,val);
if(mid<r)update(rson,mid+1,R,l,r,val);
tree[rt]=pushup(tree[lson],tree[rson]);
}
node query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r)return tree[rt];
pushdown(rt);
int mid=(L+R)>>1;node val={0x3f3f3f3f,0,0};
if(l<=mid)val=pushup(val,query(lson,L,mid,l,r));
if(mid<r)val=pushup(val,query(rson,mid+1,R,l,r));
return val;
}
}
int main(){
freopen("txdy.in","r",stdin);
freopen("txdy.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
g[u].push_back(v);g[v].push_back(u);
}
for(int l=1,r=1;r<=n;r++){
sort(g[r].begin(),g[r].end());
for(int x:g[r]){
if(x>r)break;
while(l<=x&&(d[x]==2||d[r]==2)){
for(int y:g[l]){
if(l<y&&(y<r||(y==r&&l<x)))d[l]--,d[y]--;
}
l++;
}
if(l<=x)d[x]++,d[r]++;
}
pos[r]=l;
}
seg::build(1,1,n);
long long ans=0;
for(int r=1,l=1;r<=n;r++){
seg::update(1,1,n,1,r,1);
for(int x:g[r]){
if(x>r)break;
while(l<=x&&LCT::findrt(x)==LCT::findrt(r)){
for(int y:g[l]){
if(l<y&&(y<r||(y==r&&l<x)))LCT::cut(l,y);
}
l++;
}
if(l<=x)LCT::link(x,r);
seg::update(1,1,n,1,x,-1);
}
pos[r]=max(pos[r],l);
seg::node ret=seg::query(1,1,n,pos[r],r);
if(ret.ans==1)ans+=ret.cnt;
}
printf("%lld\n",ans);
return 0;
}