• 学习记录8.22 各种思维题+扫描线

    牛客多校第10场 I

    题意：给定两个数组，从第一个数组和第二个数组中分别跳出一对数，要求这两对数做差的绝对值相等，如果有则输出下标，否则输出no

    思路：当我们的数组没有重复的数字时，如果想要任意两个数的差值（在1e7之内）不同，经过打表发现数字约有4000个就可以达到，题目中给出数据范围是1e6个在1e7之内的数。所以去重之后可以在约为4000*4000的复杂度下求出答案。

    1.我们对于a数组显然有去重的操作，我们设置一个数组记录每个数的最后一次出现的下标即可，特别注意的是两数差值为0的时候需要特殊记录一下。
    2.我们对于第二个数组在输入的过程中，先检测是否b数组输入过这个数，如果是而且a数组也有差值为0的一对数，那么就找到了。否则：记录下来当前输入值和所有去重后a数组的值进行做差，开设nx和ny数组分别记录下产生这个差值的a数组中数的坐标和b数组中数的坐标，一旦再次出现这个数值立刻就可以匹配。
    3.如果上述均失配，可以保证复杂度不过超过4000*4000（因为比这个数多的话一定就有匹配上的了），那么就可以输出-1了。

    Yet Another FFT Problem?

    #include

const int N = 2e7+100;

int n,a[N],b,m;
int n1,A[N];
int nx[N],ny[N],u=1e7;
int vis[N],ggx=0,ggy;
bool ok=0;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) 
    {
		scanf("%d",&a[i]);
		if(vis[a[i]]) 
		{
			ggx=vis[a[i]];ggy=i;
		} 
        else
            A[++n1]=i;
		vis[a[i]]=i;
	}
	memset(vis,0,sizeof vis);
	for(int i=1;i<=m;i++) {
		scanf("%d",&b);
		if(vis[b]) {
			if(ggx) {
				printf("%d %d %d %d\n",ggx,ggy,vis[b],i);
				ok=1;
				break;
			}
			continue;
		}
		vis[b]=i;
		for(int j=1;j<=n1;j++) {
			int o=b-a[A[j]]+u;
			if(nx[o]) 
			{
				printf("%d %d %d %d\n",nx[o],A[j],ny[o],i);
				ok=1;
				break;
			}
			nx[o]=A[j];
			ny[o]=i;
		}
		if(ok) break;
	}
	if(!ok) puts("-1");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    话说这题居然又人用fft写了1800行，压着2900ms过了，太恐怖了。

    C. Monoblock

    题意：给定一个数组，设定一个区间的价值是此区间连续相同数块的个数。我们给出m次修改，每次将i位置的数值修改为x，每次修改完求整个数组全部区间的价值和。

    思路：这个题非常邪恶。我们把贡献分成两份来计算是比较可行的方案。我们考虑分为对左边和对右边贡献来看。
    例如 1 2 2 4 5的第3个数2
    对左边：[1,3],[2,3],[3,3]显然都是产生了一个贡献。

    对右边：[1,4][1,5][2,4][2,5][3,4][3,5]显然，当且仅当第i项和第i+1项不同时，第i项能够产生i*(n-i)的价值：也就是从1到i的数作为左端点和从i+1到n的数作为右端点可以让i点产生的价值。

    而恰好，对右边的贡献是变化的，对左边的贡献不变，适合作为突破点。

    这题的贡献分割特别邪恶，非常不好想，，，害。

    #include 
using namespace std;

#define int long long

signed main() 
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 2, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += (a[i] != a[i + 1]) * (n - (i + 1) + 1) * i;
    }
    while (m--) {
        int i, x;
        cin >> i >> x;
        ans -= (a[i] != a[i - 1]) * (n - i + 1) * (i - 1);
        ans -= (a[i + 1] != a[i]) * (n - (i + 1) + 1) * i;
        a[i] = x;
        ans += (a[i] != a[i - 1]) * (n - i + 1) * (i - 1);
        ans += (a[i + 1] != a[i]) * (n - (i + 1) + 1) * i;
        cout << ans + n * (n + 1) / 2 << '\n';
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    D. 2+ doors
    这场感觉真的C>D

    题意：构造一个长度为n的数组，要求如下：
    1.m次规定，每次规定第i个数和第j个数做或运算等于x
    2.求出的数组可能有多个，输出字典序最小的一个。

    思路：每次规定直接给出了第i个数和第j个数那些位置可能为1，那么我们就全部都弄上1，预处理完了m次要求之后就大概能够筛选出各个位置的数那些位置可能为1.

    第二步，赋值，格外注意类似于第x个数和第x个数或等于y这样的，这个就是直接确定数值了。

    第三部，尽可能让各个二进制位的1往后移动，这样可以确保字典序最小。怎么移动？假设有好多好多数和x位置的数做了或，那么目前x位置留有的1都可以转移到这些数上，也就是说，求出这些数（包含x）共同的二进制位然后让x去掉这些二进制位分给后人承担即可，反正或运算，一个人有大家都有了。

    #include 

using namespace std;
#define int long long
const int N = 1e5+100;
vector<pair<int,int>> v[N];
int ans[N];
int fix[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int n,q,a,b,x;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        ans[i]=1<<30;
        ans[i]--;//2的 30次幂-1
    }
    for(int i=0;i<q;i++)
    {
        cin>>a>>b>>x;//a位置和b位置异或得x
        v[a].push_back({b,x});//注册a位置与b异或得x
        v[b].push_back({a,x});//注册b位置与a异或得x
        ans[a]&=x;//a位置与x做且
        ans[b]&=x;//a位置与x做且
        if(a==b)//显然就能确定a位置的数值了
            fix[a]=x;
    }
    for(int i=1;i<=n;i++)
    {
        if(v[i].empty())//不被任何条件的限制，选择最小的数0
            ans[i]=0;
        if(fix[i])//既定值赋值
            ans[i]=fix[i];
    }
    for(int i=1;i<=n;i++)//贪心，让必须有的1尽可能的往后排
    {
        int an=(1<<30)-1;
        for(auto x:v[i])
        {
            an&=ans[x.first];
        }
        if(!fix[i])
        ans[i]-=an&ans[i];
        cout<<ans[i]<<' ';
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47

    扫描线

    P5490 【模板】扫描线

    题意：有n个矩形罗列排放，求出这些矩形的并集面积。（这些矩形不会有斜着放的。）

    扫描线，顾名思义，就是有个像是线段一样的东西从下到上去扫描整个图形，在扫描的过程中，我们会不断的碰到边
    按照这个算法来，我们需要利用线段树来维护长度的变化，维护的方式是用的离散化，线段树每个点管辖的不是实际长度，而是对应的存储左右端点的数组。
    比如x点的长度在线段树中是tree[x].l 和tree[x].r那么实际上还得转化到X[tree[x].l],X[tree[x].r],对应长度也就是X[tree[x].r]-X[tree[x].l]

    注意点：
    这里的x数组是对应的横坐标，主要用来计算横截线，但是当去重后用来bulid线段树之后，tree[X].l-tree[X].r对应的是X点代表的x[l]到x[r-1],所以使用的时候要对应的要搞r+1

    #include 
#define int long long
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
using namespace std;
const int N = 1e6+100;
struct Line
{
    int l,r,h,mark;
};
bool cmp(const Line &a,const Line &b)
{
    return a.h<b.h;
}
struct segtree
{
    int l,r,len,sum;
};
int x[N<<1];
Line line[N<<1];
segtree tree[N<<2];
void bulid(int p,int l,int r)
{
    tree[p].l=l;tree[p].r=r;
    tree[p].len=0,tree[p].sum=0;
    if(l==r)
        return ;
    bulid(ls,l,mid);
    bulid(rs,mid+1,r);
    return ;
}
void up(int p)
{
    int l=tree[p].l,r=tree[p].r;
    if(tree[p].sum)
        tree[p].len=x[r+1]-x[l];
    else
        tree[p].len=tree[ls].len+tree[rs].len;
}
void fixed(int p,int nl,int nr,int c)
{
    int l=tree[p].l,r=tree[p].r;
    if(x[r+1]<=nl||nr<=x[l])
        return ;
    if(nl<=x[l]&&x[r+1]<=nr)
    {
        tree[p].sum+=c;
        up(p);
        return ;
    }
    if(x[mid]>=nl)
    fixed(ls,nl,nr,c);
    if(x[mid]<nr)
    fixed(rs,nl,nr,c);
    up(p);
}
signed main()
{
    int n,x1,y1,x2,y2;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x1>>y1>>x2>>y2;
        x[i*2-1]=x1;
        x[i*2]=x2;
        line[i*2-1]=(Line){x1,x2,y1,1};
        line[i*2]=(Line){x1,x2,y2,-1};
    }
    n<<=1;
    sort(x+1,x+n+1);
    sort(line+1,line+n+1,cmp);
    int tot=unique(x+1,x+n+1)-(x+1);
    bulid(1,1,tot-1);
    int ans=0;
    for(int i=1;i<n;i++)
    {
        fixed(1,line[i].l,line[i].r,line[i].mark);
        ans+=tree[1].len*(line[i+1].h-line[i].h);
    }
    cout<<ans<<endl;
	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84

    还有一道是变型情况，同样是给定点之后求出他们的周长并

    #include 
#include 
#include 
#define lson (x << 1)
#define rson (x << 1 | 1)
using namespace std;
const int MAXN = 2e4;
int n, X[MAXN << 1];
int x1, y1, x2, y2, pre = 0; /* 先初始化为 0 */

struct ScanLine {
	int l, r, h, mark;
	if(h == rhs.h)
		return mark > rhs.mark;
    return h < rhs.h;
//		注意！这里是后来被 hack 掉以后加上去的
//		在此感谢 @leprechaun_kdl 指出问题
//		如果出现了两条高度相同的扫描线，也就是两矩形相邻
//		那么需要先扫底边再扫顶边，否则就会多算这条边
//		这个对面积并无影响但对周长并有影响
//		hack 数据：2 0 0 4 4 0 4 4 8 输出应为：24
} line[MAXN];

struct SegTree {
	int l, r, sum, len, c;
//  c表示区间线段条数
    bool lc, rc;
//  lc, rc分别表示左、右端点是否被覆盖
//  统计线段条数(tree[x].c)会用到
} tree[MAXN << 2];

void build_tree(int x, int l, int r) {
	tree[x].l = l, tree[x].r = r;
	tree[x].lc = tree[x].rc = false;
	tree[x].sum = tree[x].len = 0;
	tree[x].c = 0;
	if(l == r)
		return;
	int mid = (l + r) >> 1;
	build_tree(lson, l, mid);
	build_tree(rson, mid + 1, r);
}

void pushup(int x) {
	int l = tree[x].l, r = tree[x].r;
	if(tree[x].sum) {
		tree[x].len = X[r + 1] - X[l];
		tree[x].lc = tree[x].rc = true;
		tree[x].c = 1;
//      做好相应的标记
	}
	else {
		tree[x].len = tree[lson].len + tree[rson].len;
		tree[x].lc = tree[lson].lc, tree[x].rc = tree[rson].rc;
		tree[x].c = tree[lson].c + tree[rson].c;
//      如果左儿子左端点被覆盖，那么自己的左端点也肯定被覆盖；右儿子同理
		if(tree[lson].rc && tree[rson].lc)
			tree[x].c -= 1;
//      如果做儿子右端点和右儿子左端点都被覆盖，
//      那么中间就是连续的一段，所以要 -= 1
	}
}

void edit_tree(int x, int L, int R, int c) {
	int l = tree[x].l, r = tree[x].r;
	if(X[l] >= R || X[r + 1] <= L)
		return;
	if(L <= X[l] && X[r + 1] <= R) {
		tree[x].sum += c;
		pushup(x);
		return;
	}
	edit_tree(lson, L, R, c);
	edit_tree(rson, L, R, c);
	pushup(x);
}

ScanLine make_line(int l, int r, int h, int mark) {
	ScanLine res;
	res.l = l, res.r = r,
	res.h = h, res.mark = mark;
	return res;
}
//  POJ 不这样做就会CE，很难受

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		line[i * 2 - 1] = make_line(x1, x2, y1, 1);
		line[i * 2] = make_line(x1, x2, y2, -1);
		X[i * 2 - 1] = x1, X[i * 2] = x2;
	}
	n <<= 1;
	sort(line + 1, line + n + 1);
	sort(X + 1, X + n + 1);
	int tot = unique(X + 1, X + n + 1) - X - 1;
	build_tree(1, 1, tot - 1);
	int res = 0;
	for(int i = 1; i < n; i++) {
		edit_tree(1, line[i].l, line[i].r, line[i].mark);
		res += abs(pre - tree[1].len);
		pre = tree[1].len;
//      统计横边
		res += 2 * tree[1].c * (line[i + 1].h - line[i].h);
//      统计纵边
	}
	res += line[n].r - line[n].l;
//  特判一下枚举不到的最后一条扫描线
	printf("%d", res);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
  • 相关阅读:
    Go-Excelize API源码阅读（三十六）——SetSheetRow、InsertPageBreak
    鱼哥赠书活动第③期：《CTF那些事儿》《构建新型网络形态下的网络空间安全体系》《智能汽车网络安全权威指南》上下册
    Springboot拦截器实现统计用户请求成功次数
    一个简单的UDP客户端和服务端的完整C++示例
    vivo大规模 Kubernetes 集群自动化运维实践
    电脑清理c盘怎么清理全教程，教你彻底清理所有垃圾
    【DR_CAN-MPC学习笔记】1.最优化控制和MPC基本概念
    【精】Devops实战学习CI/CD落地方案#CI篇#
    前端面试题JS篇（3）
    lua入门(3) - 变量
  • 原文地址：https://blog.csdn.net/qq_35866893/article/details/126475011