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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 long
using 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 _ ^ _;
}