T1：
根据异或运算的消去律，容易得到a ^ x = b的转化，于是可以利用值域枚举x
利用map维护b值进行判断是否全匹配（然而T成暴力）
考虑发现x只有n^2种可能取值，于是枚举所有x，判断是否存在x出现次数>= n即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 #define memset(name,val,typ,len) memset (name,val,sizeof (typ) * len)
20 #define Mod1(a,b) (a = a + b > mod ? a + b - mod : a + b)
21 #define Mod2(a,b) (a = a - b < 0 ? a - b + mod : a - b)
22 const I N = 2005;
23 I n,a[N],b[N];
24 vector <I> sta;
25 unordered_map <I,I> h;
26 inline I read () {
27 I x(0),y(1); C z(getchar());
28 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
29 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
30 return x * y;
31 }
32 inline V Max (I &a,I b) { a = a > b ? a : b; }
33 inline V Min (I &a,I b) { a = a < b ? a : b; }
34 inline I max (I &a,I &b) { return a > b ? a : b; }
35 inline I min (I &a,I &b) { return a < b ? a : b; }
36 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
37 inline I abs (I &a) { return a >= 0 ? a : -a; }
38 inline P operator + (const P &a,const P &b) {
39 return MP (a.a + b.a,a.b + b.b);
40 }
41 inline P operator - (const P &a,const P &b) {
42 return MP (a.a - b.a,a.b - b.b);
43 }
44 signed main () {
45 FP (f.in), FC (f.out);
46 n = read ();
47 for (I i(1);i <= n; ++ i)
48 a[i] = read ();
49 for (I i(1);i <= n; ++ i)
50 b[i] = read ();
51 for (I i(1);i <= n; ++ i)
52 for (I j(1);j <= n; ++ j)
53 h[a[i] ^ b[j]] ++ ;
54 for (auto tmp : h) if (tmp.b >= n)
55 sta.push_back (tmp.a);
56 printf ("%lu\n",sta.size ()); for (auto x : sta) printf ("%d ",x);
57 }
View Code
T2：
比较显然的DP，考虑子问题，直观想法为考虑长度这一维，定义f[i]表示当前
子串长度为i的所有方案最小值，然而发现无法进行转移，问题在于最后一个小球的
放置与交换问题，于是就暴力+贪心=40pts
实际上与正解比较接近，考虑既然单纯长度维数并不能划定问题，考虑增加维度
根据上述分析，一种小球的放置与交换与三种小球都有关系，于是定义f[i][j][k][0/1/2]
表示当前序列有i个R，j个G，k个Y，并且最后一个小球为0/1/2（R，G，Y），于是
状态转移方程f[i + 1][j][k][0] = min (f[i][j][k] + abs (i + j + k + 1 - g[0][i + 1]))，表示当往最后一个位置放置
R时，贡献的交换次数，其中g数组表示某种小球第几次出现的位置，O (n)预处理即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 // #define memset(name,val,typ,len) memset (name,val,sizeof (typ) * len)
20 #define Mod1(a,b) (a = a + b > mod ? a + b - mod : a + b)
21 #define Mod2(a,b) (a = a - b < 0 ? a - b + mod : a - b)
22 const I N = 405;
23 C s[N];
24 I n,c,upa,upb,upc,f[N >> 1][N >> 1][N >> 1][3],g[3][N >> 1];
25 inline I read () {
26 I x(0),y(1); C z(getchar());
27 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
28 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
29 return x * y;
30 }
31 inline V Max (I &a,I b) { a = a > b ? a : b; }
32 inline V Min (I &a,I b) { a = a < b ? a : b; }
33 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
34 inline I abs (I &a) { return a >= 0 ? a : -a; }
35 inline I max (const I &a,const I &b) { return a > b ? a : b; }
36 inline I min (const I &a,const I &b) { return a < b ? a : b; }
37 inline P operator + (const P &a,const P &b) {
38 return MP (a.a + b.a,a.b + b.b);
39 }
40 inline P operator - (const P &a,const P &b) {
41 return MP (a.a - b.a,a.b - b.b);
42 }
43 signed main () {
44 FP (s.in), FC (s.out);
45 n = read (); scanf ("%s",s + 1);
46 for (I i(1);i <= n; ++ i) switch (s[i]) {
47 case 'R' : g[0][++upa] = i; break;
48 case 'G' : g[1][++upb] = i; break;
49 case 'Y' : g[2][++upc] = i; break;
50 }
51 if (upa > n + 1 >> 1 || upb > n + 1 >> 1 || upc > n + 1 >> 1)
52 puts ("-1"), exit (0);
53 memset (f,0x3f,sizeof f);
54 f[0][0][0][0] = f[0][0][0][1] = f[0][0][0][2] = 0;
55 for (I len (0);len < n; ++ len)
56 for (I a(0);a <= len && a <= upa; ++ a)
57 for (I b(0);a + b <= len && b <= upb; ++ b) if ((c = len - a - b) <= upc) {
58 if (a < upa) Min (f[a + 1][b][c][0],min (f[a][b][c][1],f[a][b][c][2]) + abs (len + 1 - g[0][a + 1]));
59 if (b < upb) Min (f[a][b + 1][c][1],min (f[a][b][c][0],f[a][b][c][2]) + abs (len + 1 - g[1][b + 1]));
60 if (c < upc) Min (f[a][b][c + 1][2],min (f[a][b][c][0],f[a][b][c][1]) + abs (len + 1 - g[2][c + 1]));
61 }
62 printf ("%d\n",min (f[upa][upb][upc][0],min (f[upa][upb][upc][1],f[upa][upb][upc][2])) >> 1);
63 }
View Code
不要放弃的太早，状态方程的设计考虑问题本身进行拓展即可
T4：
根据题目给出的式子a[i] = max (a[i],a[i - 1])，模拟过程可以发现，只有每个点之前单调栈（单调递减）
内的元素才可能更新该元素，并且更新时刻即为坐标差，考虑随机数据下单调栈内元素数量在O(logn)级别
（证明考虑中间元素与单调栈的形成（不断除2）），于是考虑对于每个点维护出其单调栈内的元素
问题转化为对于若干时刻，求解一段区间的总和，能够想到前缀和优化，考虑如何处理时刻问题，首先
直接根据时间与n建模暴扫显然不行，发现存在许多冗余状态，考虑压缩状态数，根据之前分析，单调栈内
总元素数量在nlogn级别，考虑直接对单调栈元素进行维护，于是将单调栈内所有元素按时间分层，每到一个
时刻，将所有需要更新的元素进行更新，由于带修（单点修改区间查询），考虑采用树状数组进行维护
于是时间复杂度O（nlog^2n）
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UI unsigned int
10 #define UL unsigned long long
11 #define P pair<I,I>
12 #define MP make_pair
13 #define a first
14 #define b second
15 #define lowbit(x) (x & -x)
16 #define debug cout << "It's Ok Here !" << endl;
17 #define FP(x) freopen (#x,"r",stdin)
18 #define FC(x) freopen (#x,"w",stdout)
19 #define memset(name,val,typ,len) memset (name,val,sizeof (typ) * len)
20 #define Mod1(a,b) (a = a + b > mod ? a + b - mod : a + b)
21 #define Mod2(a,b) (a = a - b < 0 ? a - b + mod : a - b)
22 const I N = 2e5 + 3;
23 LL ans[N];
24 I n,q,a[N];
25 I cnt,sta[N];
26 struct A1 {I t,l,r;};
27 vector <P> t[N];
28 vector <A1> p[N];
29 inline I read () {
30 I x(0),y(1); C z(getchar());
31 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
32 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
33 return x * y;
34 }
35 inline V Max (I &a,I &b) { a = a > b ? a : b; }
36 inline V Min (I &a,I &b) { a = a < b ? a : b; }
37 inline I max (I &a,I &b) { return a > b ? a : b; }
38 inline I min (I &a,I &b) { return a < b ? a : b; }
39 inline V swap (I &a,I &b) { a ^= b, b ^= a, a ^= b; }
40 inline I abs (I &a) { return a >= 0 ? a : -a; }
41 inline P operator + (const P &a,const P &b) {
42 return MP (a.a + b.a,a.b + b.b);
43 }
44 inline P operator - (const P &a,const P &b) {
45 return MP (a.a - b.a,a.b - b.b);
46 }
47 struct BIT {
48 LL c[N];
49 inline V insert (I x,I y) {
50 for (;x <= n;x += lowbit (x))
51 c[x] += y;
52 }
53 inline LL secque (I x,I y) {
54 LL ans (0); x -- ;
55 for (; x ;x -= lowbit (x))
56 ans -= c[x];
57 for (; y ;y -= lowbit (y))
58 ans += c[y];
59 return ans;
60 }
61 }B1;
62 signed main () {
63 FP (o.in), FC (o.out);
64 n = read (), q = read ();
65 for (I i(1);i <= n; ++ i) {
66 a[i] = read (), B1.insert (i,a[i]);
67 while (cnt && a[i] >= a[sta[cnt]]) cnt -- ;
68 for (I j(1);j <= cnt; ++ j)
69 t[i - sta[j]].push_back (MP (i,a[sta[j]]));
70 sta[++cnt] = i;
71 }
72 for (I i(1);i <= q; ++ i)
73 p[read ()].push_back (A1 {i,read (), read ()});
74 for (I i(1);i <= n; ++ i) {
75 for (auto tmp : t[i])
76 B1.insert (tmp.a,tmp.b - a[tmp.a]), a[tmp.a] = tmp.b;
77 for (auto tmp : p[i])
78 ans[tmp.t] = B1.secque (tmp.l,tmp.r);
79 }
80 for (I i(1);i <= q; ++ i) printf ("%lld\n",ans[i]);
81 }
View Code