(grounding) DINO 阅读笔记

DEtection with TRansformers 阅读笔记

DEtection with TRansformers 阅读笔记

模型结构

CNN Backbone

常规做法, 用来特征提取。输出一个 C * HW 的特征图。

Transformer

  • 多头注意力机制
  • pos_embed 给 sum 到 Encoder 的 query 和 key 里
  • Decoder 里固定查 N = 100 个 token

FFN

实际上就是 1*1 的卷积。

数据

COCO Dataset

训练

计算损失

由于产出 100 个检测结果,故而和事实做二分图匹配,跑个 Hungarian 算法即可获得匹配关系。

DINO 阅读笔记

Preliminaries

论文提到两个对它影响比较大的工作:

  • DAB-DETR 将 positional query 描述成 R^4 里的一个向量 (x, y, w, h)
  • DN-DETR 认为收敛缓慢可能是因为二分图匹配不够稳定,因此引入 denosing ,将带噪声的 label 和 box 送入 DETR
  • Deformable DETR 让 attention 关注 sampling points 周围的一小部份点。首先它引入了 query selection 技术(直接从 encoder 的输出提取 features 和 reference boxes);其次是它用了所谓梯度分离技术,这里叫它 look forward once

Backbone

分别用 ResNet-50 和 SwinL 作为 backbone

模型

  • look forward twice: 一个类似 residual connection 的操作,用来减少梯度消失的风险
  • Mixed Query Selection: 选择 top-k 个 feature 传入 decoder

训练

  • Contrastive DeNoising Training (CDN) ,将 Ground Truth 内的作为正样本,外的作为负样本,可以避免重复预测。

Grounding DINO 阅读笔记

Preliminaries

提出一个范式:Backbone 用于 feature extraction, neck 用于 feature enchancement, head 用于 region refinement(box prediction)

模型

image 经过一个 Swin-T 作为 backbone, 而 text 则经过一个 BERT

然后是一个 Feature Enhance Layer, SAM 和它有点相似,都是 image 和 text (在 SAM 里是 prompt) 各经过一个 self-attention / deformable self-attention 以后做一个双向的 cross-attention, 然后各 FFN 以后输出。

接着是 Language-Guided Query Selection, 这个部分首先将 image 和 text 的 feature 沿第三维卷积,取 max 作为 img feat,最后取 topk 返回。

接着是 Cross-Modality Decoder, 将 Query 经过 self-attention 以后,取 Q 分别和 Image Features, Text Features 的 K, V 做 Cross-Attention ,再过一个 FFN 以后输出。

输入

处理 Text Prompt: 以往采用两种 text prompt, 作者称之为 Sentence Level 和 Word Level; 在这里则使用了 Sub-sentence Level

训练

  • 类似 DETR, 仍然是先二分图匹配再计算损失

Ablations

消融实验认为 Encoder fusion 是最重要的部份

Segment Anything Model 阅读笔记

Segment Anything Model(SAM) 阅读笔记

模型架构

模型主要由三个部份组成,一个笨重的 image encoder ,用于将图像 embedding;一个轻量级的 prompt encoder 和一个轻量级的 mask decoder,

Image Encoder

Vision Transformer(ViT)

这个部份采用了 NLP 领域常用的 Transformer 思想。

输入图片首先经过 PatchEmbed 模块。在这里,将图片切割成 16 * 16 个 patch, 每个 patch 的维度是 768.

然后,如果启用 absolute positional embeddings, 也就是位置信息,那么直接将它 sum 到 patch embedding 上。

接下来通过一组 depth 个的 transformer blocks. 这里使用了 Multihead Attention,然后再经过一个激活函数是 GeLU 的 MLP 。 这里它使用了 Window Attention ,也就是每次自注意力只关注一个局部。论文称它使用了 14 * 14 的 Window。同时还加上了 relative positional embeddings。

Reduce Channel Dimension

在这里它参照了Exploring Plain Vision Transformer Backbones for Object Detection,把输出先后通过 1 * 1, 256 channel 和 3 * 3, 256 channel 的卷积压缩。每次卷积后 LayerNorm 一次。

Prompt Encoder

将输入分成以下四种:

  • 一个点:将 positional encoding 和一个表示它是在前景还是背景的 embedding 相加。
  • 一个框:分别用两个 embedding 表示左上角和右下角。
  • mask:可能是用于训练,直接塞入 dense_prompt_embedding ,sparse 项置零。
  • 无输入:单独的 embedding,表示 no prompt.

分别传出两个部份 sparse_prompt_embeddingdense_prompt_embedding

Lightweight mask Decoder

传入的信息包括两个部份:

  • token:这里包括两个 Embedding :iou_tokenmask_token ,还有 prompt encoder 传出的 sparse_prompt_embedding ,将他们 concatenate 在一起。
  • src:这个部分将 image_embeddingdense_prompt_embedding sum 在一起。

接下来将 src 和 pos_src (分别代表 prompt 的信息和 image 的信息)放入 TwoWayTransformer 。分别用两个 cross attention 来处理 token 和 image 之间的相互关系。

一个 upscaling,然后生成 4 个 mask token ;同时预测一个 IoU (用来给结果质量排序)

Ambiguity-aware

这个部分主要问题是可能会把多个有效输出的 mask 给平均掉。「observe that」的处理方案是同时预测并输出三个 mask(代表整体,部份和子部份),同时预测一个 IoU 给结果排序,并且只考虑质量最好的 loss 来反向传播。

同时如果给出多个 prompt 的话只返回一个(多个 prompt 足以确认一个有效输出),为了不和前面混淆总共需要生成 4 个 mask。

数据

原文用了很大篇幅来解释数据的采样在种族,国家和生存环境上的多样性。

数据集生成

原始数据是从某个摄影公司处获取的,同时附有

大致分成三个步骤

  • Assisted-manual stage: 这个阶段主要由打标人在一个 web 端上用一些工具来打标
  • Semi-auto stage: 这个阶段标记出 confident masks,然后要求打标人给其他的对象打标
  • Fully-auto stage: 这个部份用一个 32 * 32 的 point 型 prompt 来生成一组 masks,然后根据预测的 IoU 来筛选

一些 trick

  • 只保留 confident mask ,也就是 IoU > 88.0
  • 去除覆盖超过 95% 的 mask,提升 mask 质量,同时处理掉过小(100像素)的 spurious holes 和 components

训练

Losses

用 focal loss 和 dice loss 的 20:1 的线性组合来监督 mask 用 mean-square-error loss 监督 IoU 预测,factor 是 1.0

Training Algorithm

等概率选择 foreground point 或者 bounding box,然后加一些扰动。

之后从误差区域里加入新的采样点作为 prompt

把前一代的 mask 作为 prompt 塞给后一代(这可能是前面 prompt encoder 中 mask 的作用)

由于 prompt encoder 和 mask decoder 的开销很小(不足 1% 相对 image encoder),所以可以支持多步迭代(这里选择了 1 次初始,8 次更新采样点,然后 2 次没有额外信息的迭代)

Zero-shot Text-to-Mask

The key observation here is that because CLIP’s image embeddings are trained to align with its text embeddings, we can train with image embeddings, but use textembeddings for inference. That is, at inference time we run text through CLIP’s text encoder and then give the resulting text embedding as a prompt to SAM.

用 CLIP 的 image embedding 做训练,用 text embeddings 作推理。很深刻。

第 26 次 CCF CSP 题解


第 26 次 CCF CSP 题解

A

依照题意,推式子得到欲使平均值归一化,只须:

其中 是原平均值。

欲使方差归一化,只须在上文的基础上:

$$
$$

其中 是原方差。

#include<iostream>
#include<cmath>
const int N = 1005;
int n;
double a[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%lf",a + i);
	}
	double avg = 0;
	for(int i=1;i<=n;++i){
		avg += a[i];
	}
	avg /= n;
	for(int i=1;i<=n;++i){
		a[i] -= avg;
	}
	double sqr = 0;
	for(int i=1;i<=n;++i){
		sqr += a[i] * a[i];
	}
	double dlt = std::sqrt(n / sqr);
	for(int i=1;i<=n;++i){
		a[i] *= dlt;
	}
	for(int i=1;i<=n;++i){
		printf("%.20lf\n",a[i]);
	}
	return 0;
}

 

B

观察到 较小,我们只需要存储每个点作为左下角,其右上 区域的情况即可。

之后暴力校验即可。

#include<iostream>
#include<cmath>
const int N = 2005;
int n,L,s;
int locx[N],locy[N],mp[N][55][55],sd[55][55];
int main(){
	scanf("%d%d%d",&n,&L,&s);
	int nx,ny;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&nx,&ny);
		mp[i][0][0]=1;
		for(int j=1;j<i;++j){
			if(nx>=locx[j]&&ny>=locy[j]&&nx-locx[j]<=50&&ny-locy[j]<=50){
				mp[j][nx-locx[j]][ny-locy[j]]=1;
			}
			if(nx<=locx[j]&&ny<=locy[j]&&locx[j]-nx<=50&&locy[j]-ny<=50){
				mp[i][-nx+locx[j]][-ny+locy[j]]=1;
			}
		}
		locx[i]=nx,locy[i]=ny;
	}
	for(int i=0;i<=s;++i){
		for(int j=0;j<=s;++j){
			scanf("%d",&sd[s-i][j]);
		}
	}
//	for(int i=1;i<=n;++i){
//		for(int j=0;j<=s;++j){
//			for(int k=0;k<=s;++k){
//				printf("%d ",mp[i][j][k]);
//			}
//			puts("");
//		}
//	}
	int ans=0;
	for(int i=1;i<=n;++i){
		bool bo=0;
		if(locx[i]+s>L || locy[i]+s>L){
			continue;
		}
		for(int j=0;j<=s;++j){
			for(int k=0;k<=s;++k){
				if(sd[j][k]!=mp[i][j][k]){
					bo=1;break;
				}
			}
		}
		if(!bo){
			++ans;
		}
	}
	printf("%d\n",ans);
	
}

 

C

依题意模拟即可。需要注意的是数据范围较大,因此需要调整次序,并采用 mapunordered_map 等结构维护映射。

#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
using namespace std;
struct Character{
	set<string> v, o, n;
	bool opVaild(string oper, string type, string name) {
		return (v.count(oper) || v.count("*")) && (o.count(type) || o.count("*")) && (n.count(name) || n.empty());
	}
};
map<string, Character> cL;
map< string, vector<string> > uL, gL;
int n,m,q;
set<string> nowC;
void init(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		string nowName;
		int X; string S;
		cin>>nowName;
		scanf("%d",&X);
		for(int j=1;j<=X;++j){
			cin>>S;
			cL[nowName].v.insert(S);
		}
		scanf("%d",&X);
		for(int j=1;j<=X;++j){
			cin>>S;
			cL[nowName].o.insert(S);
		}
		scanf("%d",&X);
		for(int j=1;j<=X;++j){
			cin>>S;
			cL[nowName].n.insert(S);
		}
	}
	for(int i=1;i<=m;++i){
		string s1, s2;
		char typ[2];
		int ns;
		cin>>s1>>ns;
		for(int j=1;j<=ns;++j){
			cin>>typ>>s2;
			if(typ[0]=='u'){
				uL[s2].push_back(s1);
			}else{
				gL[s2].push_back(s1);
			}
		}
	}
	for(int i=1;i<=q;++i){
		nowC.clear();
		string uN,gN,op,typ,sou;
		int ng;
		cin>>uN>>ng;
		nowC.insert(uL[uN].begin(), uL[uN].end());
		for(int i=1;i<=ng;++i){
			cin>>gN;
			nowC.insert(gL[gN].begin(), gL[gN].end());
		}
		cin>>op>>typ>>sou;
		bool bo=0;
		for(auto it=nowC.begin();it!=nowC.end();++it){
//			puts((*it).c_str());
			bo|=cL[*it].opVaild(op, typ, sou);
			if(bo){
				break;
			}
		}
		puts(bo?"1":"0");
	}
}
int main(){
	init();
}

D

注意到数据范围中有信息的点数量较少,我们可以暴力维护每个点。

首先用一个能维护映射的数据结构(如哈希或者平衡树)离散化每行/每列,于是问题转化为求前驱或后继,只须再套上一个平衡树即可。均可使用 std::map 实现。

之后,对每个询问暴力模拟即可。算一下对数发现折射的次数是较少的。

#include<iostream>
#include<map>
#include<cmath>
using namespace std;
const int N=100005;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
struct Face{
	int x1,y1,x2,y2,dir;
	double a;
}f[N];
int m;
map< int,map<int,int> > mx,my;
void prnt(int X,int Y,double I){
	printf("%d %d %d\n",X,Y,(int)I);
}
int dD(int D,int dlt){
	return (D + 4 + dlt) % 4;
}
void srch(int X,int Y,int D,double I,int T){
	if(I <= 1.0 - 1e-10){
		prnt(0,0,0);
		return;
	}
//	printf("%d %d %d %lf %d\n", X, Y, D, I, T);
	switch(D){
		case 0:{
			auto it = my[Y].upper_bound(X);
			if(it == my[Y].end() || it -> first - X > T) {
				prnt(X+T, Y, I);
				return;
			}
			int id = it->second;
			srch(it->first, Y, dD(D, (f[id]).dir), I*(f[id]).a, T - (it->first - X));
			break;
		}
		case 1:{
			auto it = mx[X].upper_bound(Y);
			if(it == mx[X].end() || it -> first - Y > T) {
				prnt(X, Y+T, I);
				return;
			}
			int id = it->second;
			srch(X, it->first, dD(D, -(f[id]).dir), I*(f[id]).a, T - (it->first - Y));
			break;
		}
		case 2:{
			auto it = my[Y].lower_bound(X);
			if(my[Y].empty() || it == my[Y].begin()){
				prnt(X-T, Y, I);
				return;
			}
			--it;
			if(X - it->first > T){
				prnt(X-T, Y, I);
				return;
			}
			int id = it->second;
			srch(it->first, Y, dD(D, (f[id]).dir), I*(f[id]).a, T - (X - it->first));
			break;
		}
		case 3:{
			auto it = mx[X].lower_bound(Y);
			if(mx[X].empty() || it == mx[X].begin()){
				prnt(X, Y-T, I);
				return;
			}
			--it;
//			printf("%d %d\n",it->first, it->second);
			if(Y - it->first > T){
				prnt(X, Y-T, I);
				return;
			}
			int id = it->second;
			srch(X, it->first, dD(D, -(f[id]).dir), I*(f[id]).a, T - (Y - it->first));
			break;
		}
	}
}
void init(){
	scanf("%d",&m);
	for(int i=1;i<=m;++i){
		int op;
		scanf("%d",&op);
		if(op==1){
			int nx1,nx2,ny1,ny2,dir;double a;
			cin>>nx1>>ny1>>nx2>>ny2>>a;
			if(nx1>nx2){
				swap(nx1,nx2);swap(ny1,ny2);
			}
			dir=1ll*(nx1-nx2)*(ny1-ny2)>0?1:-1;
			f[i]=(Face){nx1,ny1,nx2,ny2,dir,a};
			for(int j=nx1+1,k=ny1+dir;j<nx2;++j,k+=dir){
				mx[j][k] = i;my[k][j] = i;
			}
		}else if(op==2){
			int x;
			scanf("%d",&x);
			for(int j=f[x].x1+1,k=f[x].y1+f[x].dir;j<f[x].x2;++j,k+=f[x].dir){
				mx[j].erase(k);my[k].erase(j);
			}
		}else{
			int x,y,d,t;double I;
			scanf("%d%d%d%lf%d",&x,&y,&d,&I,&t);
			srch(x,y,d,I,t);
		}
	}
}


int main(){
	init();
	return 0;
}

 

E

线段树/分块维护矩阵乘法。

据称 亦可通过此题。

#include<iostream>
#include<cstdio>
#include<cmath>
const int N=500005;
int n,q;
struct Point{
	double x,y;
	
	Point operator+(const Point &B)const{
		return (Point){x+B.x,y+B.y};
	}
	
	Point operator-(const Point &B)const{
		return (Point){x-B.x,y-B.y};
	}
	
	Point operator+=(const Point &B){
		*this = *this + B;
		return *this;
	}
	
	Point operator-=(const Point &B){
		*this = *this - B;
		return *this;
	}
	
	Point operator-(){
		return (Point){0, 0} - *this;
	}
	
	void pRot(const Point &B, double theta){
		Point C = *this - B;
		double ct = cos(theta), st = sin(theta);
		C = (Point){C.x * ct - C.y * st, C.x * st + C.y * ct};
		C += B;
		x=C.x,y=C.y;
	}
	void pScale(const Point &B, double lamb){
		Point C = *this - B;
		C.x *= lamb, C.y *= lamb;
		C += B;
		x=C.x,y=C.y;
	}
	void pShot(double theta, double y0){
		double k0 = tan(theta);
		double sx = 1 / sqrt(k0 * k0 + 1);
		double sy = k0 * sx;
		y -= y0;
		double len = x * sx + y * sy;
		x = sx * len, y = sy * len;
		y += y0;
	}
	void pMirr(double theta, double y0){
		Point C = *this;C.pShot(theta, y0);
		pScale(C, -1);
	}
}p[N];

void slv1(){
	for(int i=1;i<=q;++i){
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		switch(op){
			case 1:{
				double x,y;
				scanf("%lf%lf",&x,&y);
				for(int j=l;j<=r;++j){
					p[j] += (Point){x,y};
				}
				break;
			}
			case 2:{
				double x,y,theta;
				scanf("%lf%lf%lf",&x,&y,&theta);
				for(int j=l;j<=r;++j){
					p[j].pRot((Point){x,y}, theta);
				}
				break;
			}
			case 3:{
				double x,y,lamb;
				scanf("%lf%lf%lf",&x,&y,&lamb);
				for(int j=l;j<=r;++j){
					p[j].pScale((Point){x,y}, lamb);
				}
				break;
			}
			case 4:{
				double theta, y0;
				scanf("%lf%lf",&theta,&y0);
				for(int j=l;j<=r;++j){
					p[j].pMirr(theta, y0);
				}
				break;
			}
			case 5:{
				double theta, y0;
				scanf("%lf%lf",&theta,&y0);
				for(int j=l;j<=r;++j){
					p[j].pShot(theta, y0);
				}
				break;
			}
			case 6:{
				double x=0,y=0;
				int len=r-l+1;
				for(int j=l;j<=r;++j){
					x+=p[j].x;y+=p[j].y;
				}
				printf("%.10lf %.10lf\n",x/len,y/len);
				break;
			}
			case 7:{
				double x=0,y=0,x2=0,y2=0;
				double A,B;int len=r-l+1;
				scanf("%lf%lf",&A,&B);
				for(int j=l;j<=r;++j){
					x+=p[j].x;y+=p[j].y;x2+=p[j].x*p[j].x;y2+=p[j].y*p[j].y;
				}
				printf("%.10lf\n",x2+y2-2*A*x-2*B*y+A*A*len+B*B*len);
				break;
			}
		}
	}
}

int main(){
//	freopen("./E/5.in","r",stdin);
//	freopen("./E/5.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%lf%lf",&p[i].x,&p[i].y);
	}
	slv1();
}

 

第 24 次 CCF CSP 题解


第 24 次 CCF CSP 题解

A

推式子,统计每个数 的贡献,显然每有一个比它大且比它的后继小的数都会产生 的贡献。于是可以得到下式:

直接求和即可。

#include<iostream>
#include<cstdio>
typedef long long ll;
const int N=205;
int n,m;
int a[N];
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	ll ans=0;
	for(int i=1;i<n;++i){
		ans+=(a[i+1]-a[i])*i;
	}
	ans+=(m-a[n])*n;
	printf("%lld\n",ans);
}


int main(){
	init();
	return 0;
}

 

B

对于这题我们仍然想统计贡献,于是考虑如何去绝对值符号。

我们上一题中的贡献关键节点是 , 现在我们考虑 的值发生变化的点,它们是 。将这些点和数列 拼接并排序后得到新的序列 ,在序列 中,每一段的 的值都是相同的。于是可以继续统计贡献,得到:

#include<iostream>
#include<cstdio>
#include<algorithm>
typedef long long ll;
const int N=100005;

inline ll Abs(ll X){
	return X>=0?X:-X;
}
ll n,m,r;
ll a[N],b[N<<1];
inline ll f(ll X){
	return std::upper_bound(a+1,a+1+n,X)-a-1;
}
inline ll g(ll X){
	return X/r;
}

inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	r=m/(n+1);ll tot;
	for(tot=1;tot*r<=m;++tot){
		b[n+tot]=tot*r;
	}
	tot+=n;
	b[++tot]=m;
	std::sort(b+1,b+1+tot);
	ll ans=0;
	for(int i=1;i<tot;++i){
		ans+=(b[i+1]-b[i])*Abs(f(b[i])-g(b[i]));
	}
	printf("%lld\n",ans);
}


int main(){
	init();
	return 0;
}

 

C

依题意模拟即可。

有一个数论成份:中间需要进行一次多项式除法。所幸时间复杂度要求较低,直接模拟即可。

#include<iostream>
#include<cstdio>
#include<cstring>
const int N = 2005;
const int MOD = 929;

int typ(char X){
	return ('0'<=X&&X<='9')?3:('a'<=X&&X<='z')?2:1;
}

int id(char X){
	return (typ(X)==1)?X-'A':((typ(X)==2)?X-'a':X-'0'); 
}


int w,s,n,k;
char ch[N];
int ans[N],tp=1;
int str[N],stp=0;
int pw3[N];
int d[N],g[N],r[N],tmp[N];

//now max x^(A-1), tms x+B;
inline void mlt(int A,int B){
	for(int i=0;i<A;++i){
		tmp[i]=g[i];
	}
	for(int i=A;i>0;--i){
		g[i]=g[i-1];
	}
	g[0]=0;
	for(int i=0;i<A;++i){
		g[i]+=tmp[i]*B%MOD;
		g[i]%=MOD;
	}
}

// reduce which tms A*x^B
inline void red(int A,int B){
	for(int i=B;i<=B+k;++i){
		d[i]-=(g[i-B]*A%MOD);
		d[i]+=MOD;d[i]%=MOD;
	}
}

inline void div(){
	for(int i=tp+k-1;i>=k;--i){
		red(d[i],i-k);
	}
}

inline void genG(){
	g[0]=1;
	for(int i=1;i<=k;++i){
		mlt(i,(MOD-pw3[i])%MOD);
	}
//	for(int i=0;i<=k;++i){
//		printf("%d ",g[i]);
//	}
//	puts("");
}

inline void init(){
	scanf("%d%d",&w,&s);
	k=(s>=0)?(1<<(s+1)):0;
	std::cin>>ch+1;
	n=strlen(ch+1);
	ch[0]=='S';
	for(int i=1;i<=n;++i){
		if(typ(ch[i])!=typ(ch[i-1])){
			if(typ(ch[i])==2){
				str[++stp]=27;
			}else if(typ(ch[i])==3){
				str[++stp]=28;
			}else if(typ(ch[i-1])==3){
				str[++stp]=28;
			}else{
				str[++stp]=28;
				str[++stp]=28;
			}
		}
		str[++stp]=id(ch[i]);
	}
	if(stp&1){
		str[++stp]=29;
	}
	for(int i=1;i<=stp;i+=2){
		ans[++tp]=30*(str[i])+str[i+1];
	}
	while((tp+k)%w){
		ans[++tp]=900;
	}
	ans[1]=tp;
	if(s==-1){
		return;
	}
	for(int i=0;i<k;++i){
		d[i]=0;
	}
	for(int i=1;i<=tp;++i){
		d[i+k-1]=ans[tp-i+1];
	}
	genG();
	div();
	for(int i=0;i<k;++i){
		ans[++tp]=(MOD-d[k-i-1])%MOD;
	}
}


int main(){
	pw3[0]=1;
	for(int i=1;i<=1000;++i){
		pw3[i]=pw3[i-1]*3%MOD;
	}
//	for(int i=0;i<=8;++i){
//		k=(1<<i+1);
//		genG();
//	}
	init();
	for(int i=1;i<=tp;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
}

 

D

据称是线段树模板题。我用的是平衡树模拟区间操作,同样可以通过此题。

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
struct Data{
	int l;int r;int id;int v;mutable bool bo;
	bool operator<(const Data &B)const{
		return r<B.r;
	}
};

std::set<Data> st;
int n,m,q;

inline std::set<Data>::iterator srch(int X){
	return st.lower_bound((Data){0,X,0,0,0});
}

//split between X & X+1:
inline void split(int X){
//	printf("split from:%d\n",X);
	std::set<Data>::iterator it = srch(X);
	if(it == st.end() || X == m || it->r == X || it->l > X){
		return;
	}
	int l=it->l,r=it->r,id=it->id,v=it->v,bo=it->bo;
	st.erase(it);
	st.insert((Data){l,X,id,v,bo});
	st.insert((Data){X+1,r,id,v,bo});
}


inline int add(int L,int R,int ID,int X){
	split(L-1);split(R);
	std::set<Data>::iterator itx = srch(L);
	if(itx == st.end() || itx->l > R){
		st.insert((Data){L,R,ID,X,1});
		return R;
	}
	int R1=L-1;
	std::set<Data>::iterator ity;
	bool nbo=0;
	for(ity = itx; ity!=st.end()&&ity->l<=R;++ity){
		R1=ity->l-1;
		if(ity->id != ID && ity->bo){
			nbo=1;
			break;
		}
	}
	if(!nbo){
		R1=R;
	}
	if(R1<L){
		return -1;
	}
	st.erase(itx,ity);
	st.insert((Data){L,R1,ID,X,1});
	return R1; 
}

inline void prnt(std::set<Data>::iterator it){
	if(it==st.end()){
		puts("end");
		return;
	} 
	printf("%d %d %d %d %d\n",it->l,it->r,it->id,it->v,it->bo);
}

inline bool del(int L,int R,int ID){
	split(L-1);split(R);
	std::set<Data>::iterator itx = srch(L);
	if(itx == st.end() || itx->l!=L){
		return 0;
	}
	std::set<Data>::iterator ity;
	int R1=L-1;
	for(ity = itx; ity!=st.end()&&ity->l<=R;++ity){
//		prnt(ity);
		if(ity->id != ID || (!ity->bo) || ity->l!=R1+1){
			return 0;
		}
		R1=ity->r;
	}
	if(R1<R){
		return 0;
	}
	for(ity = itx; ity!=st.end()&&ity->l<=R;++ity){
		ity->bo=0;
	}
	return 1;
}

inline bool rbck(int L,int R,int ID){
	split(L-1);split(R);
	std::set<Data>::iterator itx = srch(L);
	if(itx == st.end() || itx->l!=L){
		return 0;
	}
	std::set<Data>::iterator ity;
	int R1=L-1;
	for(ity = itx; ity!=st.end()&&ity->l<=R;++ity){
		if(ity->id != ID || ity->bo || ity->l != R1+1){
			return 0;
		}
		R1=ity->r;
	}
	if(R1<R){
		return 0;
	}
	for(ity = itx; ity!=st.end()&&ity->l<=R;++ity){
		ity->bo=1;
	}
	return 1;
}

inline void init(){
	scanf("%d%d%d",&n,&m,&q);
	int op,id,l,r,p,v;
	for(int i=1;i<=q;++i){
		scanf("%d",&op);
		switch(op){
			case 0:{
				scanf("%d%d%d%d",&id,&l,&r,&v);
				printf("%d\n",add(l,r,id,v));
				break;
			}
			case 1:{
				scanf("%d%d%d",&id,&l,&r);
				puts(del(l,r,id)?"OK":"FAIL");
				break;
			}
			case 2:{
				scanf("%d%d%d",&id,&l,&r);
				puts(rbck(l,r,id)?"OK":"FAIL");
				break;
			}
			case 3:{
				scanf("%d",&p);
				std::set<Data>::iterator it = srch(p);
				if(it == st.end() || it->l>p || it->bo == 0){
					puts("0 0");
				}else{
					printf("%d %d\n",it->id,it->v);
				}
				break;
			}
		}
	}
}


int main(){
	init();
	return 0;
}

 

E

来不及了,打个暴力走人

#include<iostream>
#include<cstdio>
typedef long long ll;
const int N=100005;
const int INF=0x3f3f3f3f;

inline int Max(int A,int B){
	return A>B?A:B;
}

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[N<<1];
int et=0,h[N];
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}

int n,k1,k2;

int rt;
int mx[N],mn[N];
ll dfs(int X,int FA){
	mx[X]=Max(mx[FA],X);
	mn[X]=Min(mn[FA],X);
	ll ret=(mn[X]>=(Min(X,rt)-k1))&&mx[X]<=(Max(X,rt)+k2)&&X>=rt;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			ret+=dfs(e[i].v,X);
		}
	}
	return ret;
}
inline ll calc(int X){
	rt=X;
	for(int i=1;i<=n;++i){
		mx[i]=INF;
		mn[i]=0;
	}
	mn[0]=mx[0]=X;
	return dfs(X,0);
}

inline void slv1(){
	ll ans=0;
	for(int i=1;i<=n;++i){
		ans+=calc(i);
	}
	printf("%lld\n",ans);
}

inline void init(){
	scanf("%d%d%d",&n,&k1,&k2);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	if(n<=5000){
		slv1();
	}
}


int main(){
	init();
	return 0;
}

 

知识图谱领域部份论文阅读笔记:TransE/H/R/D RotatE PairRE


知识图谱领域部份论文阅读笔记:TransEHRD RotatE PairRE

Trans E

Translating Embeddings

基本概念

将集合里的关系和实体各嵌入(embedding)成 中的一个向量。 Trans E 的合法性是基于下述假设:

设关系 嵌入为 ,实体 嵌入为向量

对于实体 和关系 ,关系 成立当且仅当 在向量空间成立

流程

input: 训练集 , 实体 , 关系 ,差额 , 图谱维度
//为何是 6?

loop:

  • //b 是集合大小
  • for each //在这里 h’ 和 t’ 表示二者之一随机替换成其他实体

这样训练的参量规模是 的。

SGD

上一节我们提到了 是损失函数。

其中 是:

其中表示 意义下的范数, 表示 范数,意义是对自己应用乘法以后开根号。上式可以理解为 的简单展开。

当然这里的加法和乘法(包括乘方)都是构成 的群操作和域操作。

Trans H

Translating Hyperplanes

基本概念

事实上, Trans E 的假设是建立在关系集合 中每一个单独的关系 对应的图的边的出入度都至少为 的基础上。

倘若任意关系 存在度数不为 的点,那么在把元素映射到线性空间时 就会迫使这个度数不为 的点相邻的点映射到相近的位置。尽管它们可能完全不同。

Trans H 为了解决这个问题做出如下假设:

设关系 嵌入为法向量为 维超平面及其上的向量 ,实体 嵌入为向量

则对于实体 和关系 ,关系 成立当且仅当 恒成立。

其中:

如果说 Trans E 是把关系集合里的每一张图都嵌入成 中的一个向量,那 Trans H 就是改为把这张图嵌入成 中的 维超平面及其上的一个向量。显然,听起来把一张图嵌入成一个平面比嵌入成一个向量科学很多。

损失函数

其中

其中 表示先后的情况。

这样训练的参量规模是 的。

 

Trans R

Translating Relations

基本概念

Trans H 把每个关系的那张图嵌入到一个平面中,而 Trans R 则认为每个关系是将原空间进行一次线性变换,然后线性变换之后,关系两端的向量会各自聚成一堆。因此,它做出如下假设:

设关系 可被看做 上的某种线性变换 和变换后的向量空间中的向量 ,实体 嵌入为向量

则关系 成立当且仅当 在向量空间成立。

 

损失函数

损失函数基本同上。

同样地有评分函数

损失函数也同理。

CTrans R

所谓 Cluster-based TransR ,基于聚类的 Trans R

基本思路是对映射后的实体对的差值做聚类。

对于每个聚类 得到评分函数:

显著缺点

Trans R 在性能上存在一个明显的缺点:线性变换需要一个 级别的矩阵,因此需要训练的参量规模是 级别的。这意味着,随着对拟合度要求的提高(即向量空间维数 的增加),参量规模会显著提升并迅速变得不可接受。

Trans D

Translating Dynamic Mapping Matrix

基本概念

Trans D 认为,前面的几种模型是建立在反对称的关系上的。但事实上,关系未必总是反对称(甚至可能是对称的)。所以,在一些特定的样本中,前述模型就会出现问题。

一个自然的想法就是区分头实体和尾实体。

Trans D 于是尝试将每个实体各自嵌入到两个向量:它的位置,和它作为头/尾实体时的调整。

它作出如下假设:

设关系 嵌入为 上的位置向量 和投影向量 ,实体 嵌入为位置向量 和投影向量

则关系 成立当且仅当 在向量空间成立。

其中:

这样处理,除了可以拟合非对称的关系以外还有一个优点就是它显著降低了参量规模。因为这里的线性变换矩阵 是通过投影向量实时(所谓的 Dynamic !)生成的,所以参量规模降低到了 。当然,这一定层度上会降低拟合效率。

损失函数

估价函数是:

RotatE

Rotate Embedding(大概)

基本概念

上述的模型都是将关系对映射到 的。自然地联想到,可以尝试将它映射到其他向量空间中。一个可以考虑的对象是

RotatE 上作出如下假设:

设关系 嵌入为 ,实体 嵌入为向量

关系 成立当且仅当 在向量空间成立。

其中 表示 Hadamard 积,而非作用在 上的那个域的乘法(内积)。

那么有距离函数:

这里的范数是内积意义上的。(显然, Hadamard 积不能导出范数)

RotatE 相比与 Trans E 的一大优势是它良好地解决了对称关系的问题:如果 的每一个分量都是 的话,它就代表一个对称关系。

最优化方案

最优化的核心仍然是设计损失函数。 RotatE 采用了一种被称为「负采样」的损失函数设计方式:

其中 Sigmoid 函数,即 是各自将其第 个分量替换以后得到的向量。 是负样本集合规模。

自对抗采样

设计权值函数

其中 是一个「温度」参量。这个权重将替换上文的 而作为每个样本的权重。

这是因为作者认为不同的负样本在学习的时候能够提供不同的启发性。如果一个负样本的估值函数很正,说明它还没有被良好地和正样本区分开,那它就需要加上更多的权重;反之,它就已经被良好地区分开了,于是就不必特别考虑它的影响。这种方法可以有效提升训练效率。

PairRE

Paired Relation Embedding

基本概念

上述的模型常常遇到一个问题,就是无法同时优质拟合多对多、 对多、多对 的关系。就是说,它对度数分布比较复杂的关系拟合可能会出现问题。因为误差参量(margin) 是个固定值。

PairRERotatE 的基础上做了一些改良。它结合了 Trans D 的思想,作出如下假设:

设关系 嵌入为 ,实体 嵌入为向量

关系 成立当且仅当 在向量空间成立。

其中 表示Hadamard 积。

另外, PairRE 还做到了较好的拟合子关系:

若存在子关系对 ,使得 ,则施加如下约束:

这样就能推导出前者。证明是显然的。

PairRE 的另一个特点是区分了多对多、 对多、多对 的关系。类似于 Trans D ,它通过区分每个关系向量和头实体的相关与其和尾实体的相关,得到了j较好的拟合性。

中间有一些精妙的数学推导,详见论文。

最优化

估价函数:

同样是进行了负采样和自对抗采样。

论文打包下载地址:http://SmokeyDays.top/wordpress/wp-content/uploads/2022/04/KGE-References-TransEHRD-RotatE-PairRE.zip

PyTorch 环境配置踩坑记录 – 1

首先配好 Anaconda

参照https://blog.csdn.net/weixin_47525457/article/details/115287373

1.5G的包始终装不上

用镜像。如清华提供的镜像:

 https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/main/
 https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/

CUDA 不匹配

典型报错:

The current PyTorch install supports CUDA capabilities sm_37 sm_50 sm_60 sm_61 sm_70 sm_75 compute_37.
If you want to use the GeForce RTX 3060 Laptop GPU GPU with PyTorch, please check the instructions at https://pytorch.org/get-started/locally/

在NVIDIA的控制面板里查看CUDA版本,我是11.6.58,故而在下载Pytorch的时候应当使用这样的指令:

conda install pytorch torchvision torchaudio cudatoolkit=11.3 -c pytorch

OSError: [WinError 1455] 页面文件太小,无法完成操作。

往往体现在。

Error loading “\site-packages\torch\lib\caffe2_detectron_ops_gpu.dll“ or one of its dependencies.

首先需要在控制面板-查看高级系统设置中,给Python的安装盘(我是D盘)配置额外的虚拟内存。

参见https://www.cnblogs.com/blue-lin/p/14982097.html

同时调小 BATCH_SIZE 和 num_workers。

之所以调小后者,可参见:

https://github.com/ultralytics/yolov3/issues/1643#issuecomment-985652432

这个comment讲得鞭辟入里。

具体来说就是,它会载入一个dll文件,尽管这个dll文件里的绝大部分都用不到;windows系统会给它预留非常充分的内存;而多线程运行的时候每次 import torch 都会载入一遍,这就无端占据了巨额的内存,以至于怎么分配都不足够。

无论如何,总算跑起来了!

(希望不会有下一个踩坑记录)

CF558E A Simple Task

开一颗珂朵莉树,对于每个新的查询,先把l-1,l之间和r,r+1之间split开,然后对于剩下的部份用桶排序并暴力合并即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set> 
using namespace std;
const int N=100005;

struct Data{
	int l;int r;char id;
	bool operator<(const Data &B)const{
		return r<B.r;
	}
};
int n,q;
char ch[N];
std::set<Data> st;
inline void split(std::set<Data>::iterator it, int X){
	int l=it->l,r=it->r;char id=it->id;
	if(X<l||X>=r){
		return;
	}
	st.erase(it);st.insert((Data){l,X,id});st.insert((Data){X+1,r,id});
}
int bckt[30];
inline void clr(){
	for(int i=0;i<26;++i){
		bckt[i]=0;
	}
}
inline void uni(int l,int r,int op){
	std::set<Data>::iterator itx,ity;
	itx=st.lower_bound((Data){0,l-1,0});
	split(itx,l-1);
	ity=st.lower_bound((Data){0,r,0});
	split(ity,r);
	itx=st.lower_bound((Data){0,l,0});
	ity=st.lower_bound((Data){0,r,0});
	++ity;
	for(std::set<Data>::iterator it=itx;it!=ity;++it){
		bckt[(it->id)-'a']+=(it->r)-(it->l)+1;
	}
	st.erase(itx,ity);
	int loc,nl=l;
	for(int i=0;i<26;++i){
		loc=op?i:(26-i-1);
		if(bckt[loc]<=0){
			continue;
		}
		st.insert((Data){nl,nl+bckt[loc]-1,'a'+loc});
		nl+=bckt[loc];
	}
	clr();
}
inline void prnt(){
	for(std::set<Data>::iterator it=st.begin();it!=st.end();++it){
		for(int j=it->l;j<=it->r;++j){
			putchar(it->id);
		}
	}
	puts("");
}
inline void init(){
	scanf("%d%d",&n,&q);
	std::cin>>ch+1;
	for(int i=1;i<=n;++i){
		st.insert((Data){i,i,ch[i]});
	}
	int l,r,op;
	for(int i=1;i<=q;++i){
		scanf("%d%d%d",&l,&r,&op);
		uni(l,r,op);
//		prnt();
	}
	prnt();
}

int main(){
	init();
	return 0;
}

CF527C Glass Carving

开四个set,分别存切割的刀以及每个区间段,然后每次各自从行和列取最长的区间段,乘一起即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;


ll w,h;
std::set<ll> st[2];
std::multiset<ll> sm[2];
std::multiset<ll>::iterator it;

inline void init(){
	char ch[5];ll x,l,r;int id;
	std::cin>>ch+1;scanf("%lld",&x);
	id=(ch[1]=='H');
	set<ll> &nst=st[id];
	multiset<ll> &nsm=sm[id];
	nst.insert(x);
	it=nst.find(x);
	--it;l=*it;
	++it,++it;r=*it;
	it=nsm.find(r-l);
	nsm.erase(it);nsm.insert(r-x);nsm.insert(x-l);
	it=sm[0].end();--it;l=*it;
	it=sm[1].end();--it;r=*it;
	printf("%lld\n",l*r);
}

int main(){
	scanf("%lld%lld",&w,&h);
	int T;
	scanf("%d",&T);
	st[0].insert(0),st[0].insert(w);
	st[1].insert(0),st[1].insert(h);
	sm[0].insert(w),sm[1].insert(h);
	while(T--){
		init();
	}
	return 0;
}

lp3902 递增

最长上升子序列裸题。
dp+二分即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=100005;
const int INF=0x3f3f3f3f;
inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}
int n,a[N],f[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	memset(f,0x3f,sizeof(f));
	f[1]=a[1];
	int pos,ans=1;
	for(int i=2;i<=n;++i){
		pos=lower_bound(f+1,f+1+n,a[i])-f-1;
		ans=Max(ans,pos+1);
		f[pos+1]=Min(f[pos+1],a[i]);
	}
	printf("%d\n",n-ans);
}

int main(){
	init();
	return 0;
}

lp1438 无聊的数列

区间加上一个等差数列这件事情其实并不好维护。但既然是单点查询,那就可以考虑差分。
我们考虑将数列差分,维护一个差分数列。于是区间 [l,r] 加上等差数列 {K,D},就变成了三个操作:
点 l 加上 K
区间 [l+1,r] 加上 D
点 r+1 减去 K+(r-l)*D
对于每个查询求前缀和即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

const int N=100005;
int n,m;
ll a[N];
ll val[N<<2],tag[N<<2];
inline void pshd(int L,int R,int X){
	int MID=(L+R)>>1;
	tag[X<<1]+=tag[X];tag[X<<1|1]+=tag[X];
	val[X<<1]+=tag[X]*(MID-L+1);val[X<<1|1]+=tag[X]*(R-MID);
	tag[X]=0;
}
inline void updt(int X){
	val[X]=val[X<<1]+val[X<<1|1];
}
ll qry(int L,int R,int A,int B,int X){
	if(A<=L&&B>=R){
		return val[X];
	}
	int MID=(L+R)>>1;ll ret=0;
	pshd(L,R,X);
	if(A<=MID){
		ret+=qry(L,MID,A,B,X<<1);
	}
	if(B>MID){
		ret+=qry(MID+1,R,A,B,X<<1|1);
	}
	return ret;
}
void mdf(int L,int R,int A,int B,int X,ll V){
	if(A<=L&&B>=R){
		tag[X]+=V;
		val[X]+=V*(R-L+1);
		return;
	}
	int MID=(L+R)>>1;
	pshd(L,R,X);
	if(A<=MID){
		mdf(L,MID,A,B,X<<1,V);
	}
	if(B>MID){
		mdf(MID+1,R,A,B,X<<1|1,V);
	}
	updt(X);
}
void build(int L,int R,int X){
	if(L==R){
		val[X]=a[L];
		return;
	}
	int MID=(L+R)>>1;
	build(L,MID,X<<1);
	build(MID+1,R,X<<1|1);
	updt(X);
}
inline void chg(int L,int R,ll V){
	if(L>R||L<1||R>n){
		return;
	}
	mdf(1,n,L,R,1,V);
}
inline void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=n;i>1;--i){
		a[i]-=a[i-1];
	}
	build(1,n,1);
	ll opt,l,r,k,d,p;
	for(int i=1;i<=m;++i){
		scanf("%lld",&opt);
		if(opt==1){
			scanf("%lld%lld%lld%lld",&l,&r,&k,&d);
			chg(l,l,k);chg(l+1,r,d);chg(r+1,r+1,-(k+d*(r-l)));
		}else{
			scanf("%lld",&p);
			printf("%lld\n",qry(1,n,1,p,1));
		}
	}
}

int main(){
	init();
	return 0;
}

lp2757 [国家集训队]等差子序列

因为只要求存在性,故而观察到长度>3的等差序列只需要求前3项即可。
于是就转化为求 $$ a_j+a_k=2*a_i $$ 是否存在。
观察到数据范围 n<=10000 ,于是用两个 bitset 分别维护前缀桶和后缀桶,稍微左右移一下求交即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;
/*

*/
const int N=10005;
bitset<N> pre,lst;
int n,a[N];
inline void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	pre.reset();lst.reset();
	for(int i=2;i<=n;++i){
		lst[n-a[i]]=1;
	}
	for(int i=2;i<n;++i){
		pre[a[i-1]]=1;lst[n-a[i]]=0;
		if(((2*a[i]>=n?lst<<(2*a[i]-n):lst>>(n-2*a[i]))&pre).any()){
			puts("Y");
			return;
		}
	}
	puts("N");
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

易错点整理

文件及输入输出相关

文件输入输出要注意,文件名不要打错,一定要复制。

文件要独立。

打表要用文件输出,防止手抖。

随手 ctrl+s 。

输入不要想当然,n m 不要弄反。

std 相关

变量不要冲突。

DevC++ 可能会放一些莫名其妙的代码过。有的可能交上去 CE 的本地可以编译通过。头文件一定要记得开。

multi_set 删点的时候不能指定名字并删除,要找到以后再删除。

变量与操作

逻辑或是用在bool上的。

三目运算符和逗号的优先级。位运算的优先级。实在拿不准就加括号。

结构体内重载运算符如果类型不对可能会 CE ,记得要写 const 。

ull 的左移有坑!!!

取模

快速幂的底数要先取模,因为 long long 乘 long long 可能会爆掉。

多测

多测要清空,但不要 memset ,同 dsu on tree 。

CSP 2019

退役了。

Day1 大众分应该是 210 。

记住,写东西的时候要写 1ull<<N ,而非 1<<N 。 我 T1 在这里被卡了一个多小时,直接导致 T3 没有时间写暴力。 T2 反正大家都会做就不说了,大概就是树形 DP ,优化一下状态转移。有一个 trick 就是括号可以考虑前缀和什么的。 T3 不会做。不过 35pts 的暴力其实还是挺好想的。实在是时间不够。 估分 200 pts。

Day2 大众分应该是 263 。

T1 整个人都傻了。一道傻逼容斥居然没想出来。其实挺显然的,提示也给得很多,但是大概是题面太长,给了一些干扰吧。写了 m=3 的暴力走人。 T2 人没了。大概花了二十分钟左右的时间猜了一个结论,感觉挺正确的,大概就是如果你能分割最多份并且每一份的大小都尽可能小,那么答案是最优的。写了份代码调了一下。反正就记一个 g 函数表示以当前点结尾的最小值。然后记一下前缀和移项用单调栈优化一下转移就好了。然后写了个暴力拍了一下。还写了个高精。结果最后暴力拍出问题了。人都傻了,只好把暴力交上去走人。结果出来一对答案,发现我正解写得是对的,暴力写挂了。人没了。 T3 没有仔细想,写了 55 分的暴力。其实二叉树的结论挺好想的,但是没认真打,其实打了还是收益更高的。 想来想去还是 T2 犯的错太可惜了,一下子少掉了一大堆分。 估分 119 pts。

总估分 319 pts。

其实本来就知道这场已经是退役场了,只是没想到会退役得那么惨。

高一开始搞 OI ,当时意气风发。然后从 NOIP 到省选,再到 CTSC-APIO ,接二连三地,总是没能发挥出全力、总是出现这样那样的问题、总是把能拿的分给丢了。

其实考试的时候的题并不是题题都那么难。但是一方面自己经验不足,在考场上总是会出现这样那样的错误,有的时候是对分数的估计没有那么准确,有的时候是一些小点不知道导致调题调了很久,有的时候是没看出来一些显然的结论。大概是写题的时候总是没有理清思路吧。

所以就退役了吧,也就断了这份念想。

说到底还是菜。但是只是「菜」这个字是无法概括的。「菜」是有很多种形式的、是由很多个部分构成的。如果没有仔细地分析其中的每一个成分,那就没办法解决这个问题。

其实最近的出题趋势有点向国外靠拢的意思,也就是,大码农题逐渐变少,而有趣的结论题、有一定思维难度的题则增多。其代表就是 DP 题的逐渐增加。 从这个角度上说,刷一刷 Atcoder 或者 Codeforces 的意义是很大的。 然而我并没有发现这个趋势,也没有认真地培养自己的思维能力。

当然另一方面就是代码能力的问题。譬如,如果那一次和 XRJ 一起手写 bitset ,那我在 Day1T1 ,就不会在那个错上花那么多时间。

还有就是考试策略。实际上,考试的时候,应当要看好每一个部分分、预估一下难度。这样可能会发挥得更好一些。诸如 D1T1 为了 5pts 花了一个多小时、 D2T2 为了 12pts 花了快一个小时,都是相似的原因。

说到底,就是这样一个风气:我 A 了这道题,所以我牛逼。 但是其实考场上这个心态是毫无意义的。 然而 AC 实在是太爽了。你看到那一片大大的绿色,正反馈简直是无穷的。 所以即便明白这个道理也很难改正。

再有一个问题就是做题时的劲。唯独在考试的时候才能有一种无往不利的锐气,才能想出很多平时呆坐半天都无法解决的结论。说不定是猜结论的时候胆子不够大吧。

说也挺可笑的,我现今怀念以前的时候比展望未来的时候竟要多得多。 即便到了今日,对现今的状况仍然没有什么实感。实感想必是之后的事情了。

又有什么可说的呢? 那就这样了吧。

「过去的事情就过去了吧。」这样的话实在是太好说出口了。然而正是这种话太好说出口,所以不免惹得疑心这事情是否曾经挂在心上。 或许在多年之后,我仍然会梦回今日,遗憾着当时的 Day2 怎么考得那么差。但是 CSP2019 只不过是一个迟来的句号,就好比古典音乐结束之后那悠扬的尾声淡出于空气之中的那个位置。我的 OI 生涯其实早在那之前就结束了。

今から後悔しても無駄です。

这个博客我也许还会挂在这里,留待以后使用;也许会就此关停。 但那又有什么关系呢,这毕竟只是个写给自己看的博客啊。

在最后的时刻看到他们在讨论 D2T2 ,我又想冲上去把我 D2T2 犯的错大说特说,毕竟这是我此刻要紧的感受。
然后在此时我突然意识到:那又有什么用呢?他们尚且有下一年,而我已经不在此间了。
于是疏离感淹没了我。
我的手离开了键盘。

lp5431 【模板】乘法逆元2


挺套路的。
先计算出所有数的积的逆元,再计算除了这个数以外的数的积,然后乘一起,这样就完成了线性求逆元。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
const int N=5000005;
inline int rd(){
	int rt=0;char ch=getchar();
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){rt=rt*10+ch-'0';ch=getchar();}
	return rt;
}
int n,MOD,k;
int a[N],pr[N],sf[N];
inline int pw(int A,int X){
	int RT=1;
	while(X){
		if(X&1){
			RT=1ll*RT*A%MOD;
		}
		A=1ll*A*A%MOD;X>>=1;
	}
	return RT;
}

void init(){
	scanf("%d%d%d",&n,&MOD,&k);
	int pl=1;
	pr[0]=sf[n+1]=1;
	for(int i=1;i<=n;++i){
		a[i]=rd();
	}
	for(int i=1;i<=n;++i){
		pr[i]=1ll*pr[i-1]*a[i]%MOD;
	}
	pl=pw(pr[n],MOD-2);
	for(int i=n;i>=1;--i){
		sf[i]=1ll*sf[i+1]*a[i]%MOD;
	}
	int nk=1;
	int ans=0;
	for(int i=1;i<=n;++i){
		nk=1ll*nk*k%MOD;
		ans+=1ll*(1ll*pr[i-1]*sf[i+1]%MOD)*(1ll*pl*nk%MOD)%MOD;ans%=MOD;
	}
	printf("%d\n",ans);
	
}
int main(){
	init();
	return 0;
}

lp3225 HNOI2012 矿场搭建

这实际上是一个 Tarjan 求割点的裸题。

具体来说是这样的。首先,对于每一个连通块,答案显然是独立的。然后,一个连通块至少要有两个出口——这也是容易理解的。

接下来,我们把所有点双都缩成一个点,这时候整张图就一定是一棵无根树。

我们观察这棵树。如果树上只有一个节点,那么两个出口就都必须设在这个点双中;如果树上有多个节点,那么有且仅有叶子节点要各自设一个出口:这是因为,对于非叶子节点,它都有多条路走向叶子节点。

现在问题是如何求出这棵树。我们不妨用 Tarjan 来求。

Tarjan 是一种用于求点双联通分量的常用算法,以其发明者 Tarjan 所命名。特别需要注意的是,这里用到的是 Tarjan 求割点的部分,而不是像圆方树那样求点双的部分。

对于一个点,我们记两个数组,dfn 和 lw,分别表示它的 dfs 序和它在 dfs 树的子树内的所有节点的返祖边中 dfs 最小的节点。

如果某一个节点,它是根节点,并且它在 dfs 树上有超过一个子节点,那么它必然是割点——这是由 dfs 树的性质决定的。

如果一个节点,它的子节点的 lw 总是大等于它的 dfn ,那么就说明它的这棵子树内的所有节点只能抵达它或者它子树内的点,因而它必然是割点。

结合这两条性质即可找出点双。

然后统计一下即可。存在一定的细节。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=505;
struct ee{
	int v;
	int nxt;
}e[N<<2];
struct Data{
	int u;int v;
}lst[N<<2];
int g[N],h[N],et=0;
inline void Eadd(int U,int V,int *H){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int U,int V,int *H){
	Eadd(U,V,H);
	Eadd(V,U,H);
}
int n;
int dfn[N],lw[N],dfsid=0,cnt=0,ag[N],sn[N];
inline void dfs0(int X,int FA){
	dfn[X]=lw[X]=++dfsid;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		if(!dfn[e[i].v]){
			++sn[X];
			dfs0(e[i].v,X);
			lw[X]=min(lw[X],lw[e[i].v]);
			if((FA&&lw[e[i].v]>=dfn[X])){
				ag[X]=1;
			}
		}else{
			lw[X]=min(lw[X],dfn[e[i].v]);
		}
	}
	if(!FA&&sn[X]>1){
		ag[X]=1;
	}
}
ll vis[N],sm[N],tot[N],cal,sz,nv,deg[N];
inline void dfs1(int X){
	vis[X]=nv;++sz;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]==nv){
			continue;
		}
		if(ag[e[i].v]){
			vis[e[i].v]=nv;++cal;
			continue;
		}
		dfs1(e[i].v);
	}
}
ll ans,cans,nt;
void init(){
	cnt=et=dfsid=nt=0;
	for(int i=1;i<=n;++i){
		h[i]=dfn[i]=lw[i]=vis[i]=sm[i]=tot[i]=deg[i]=ag[i]=0;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		add(u,v,h);
		++deg[u];++deg[v];
		lst[i]=(Data){u,v};
		nt=max(nt,1ll*u);nt=max(nt,1ll*v);
	}
	for(int i=1;i<=nt;++i){
		if(!dfn[i]){
			dfs0(i,0);
		}
	}
//	for(int i=1;i<=nt;++i){
//		printf("%d ",ag[i]);
//	}
//	puts("");
	ans=0,cans=1;
	for(int i=1;i<=nt;++i){
		if(ag[i]){
			if(deg[i]<=1){
				++ans;
			}
		}else if(!vis[i]){
			nv=i;cal=0;sz=0;
			dfs1(i);
			if(cal==1){
				++ans;cans*=sz;
			}else if(cal==0){
				ans+=(sz==1?1:2),cans*=(sz==1?1:sz*(sz-1)/2);
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	int T=0;
	while(n){
		++T;
		init();
		printf("Case %d: %lld %lld\n",T,ans,cans);
		scanf("%d",&n);
	}
	init();
	return 0;
}

lp4430 猴子打架/Prufer 序列

额…看起来是一道找规律题,实际上还是挺有门道的。

题目的题意就是,求 n 个点的点、边均有标号的生成树个数。

n 个点的无根有标号生成树个数,根据某个叫做 Cayley 的古老定理, 值是:

当然,由于边有标号,所以这里的值还要乘上一个​。

问题是 Cayley 定理要如何证明。

一种比较简易的方法是一种被称为 Prufer 序列的构造。通过这种构造,我们发现,有且仅有 ​ 种不同的方法来构造一棵有标号无根树。

这个序列是如何构造的呢?

我们考虑递归地构造这个序列。对于当前的树,我们选其中的编号最小的叶子节点,将它的相邻点——显然是唯一的——加入序列,然后删掉这个叶子节点。

这样,我们就得到了一个序列。这个序列中每一个点的出现次数是它的入度 -1 。

由此我们可以构造出这个序列。

通过 Prufer 序列,我们无损地将一棵有标号无根树的信息压缩成了一个序列。

那么要怎么把 Prufer 序列还原为一棵有标号无根树呢?我们有一种系统的方法。

首先选择一个数,这个数既不在已有的树中,也不在当前的序列中,并且它最小。那么,我们就可以确定,这个数便是我们当前要处理的叶子节点。

然后,我们把这个节点与当前枚举到的序列中的点连边。这等于是逆向还原 Prufer 序列的生成过程。

是不是对于任何一个值域在 n 范围内的长度为 n-2 的序列都可以还原成一棵树呢?

假设我们当前正在处理第 i 个节点,序列中剩下 k 种数,那么已经被作为叶子节点,已经连接或即将被连接的节点数则是 n-k 个。每处理一个节点,至多会消耗掉一个叶子节点的配额。因此已经连接的节点至多为 i-1 个。又因为 n-2-i+1 必须大于等于 k ,所以叶子节点必然不会不够。

那么完成最后一步以后叶子节点会不会有剩呢?每个节点会被连接的次数正好是它在序列中出现的次数 +1 ,这也就意味着,总度数恰好是 2n-2 ,由于每一条边都无向,所以构成的正好是一张 n-1 条边的图。

最后的疑问就是构成的图是不是连通的。考虑到 n-1 条边的连通图与 n-1 条边的无环图是等价的,我们不妨尝试证明它无环。

我们称,一个点被作为「要处理的叶子节点」来连接的过程为「向上连边」,那么每个点的向上连边操作会且仅会发生一次。在这种情况下,环会出现,只有可能是「向上连边」的时候连向的是自己所在的连通块内的点。

然而,向上连边的目标,一定还在 Prufer 序列中,而可以向上连边的点,一定不在 Prufer 序列中。我们于是证明了这张图无环。

既然这张 n-1 条边的图无环,那么它一定连通。

由此,我们发现,每一棵树都能唯一对应地生成一个 Prufer 序列,并且每一个 Prufer 序列都能生成一棵树。

这样我们就证明了 Prufer 序列和有标号无根树的一一对应性。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=9999991;

inline ll pw(ll A,ll X){
	ll RT=1;
	while(X){
		if(X&1){
			RT*=A;
			RT%=MOD;
		}
		A*=A;A%=MOD;X>>=1;
	}
	return RT;
}
int n;
void init(){
	scanf("%d",&n);
	ll fac=1;
	for(int i=1;i<n;++i){
		fac=fac*i%MOD;
	}
	printf("%lld\n",pw(n,n-2)*fac%MOD);
}
int main(){
	init();
	return 0;
}

lp4577 FJOI2018 领导集团问题

我们尝试类比序列上的情况来看这一题。

对于序列上的情况,我们维护一个集合 \(S\) ,其中 \(S_i\) 表示,长度为 \(i\) 的最长不下降子序列的最后一项的最小值。 那么,对于新的点,我们考虑两种情况:它能加长序列,那么就加长;否则,就尽可能地更新最小值。

对于树上的情况,我们首先尝试考虑一种 \(O(n^2logn)\) 的做法。我们对于每一个节点维护一个集合 \(S_i\), 其中 \(S_{i,j}\) 表示仅用到这个节点及其子树内的所有点,能够构造的大小为 \(j\) 的集合的最小项的最大值。

如果我们把所有子节点的 \(S\) 都已经整合在一起了,那么更新根节点是比较容易的:类比于序列即可。 问题在于子节点要如何合并。

仔细观察,发现,子节点的合并是一个类似于归并的操作。 这样我们就有了一个 \(O(n^2logn)\) 的「高」效做法。

怎么优化这个做法呢? 我们不妨考虑重链剖分启发式合并。这样就将复杂度优化到了 \(O(nlog^2n)\) ,足以通过此题。 具体来说,我们对于每个节点开一个map,然后暴力合并。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=200005;
struct ee{
	int v;
	int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int w[N],sz[N],sn[N],dep[N],fa[N];
int id[N];
multiset<int> lst[N];
int n;
inline void dfs0(int X){
	sn[X]=0,sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
inline void dfs1(int X){
	if(sn[X]){
		dfs1(sn[X]);
		id[X]=id[sn[X]];
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v);
		lst[id[X]].insert(lst[id[e[i].v]].begin(),lst[id[e[i].v]].end());
	}
	lst[id[X]].insert(w[X]);
	multiset<int>::iterator it=lst[id[X]].lower_bound(w[X]);
	if(it!=lst[id[X]].begin()){
		--it;lst[id[X]].erase(it);
	}
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
		id[i]=i;
	}
	int x;
	for(int i=2;i<=n;++i){
		scanf("%d",&x);
		fa[i]=x;add(x,i);
	}
	dfs0(1);
	dfs1(1);
	printf("%d\n",lst[id[1]].size());
}
int main(){
	init();
	return 0;
}

lp4980 【模板】Polya定理

Polya定理是一个关于置换群中组合计数的定理。
首先我们来了解Burnside引理。这个引理的证明较为复杂,在这里仅介绍其内容。
Burnside引理的内容是这样的:在置换意义下本质不同的染色方案数,等于单个置换不会改变的染色方案数的平均值。
那么,单个置换不会改变的染色方案数要怎么求呢?我们不妨把置换关系建成一张图,那么这张图必然由若干个环构成。也就是说,对于同一种置换,可能存在若干个环,而每个初始状态就是环上的一个节点。Polya定理描述的就是,某一种置换不会改变的方案数,等于颜色数的「这个置换对应的循环节个数」

阐述了上述两个定理,现在我们来看这一题。
我们观察到,这个环上存在 n 种置换。对于置换 i 而言,它的循环大小是:
$$
\frac{n}{\gcd(n,i)}
$$
这也就意味着,它的循环个数是:
$$
\gcd(n,i)
$$
那么我们要求的答案就是:
$$
\frac{\sum_{i=1}^nn^{(n,i)}}{n}
$$
然而这样计算答案的复杂度是 O(n) 的,我们无法接受。
我们不妨考虑枚举这个公因子。那么,容易证明的是,每一个公因子d对应的置换个数是\(\varphi(\frac{n}{d})\)

这是因为, d 是 \(\frac{n}{d}\) 个数的因数,而这些数中,如果它和\(\frac{n}{d}\)存在公因子的话,那么它和n的最大公因数必然大于d。

所以,我们求的就是:
$$
\frac{\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}}}{n}=\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}-1}
$$
我们只要枚举n的因数即可。

然而求这里的 \(\varphi\) 倒可能存在一些问题。事实上,由于我们要取的因数的值域是 \(10^9\) ,我们无法使用欧拉筛来预处理,而需要现场做。

这样的复杂度是不是对的呢?它的最坏情况是 \(O(Tn^{\frac{3}{4}})\) 的,但由于我并不会分析的一些性质,它不会达到这个值。因此可以通过此题。

另:括号忘记加,爆O泪两行。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
const int N=1000005;
inline ll pw(ll A,ll X){
	ll RT=1;
	while(X){
		if(X&1){
			RT*=A;RT%=MOD;
		}
		A*=A;A%=MOD,X>>=1;
	}
	return RT;
}
int n;
inline int phi(int X){
	int RT=1;
	for(int i=2;i*i<=X;++i){
		if(X%i==0){
			X/=i;RT*=i-1;
			while(X%i==0){
				X/=i;RT*=i;
			}
		}
		if(X==1){
			break;
		} 
	}
	if(X>1){
		RT*=X-1;
	}
	return RT;
}
void init(){
	scanf("%d",&n);
	ll ans=0;
	for(int i=1;i*i<=n;++i){
		if(n%i==0){
			ans+=(1ll*phi(n/i)*pw(n,i-1))%MOD;
			if(i*i!=n){
				ans+=(1ll*phi(i)*pw(n,n/i-1))%MOD;
			}
			ans%=MOD;
//			printf("%d %lld\n",i,ans);
		}
	}
	printf("%lld\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

CF102268C

贪心构造即可。
具体来说,如果把a依次标成-n…-1,那么只会有三种数:0(贡献是下标-1),n(贡献是0)以及x(贡献是下标比x小且<-x)的数。
贪心地构造,可以保证x只出现一次。暴力枚举检验即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=300005;
int n;ll m;
int a[N],b[N],p[N],q[N];
int bckt[N];
void init(){
	scanf("%d%lld",&n,&m);
	for(int i=0;i<=n;++i){
		bckt[i]=0;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&p[i]);
		a[p[i]]=-n+i-1;
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&q[i]);
		if(m==0){
			b[q[i]]=n;
		}else if(m>=q[i]-1){
			m-=q[i]-1;
			b[q[i]]=-1;
		}else{
			for(int j=1;j<q[i];++j){
				++bckt[a[j]+n];
			}
			for(int j=1;j<=n;++j){
				bckt[j]+=bckt[j-1];
			}
			for(int j=1;j<q[i];++j){
				if(bckt[a[j]+n]==m){
					m=0;b[q[i]]=-a[j]-1;
					break;
				}
			}
		}
	}
	puts("Yes");
	for(int i=1;i<=n;++i){
		printf("%d ",a[i]);
	}
	puts("");
	for(int i=1;i<=n;++i){
		printf("%d ",b[i]);
	}
	puts("");
}
int main(){
	init();
	return 0;
}

CF1009F Dominant Indices

首先介绍一下我们亲爱的dsu on tree,也就是(一种?)树上启发式合并。
它本质上就是一种优化的暴力:对于树上的信息,我们先把树以某种方式剖分,然后对于关键链直接上传,非关键链暴力合并。
其中,长链剖分一般用来维护和深度相关的信息。
复杂度是O(n)的。证明我不太会。
在这一题中,我们考虑暴力维护每个点为根的子树中每一层的信息,并把非长儿子的信息合并到长儿子中。
为了保证线性,我们使用指针。
我们建一个指针数组f,其中f_{i,j}表示以i为根的根节点的子树中到i的距离为j的节点的个数。
同时建一个数组tmp,那么f就变成指向的是tmp里面的值。这样子就可以O(1)合并非长儿子的信息了。因为\sigma len<=n,所以空间是足够的。
那就昨晚了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n;
int sn[N],len[N],ans[N],tmp[N],*f[N],*id=tmp;
inline void dfs0(int X,int FA){
	sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		if(len[sn[X]]<len[e[i].v]){
			sn[X]=e[i].v;
		}
	}
	len[X]=len[sn[X]]+1;
}
inline void dfs1(int X,int FA){
	f[X][0]=1;
	if(sn[X]){
		f[sn[X]]=f[X]+1;
		dfs1(sn[X],X);
		ans[X]=ans[sn[X]]+1;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		f[e[i].v]=id;id+=len[e[i].v];
		dfs1(e[i].v,X);
		for(int j=1;j<=len[e[i].v];++j){
			f[X][j]+=f[e[i].v][j-1];
			if((j<ans[X]&&f[X][j]>=f[X][ans[X]])||(j>ans[X]&&f[X][j]>f[X][ans[X]])){
				ans[X]=j;
			}
		}
	}
	if(f[X][ans[X]]==1){
		ans[X]=0;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	dfs0(1,0);
	f[1]=id;id+=len[1];
	dfs1(1,0);
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	} 
}
int main(){
	init();
	return 0;
}