A、打怪
判掉 -1 ，由于数据较小，直接暴力就行
也可以求出打败一只怪兽的花费的血量，然后暴力剩下的血量
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
const int MAXN = 2e5 + 5;
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int h, atk, h1, atk1, t;
sc("%d%d%d%d", &h, &atk, &h1, &atk1);
if (atk1 == 0 || atk >= h1)
{
pr("-1\n");
continue;
}
t = h1;
int cnt = 0;
while (true)
{
h1 -= atk;
if (h1 <= 0)
{
cnt++;
h1 = t;
continue;
}
h -= atk1;
if (h <= 0)
break;
}
pr("%d\n", cnt);
}
} B、吃水果
对于加倍操作，肯定作用在较小的数字上，由于要全部清0，最少操作次数一定是最大的那个数字，假定我们先通过加倍操作让最小的数字 小于 最大的数字，并且最小的数字*2 大于等于 最大的数字
那么我们可以通过若干次减一操作使得 最小的数字的两倍等于最大的数字，然后在将最小的数字翻倍，执行建议操作即可。
所以答案就是最大的数字加上使得最小的数字大于等于最大的数字的翻倍操作次数
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
const int MAXN = 2e5 + 5;
int main()
{
int T;
sc("%d", &T);
while (T--)
{
int n, m;
sc("%d%d", &n, &m);
if (n > m)
swap(n, m);
int cnt = m;
while (n < m)
{
n = n * 2;
cnt++;
}
pr("%d\n", cnt);
}
} C、四个选项
考虑到范围比较小，并且其中不可行解非常多，我们考虑先用并查集合并相同答案，考虑到四个选项，两个二进制位表示一个状态，然后状压枚举合并后的数量，（其实感觉直接 dfs 效率应该更高
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
int num[15];
int que[15];
void init()
{
for (int i = 1; i <= 12; i++)
que[i] = i;
}
int getf(int k)
{
return k == que[k] ? k : que[k] = getf(que[k]);
}
void merge(int a, int b)
{
que[getf(a)] = getf(b);
}
int main()
{
init();
int a, b, c, d, m;
sc("%d%d%d%d%d", &a, &b, &c, &d, &m);
while (m--)
{
int a, b;
sc("%d%d", &a, &b);
merge(a, b);
}
vector<int>v;
for (int i = 1; i <= 12; i++)
num[getf(i)]++;
for (int i = 1; i <= 12; i++)
{
if (num[i])
v.push_back(num[i]);
}
int sz = v.size() - 1;
ll cnt = 0;
for (int i = 0; i < (1 << (2 * sz)); i++)
{
int aa = a, bb = b, cc = c, dd = d;
for (int j = 0; j < sz; j++)
{
int t = 0;
if (i & (1 << (j * 2)))
t += 2;
if (i & (1 << (j * 2 + 1)))
t += 1;
if (t == 0)
aa -= v[j];
else if (t == 1)
bb -= v[j];
else if (t == 2)
cc -= v[j];
else if (t == 3)
dd -= v[j];
if (aa < 0 || bb < 0 || cc < 0 || dd < 0)
goto qwe;
}
if (aa == v[sz] || bb == v[sz] || cc == v[sz] || dd == v[sz])
cnt++;
qwe:;
}
pr("%lld\n", cnt);
} D、最短路变短了
比较套路的一个题吧
从 1 开始跑最短路，从 n 开始跑反向边的最短路，然后枚举每条边方向相反，即可。
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define Pair pair<ll,int>
#define ll long long
const ll inf = 1e18 + 7;
const int MAXN = 2e5 + 5;
using namespace std;
struct edge
{
int to;
ll w;
int nex;
}e1[MAXN], e2[MAXN];
int head1[MAXN], tot1;
int head2[MAXN], tot2, n, m;
ll dis1[MAXN], dis2[MAXN];
bool book1[MAXN], book2[MAXN];
void init()
{
fill(head1, head1 + 200005, -1);
fill(head2, head2 + 200005, -1);
tot1 = 1;
tot2 = 1;
}
void add1(int a, int b, ll c)
{
e1[tot1] = edge{ b,c,head1[a] };
head1[a] = tot1++;
}
void add2(int a, int b, ll c)
{
e2[tot2] = edge{ b,c,head2[a] };
head2[a] = tot2++;
}
void dij1()
{
priority_queue<Pair, vector<Pair>, greater<Pair> >q;
q.push(Pair{ 0,1 });
dis1[1] = 0;
while (!q.empty())
{
int now = q.top().second;
q.pop();
if (book1[now])
continue;
book1[now] = true;
for (int i = head1[now]; i + 1; i = e1[i].nex)
{
int t = e1[i].to;
if (dis1[t] > dis1[now] + e1[i].w)
{
dis1[t] = dis1[now] + e1[i].w;
q.push(Pair{ dis1[t],t });
}
}
}
if (dis1[n] == inf)
dis1[n] = -1;
//printf("%lld\n", dis1[n]);
}
void dij2()
{
priority_queue<Pair, vector<Pair>, greater<Pair> >q;
q.push(Pair{ 0,n });
dis2[n] = 0;
while (!q.empty())
{
int now = q.top().second;
q.pop();
if (book2[now])
continue;
book2[now] = true;
for (int i = head2[now]; i + 1; i = e2[i].nex)
{
int t = e2[i].to;
if (dis2[t] > dis2[now] + e2[i].w)
{
dis2[t] = dis2[now] + e2[i].w;
q.push(Pair{ dis2[t],t });
}
}
}
if (dis2[n] == inf)
dis2[n] = -1;
//printf("%lld\n", dis2[n]);
}
struct node
{
int a;
int b;
ll c;
}que[MAXN];
int main()
{
init();
scanf("%d%d", &n, &m);
fill(dis1, dis1 + 200005, inf);
fill(dis2, dis2 + 200005, inf);
fill(book1, book1 + 200005, false);
fill(book2, book2 + 200005, false);
for (int i = 1; i <= m; i++)
{
int a, b; ll c;
sc("%d%d%lld", &a, &b, &c);
add1(a, b, c);
add2(b, a, c);
que[i] = node{ b,a,c };
}
dij1();
dij2();
ll ans = dis1[n];
int q;
sc("%d", &q);
while (q--)
{
int tt;
sc("%d", &tt);
node t = que[tt];
if (dis1[t.a] + t.c + dis2[t.b] < ans)
pr("YES\n");
else
pr("NO\n");
}
} E、相似的子串
字符串哈希，（不会
考虑到答案具有单调性，考虑二分，判断的时候，遍历每个位置 i 作为终点，长度为 k 的值，然后简单 dp，dp[n] 表示前 n 个字符选则若干个长度为 k 的子串，价值为 val[n]（以 n 结尾的长度为 k 的字符哈希值），最多的相同串个数，dp[i][val[i]]=dp[i-k][val[i]]+1
#include <bits/stdc++.h>
#include <unordered_map>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2e5 + 5;
int n, k;
char s[MAXN];
const ll p1 = 233, mod1 = 1e9+7;
const ll p2 = 1e9+7, mod2 = 1e9+9;
ll power(ll a, ll b, ll mod)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
#define Pair pair<ll,ll>
bool check(int mid)//长度
{
map<Pair, Pair>mp;
int cnt = 1, len = 0;
ll hash1 = 0, hash2 = 0;
for (int i = 1; i <= n; i++)
{
hash1 = (p1 * hash1 + s[i] - 'a' + 1) % mod1;
hash2 = (p2 * hash2 + s[i] - 'a' + 1) % mod2;
len++;
if (len > mid)
{
hash1 = (hash1 - (power(p1, mid, mod1) * (s[i - mid] - 'a' + 1)) % mod1 + mod1) % mod1;
hash2 = (hash2 - (power(p2, mid, mod2) * (s[i - mid] - 'a' + 1)) % mod2 + mod2) % mod2;
len--;
}
if (len == mid)
{
if (mp.count(Pair{ hash1,hash2 }) == 0)
mp[Pair{ hash1,hash2 }] = Pair{ i,1 };
else if (mp[Pair{ hash1,hash2 }].first + mid <= i)
mp[Pair{ hash1,hash2 }] = Pair{ i,mp[Pair{ hash1,hash2 }].second + 1 };
if (mp[Pair{ hash1,hash2 }].second >= k)
return true;
}
}
return false;
}
int main()
{
sc("%d%d%s", &n, &k, s + 1);
int l = 0, r = n / k;
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (check(mid))
l = mid;
else
r = mid;
}
if (check(r))
l = r;
pr("%d\n", l);
} 
京公网安备 11010502036488号