传送门


这一场比赛D题想假了，结果fst。本来能涨，这下掉了12分。

A

有结论？A题还猜什么结论，直接留1个3,2个2,3个1暴力，时间复杂度\(O(1000 * 2^6)\)，过了就是了。

至于结论，是这么推出来的：令\(S=a+2b+3c\)，即所有数的和。那么用这些数一定能凑出来\([1\sim S]\)中的任何一个整数。因为\(a,b,c\geqslant 1\)，那么先贪心的用3凑，这样要么3没了，要么余数小于3，因此再用2和1必定能凑出来。

那么就分成\(\lfloor \frac{S}{2} \rfloor\)和\(\lceil \frac{S}{2} \rceil\)两组即可，进而得出，当\(S\)为奇数的时候答案为1，偶数的时候答案为0.

代码不贴了。

B

水题一道，统计0的个数为\(c_0\)，1的个数为\(c_1\)，输出\(2^{c_0} * c_1\)即可。

C

C题稍有点意思，但也不难。

显然对于每个字母可以单独考虑，那么枚举字母ch，然后反过来想：先把ch都删去，然后对称的贪心添加ch即可。要注意的是ch可以作为回文中心，即最中间的c不用成对的添加。

我这代码学的略丑，推荐题解的代码。

#include<bits/stdc++.h>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
In ll read()
{
	ll ans = 0;
	char ch = getchar(), las = ' ';
	while(!isdigit(ch)) las = ch, ch = getchar();
	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
	if(las == '-') ans = -ans;
	return ans;
}
In void write(ll x)
{
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}

int n;
char s[maxn];

int cnt = 0;
char t[maxn];
In bool check()
{
	for(int i = 1, j = cnt; i <= cnt; ++i, --j)
		if(t[i] != t[j]) return 0;
	return 1;
}
In int solve(char c)
{
	cnt = 0; int sum = 0;
	for(int i = 1; i <= n; ++i)
		if(s[i] != c) t[++cnt] = s[i];
		else sum++;
	if(!check()) return INF;
	int suml = 0, sumr = 0;
	int i = 1, j = n, tot = 0;
	while(s[i] != c && i <= n) ++i, suml++;
	while(s[j] != c && j) --j, sumr++;	
	while(i < j)
	{
		if(suml == sumr)
		{
			tot += 2, ++i, --j;
			while(s[i] != c && i <= n) ++i, suml++;		
			while(s[j] != c && j) --j, sumr++;		
		} 
		else if(suml < sumr)
		{
			++i;
			while(s[i] != c && i <= n) ++i, suml++;
		}
		else if(suml > sumr)
		{
			--j;
			while(s[j] != c && j) --j, sumr++;
		} 
	}
	if(i == j && suml == sumr) tot++;
	return sum - tot;
}

int main()
{
	int T = read();
	while(T--)
	{
		n = read();
		scanf("%s", s + 1);
		int ans = INF;
		for(int i = 0; i < 26; ++i) ans = min(ans, solve('a' + i));
		write(ans == INF ? -1 : ans), enter;
	}
	return 0;
}

D

这题我想复杂了，还不对……

首先当\(n\)是偶数的时候很好办，只要令\(b_i=a_{i+1},b_{i+1}=-a_i\)即可，而且这样有\(\sum_{i=1}^n |b_i| \leqslant MAXA * MAXN = 10^9\)，刚好不会超题中的限制。

当\(n\)是奇数的时候怎么办呢？前面的三个数单独处理，后面的就变成\(n\)是偶数的情况。至于前面的三个数，直接令\(b_1 = -a_3,b_2=-a_3,b_3=a_1+a_2\)即可。但是要注意两数之和不能等于0，而这在三个数中必然存在（因为至少有两个数是同号）

我们在算一下这种构造方法的最大值：对于后面的\(n-3\)个数，他们的最大值是\(MAXA * (MAXN-1-3)\)（因为\(n\)是奇数，而\(MAXN\)是偶数，所以要多减1），而前三个数的最大值是\(MAXA * (1+1+2)\).把这两部分加起来，刚好就是\(MAXA * MAXN=10^9\)，妙吧。

而我场上的方法就比较蠢了。对于\(n\)是奇数的那三个数，我列出了一个不定方程，用exgcd解……虽然能解出来，但这样就不满足题目中最大值的限制了。

给个正解的代码：

#include<bits/stdc++.h>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
In ll read()
{
	ll ans = 0;
	char ch = getchar(), las = ' ';
	while(!isdigit(ch)) las = ch, ch = getchar();
	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
	if(las == '-') ans = -ans;
	return ans;
}
In void write(ll x)
{
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}

int n, a[maxn];

In int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}

In void solve()
{
	int beg;
	if(n & 1)
	{
		beg = 4;
		if(a[1] + a[2]) printf("%d %d %d ", -a[3], -a[3], a[1] + a[2]);
		else if(a[1] + a[3]) printf("%d %d %d ", -a[2], a[1] + a[3], -a[2]);
		else printf("%d %d %d ", a[2] + a[3], -a[1], -a[1]);		
	}
	else beg = 1;
	for(int i = beg; i <= n; i += 2)
	{
		int g = gcd(abs(a[i]), abs(a[i + 1]));
		write(a[i + 1] / g), space, write(-a[i] / g), space;
	}
	enter;
}

int main()
{
	int T = read();
	while(T--)
	{
		n = read();
		for(int i = 1; i <= n; ++i) a[i] = read();
		solve();
	}
	return 0;
}

E

这题其实非常简单，注意到\(K \leqslant \sqrt{2n}\)，因此可以直接dp。

因为题目中序列的长度递减，所以可以倒着dp.令\(dp[i][j]\)表示到第\(i\)个位置，最后一段长度为\(j\)时，能取到的最大值，那么就有\(dp[i][j] = \max\{dp[i - 1][j], S(i, i + j - 1)\}\)（需满足\(S(i, i + j - 1) < dp[i + j][j - 1]\)）

这样\(O(n\sqrt{n})\)就能轻松搞定了。

而我比赛的时候就狠奇葩了：dp方程我想出来了，但是我是正的dp的。因为\(K\)满足单调性，所以我先二分，然后用dp检验。注意到dp的状态（应该）不是很多，所以我只把合法的状态存下来，转移的时候用单调栈优化，用时1918ms卡掉了这道题……

我贴一个正解的代码：

#include<bits/stdc++.h>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
const int maxk = 455;
In ll read()
{
	ll ans = 0;
	char ch = getchar(), las = ' ';
	while(!isdigit(ch)) las = ch, ch = getchar();
	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
	if(las == '-') ans = -ans;
	return ans;
}
In void write(ll x)
{
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}

int n;
ll a[maxn], sum[maxn];

In ll S(int L, int R) {return sum[R] - sum[L - 1];}
ll dp[maxn][maxk];
In int DP()
{
	int K = 1;
	while((K + 1) * (K + 2) / 2 <= n) ++K;
	for(int i = 1; i <= K; ++i) dp[n + 1][i] = -1;
	dp[n + 1][0] = INF;
	for(int i = n; i; --i)
	{
		dp[i][0] = INF; 
		for(int j = 1; j <= K; ++j)
		{
			dp[i][j] = dp[i + 1][j];
			if(i + j - 1 <= n && S(i, i + j - 1) < dp[i + j][j - 1]) dp[i][j] = max(dp[i][j], S(i, i + j - 1));
		}
	} 
	for(int i = K; i; --i) if(~dp[1][i]) return i;
	return 0;
}

int main()
{
	int T = read();
	while(T--)
	{
		n = read();
		for(int i = 1; i <= n; ++i)
		{
			a[i] = read();
			sum[i] = sum[i - 1] + a[i];
		}
		write(DP()), enter;
	}
	return 0;
}

还有这是我的神奇做法：

#include<bits/stdc++.h>
using namespace std;
#define enter puts("") 
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
#define forE(i, x, y) for(int i = head[x], y; ~i && (y = e[i].to); i = e[i].nxt)
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 1e5 + 5;
In ll read()
{
	ll ans = 0;
	char ch = getchar(), las = ' ';
	while(!isdigit(ch)) las = ch, ch = getchar();
	while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
	if(las == '-') ans = -ans;
	return ans;
}
In void write(ll x)
{
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}

int n;
ll a[maxn], sum[maxn];

In ll S(int L, int R) {return sum[R] - sum[L - 1];}

struct Node
{
	int pos; ll val;
	In bool operator < (const Node& oth)const
	{
		return pos < oth.pos;
	}
};
vector<Node> st[maxn];
int cnt[maxn];
In void in(int pos, int len, ll val)  //把合法的dp状态存到栈里
{
	int& top = cnt[len];
	if(top && st[len][top].val <= val) return;
	if(++top == (int)st[len].size()) st[len].push_back((Node){0, 0});
	st[len][top] = (Node){pos, val};
}
In bool check(int len)
{
	for(int i = 1; i <= n; ++i) st[i].clear(), st[i].push_back((Node){0, 0}), cnt[i] = 0;
	for(int i = len; i <= n; ++i)
	{
		in(i, len, S(i - len + 1, i));
		int tot = len;
		for(int j = len - 1; j; --j)
		{
			if(j + tot > i) break;
			ll tp = S(i - j + 1, i); 
			int pos = upper_bound(st[j + 1].begin(), st[j + 1].end(), (Node){i - j, 0}) - st[j + 1].begin() - 1;
			if(pos > 0 && pos <= cnt[j + 1] && st[j + 1][pos].val < tp) in(i, j, tp);
			tot += j;
		}
	}
	return cnt[1] > 0;
}

int main()
{
	int T = read();
	while(T--)
	{
		n = read();
		for(int i = 1; i <= n; ++i)
		{
			a[i] = read();
			sum[i] = sum[i - 1] + a[i];
		}
		int L = 1, R = 1;
		while(R * (R + 1) / 2 <= n) R++;
		R--;
		while(L < R)
		{
			int mid = (L + R + 1) >> 1;
			if(check(mid)) L = mid;
			else R = mid - 1;
		}
		write(L), enter;
	}
	return 0;
}

F1

F2以后再看吧，先说一下F1的思路。

F1其实一点也不难，我也纳闷比赛的时候怎么没想出来。首先观察到\(a_i \leqslant 500\)，这就意味着异或出来的数也不超过511.因此我们用\(val[i][x]\)表示到序列的第\(i\)个数，异或出\(x\)时，最后一个数\(a_j\)的最小值。那么每读一个\(a_i\)，就判断\(val[i-1][x]\)是否小于\(a_i\)，是的话就可以转移到\(val[i][x \ \ \textrm{XOR} \ \ a_i]\)上。

这样的时间复杂度是\(O(500n)\)的。实现的时候可以省去第一维。

看代码吧，一看就懂了。

const int maxb = 512;
int n, val[maxb];

int main()
{
	n = read();
	Mem(val, 0x3f), val[0] = 0;
	for(int i = 1; i <= n; ++i)
	{
		int x = read();
		for(int i = 0; i < maxb; ++i) if(val[i] < x) val[i ^ x] = min(val[i ^ x], x);
	}
	int cnt = 0;
	for(int i = 0; i < maxb; ++i) if(val[i] != INF) ++cnt;
	write(cnt), enter;
	for(int i = 0; i < maxb; ++i) if(val[i] != INF) write(i), space; enter; 
	return 0;
}