题意：有N个物品，每个物品有一个价格，有K个优惠券，每个优惠券能抵消X元，当物品剩余价格低于X时，可以用掉抵用券把免费兑换物品，问最低花多少钱买走全部物品
解法：商品按价格从大到小排序，然后，在保证剩余价格大于零的情况下尽可能用掉优惠券，最后，如果优惠券有剩余，则按照从剩余价格大到小排序花掉优惠券
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const long long mod = 1e9 + 7;
const int inf = 0x7fffffff;
const int maxn = 2e5 + 5;
int main(){
#define int ll
int n,k,x;
cin>>n>>k>>x;
vector<int> a(n);
for(int i=0;i<n;++i){
cin>>a[i];
}
sort(a.begin(),a.end(),greater<int>());
for(int i=0;i<n;++i){
if(a[i]/x <= k){
k -= a[i]/x;
a[i] %= x;
if(k==0) break;
}else{
a[i] -= k*x;
k = 0;
break;
}
}
sort(a.begin(),a.end(),greater<int>());
int res = 0;
for(int i=0;i<n;++i){
if(a[i]==0) break;
if(k>0){
k--;
}else{
res += a[i];
}
}
cout<<res<<endl;
return 0;
}
|
题意：给出N，求一个最小的大于等于N的数X，满足存在非负整数$a,b$使得$X = a^3+a^2b+ab^2+b^3$
解法：可以看出，$N\le X=(a+b)(a^2+b^2)$，因此从数据范围推断出$\max{a,b}\le 1e6$，因此可以枚举$a$，然后二分查找满足条件的最小的$b$
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const long long mod = 1e9 + 7;
const int inf = 0x7fffffff;
const int maxn = 1e5 + 5;
int main(){
ll n;
cin>>n;
auto f = [&](ll a,ll b){
return (a+b)*(a*a+b*b);
};
ll ans = 1e18;
for(ll a=0;a<=1e6;++a){
ll l = 0, r = 1e6;
while(l<r){
ll mid = (l+r)>>1;
if(f(a,mid)<n) l = mid + 1;
else r = mid;
}
ans = min(ans, f(a,l));
}
cout<<ans<<endl;
return 0;
}
|
题意：给出一个国际象棋棋盘，有一些格子不能走，给出一个象，一步可以朝斜着的四个方位走任意格子，给出起点和终点，问最少多少步能完成，如果完不成，返回-1
解法：BFS，需要注意的是，定义vis[x][y][dir]数组用来存储位置x,y和此时的方向dir（一定要有方向）是否被访问过，在遍历的时候，外层枚举方位，内层枚举长度，一旦 走出去 or 不能走 or vis标记过 都直接break，用于剪枝
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const long long mod = 1e9 + 7;
const int inf = 0x7fffffff;
const int maxn = 1500 + 5;
int n,ax,ay,bx,by;
char mm[maxn][maxn];
int dir[4][2] = {{1,1},{-1,1},{1,-1},{-1,-1}};
struct node
{
int x,y,step;
};
bool vis[maxn][maxn][4];
int main(){
cin>>n>>ax>>ay>>bx>>by;
if(((ax+ay)%2==0 && (bx+by)%2==1) or ((bx+by)%2==0 && (ax+ay)%2==1)){
return cout<<-1<<endl,0;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cin>>mm[i][j];
}
}
auto in = [&](int x,int y){
return x>=1 && x<=n && y>=1 && y<=n;
};
queue<node> q;
q.push(node{ax,ay,0});
while(!q.empty()){
node q1 = q.front();
q.pop();
int x = q1.x, y = q1.y, step = q1.step;
if(x==bx && y==by){
return cout<<step<<endl,0;
}
for(int k=0;k<4;++k){
for(int i=1;i<=n;++i){
int dx = x + dir[k][0] * i;
int dy = y + dir[k][1] * i;
if(!in(dx,dy) or mm[dx][dy]=='#' or vis[dx][dy][k]) break;
vis[dx][dy][k] = 1;
q.push(node{dx,dy,step+1});
}
}
}
cout<<-1<<endl;
return 0;
}
|
题意：给出$N(\le 18)$个字符串（都是abcdefghijklmnopqrstuvwxyz的子序列），每次从其中一个里挑任意字符组成一个长度为$L$的字符串，问可以组成多少种不同的字符串
解法：状态压缩+组合数学+容斥原理
一个长度为A的字符串能组成$A^L$个字符串，但是会发现重复枚举了，于是挑出两两字符串公共的字符（假设有B个），则减去$B^L$个，再挑出三个三个的字符串公共字符（假设有C个），则加上$C^L$个，以此类推（奇数加，偶数减）。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const long long mod = 998244353;
const int inf = 0x7fffffff;
const int maxn = 1e5 + 5;
int n,L;
vector<string> s;
int main(){
ios::sync_with_stdio(false);
auto qpow = [&](ll x,ll y){
ll res = 1, base = x;
while(y){
if(y&1) res = (res * base)%mod;
base = (base * base) % mod;
y >>= 1;
}
return res;
};
cin>>n>>L;
s.resize(n);
for(int i=0;i<n;++i) cin>>s[i];
ll ans = 0;
for(int i=1;i<(1<<n);++i){
int cnt = __builtin_popcount(i);
int tot = 0;
unordered_map<char,ll> ma;
for(int j=0;j<n;++j){
if((i>>j)&1){
for(char &c:s[j]){
if(++ma[c]==cnt) tot++;
}
}
}
ll tp = qpow(tot, L);
if(cnt&1) ans = (ans + tp) % mod;
else ans = (ans - tp + mod) % mod;
}
cout<<ans<<endl;
return 0;
}
|
PS：想不出来，看的题解
题意：有一棵树，除根节点外每个节点有个权值，A和B玩树上游戏，初始时树根有一个小人，B先开始。
B的行为：可以将任意非根节点权值变为0
A的行为：可以将小人移动到所在节点的任意儿子处
问：最终A的得分为小人所在处的权值
A想让得分尽可能大，B想让得分尽可能小，问两者在最优操作下，A最大得分
解法：博弈+二分+树形dp
大概就是，考虑给定一个X，令权值大于X的为黑点($color=1$)，其余为白点($color=0$)，玩一个等价的新游戏（B先行动）：
A赢定义为：A此刻在黑色节点
B赢定义为：A此刻在叶子节点
B的行为：将任意非根节点变为白色
A的行为：将小人移动到任意一个儿子节点
定义dp[u]表示u为根的树，B想要获胜的话需要在游戏开始之前将其变成白色的最少节点数
则显然有：dp[1] = 0时B必胜，否则必败
转移方程：$dp[u] = \max { \sum_{v\in C_u} dp[v] - 1,0 } + color[u]$
最后，二分得到最大的X即可
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-6;
const long long mod = 1e9 + 7;
const int inf = 0x7fffffff;
const int maxn = 1e5 + 5;
int n;
vector<int> a,color,dp;
vector<vector<int>> e;
void dfs(int u,int fa){
for(auto &v:e[u]){
if(v!=fa){
dfs(v,u);
dp[u] += dp[v];
}
}
dp[u] = max(dp[u]-1, 0) + color[u];
}
bool check(int x){
for(int i=0;i<n;++i){
color[i] = (a[i]>x);
}
dp.assign(n,0);
dfs(0,-1);
return dp[0];
}
int main(){
cin>>n;
a.resize(n);
e.resize(n);
color.resize(n);
dp.resize(n);
for(int i=1;i<n;++i){
cin>>a[i];
}
for(int u,v,i=0;i<n-1;++i){
cin>>u>>v;
--v,--u;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
int l = 0, r = 1e9;
while(l<r){
int mid = (l+r)>>1;
if(check(mid)){
l = mid + 1;
}else{
r = mid;
}
}
cout<<l<<endl;
return 0;
}
|