A. A Xor B Problem（计数）
输入
5
1 1 2 2 3
输出
9
说明
点击查看代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define int long longusing namespace std;const int N = 2e5 + 10;unordered_map<int, int> mp;
int ans, s, n, x;void solve()
{cin >> n;while(n --){cin >> x;s += mp[x] * mp[x];mp[x] ++;ans += mp[x] * mp[x];}cout << ans - s << '\n';
}signed main()
{IOS;int _ = 1;
// cin >> _;while(_ --)solve();return _ ^ _;
}
B. 吃苹果（贪心）
输入
4 3
3 1
4 5
2 3
1 5
输出
16
说明
对于 10% 的数据，1≤n≤10。
对于 40% 的数据，\(1≤n≤10^4\) 。
对于 100% 的数据，\(1≤k≤n≤10^5,1≤a_i,b_i≤10^4\)。
点击查看代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define int long longusing namespace std;const int N = 2e5 + 10;int n, m, ans;
int a[N];
struct node
{int x, y, s;
}p[N];bool cmp(node a, node b)
{return a.s > b.s;
}void solve()
{cin >> n >> m;for(int i = 0; i < n; i ++)cin >> p[i].x >> p[i].y, p[i].s = p[i].y - p[i].x;sort(p, p + n, cmp);for(int i = 0; i < n; i ++){if(m) ans += p[i].y, m --;else ans += p[i].x;}cout << ans << '\n';
}signed main()
{IOS;int _ = 1;
// cin >> _;while(_ --)solve();return _ ^ _;
}
C. n皇后问题（模拟）
输入
2 4
1 1
1 2
2 1
2 2
输出
Yes
No
No
No
说明
点击查看代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define int long longusing namespace std;const int N = 1e7 + 10;int n, m;
int l[N], r[N], p[N], up[N];void solve()
{cin >> n >> m;while(m --){int x, y;cin >> x >> y;if(!l[x]&&!r[y]&&!p[x + n + y]&&!up[2 * n + x - y]){cout << "Yes\n";l[x] = 1, r[y] = 1;p[x + y + n] = 1;up[2 * n + x - y] = 1;}else cout << "No\n";}
}signed main()
{IOS;int _ = 1;
// cin >> _;while(_ --)solve();return _ ^ _;
}
D. 分苹果（模拟）
输入
4
0 1 0
1 0 0
1 1
1 -1
-1 1
-1 -1
输出
1 1 1 1
说明
对于 10% 的数据，\(1≤n≤10,−10 ^2≤Ae,Be,Ce,Ar,Br,Cr≤10^2,−10^3≤x,y≤10 ^3\)。
对于 40% 的数据，\(1≤n≤10^4,−10^4≤Ae,Be,Ce,Ar,Br,Cr≤10^4,−10^5≤x,y≤10^5\)。
对于 100% 的数据，\(1≤n≤10^5,−10^8≤Ae,Be,Ce,Ar,Br,Cr≤10^8,−10^9≤x,y≤10^9，(Ae∣Be)!=0,(Ar∣Br)!=0\)。
点击查看代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define int long longusing namespace std;const int N = 2e5 + 10;int a1, a2, b1, b2, c1, c2;
int s[10], n;bool get1(int x, int y)
{return a1 * x + b1 * y + c1 > 0;
}bool get2(int x, int y)
{return a2 * x + b2 * y + c2 > 0;
}void solve()
{cin >> n;cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2;while(n --){int x, y;cin >> x >> y;if(get1(x, y)&&get2(x, y))s[1] ++;else if(!get1(x, y)&&get2(x, y))s[2] ++;else if(!get1(x, y)&&!get2(x, y))s[3] ++;else s[4] ++;}sort(s + 1, s + 5);for(int i = 1; i < 5; i ++)cout << s[i] << ' ';
}signed main()
{IOS;int _ = 1;
// cin >> _;while(_ --)solve();return _ ^ _;
}
E. 完形填空（概率dp）
输入
4
10 20 30 40
40 30 20 10
10 40 20 30
30 10 40 20
输出
160
说明
对于30% 的数据，n=4
对于 60% 的数据，1≤n≤20
对于 100% 的数据，1≤n≤100
点击查看代码
#include<iostream>
#include<cstring>using namespace std;const int N = 26, M = 110;int dp[M][N][N][N][N];
int A[M], B[M], C[M], D[M];
int n;int dfs(int n, int a, int b, int c, int d)
{if(n == 0) return 0;if(a < 0||b < 0||c < 0||d < 0) return -1e9;int &ans = dp[n][a][b][c][d];if(ans) return ans;if(a) ans = max(ans, A[n] + dfs(n - 1, a - 1, b, c, d));if(b) ans = max(ans, B[n] + dfs(n - 1, a, b - 1, c, d));if(c) ans = max(ans, C[n] + dfs(n - 1, a, b, c - 1, d));if(d) ans = max(ans, D[n] + dfs(n - 1, a, b, c, d - 1));return ans;
}int main()
{cin >> n;for(int i = 1; i <= n; i ++)cin >> A[i] >> B[i] >> C[i] >> D[i];cout << dfs(n, n / 4, n / 4, n / 4, n / 4) << endl;return 0;
}
G. A Xor B Problem again（计数）
输入
5
1 1 2 2 3
输出
8
说明
点击查看代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define int long longusing namespace std;const int N = 2e5 + 10;int sum[N], val[N];
int vis[N];
int n, ans, a[N];
int bin[N];void solve()
{cin >> n;bin[0] = 1;for(int i = 1; i < 19; i ++) bin[i] = bin[i - 1] << 1;for(int i = 1; i <= n; i ++)cin >> a[i], sum[a[i]] ++;for(int i = 1; i <= n; i ++){int v = 0;for(int j = 0; j < 17; j ++)if((a[i] & bin[j]) == 0)v |= bin[j];if(vis[v]) ans += val[v];else{for(int s = v; s; s = v&(s - 1))val[v] += sum[s];val[v] += sum[0];ans += val[v];vis[v] = 1;}}cout << ans << '\n';
}signed main()
{IOS;int _ = 1;
// cin >> _;while(_ --)solve();return _ ^ _;
}
H. 摘苹果（线段树）
输入
5 5
1 10 100 1000 10000
2 1 5
3 1 5
1 1 5
2 1 5
3 1 5
输出
2
11111
3
7405
说明
对于 100% 的数据，\(1≤n≤10^5 ，1≤m≤10^5 ， 1≤a_i ≤10^9 ，1≤op≤3，1≤l≤r≤n\)。
点击查看代码
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define int long longusing namespace std;const int N = 1e5 + 10;struct node
{int l, r;int s, e;bool f;
}tr[N << 2];
int n, m;
int a[N];void pushup(int u)
{tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;tr[u].e = tr[u << 1].e + tr[u << 1 | 1].e;tr[u].f = tr[u << 1].f || tr[u << 1 | 1].f;
}void build(int u, int l, int r)
{if(l == r) tr[u] = {l, r, a[l], a[l] < 100, a[l] > 9};else{tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);}
}void modify(int u, int l, int r)
{if(!tr[u].f) return ;if(tr[u].l == tr[u].r){tr[u].s -= (tr[u].s + 2) / 3;tr[u].e = tr[u].s < 100;tr[u].f = tr[u].s > 9;}else{int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify(u << 1, l, r);if(r > mid) modify(u << 1 | 1, l, r);pushup(u);}
}int query(int u, int l, int r, int f)
{if(tr[u].l >= l&&tr[u].r <= r){if(f == 2) return tr[u].e;return tr[u].s;}else{int mid = tr[u].l + tr[u].r >> 1;int s = 0;if(l <= mid) s += query(u << 1, l, r, f);if(r > mid) s += query(u << 1 | 1, l, r, f);return s;}
}void solve()
{cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> a[i];build(1, 1, n);int f, l, r;while(m --){cin >> f >> l >> r;if(f == 1) modify(1, l, r);else cout << query(1, l, r, f) << '\n';}
}signed main()
{IOS;int _ = 1;
// cin >> _;while(_ --)solve();return _ ^ _;
}
