A-打怪
因为我先手，我的攻击力如果大于怪物的血量，那么我就能杀无数个，输出-1即可
考虑到我先手，所以先把怪物的血扣掉一次，然后就是怪物先手了，
计算出我的血量能够让怪物打我几次，以及我需要打几下怪物才能死即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin >> t;
while (t--)
{
int a, b, x, y;
cin >> a >> b >> x >> y;
if (b >= x)
cout << "-1" << endl;
else
{
int num = 0;
int q = a / y;
if (a % y)
q++;
x -= b;
int p = x / b;
if (x % b)
p++;
cout <<q/p+(q%p==0?-1:0)<< endl;
}
}
return 0;
}当然了，数据量很小，模拟过程也可以
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin >> t;
while (t--)
{
int a, b, x, y;
cin >> a >> b >> x >> y;
if (b >= x)
cout << "-1" << endl;
else
{
int num = 0;
int flag = 0;
int k = x;
while (1)
{
if (flag == 0)
{
k -= b;
if (k <= 0)
num++, k = x;
else
flag = 1;
}
else
{
a -= y;
if(a<=0) break;
flag = 0;
}
}
cout << num << endl;
}
}
return 0;
}B-吃水果
计算n和m的关系是不是二倍
假设n小于m
如果是n * 2==m 自然是把n乘2，然后每天都吃一个，答案就是1+m;
如果n * 2>m 我们想让他们是二倍关系 设x天后满足二倍关系 则有 2 * (n-x)= m-x -> x=2*n-m
即花x天使得n * 2 = m 然后花一天把n * 2 因为m前面减少了x个 所以剩下m-x个 答案就是x+1+m-x =1+m
发现n * 2 >= m 答案都是m+1
如果n * 2<m 一直把n乘2，直到n * 2 >=m 即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int t;
cin >> t;
while (t--)
{
int n,m;cin>>n>>m;
if(n==m) cout<<n<<endl;
else
{
int sum=0;
int mi=min(n,m),ma=max(n,m);
while(mi*2<ma) mi<<=1,sum++;
cout<<sum+1+ma<<endl;
}
}
return 0;
}C-四个选项
范围很小，考虑暴搜。
用并查集合并，计算出来每个联通块的大小。搜每个块的即可 复杂度4^cnt cnt为块的个数
实际复杂度远远小于4^cnt 因为块的大小和a、b、c、d个数的限制会减少很多没必要的搜索过程
#include<bits/stdc++.h>
using namespace std;
int f[15];
int a,b,c,d,m;
int cnt,ans[15];
int sum;
int vis[15];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void join(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy) f[fx]=fy;
}
void dfs(int x){
if(x>cnt) {
sum++;return ;
}
if(ans[x]<=a) a-=ans[x],dfs(x+1),a+=ans[x];
if(ans[x]<=b) b-=ans[x],dfs(x+1),b+=ans[x];
if(ans[x]<=c) c-=ans[x],dfs(x+1),c+=ans[x];
if(ans[x]<=d) d-=ans[x],dfs(x+1),d+=ans[x];
}
int main(){
cin>>a>>b>>c>>d>>m;
for(int i=1;i<=12;i++) f[i]=i;
while(m--){
int x,y;cin>>x>>y;
join(x,y);
}
for(int i=1;i<=12;i++){
int fa=find(i);
if(!vis[fa]) ans[++cnt]++,vis[fa]=cnt;
else ans[vis[fa]]++;
}
dfs(1);
cout<<sum<<endl;
return 0;
}D-最短路变短了
考虑以1为源点跑一次dijkstra，然后把边反向过来以n为源点跑dijkstra
那么对于第i条边 x->y 边权为d
如果d1[y]+d+d2[x] < d1[n] 就是YES 否则就是NO
我们这样考虑，如果原图的最短路经过第i条边 也就是经过了x->y 那么按照上面的式子我们等于走了1->x->y +d 相当于走了两边这条边，因为没有负边权 显然是会＞d1[n]的 也就是NO
如果原图没有经过x->y 那么最短路想要要变短只可能是 1->y->x->n这样走 因为最短路的路径压根没有走这条 关键路径是不变的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
ll to, cost;
friend bool operator<(node a, node b)
{
return a.cost > b.cost;
}
};
struct nodee
{
ll x, y, d;
} q[200005];
int n, m;
struct dijkstra
{
ll d[100005];
ll e[200005], v[200005], ne[200005], h[200005], idx;
bool vis[100005];
void Init()
{
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++)
d[i] = -1, vis[i] = 0;
}
void add(ll a, ll b, ll c)
{
e[idx] = b, v[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dj(int x)
{
priority_queue<node> q;
q.push({x, 0});
while (!q.empty())
{
node now = q.top();
q.pop();
if (!vis[now.to])
{
vis[now.to] = 1;
d[now.to] = now.cost;
for (int i = h[now.to]; i != -1; i = ne[i])
{
node next;
next.to = e[i];
next.cost = now.cost + v[i];
if (!vis[next.to])
q.push(next);
}
}
}
}
} a, b;
int main()
{
cin>>n>>m;
a.Init();b.Init();
for (int i = 1; i <= m; i++)
{
ll x, y, d;
cin >> x >> y >> d;
q[i] = {x, y, d};
a.add(x, y, d);
b.add(y, x, d);
}
a.dj(1),b.dj(n);
int t; cin >> t;
while (t--)
{
ll x;cin >> x;
if (a.d[q[x].y] + q[x].d + b.d[q[x].x] >= a.d[n])
cout << "NO" << endl;
else
cout << "YES" << endl;
}
return 0;
}E
忽然发现这题挺中规中矩的，没做出来不应该(好吧 摊牌了我承认是我菜)。
题意要求k个有最长公共前缀长度为x且互不相交的x最大值，那么我们只需要考虑前缀即可，这样能保证答案最大。
可以明显发现，如果当前长度满足，那么我们肯定考虑长度大一点满不满足，如果当前长度不满足，那我们肯定考虑长度小一点满不满足。
所以问题可以转为二分答案来进行判定。
等于是要求最大的x，使得有k个长度为x的子串不相交，因为牵扯到求子串的个数有多少个，考虑哈希，O(n)预处理，然后可以O(1)求出任意子串的哈希值。
那么对于二分的判定，我们枚举每个子串，记录下这个子串的个数和出现的最后位置，现在的结尾位置减去记录下的结尾位置>=x 说明两个串不相交 满足不相交的话，我们可以把这个子串个数增加，并更新最后位置为当前的结尾位置 如果存在一个子串的个数≥k，说明长度x是满足的
这样的话，我们对于每次判定可以考虑一个umap的键来保存子串的哈希值，umap的值套一个pair，一个保存最后出现位置，一个保存子串个数
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
unordered_map<ull,pair<int,int>> mp;
const int maxn=2e5+5;
int base=131;
char s[maxn];
ull po[maxn],has[maxn];
int n,k;
bool check(int x){
mp.clear();
for(int i=x;i<=n;i++){
ull ha=has[i]-has[i-x]*po[x];
if(i-mp[ha].first>=x) mp[ha].first=i,mp[ha].second++;
if(mp[ha].second>=k) return 1;
}
return 0;
}
int main(){
cin>>n>>k>>s+1;
po[0]=1;
for(int i=1;i<=n;i++){
has[i]=has[i-1]*base+s[i]-'a';
po[i]=po[i-1]*base;
}
int l=0,r=n+1,ans=0;
while(l+1<r){
int mid=l+r>>1;
if(check(mid)) l=mid,ans=mid;
else r=mid;
}
cout<<ans<<endl;
return 0;
}F 待补
京公网安备 11010502036488号