由于重启电脑以后所有东西都没了因此还要重写一遍。
每天使用的算草数量确实是上了个数量级。
“你都敢拿小刀往胳膊上划为什么不敢吃这个（指魔芋爽）”——H_Kaguya 睿频 gtm1514。不过我觉得吃辣也不会让人精神状态 ++ 吧。不过我的小刀现在彻底成为破伤风之刃了，我就扔了。
吗了，吃了四分之一袋魔芋爽喝了一瓶水，喝都喝饱了。今天晚上两个小时已经喝了两瓶半水了！（7.8）
感觉很大程度上失去了活着的意义。昨天中午路上和 abhwolxq 的一些谈话似乎也能说明。其实不如说从来没有过。打算探讨一下。同时也应该找时间拜读一下《查拉图斯特拉如是说》。
Summer lasts no more,we won't slumber to the past we adore.
残暑已褪，我们亦不会沉溺于所爱的往昔
[NOI2022] 冒泡排序
十分困难，一开始以为是某不可做 dp，会了所有部分分之后才发现是贪心大题。并没有十分想出 A 怎么做。
首先显然可以让所有数只取到给定的 \(V\) 中的数。于是先离散化一下。然后最小化逆序对个数。
先看 B 部分分。确定了一堆单点，那么开个区间加查最小值的线段树随便扫一扫就行了。
然后是 C。容易发现把区间的最小值放在开头一定最优，于是变成了确定一堆单点，每个位置 \(\ge\) 某个数。也是线段树扫一扫就行了。
最后是比较困难的 A。根据上边的性质，我们必须把 \(1\) 铺满。然后看剩下的 \(0\) 的区间，它就变成了 C 部分。在开头安上然后线段树扫一扫就行了。
于是正解就十分显然了：我们把 \(V\) 从大到小排序，每次扫所有 \(\ge V\) 且没扫过的位置（可以用并查集记录扫没扫），在开头确定为最小值，然后给剩下的位置打个 \(\ge\) 这个最小值的标记。确定的部分可以树状数组扫一遍统计，不确定的线段树扫一扫。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n,m,lsh[1000010];
long long ans;
struct ques{
int l,r,val;
}q[1000010];
vector<pair<int,int> >v[1000010];
struct BIT{
int c[1000010];
#define lowbit(x) (x&-x)
void update(int x){
while(x)c[x]++,x-=lowbit(x);
}
int query(int x){
int sum=0;
while(x<=m)sum+=c[x],x+=lowbit(x);
return sum;
}
}c;
int fa[1000010];
int find(int x){
return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
struct node{
#define lson rt<<1
#define rson rt<<1|1
int mn,pos,lz;
}tree[4000010];
void pushup(int rt){
tree[rt].mn=min(tree[lson].mn,tree[rson].mn);
if(tree[rt].mn==tree[lson].mn)tree[rt].pos=tree[lson].pos;
else tree[rt].pos=tree[rson].pos;
}
void pushtag(int rt,int val){
tree[rt].mn+=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].mn=tree[rt].lz=0;tree[rt].pos=l;
if(l==r)return;
int mid=(l+r)>>1;
build(lson,l,mid);build(rson,mid+1,r);
}
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);
}
pair<int,int> query(int rt,int L,int R,int l,int r){
if(l<=L&&R<=r)return make_pair(tree[rt].mn,tree[rt].pos);
pushdown(rt);
int mid=(L+R)>>1;
pair<int,int>val=make_pair(0x3f3f3f3f,0x3f3f3f3f);
if(l<=mid)val=min(val,query(lson,L,mid,l,r));
if(mid<r)val=min(val,query(rson,mid+1,R,l,r));
return val;
}
int val[1000010],mn[1000010];
void solve(){
scanf("%d%d",&n,&m);ans=0;
for(int i=1;i<=n+1;i++)fa[i]=i,val[i]=mn[i]=0;
for(int i=1;i<=m;i++)c.c[i]=0,v[i].clear();
for(int i=1;i<=m;i++)scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].val),lsh[i]=q[i].val;
sort(lsh+1,lsh+m+1);
for(int i=1;i<=m;i++){
q[i].val=lower_bound(lsh+1,lsh+m+1,q[i].val)-lsh;
v[q[i].val].push_back(make_pair(q[i].l,q[i].r));
}
for(int i=m;i>=0;i--){
if(v[i].empty())continue;
sort(v[i].begin(),v[i].end());
int pre=n+1;
for(int j=v[i].size()-1;j>=0;j--){
if(v[i][j].second<pre){
int pos=find(v[i][j].first);
if(pos>v[i][j].second){
puts("-1");return;
}
val[pos]=i;pre=pos;
}
}
for(pair<int,int>p:v[i]){
for(int j=find(p.first);j<=p.second;j=find(j))mn[j]=i,fa[j]=j+1;
}
}
build(1,0,m+1);
for(int i=1;i<=n;i++){
if(val[i]){
ans+=c.query(val[i]+1);
c.update(val[i]);
update(1,0,m+1,val[i]+1,m+1,1);
}
}
for(int i=1;i<=n;i++){
if(val[i]){
update(1,0,m+1,val[i]+1,m+1,-1);
update(1,0,m+1,0,val[i]-1,1);
}
else{
pair<int,int>p=query(1,0,m+1,mn[i],m+1);
ans+=p.first;
if(p.second)update(1,0,m+1,0,p.second-1,1);
}
}
printf("%lld\n",ans);
}
int main(){
int tim;scanf("%d",&tim);
while(tim--)solve();
return 0;
}
[NOI2021] 庆典
感觉不会做 \(k=2\) 是不是不太合适就放到这里来了。
想出了 \(k=0,1\) 的部分，\(k=2\) 感觉分讨气息浓重就没打算写。看了题解结果有不需要分讨的做法。
首先缩点。然后根据这图的性质一定能找一个拓扑序是一棵树，在最后一条入边连上去即可。于是变成了树上问题。\(k=0,1\) 就显然了。
然后是 \(k\) 更大的情况。可以建虚树，然后变成点有点权边有边权，从 \(s\) 到 \(t\) 的路径并。点数是 \(O(k)\) 的，爆扫一遍就行了。
不是很想写。感觉代码很巨大。
[NOI2021] 量子通信
小小结论题，如果细想一下似乎不难？
因为 \(k\le 15\) 所以拆 \(16\) 段一定有一个相同。然后因为数据随机在某一位为某个数的期望个数是 \(\dfrac n{2^{16}}\approx 6\)。于是暴力扫就行了。
挺卡常的。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef unsigned long long ull;
namespace IO{
char buf[1<<23],*p1=buf,*p2=buf;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
inline int read(){
int x=0;char s=gc;
while(!isdigit(s))s=gc;
while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=gc;
return x;
}
}
using namespace IO;
int n,m,K;
ull a,b;
ull myRand(ull &k1,ull &k2){
ull k3=k1,k4=k2;
k1=k4;
k3^=(k3<<23);
k2=k3^k4^(k3>>17)^(k4>>26);
return k2+k4;
}
unsigned short s[400010][16];
ull S[400010][4];
vector<int>v[16][1<<16];
void gen(int n,ull a1,ull a2){
for(int i=1;i<=n;i++){
for(int j=0;j<16;j++){
for(int k=15;k>=0;k--)s[i][j]|=((myRand(a1,a2)&(1ull<<32))?1:0)<<k;
v[j][s[i][j]].push_back(i);
}
for(int j=0;j<4;j++){
S[i][j]|=(ull)s[i][j*4]<<48;
S[i][j]|=(ull)s[i][j*4+1]<<32;
S[i][j]|=(ull)s[i][j*4+2]<<16;
S[i][j]|=(ull)s[i][j*4+3];
}
}
}
bool lastans;
char ch[110];
unsigned short od[256],tmp[16];
ull TMP[4];
bool check(int id){
int ans=0;
for(int i=0;i<4;i++){
ans+=__builtin_popcountll(TMP[i]^S[id][i]);
if(ans>K)return false;
}
return true;
}
void solve(){
for(int i=0;i<64;i++){
unsigned short num;
char ch=gc;
if(isdigit(ch))num=ch-'0';
else if(ch>='A'&&ch<='F')num=10+ch-'A';
else {i--; continue;}
for(int j=3;j>=0;j--){
od[(i+1)*4-j-1]=((num>>j)&1)^lastans;
}
}
K=read();
for(int i=0;i<16;i++){
tmp[i]=0;
for(int j=15;j>=0;j--)tmp[i]|=od[(i+1)*16-j-1]<<j;
}
for(int i=0;i<4;i++){
TMP[i]=0;
TMP[i]|=(ull)tmp[i*4]<<48;
TMP[i]|=(ull)tmp[i*4+1]<<32;
TMP[i]|=(ull)tmp[i*4+2]<<16;
TMP[i]|=(ull)tmp[i*4+3];
}
for(int i=0;i<16;i++){
for(int x:v[i][tmp[i]]){
if(check(x)){
lastans=1;cout<<1<<'\n';
return;
}
}
}
lastans=0;cout<<0<<'\n';
}
int main(){
cin>>n>>m>>a>>b;
gen(n,a,b);
while(m--)solve();
return 0;
}
[NOI2020] 超现实树
某科学的超现实树。这题也挺超现实的。不过不是不可做。
首先通过考虑在一个叶子上不断挂单向链的情况可以发现只有左右子树大小最小值不超过 \(1\) 的有贡献。
然后看树的形式感觉上就是个递归东西。首先只有一个节点肯定几乎完备。看有多层的情况。对于一层，考虑在根节点挂链的情况，发现必须有至少一个满足左右子树都几乎完备，然后是根节点没东西的情况，必须满足只有一个子树。
具体的说就是四个情况：只有左 / 右子树且几乎完备，同时有左右子树且几乎完备。四个情况必须都有树满足，直接递归扫。或者说有单独节点则直接满足。
具体实现可以把上边四种情况看做树的四个叉，每棵树往下递归把树塞进去，需要所有叶子都几乎完备。
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int n,rt,t,lson[2000010],rson[2000010],son[2000010][4];
bool vis[2000010];
bool check(int rt){
if(!lson[rt]&&!rson[rt])return true;
return check(lson[rt])||check(rson[rt]);
}
void merge(int &rt,int x){
if(!rt)rt=++t;
if(!lson[x]&&!rson[x]){
vis[rt]=true;return;
}
if(!rson[x])merge(son[rt][0],lson[x]);
if(!lson[x])merge(son[rt][1],rson[x]);
if(!lson[rson[x]]&&!rson[rson[x]]&&lson[x]&&rson[x])merge(son[rt][2],lson[x]);
if(!lson[lson[x]]&&!rson[lson[x]]&&lson[x]&&rson[x])merge(son[rt][3],rson[x]);
}
bool getans(int rt){
if(!rt)return false;
if(vis[rt])return true;
return getans(son[rt][0])&&getans(son[rt][1])&&getans(son[rt][2])&&getans(son[rt][3]);
}
int main(){
int tim;scanf("%d",&tim);
while(tim--){
int x;scanf("%d",&x);
while(x--){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&lson[i],&rson[i]);
if(!check(1))continue;
merge(rt,1);
}
puts(getans(1)?"Almost Complete":"No");
for(int i=1;i<=t;i++)son[i][0]=son[i][1]=son[i][2]=son[i][3]=vis[i]=0;
rt=t=0;
}
return 0;
}