Liyb

3105

77777777777

Hangya

s.y.
NULL_
JcWing
incra

ljlhandsome
................
V1
lsz_
WangJY

Liyb
14小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 10010;
int f[N];
int n,m;

struct Node
{
int s,e,l;
bool operator<(const Node &W)const
{
return W.l * s < W.s * l;
}
}q[N];

int main()
{
int t;cin >> t;
for(int k = 1; k <= t; k ++)
{
cin >> n;m = 0;
for(int i = 1; i <= n; i ++)
{
cin >> q[i].s >> q[i].e >> q[i].l;
m += q[i].s;
}

sort(q + 1, q + n + 1);
//体积恰好为j
memset(f, -0x3f, sizeof f);
f[0] = 0;

for(int i = 1; i <= n; i ++)a
{
for(int j = m; j >= q[i].s; j --)
{
int s = q[i].s,e = q[i].e,l = q[i].l;
f[j] = max(f[j], f[j - s] + e - (j - s) * l);
}
}

int res = 0;
for(int i = 0; i <= m; i ++)
res = max(res, f[i]);
printf("Case #%d: %d\n", k,res);
}
return 0;
}


Liyb
18小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

bool check(int x)
{
x --;
if(x & 1)return false;

bool meet_one = false;
while(x)
{
if(x & 1)meet_one = true;
else if(meet_one)return false;
x >>= 1;
}

return true;
}

int main()
{
int q;cin >> q;
while(q --)
{
int x;cin >> x;
if(check(x))cout << "Y" << endl;
else cout << "N" << endl;
}

return 0;
}


Liyb
23小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1010,mod = 1e9 + 7;
int g[N],f[N];

int main()
{
int n,m;cin >> n >> m;
g[0] = 1;

for(int i = 1; i <= n; i ++)
{
int v,w;cin >> v >> w;
int maxv = 0;
for(int j = m; j >= v; j --)
{
LL cnt = 0;
maxv = max(f[j], f[j - v] + w);
if(maxv == f[j])cnt += g[j];
if(maxv == f[j - v] + w)cnt += g[j - v];
f[j] = maxv;
g[j] = cnt % mod;
}
}

int res = 0;
for(int i = 0; i <= m; i ++)
if(f[i] == f[m])res += g[i];

cout << res << endl;
return 0;
}


Liyb
23小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1010,mod = 1e9 + 7;
int g[N],f[N];

int main()
{
int n,m;cin >> n >> m;
g[0] = 1;

for(int i = 1; i <= n; i ++)
{
int v,w;cin >> v >> w;
int maxv = 0;
for(int j = m; j >= v; j --)
{
LL cnt = 0;
maxv = max(f[j], f[j - v] + w);
if(maxv == f[j])cnt += g[j];
if(maxv == f[j - v] + w)cnt += g[j - v];
f[j] = maxv;
g[j] = cnt % mod;
}
}

int res = 0;
for(int i = 0; i <= m; i ++)
if(f[i] == f[m])res += g[i];

cout << res << endl;
return 0;
}


Liyb
2天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1e5 + 10;
int a[N];
vector<int>nums;
int n,m;

struct Node
{
int l,r;
int cnt;
}tr[4 * N + N * 17];

int root[N],idx;

int build(int l,int r)
{
int p = ++ idx;//建立一个新的点
if(l == r)return p;//走到叶节点就不用继续开点了,直接返回
int mid = l + r >> 1;//否则继续往下走
tr[p].l = build(l, mid),tr[p].r = build(mid + 1, r);//记录左子树和右子树的编号
return p;//返回每一棵子树的p更新上一层
}

int find(int x)
{
//返回x在离散化数组中的位置
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}

//前一个根节点是u,要插入的区间范围,要插入的位置
int insert(int p, int l, int r, int x)
{
int q = ++ idx;//创建一个新的点
tr[q] = tr[p];//将上一个版本复制过来
if(l == r)//叶节点
{
tr[q].cnt ++;//将这个位置的数量加1
return q;//返回当前最新的根结点的编号
}
int mid = l + r >> 1;
if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);//递归到左儿子
else tr[q].r = insert(tr[p].r, mid + 1, r, x);
//当前点的cnt等于左子树的cnt加上右子树的cnt
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
return q;
}

int query(int q, int p, int l, int r, int k)
{
if(l == r)return r;
//左子树的cnt等于当前版本左子树的cnt(1,r)减去先前版本左子树的cnt(1,l-1)
//我们先考虑左子树[l,r]这一段的cnt
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;//然后在[l,r]内递归查找到某个确定的值
if(k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
nums.push_back(a[i]);
}

//有序离散化
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());

//第一个版本的线段树
root[0] = build(0, nums.size() - 1);

//记录各个版本的线段树编号
for(int i = 1; i <= n; i ++)
root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));//在a[i]这个位置上加1

while(m --)
{
int l,r,k;cin >> l >> r >> k;
//返回的是离散化之前的值
cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)] << endl;
}
return 0;
}


Liyb
3天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 6e5 + 10,M = N * 25;
int s[N];
int tr[M][2];
int root[N],idx;
int max_id[M];//记录trie树上每一个结点能到达的最大位置
int n,m;

//i表示当前插入的是第i个数,k是第几位,p是上一个版本的根节点号,q是当前结点的根节点号
void insert(int i,int k,int p,int q)
{
if(k < 0)//走到结尾判断给他赋一个编号
{
max_id[q] = i;
return;
}
else
{
int u = s[i] >> k & 1;//取出第k位
//如果p不空的话,将不同方向的路径复制过来
if(p)tr[q][u ^ 1] = tr[p][u ^ 1];

tr[q][u] = ++ idx;
//递归到儿子结点
insert(i, k - 1, tr[p][u], tr[q][u]);
//当前根节点下能走到的最大编号是他的所有儿子取一个max
max_id[q] = max(max_id[tr[q][0]],max_id[tr[q][1]]);
//最终我们的每个结点都会存储一个对应的最大值
}
}

int query(int l,int r,int c)
{
int p = root[r];//查询r版本的trie树
for(int i = 23; i >= 0; i --)
{
int u = c >> i & 1;
//如果当前结点子树的存在最大编号大于等于l的直接走下去
if(max_id[tr[p][u ^ 1]] >= l)p = tr[p][u ^ 1];
//否则退而求其次,走另一侧
else p = tr[p][u];
}
//最后我们会走到一个满足条件的最优叶节点
return c ^ s[max_id[p]];//我们的max_id存的是结点的编号在前缀和数组中的下标
}

int main()
{
cin >> n >> m;
//前缀和初始化root[0]
max_id[0] = -1;
root[0] = ++ idx;
insert(0,23,0,root[0]);

for(int i = 1; i <= n; i ++)
{
int x;cin >> x;
s[i] = s[i - 1] ^ x;
root[i] = ++ idx;
insert(i, 23, root[i - 1],root[i]);
}

while (m -- )
{
char op[2];
int l,r,x;
scanf("%s",op);
if(*op == 'A')
{
cin >> x;
n ++;
s[n] = s[n - 1] ^ x;
root[n] = ++ idx;
insert(n, 23, root[n - 1], root[n]);
}
else
{
cin >> l >> r >> x;
cout << query(l - 1, r - 1, s[n] ^ x) << endl;
}
}
return 0;
}


Liyb
3天前

签到题

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
#define int long long
const int N = 1e7 + 10,mod = 1e11 + 3;
//typedef long long LL;

#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second

char g[5][20] =
{
{'q','w','e','r','t','y','u','i','o','p'},
{'a','s','d','f','g','h','j','k','l',' '},
{'!','z','x','c','v','b','n','m',' ',' '}
};

void solve()
{
string s;cin >> s;
for(int i = 0; i < s.size(); i ++)
{
if(s[i] >= 'A' && s[i] <= 'Z')
{
s[i] += 'a' - 'A';
cout << 3 << " " << 1 << " ";
for(int j = 0; j < 3; j ++)
for(int k = 0; k < 10; k ++)
if(s[i] == g[j][k]){
cout << j + 1 << ' ' << k + 1 << endl;
break;
}
}
else
{
for(int j = 0; j < 3; j ++)
for(int k = 0; k < 10; k ++)
if(s[i] == g[j][k]){
cout << j + 1 << ' ' << k + 1 << endl;
break;
}
}
}
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}


签到题

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
#define int long long
const int N = 1e7 + 10,mod = 1e11 + 3;
//typedef long long LL;

#define endl "\n"

void solve()
{
int n;cin >> n;
int sum = 0;
if(n == 1)cout << 1 << endl;
else if(n == 2)cout << 4 << endl;
else
{
int a = 1,b = 3,c;
for(int i = 3; i <= n; i ++)
{
c = (a + b) % mod;
sum = (sum + c) % mod;
a = b,b = c;
}

printf("%lld\n",(sum + 4) % mod);
}
}

signed main()
{
//ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
solve();
return 0;
}


设x为一合数,那么有x=a^k * b^p * ...,约数个数为(k+1)*(p+1)*...


#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
#define int long long

const int N = 1001,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int primes[N],cnt;
bool st[N];

void solve()
{
for(int i = 2; i < N; i ++)
{
if(!st[i])primes[cnt ++] = i;

for(int j = 0; i * primes[j] < N; j ++)
{
st[i * primes[j]] = true;
//i是pj的倍数了就退出
if(i % primes[j] == 0)break;
}
}

int T;cin >> T;
while(T --)
{
int l,r;cin >> l >> r;

int res = 0;
for(int i = 0; i < cnt; i ++)
{
int t = primes[i] * primes[i] * primes[i] * primes[i];
if(t >= l && t <= r)res ++;
}

cout << res << endl;
}
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
solve();
return 0;
}

Nim游戏是所有的异或和为0先手必输,我们只能从第一堆中移动,所以可以枚举移到那一堆


#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#define int long long

const int N = 1010,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int a[N];

void solve()
{
int n;cin >> n;
int sum = 0;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
sum ^= a[i];
}

int t = sum;
for(int i = 0; i < a[1]; i ++)//枚举从第一堆中移多少
{
for(int j = 2; j <= n ; j ++)//枚举移动到那一堆中
{
sum = sum ^ a[1] ^ (a[1] - i) ^ a[j] ^ (a[j] + i);
if(sum == 0){
cout << i << endl;
return;
}
sum = t;
}
}

cout << -1 << endl;
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
solve();
return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#define int long long

const int N = 1010,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
//typedef pair<int,int>PII;
//#define x first
//#define y second

void solve()
{
int x1,y1,x2,y2;
double k,x;
cin >> x1 >> x2 >> y1 >> y2;
k = (y2 - y1) * 1.0 / (x2 - x1);
x = (x1 * y1 + x2 * y2) / (k * (x1 + x2) + y1 + y2);
printf("%lf %lf",x,k * x);
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
solve();
return 0;
}

大胆猜测考察的应该是求字符串的循环节,kmp的经典应用,只要能除尽就说明合法

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#define int long long

const int N = 2e6 + 10,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
//typedef pair<int,int>PII;
//#define x first
//#define y second
char p[N];
int ne[N];
void solve()
{
int n;cin >> n;
cin >> p + 1;

for(int i = 2,j = 0; i <= n; i ++)
{
while(j && p[i] != p[j + 1])j = ne[j];
if(p[j + 1] == p[i])j ++;
ne[i] = j;
}

int k = n - ne[n];

if(n % k)cout << 1 << endl;
else cout << n / k << endl;
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
solve();
return 0;
}

看到数据范围我们可以想到采用二分,而且数越大越更劣,具有单调性



参考求1到n中1的个数

我们对0进行分类讨论:

1.如果当前位上不是0,那么高位上可以取[1,a],低位上可以取[0,10^i),(这样低位不受高位影响了)方案数为a*10^i
2.如果当前位上是0,
(1)如果高位上的数字取[1,a),则低位数字随便取.方案数为(a-1)*10^i
(2)如果高位上的数字为a,那么低位上只能取到b.方案数为1*(b+1)


#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
#define int long long

const int N = 20,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
//typedef pair<int,int>PII;
//#define x first
//#define y second
int f[N];
int n,k;

int quick(int x,int i)
{
return f[i];
}

{
int a = x / 10,b = 0,now = x % 10,res = 1;//将0加进去
for(int i = 0; a; i ++)//枚举每位
{
if(now != 0)
res = res + a * quick(10,i);
else res = res + (a - 1) * quick(10, i) + b + 1;
now = a % 10;
a /= 10;
b = b + x % 10 * quick(10,i);
x /= 10;
}

return res;
}

bool check(int x)
{
return false;
}

void solve()
{
cin >> n >> k;
f[0] = 1;
for(int i = 1; i <= 18; i ++)
f[i] = f[i - 1] * 10;

if(ask(n) < k)cout << -1 << endl;
else
{
int l = 0,r = n;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(check(mid))l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
solve();
return 0;
}


### 性质:a是b的祖先的充分必要条件是a点的入栈时间早于b点且a点的出栈时间晚于b点

首先必要性是显然成立的

充分性也是显然的,祖先一定也满足入栈时间早并且出栈时间晚于b,否则他们就没有在同一分支中
则有本条性质成立

因此我们只需要求出每个点的进栈时间和出栈时间,然后在b中查找是否有满足条件的存在即可

当然我们可以写lca的板子,但是要知道一个结论:求若干个点的最近公共祖先,我们只需要取这些点中dfs序最小的和最大的


#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//typedef long long LL;
#define int long long
const int N = 1e5 + 10,INF = 0x3f3f3f3f;

//typedef pair<int,int>PII;
//#define x first
//#define y second

int h[N],e[N],ne[N],idx;
int dfn[N],lfn[N],timestamp;

{
e[idx] = b,ne[idx] = h[a],h[a] = idx ++;
}

void dfs(int u)
{
dfn[u] = ++ timestamp;//入栈时间
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
}
lfn[u] = ++ timestamp;//出栈时间
}

void solve()
{
int n,q;cin >> n >> q;

memset(h,-1,sizeof h);

for(int i = 2; i <= n; i ++)
{
int x;cin >> x;
}

dfs(1);

while(q --)
{
int l,r;cin >> l >> r;
//cout << l << ' ' << r << endl;
int minv = INF,maxv = 0;
for(int i = 0; i < l; i ++)
{
int a;cin >> a;
minv = min(minv, dfn[a]);
maxv = max(maxv, lfn[a]);
}

bool ok = false;
for(int i = 0; i < r; i ++)
{
int a;cin >> a;
if(dfn[a] < minv && lfn[a] > maxv)
ok = true;
//注意这里不能提前退出,我们要读完所有的输入,否则会出现错误
}

if(ok)cout << "yes" << endl;
else cout << "no" << endl;
}
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
solve();
return 0;
}


Liyb
4天前

A Wonderful Permutation
只需要将前k小的数放到前k位即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#define int long long

const int N = 110,M = N * N,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int a[N];

void solve()
{
int n,k;cin >> n >> k;
for(int i = 1; i <= n; i ++)cin >> a[i];
//我们只需要将前k小的数放到前k位即可
int res = 0;
for(int i = 1; i <= k; i ++)
if(a[i] > k)res ++;
cout << res << endl;

}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}


B Woeful Permutation
从大到小考虑每个数,只要两个数互质乘积一定是最大的,详见代码

  #include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;

const int N = 1e5 + 10;
typedef long long LL;
//#define int long long
#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
//{
//  int x = 0,f = 1; char ch = getchar();
//  while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
//  while(ch >= '0' && ch <= '9')x = (x << 3) + (x << 1) + ch - '0',ch = getchar();
//  return x * f;
//}

//互质
void solve()
{
int n;cin >> n;
if(n & 1)
{
cout << 1 << " ";
for(int i = 2; i <= n; i ++)
cout << (i ^ 1) << " ";
}

else
{
for(int i = 1; i <= n; i += 2)
cout << i + 1 << " " << i << " ";
}
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
return 0;
}

题意:给定你一个数组,定义一种操作为将所有值为x的数变成0,问最少操作多少次后数组变成


#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#define int long long

const int N = 1e5 + 10,INF = 0x3f3f3f3f;
typedef long long LL;

#define endl "\n"
typedef pair<int,int>PII;
#define x first
#define y second
int a[N];

void solve()
{
int n; cin >> n;
for(int i = 1; i <= n; i ++)cin >> a[i];

map<int,int>mp;//用来标记这个数是否出现过
int maxv = 0;//用来找到最远的一个至少出现两次的不相邻的数的位置
for(int i = 1; i <= n; i ++)
{
if(mp[a[i]] && a[i] != a[i - 1])
{
maxv = max(maxv, i);
mp[a[i]] = 1;
}
else mp[a[i]] = 1;
}
//cout << maxv << endl;

//在限制条件下找到最长后缀
for(int i = n; i > maxv + 1; i --)//我们最多到maxv+1的位置
if(a[i] < a[i - 1]) {
maxv = i - 1;
break;
}

//cout << maxv << endl;
map<int,int>m;//判重
int res = 0;
//将前面不合法的置成0
for(int i = 1; i <= maxv; i ++)
{
if(!m[a[i]])res ++;
m[a[i]] = 1;
}

cout << res << endl;
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
//solve();
return 0;
}

题意:给定一个n个结点的无向图,定义边权为数组种l->r一段的最小值

1.直达 a[i]和a[i+1]的最小值
2.经中转点到最小值点 2*minv

(1)使第k小的数变成正无穷
(2)使得a[i]和a[i+1]比较中取到最大的那一个


#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
const int N = 2e5 + 10,INF = 1e9;
typedef long long LL;
#define int long long
typedef pair<int,int>PII;
#define x first
#define y second
PII q[N];
int a[N],b[N];

bool cmp(PII a, PII b)
{
return a.second < b.second;
}

void solve()
{
int n,k;cin >> n >> k;
for(int i = 0; i < n; i ++)cin >> a[i],q[i] = {i, a[i]};

sort(q, q + n, cmp);

//将前k小的数变成正无穷
for(int i = 0; i < k - 1 ; i ++)
{
q[i].second = INF;
a[q[i].first] = INF;
}

for(int i = 0; i < n; i ++)b[i] = a[i];//两种情况

int t = -INF;
a[q[k - 1].first] = INF;//将前k小的全部置成无穷的情况
for(int i = 0; i < n - 1; i ++)
t = max(t, min(a[i], a[i + 1]));

int res1 = 0,res2 = 0;
sort(a, a + n);
res1 = min(a[0] * 2, t);//现在a数组中最小的数和t取一个最小是我们的距离
sort(b, b + n);
//最小数的二倍和最大的数取一个最小
res2 = min(b[0] * 2, b[n - 1]);//剩一种操作,一定能取到最大的数

//两种情况取一个最大就是直径
cout << max(res1,res2) << endl;
}

signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
int t;cin >> t;
while(t --)
{
solve();
}
return 0;
}


Liyb
5天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
#define int long long

const int N = 3e5 + 10;
int a[N],b[N];
int n;
signed main()
{
cin >> n;
for(int i = 1; i <= n; i ++)cin >> a[i];
// for(int i = 1; i <= n; i ++)
// {
//     cin >> a[i];
//     b[i] = b[i - 1] ^ a[i];
// }

// int res = 0;
// for(int len = 2; len <= n; len += 2)
// {
//     for(int l = 1; l + len - 1 <= n; l ++)
//     {
//         int r = l + len - 1;
//         cout << b[l - 1] << ' ' << b[r] << ' ' << endl;
//         if(b[l - 1] == b[r])res ++;
//     }
// }

// cout << res << endl;

//考虑优化:固定一个点r,那么我们的条件就变为了查询前面有多少个数的前缀b等于b[r](哈希表维护)
//且与r奇偶性不同,所以开两个哈希表
unordered_map<int,int>hash[2];//0存偶数,1存奇数
int res = 0,sum = 0;
hash[0][sum] ++;//初始化,我们要找的是l-1,所以0也要算
for(int r = 1; r <= n; r ++)//从前向后枚举我们的r
{
sum ^= a[r];
res += hash[r & 1][sum];
hash[r & 1][sum] ++;//合法的答案
}
cout << res << endl;
return 0;
}


Liyb
5天前
//我们将每个牌子看成是由若干个小正方形组成的,我们将所有第一个组成的置成true
//所有第二个组成的置成false,然后找到四个最值即可得解
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2010,B = N / 2;
bool st[N][N];
int main()
{
int a,b,c,d;cin >> a >> b >> c >> d;
a += B,b += B,c += B,d += B;
for(int i = a; i < c; i ++)//枚举格子的横坐标
for(int j = b; j < d; j ++)
st[i][j] = true;

cin >> a >> b >> c >> d;
a += B,b += B,c += B,d += B;
for(int i = a; i < c ;i ++)
for(int j = b;j < d; j ++)
st[i][j] = false;

//分别维护横坐标最小值,纵坐标最小值,横坐标最大值,纵坐标最大值
a = N,c = N,b = 0,d = 0;
for(int i = 1; i < N; i ++)
for(int j = 1; j < N; j ++)
if(st[i][j])
{
a = min(a, i),c = min(c, j);
b = max(b, i),d = max(d, j);
}

int w = max(0, b - a + 1);
int h = max(0, d - c + 1);
cout << w * h << endl;
return 0;
}