2024-04-01

改题

第一天考试 T3

考场上主席树写挂了

正解是扫描线

树状数组下标是询问编号 维护 考虑从 1 到某个询问编号的 当前横坐标的高度

扫描到修改的左端点就 + h 右端点 - h
扫描到查询就在树状数组上二分第一个 >= y 的编号

代码第 75 行 ur 写成 ul 了，数组越界 调了一会

还有整体二分的方法，但是复杂度不对，常数小才能过

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;

const int N=1e6+10;

int n,m;

struct Upd {
	int l,r;
	ll h;
}u[N];
struct Qry {
	int x;
	ll y;
	int ans;
}q[N];

vector<int> ul[N],ur[N],qx[N];

int lowbit(int x) {
	return x&-x;
}

ll tr[N];

void update(int x,ll k) {
	while(x<=m) {
		tr[x]+=k;
		x+=lowbit(x);
	}
	return;
}

ll query(int x) {
	ll res=0;
	while(x) {
		res+=tr[x];
		x-=lowbit(x);
	}
	return res;
}

void getans(int id,ll y) {
	if(query(id-1)<y) {
		q[id].ans=0;
		return;
	}
	int lft=1,rgh=id;
	while(lft<rgh) {
		int mid=lft+rgh>>1;
		if(query(mid)>=y) rgh=mid;
		else lft=mid+1;
	}
	q[id].ans=lft;
	return;
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		int opt;
		scanf("%d",&opt);
		if(opt==1) scanf("%d%d%lld",&u[i].l,&u[i].r,&u[i].h),ul[u[i].l].push_back(i),ur[u[i].r].push_back(i);
		else scanf("%d%lld",&q[i].x,&q[i].y),qx[q[i].x].push_back(i);
	}
	for(int i=1;i<=n;i++) {
		for(int j=0;j<ul[i].size();j++) update(ul[i][j],u[ul[i][j]].h);
		for(int j=0;j<qx[i].size();j++) getans(qx[i][j],q[qx[i][j]].y);
		for(int j=0;j<ur[i].size();j++) update(ur[i][j],-u[ur[i][j]].h);
	}
	for(int i=1;i<=m;i++) if(q[i].x) printf("%d\n",q[i].ans); 
	
	return 0;
} 

第 2 题 subset

构造题
特判 n==1&&k==1 的情况
若 \(S=n\times(n+1)\bmod k\ne 0\) 肯定无解
记 m=n/k 若 m 为偶数，不难发现排成“蛇形”是符合条件的
否则如果 m 为奇数
这时候 n 肯定也是奇数，否则 S 不能被 k 整除
可以先把两边的大小配对排好，剩下一个 m=3 的情况
把这种情况解决就完事了

画几个 \(k=3,k=5,k=7\) 的情况
发现规律：

• 第一列按顺序放
• 第二列向上循环平移 \((k-1)/2\) 位
• 第三列上半部分和下半部分（上比下多一个）分别是一个公差为 2 的等差数列，且上是奇数，下是偶数

做完了

代码里有一处 k 写成 m 了又是一直数组越界
感觉最近总是犯这种错误，好智障啊，浪费好多时间
还得再细心一点，写代码的时候脑子清楚点！

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;

const ll N=1e6+10;

vector<ll> g[N];

ll n,k,m;

int main() {
	ll T;
	scanf("%lld",&T);
	while(T--) {
		scanf("%lld%lld",&n,&k);
		if(n==1&&k==1) {
			puts("Yes");
			puts("1");
			continue;
		}
		memset(g,0,sizeof(g));
		m=n/k;
		if(k==1) {
			puts("Yes");
			for(int i=1;i<=n;i++) printf("%d ",i);
			puts("");
			continue;
		}
		if(m==1) {
			puts("No");
			continue;
		}
		long long s=1ll*n*(n+1)/2;
		if(s%(long long)k!=0) {
			puts("No");
			continue;
		}
		if(m%2==0) {
			ll num=1;
			for(ll i=1;i<=m;i+=2) {
				for(ll j=1;j<=k;j++) g[j].push_back(num++);
				for(ll j=k;j>=1;j--) g[j].push_back(num++);
			}
			puts("Yes");
			for(ll i=1;i<=k;i++) {
				for(ll j=0;j<g[i].size();j++) printf("%lld ",g[i][j]);
				puts("");
			}
			continue;
		}
		if((n%2==0)&&(m%2==1)) {
			puts("No");
			continue;
		}
		for(ll d=0;d<(m-3)/2;d++) {
			for(ll i=1;i<=k;i++) g[i].push_back(i+d*k),g[i].push_back(n-i+1-d*k);
		}
		ll num=(m-3)/2*k+1;
		for(ll i=1;i<=k;i++) g[i].push_back(num++);
		for(ll i=k-(k-3)/2;i<=k;i++) g[i].push_back(num++);
		for(ll i=1;i<k-(k-3)/2;i++) g[i].push_back(num++);
		ll nm=num;
		for(ll i=(k+1)/2;i>=1;i--) g[i].push_back(nm),nm+=2;
		nm=num+1;
		for(ll i=k;i>(k+1)/2;i--) g[i].push_back(nm),nm+=2;
		puts("Yes");
		for(ll i=1;i<=k;i++) {
			for(ll j=0;j<g[i].size();j++) printf("%lld ",g[i][j]);
			puts("");
		}
	}
	
	return 0;
}

L语言

AC自动机 + DP

f[i] 表示 \(t\) 的从 \(1\) 到 \(i\) 这个前缀是否能够被理解

\(f[i]=\bigvee f[j]\) 其中 \([j+1,i]\) 这个字串 是 \(s\) 中的一个

AC自动机中 fail 就是一个前缀的后缀的集合
当一个后缀属于 \(s\) 的时候就可以转移

因为 \(\left|s\right|\le20\) 所以能转移的后缀长度最大是 \(20\) 这样我们就可以把他们压缩到一个数里

具体的
\(g_u\) 在二进制下的第 \(i\) 位表示 \(u\) 的长度为 \(i\) 的后缀是不是一个可以转移的后缀

然后我们再把第 \(i\) 位之前 \(20\) 位的 \(f\) 值压缩成 \(now\)（实现的时候是每次右移一位或上 \(f_{i-1}\)，然后与上 \((1<<20)-1\) 保证 \(20\) 位之前的不存）

这样，如果 \(g_u\) 和 \(now\) 的某一位或某几位同时是 \(\tt True\) ，\(f_i=\tt True\)

就是按位与一下

【L语言】提交记录&Code

作业

昨天留的坑，填一下

每天完，明天继续