• 2022杭电多校（二）

    2022杭电多校（二）

    文章目录

    一、比赛小结

    比赛链接：Problems (hdu.edu.cn)

    二、题目分析及解法（基础题）

    1001、Static Query on Tree

    题目链接：Problem - 7150 (hdu.edu.cn)

    题意：

    有一棵有向树，所有节点均可到达根节点，然后给出三个集合， A 、 B 、 C A、B、C A、B、C ，对于集合中的元素进行染色，具体地，是向元素的子树进行染色，最后问这棵树上同时染三种色的节点有多少个

    题解：

    很直接的一道树剖，但在用线段树染色这个子问题上，比较麻烦，自己还不太会实现QWQ ，参考了一个大佬的博客：2022杭电多校第二场 A.Static Query on Tree（树剖）

    代码：

    #pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include
//#define int long long
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define yesno if(fg)yes;else no;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int inf=8e18;
const int maxn=2e5+100;
vector<int>g[maxn];
int a[maxn],b[maxn],c[maxn],son[maxn],siz[maxn],fa[maxn];
int dep[maxn],top[maxn],dfn[maxn],rk[maxn],clk,out[maxn];
template <typename T> inline void read(T& x)
{
	x=0;
	T f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=x*f;
	return;
}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg)
{
	read(x);
	read(arg...);
}
template <typename T>inline void write(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
template <typename T,typename ...Arg>void write(T& x,Arg& ...arg)
{
	write(x);
	putchar(' ');
	write(arg...);
}

struct node
{
	int l,r;
	int sum;
	int s[8];
	int lazy;
	int lazy2;//清空标志
} t[maxn*4];
void dfs(int x,int f)
{
	fa[x]=f;
	dep[x]=dep[f]+1;
	siz[x]=1;
	son[x]=-1;
	for(auto it:g[x])
	{
		if(it==f)continue;
		dfs(it,x);
		siz[x]+=siz[it];
		if(son[x]==-1||siz[it]>siz[son[x]])son[x]=it;
	}
}
void dfs2(int x,int t)
{
	top[x]=t;
	dfn[x]=++clk;
	rk[clk]=x;
	if(son[x]==-1)
	{
		out[x]=clk;
		return ;
	}
	dfs2(son[x],t);
	for(auto it:g[x])
	{
		if(it==fa[x])continue;
		if(it==son[x])continue;
		dfs2(it,it);
	}
	out[x]=clk;
}
void push_down(int k)
{
	if(t[k].l==t[k].r)
	{
		t[k].lazy=0;
		t[k].lazy2=0;
		return ;
	}
	if(t[k].lazy2)//清空 
	{
		t[k<<1].lazy2=t[k<<1|1].lazy2=1;
		t[k<<1].lazy=t[k<<1|1].lazy=0;//note
		for(int i=0; i<=7; i++)
		{
			t[k<<1].s[i]=t[k<<1|1].s[i]=0;
		}

		t[k<<1].s[0]=t[k<<1].r-t[k<<1].l+1;
		t[k<<1|1].s[0]=t[k<<1|1].r-t[k<<1|1].l+1;

		t[k].lazy2=0;
	}
	if(t[k].lazy>0)
	{
		for(int i=7; i>=0; i--)
		{
			if((i|t[k].lazy)==i)continue;

			t[k<<1].s[i|t[k].lazy]+=t[k<<1].s[i];
			t[k<<1].s[i]=0;

			t[k<<1|1].s[i|t[k].lazy]+=t[k<<1|1].s[i];
			t[k<<1|1].s[i]=0;
		}
		t[k<<1].lazy|=t[k].lazy;
		t[k<<1|1].lazy|=t[k].lazy;
		t[k].lazy=0;
	}



}
void push_up(int k)
{
	if(t[k].l!=t[k].r)
	{
		for(int i=0; i<8; i++)
		{
			t[k].s[i]=t[k<<1].s[i]+t[k<<1|1].s[i];
		}
	}
}

void build(int l,int r,int k)
{
	t[k].l=l;
	t[k].r=r;
	t[k].sum=0;
	for(int i=0; i<8; i++)t[k].s[i]=0;
	t[k].s[0]=t[k].r-t[k].l+1;
	t[k].lazy=0;
	t[k].lazy2=0;
	if(l==r)
	{
		return ;
	}
	int mid=(l+r)>>1;
	build(l,mid,k<<1);
	build(mid+1,r,k<<1|1);
	push_up(k);
}
void update(int l,int r,int k,int type,int val)
{
	if(r<t[k].l||l>t[k].r)return ;
	push_down(k);
	if(l<=t[k].l&&t[k].r<=r)
	{
		if(val==1)
		{
			t[k].lazy=type;
			for(int i=7; i>=0; i--)
			{
				if((i|type)==i)continue;
				t[k].s[i|type]+=t[k].s[i];
				t[k].s[i]=0;
			}
		}
		else
		{
			t[k].lazy2=1;
			for(int i=0; i<8; i++)t[k].s[i]=0;
			t[k].s[0]=t[k].r-t[k].l+1;
		}
		push_down(k);
		return ;
	}
	update(l,r,k<<1,type,val);
	update(l,r,k<<1|1,type,val);
	push_up(k);
}

int querysum(int l,int r,int k)
{
	if(r<t[k].l||l>t[k].r)return 0;
	push_down(k);
	if(l<=t[k].l&&t[k].r<=r)
	{
		return t[k].s[7];
	}
	int ans=0;
	ans+=querysum(l,r,k<<1);
	ans+=querysum(l,r,k<<1|1);
	return ans;
}
int na,nb,nc;
int n,q;
signed main()
{
	int tt;
	read(tt);
	int cas=0;
	while(tt--)
	{
		cas++;
		clk=0;
		read(n,q);
		for(int i=2; i<=n; i++)
		{
			int x;
			read(x);
			g[x].pb(i);
			g[i].pb(x);
		}
		dfs(1,0);
		dfs2(1,0);
		build(1,n,1);

		while(q--)
		{
			read(na,nb,nc);
			for(int i=1; i<=na; i++)
			{
				read(a[i]);
				int x=1,y=a[i];
				while(top[x]!=top[y])
				{
					if(dep[top[x]]<dep[top[y]]) swap(x,y);
					update(dfn[top[x]],dfn[x],1,1,1);
					x=fa[top[x]];
				}
				if(dfn[x]<dfn[y]) swap(x,y);
				update(dfn[y],dfn[x],1,1,1);
			}
			for(int i=1; i<=nb; i++)
			{
				read(b[i]);
				int x=1,y=b[i];
				while(top[x]!=top[y])
				{
					if(dep[top[x]]<dep[top[y]]) swap(x,y);
					update(dfn[top[x]],dfn[x],1,2,1);
					x=fa[top[x]];
				}
				if(dfn[x]<dfn[y]) swap(x,y);
				update(dfn[y],dfn[x],1,2,1);
			}
			for(int i=1; i<=nc; i++)
			{
				read(c[i]);
				int x=c[i];
				update(dfn[x],out[x],1,4,1);
			}
			int ans=querysum(1,out[1],1);
			write(ans);
			printf("\n");

			update(1,out[1],1,1,-1);

		}
		build(1,n,1);
		for(int i=0; i<=n+2; i++)
		{
			g[i].clear();
			a[i]=b[i]=c[i]=son[i]=siz[i]=fa[i]=0;
			dep[i]=top[i]=dfn[i]=rk[i]=clk=out[i]=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
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281

    1002、C++ to Python

    题目链接：Problem - 7151 (hdu.edu.cn)

    题意：

    给出一段 python 代码，将其翻译成 c++ 代码

    题解：

    无视其他杂余字符即可

    代码：

    #include 
using namespace std;
string s, ans;
bool judge(char c) {
  if (c == '-' || c == ',') return true;
  if (c == '(' || c == ')') return true;
  if ('0' <= c && c <= '9') return true;
  return false;
}
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> s;
    int len = s.length();
    ans = "";
    for (int i = 0; i < len; i++)
      if (judge(s[i])) ans += s[i];
    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

    1003、Copy

    题目链接：Problem - 7152 (hdu.edu.cn)

    题意：

    给出一串序列，和两种操作，一种是将序列中的一段区间复制粘贴到序列结尾，另一种是查询某个位置的元素的值，最后对这个值求个异或和

    题解：

    比赛时是暴力过的，标程还没暴力快。。。

    标答是用离线+bitset暴力优化过的，考试时也没想到。关于思路来源，可以这么去分析，既然是离线，那先把这些东西给存起来，更容易优化起来。然后思考一下操作1对操作2的影响，若 x ≤ r x\le r x≤r 那么不会产生影响，若 x > r x>r x>r 那么相当于查询 x − ( r − l + 1 ) x-(r-l+1) x−(r−l+1) 。于是我们从后往前分析，设dp是用来存储是否对相应位要进行异或的一个 bitset 。这样就把 O ( n ) O(n) O(n) 的移位操作变成了 O ( 1 ) O(1) O(1) 的bitset操作了。

    其实做法也挺自然的，需要对 bitset 有较熟的操作。

    代码：

    #include 
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
bitset<maxn> dp, low, high;
array<int, 3> v[maxn];
int n, q;

int main() {
  //   freopen("in.txt", "r", stdin);
  //   freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= q; i++) {
      cin >> v[i][0];
      if (v[i][0] == 1)
        cin >> v[i][1] >> v[i][2];
      else
        cin >> v[i][1];
    }
    dp = 0;
    for (int i = 1; i >= 1; i--) {
      if (v[i][0] == 1) {
        int l = v[i][1], r = v[i][2];
        low = dp & (~bitset<maxn>(0) >> (maxn - r - 1));
        high = dp & (~bitset<maxn>(0) << (r + 1));
        dp = low ^ (high >> (r + 1 - l));
      } else {
        int x = v[i][1];
        dp[x] = !dp[x];
      }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
      if (dp[i]) ans ^= a[i];
    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
    #include 
using namespace std;
const int maxn = 100010;
int n, q;
int a[maxn * 2];
int main() {
  // freopen("in.txt", "w", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    int ans = 0;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (q--) {
      int op;
      cin >> op;
      if (op == 1) {
        int l, r;
        cin >> l >> r;
        int x = r - l + 1;
        for (int i = n; i >= r + 1; i--) a[i] = a[i - x];
      } else {
        int x;
        cin >> x;
        ans = ans ^ a[x];
      }
    }
    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

    1004、Keychains

    题目链接：Problem - 7153 (hdu.edu.cn)

    题意：

    给出两个圆环，查询两个圆环是否互锁

    题解：

    思路还是很好想的，让一个圆环与另一个圆环所在平面求交点，对这两个交点分类讨论即可

    代码：

    #include 
using namespace std;

typedef double lf;

struct vec {
  lf x, y, z;
  vec() {}
  vec(lf x, lf y, lf z) : x(x), y(y), z(z) {}
  vec operator-(vec b) { return vec(x - b.x, y - b.y, z - b.z); }
  vec operator+(vec b) { return vec(x + b.x, y + b.y, z + b.z); }
  vec operator*(lf k) { return vec(k * x, k * y, k * z); }
  lf sqr() { return x * x + y * y + z * z; }
  lf len() { return sqrt(x * x + y * y + z * z); }
  vec trunc(lf k = 1) { return *this * (k / len()); }
  friend vec cross(vec a, vec b) {
    return vec(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z,
               a.x * b.y - a.y * b.x);
  }
  friend lf dot(vec a, vec b) { return a.x * b.x + a.y * b.y + a.z * b.z; }
  void scan() { scanf("%lf%lf%lf", &x, &y, &z); }
};

void inter_ff(vec p1, vec dir1, vec p2, vec dir2, vec &res1, vec &res2) {
  vec e = cross(dir1, dir2), v = cross(dir1, e);
  lf d = dot(dir2, v);
  if (abs(d) < 1e-9) return;
  vec q = p1 + v * (dot(dir2, p2 - p1) / d);
  res1 = q;
  res2 = q + e;
}

lf dist_pp(vec p1, vec p2) { return (p2 - p1).len(); }

lf dist_pl(vec p, vec l1, vec l2) {
  return cross(l2 - l1, p - l1).len() / (l2 - l1).len();
}

vec perpendicular_pl(vec p, vec l1, vec l2) {
  return l1 + (l2 - l1) * (dot(l2 - l1, p - l1) / (l2 - l1).sqr());
}

void solve() {
  vec p1, d1, p2, d2;
  lf r1, r2;

  p1.scan();
  d1.scan();
  scanf("%lf", &r1);
  p2.scan();
  d2.scan();
  scanf("%lf", &r2);

  vec dir = cross(d1, d2);
  if (dir.sqr() < 0.1) {
    puts("No");
    return;
  }

  vec l1, l2;
  inter_ff(p1, d1, p2, d2, l1, l2);
  lf dis = dist_pl(p2, l1, l2);
  if (dis > r2) {
    puts("No");
    return;
  }
  vec delta = (l2 - l1).trunc(sqrt(r2 * r2 - dis * dis));
  vec mid = perpendicular_pl(p2, l1, l2);
  vec a = mid + delta;
  vec b = mid - delta;
  if ((dist_pp(a, p1) < r1) ^ (dist_pp(b, p1) < r1)) {
    puts("Yes");
  } else {
    puts("No");
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    solve();
  }
  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

    1007、Snatch Groceries

    题目链接：Problem - 7156 (hdu.edu.cn)

    题意：

    阅读理解题，有 n 个人，每人有一个对应的时间区间，题目问，在区间重叠前有多少个区间。

    题解：

    sort 排个序，再对相邻两个区间进行比较即可。

    代码：

    #include 
#define pii pair<int, int>
using namespace std;
const int maxn = 1e5 + 5;
int n;
pii b[maxn];
int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _;
  cin >> _;
  while (_--) {
    int res = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> b[i].first >> b[i].second;
    sort(b + 1, b + 1 + n);
    bool flag = true;
    for (int i = 1; i < n; i++)
      if (b[i].first < b[i + 1].first && b[i].second < b[i + 1].first)
        res++;
      else {
        flag = false;
        break;
      }
    if (flag) res++;
    cout << res << 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

    1009、ShuanQ

    题目链接：Problem - 7158 (hdu.edu.cn)

    题意：

    给出 p q d 三个数，p 和 q 是关于某个素数的逆元，并且这个素数大于 d 。问你是否可以唯一确定这个素数。

    题解：

    对 p*q-1 进行素因子分解即可

    代码：

    #include 
#define int long long
using namespace std;
const int maxn = 2e6 + 6;
int prime[maxn], pn;
bool isp[maxn];
void table() {
  memset(isp, true, sizeof(isp));
  isp[0] = isp[1] = false;
  for (int i = 2; i < maxn; i++) {
    if (isp[i]) prime[pn++] = i;
    for (int j = 0; j < pn; j++) {
      if (i * prime[j] > maxn) break;
      isp[i * prime[j]] = false;
      if (i % prime[j] == 0) break;
    }
  }
}
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  table();
  int _;
  cin >> _;
  while (_--) {
    int p, q, d;
    cin >> p >> q >> d;
    int M = max(d, max(p, q));
    int N = p * q - 1ll;
    vector<int> res;
    res.clear();
    for (int i = 2ll; i * i <= N; i++)
      if (N % i == 0) {
        while (N % i == 0) N /= i;
        if (i > M) res.push_back(i);
      }
    if ((N != 1) && (N > M)) res.push_back(N);
    if (res.size() == 1ll)
      cout << d * q % res[0] << endl;
    else
      cout << "shuanQ\n";
  }
  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

    1011、DOS Card

    题目链接：Problem - 7160 (hdu.edu.cn)

    题意：

    给定一段序列，以及一些询问，查询区间 [ l , r ] [l,r] [l,r] 内最大的 a u 2 − a v 2 + a x 2 − a y 2 a_u^2-a_v^2+a_x^2-a_y^2 au2​−av2​+ax2​−ay2​

    题解：

    一对匹配的值 = 左 ∗ 左 − 右 ∗ 右

    线段树上维护以下8个变量：

    区间最大值

    区间次大值

    区间最小值

    区间次小值

    选了一对的最大值

    选了两对的最大值

    （一对的值 + 剩下的最大值）的最大值

    （一对的值 − 剩下的最小值）的最大值

    代码：

    #include
using namespace std;
typedef long long ll;
template<class T>inline void MAX(T &x,T y){if(y>x)x=y;}
template<class T>inline void MIN(T &x,T y){if(y<x)x=y;}
template<class T>inline void rd(T &x){
	x=0;char o,f=1;
	while(o=getchar(),o<48)if(o==45)f=-f;
	do x=(x<<3)+(x<<1)+(o^48);
	while(o=getchar(),o>47);
	x*=f;
}
template<class T>inline void print(T x,bool op=1){
	static int top,stk[105];
	if(x<0)x=-x,putchar('-');
	if(x==0)putchar('0');
	while(x)stk[++top]=x%10,x/=10;
	while(top)putchar(stk[top--]+'0');
	putchar(op?'\n':' ');
}
const int M=1e5+5;
int cas,n,m,A[M];
struct node{
	int len;
	ll max1,max2,min1,min2,res1,res2,res1_max,res1_min;
	node(int len=0){
		this->len=len;
		max1=max2=-1e18;
		min1=min2=1e18;
		res1=res2=res1_max=res1_min=-1e18;
	}
	void update_max(ll v){
		if(v>max1)max2=max1,max1=v;
		else if(v>max2)max2=v;
	}
	void update_min(ll v){
		if(v<min1)min2=min1,min1=v;
		else if(v<min2)min2=v;
	}
	node operator +(const node &A)const{
		if(len==0)return A;
		if(A.len==0)return *this;
		
		node T(len+A.len);
		
		T.update_max(max1);
		T.update_max(max2);
		T.update_max(A.max1);
		T.update_max(A.max2);
		
		T.update_min(min1);
		T.update_min(min2);
		T.update_min(A.min1);
		T.update_min(A.min2);
		
		MAX(T.res2,res2);
		MAX(T.res2,A.res2);
		MAX(T.res2,res1+A.res1);
		MAX(T.res2,max1+max2-A.min1-A.min2);
		MAX(T.res2,res1_max-A.min1);
		MAX(T.res2,max1+A.res1_min);
		
		MAX(T.res1,res1);
		MAX(T.res1,A.res1);
		MAX(T.res1,max1-A.min1);
		
		MAX(T.res1_max,res1_max);
		MAX(T.res1_max,A.res1_max);
		MAX(T.res1_max,res1+A.max1);
		MAX(T.res1_max,A.res1+max1);
		if(A.len>=2)MAX(T.res1_max,max1-A.min1+A.max1);
		if(len>=2)MAX(T.res1_max,max1-A.min1+max2);
		
		MAX(T.res1_min,res1_min);
		MAX(T.res1_min,A.res1_min);
		MAX(T.res1_min,res1-A.min1);
		MAX(T.res1_min,A.res1-min1);
		if(A.len>=2)MAX(T.res1_min,max1-A.min1-A.min2);
		if(len>=2)MAX(T.res1_min,max1-A.min1-min1);
		
		return T;
	}
}tree[M<<2];
void build(int l=1,int r=n,int p=1){
	if(l==r){
		tree[p]=node(1);
		tree[p].max1=tree[p].min1=1ll*A[l]*A[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,p<<1);
	build(mid+1,r,p<<1|1);
	tree[p]=tree[p<<1]+tree[p<<1|1];
}
node query(int a,int b,int l=1,int r=n,int p=1){
	if(l>b||r<a)return node(0);
	if(l>=a&&r<=b)return tree[p];
	int mid=l+r>>1;
	return query(a,b,l,mid,p<<1)+query(a,b,mid+1,r,p<<1|1);
}

signed main(){
#ifndef ONLINE_JUDGE
//	freopen("jiedai.in","r",stdin);
//	freopen("jiedai.out","w",stdout);
#endif
	rd(cas);
	while(cas--){
		rd(n),rd(m);
		for(int i=1;i<=n;i++)rd(A[i]);
		build();
		while(m--){
			int l,r;
			rd(l),rd(r);
			print(query(l,r).res2);
		}
	}
	return (0-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
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120

    1012、Luxury cruise ship

    题目链接：Problem - 7161 (hdu.edu.cn)

    题意：

    给你一个 N ，对于方程 7 x 1 + 31 x 2 + 365 x 3 = N ,   x ∈ N 7x_1+31x_2+365x_3=N, \ x\in \N 7x1​+31x2​+365x3​=N, x∈N ，求 x 1 + x 2 + x 3 x_1+x_2+x_3 x1​+x2​+x3​ 的最小值。

    题解：

    有点类似于《小凯的疑惑》这道题，对 ab+a+b 内的答案进行枚举即可

    代码：

    #include 
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
int n;
signed main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  int _;
  cin >> _;
  while (_--) {
    cin >> n;
    int x = 0, y = 0, z = 0;
    z = n / 365;
    n %= 365;
    bool flag = false;
    for (int i = n / 31; i >= 0; i--)
      if ((n - 31 * i) % 7 == 0) {
        y = i;
        x = (n - 31 * i) / 7;
        flag = true;
        break;
      }
    if (flag)
      cout << x + y + z << endl;
    else if (!flag && z == 0)
      cout << -1 << endl;
    else {
      z--;
      n += 365;
      for (int i = n / 31; i >= 0; i--)
        if ((n - 31 * i) % 7 == 0) {
          y = i;
          x = (n - 31 * i) / 7;
          break;
        }
      cout << x + y + z << 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

    三、题目分析及解法（进阶题）

    不会做X

    1005、Slayers Come

    1006、Bowcraft

    1008、Keyboard Warrior

    1010、Assassination

  • 相关阅读:
    流畅的vim配置和使用
    Java 中各种异常的讲解和举例
    Spring Cloud---服务熔断Hystrix
    【Vue】vue-router新窗口打开页面
    HPE脚本更新致京都大学77TB数据被删
    回调函数 事件回调 异步事件 异步函数 JS事件流 事件的捕获模式
    代理IP的命令是什麼？
    优先级队列实现原理
    数据结构与算法笔记七（暴力递归到动态规划）
    申请实用新型专利有什么好处？及实用新型专利申请流程
  • 原文地址：https://blog.csdn.net/m0_54646258/article/details/126789181