南昌邀请赛网络赛

A. PERFECT NUMBER PROBLEM

#include <bits/stdc++.h>
using namespace std;
int main()
{
	printf("6\n28\n496\n8128\n33550336\n");
}

 H. Coloring Game

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const int maxn = 1e5 + 5;
ll power(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b&1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
int main()
{
	ll n;
	scanf("%lld", &n);
	if (n == 1)
	{
		printf("1");
		return 0;
	}
	ll res = 4;
	ll q = power(3, n - 2);
	res = res * q % mod;
	printf("%lld", res);
}

 M. Subsequence

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const int maxn = 1e5 + 5;
char s[100005], ss[100005];
int main()
{
	scanf("%s", s);
	int lens = strlen(s);
	int q;
	scanf("%d", &q);
	while (q--)
	{
		scanf("%s", ss);
		int len = strlen(ss), flag = 0, i = 0;
		bool q = false;
		for (i = 0; i < len; i++)
		{
			while (s[flag] != ss[i] && flag < lens)
				flag++;
			if (flag < lens)
				flag++;
			else
				break;
		}
		if (i == len)
			puts("YES");
		else
			puts("NO");
	}
}

K. MORE XOR

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const int maxn = 1e5 + 5;
int a[100055];
int xors[100055];
int xor0[100055], ji[100055], ou[100055];
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		memset(xors, 0, sizeof(xors));
		memset(xor0, 0, sizeof(xor0));
		memset(ji, 0, sizeof(ji));
		memset(ou, 0, sizeof(ou));
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i + 20]);
			xors[i+20] = xors[i - 1+20] ^ a[i + 20];
			if (i & 1)
				ji[i +20] = ji[i - 2 + 20] ^ a[i+20];
			else
				ou[i + 20] = ou[i - 2 + 20] ^ a[i+20];
			if (i < 4)
				xor0[i+20] = a[i+20];
			else
				xor0[i+20] ^= xor0[i - 4 +20] ^ a[i+20];
		}
		int q;
		scanf("%d", &q);
		while (q--)
		{
			int l, r;
			scanf("%d%d", &l, &r);
			int ans = xors[r+20] ^ xors[l - 1+20];
			
			int q = l, w = r;
			if ((w - q + 1) % 2 == 0)
			{
				q = l + 1;
				w = r;
				if (q == w)
					;
				else if ((w - q) % 4 == 0)
					ans ^= xor0[w - 2+20] ^ xor0[q - 2+20];
				else
				{
					if (q & 1)
						ans ^= ji[w+20] ^ ji[q - 2+20];
					else
						ans ^= ou[w +20] ^ ou[q - 2+20];
				}

				q = l;
				w = r - 1;
				if (q == w)
					;
				else if ((w - q) % 4 == 0)
					ans ^= xor0[w - 2+20] ^ xor0[q - 2+20];
				else
				{
					if (q & 1)
						ans ^= ji[w + 20] ^ ji[q - 2 + 20];
					else
						ans ^= ou[w + 20] ^ ou[q - 2 + 20];
				}
			}
			else
			{
				q = l;
				w = r;
				if (q == w)
					;
				else if ((w - q) % 4 == 0)
					ans ^= xor0[w - 2 + 20] ^ xor0[q - 2 + 20];
				else
				{
					if (q & 1)
						ans ^= ji[w + 20] ^ ji[q - 2 + 20];
					else
						ans ^= ou[w + 20] ^ ou[q - 2 + 20];
				}

				q = l + 1;
				w = r - 1;
				if (q == w)
					;
				else if ((w - q) % 4 == 0)
					ans ^= xor0[w - 2 + 20] ^ xor0[q - 2 + 20];
				else
				{
					if (q & 1)
						ans ^= ji[w + 20] ^ ji[q - 2 + 20];
					else
						ans ^= ou[w + 20] ^ ou[q - 2 + 20];
				}

			}

			printf("%d\n", ans);
		}
	}
}

I. Max answer

#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1;
using namespace std;
const int MAXN = 500005;
struct node
{
	int l;
	int r;
	ll maxn;
	ll minn;
}que[MAXN * 4];
int n;
int ql, qr;
ll a[MAXN], pre[MAXN];
void up(int k)
{
	que[k].maxn = max(que[k << 1].maxn, que[k << 1 | 1].maxn);
	que[k].minn = min(que[k << 1].minn, que[k << 1 | 1].minn);
}
void build(int left = 0, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	if (left == right)
	{
		que[k].minn = pre[left];
		que[k].maxn = pre[left];
		return;
	}
	imid;
	build(lson);
	build(rson);
	up(k);
}
ll querymin(int left = 0, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 1e18;
	if (ql <= left && right <= qr)
		return que[k].minn;
	imid;
	return min(querymin(lson), querymin(rson));
}
ll querymax(int left = 0, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return -1e18;
	if (ql <= left && right <= qr)
		return que[k].maxn;
	imid;
	return max(querymax(lson), querymax(rson));
}
int l[MAXN], r[MAXN];
stack<int>st;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		pre[i] = pre[i - 1] + a[i];
	}

	a[0] = -1000000;
	a[n + 1] = -999999;
	st.push(0);
	for (int i = 1; i <= n + 1; i++)
	{
		while (a[st.top()] > a[i])
		{
			r[st.top()] = i - 1;
			st.pop();
		}
		l[i] = st.top() + 1;
		st.push(i);
	}

	build();
	ll res = -1e9;
	for (int i = 1; i <= n; i++)
	{
		if (a[i] > 0)
		{
			ql = l[i] - 1;
			qr = i;
			ll minn = querymin();
			ql = i;
			qr = r[i];
			ll maxn = querymax();
			res = max(res, (maxn - minn) * a[i]);
		}
		else
		{
			ql = l[i] - 1;
			qr = i;
			ll maxn = querymax();
			ql = i;
			qr = r[i];
			ll minn = querymin();
			res = max(res, (minn - maxn) * a[i]);
		}
	}
	printf("%lld\n", res);
}