A.打怪
题意：
你有h的血量，a的攻击你有h的血量，a的攻击你有h的血量，a的攻击
怪兽有H的血量，A的攻击怪兽有H的血量，A的攻击怪兽有H的血量，A的攻击
每次你先出手，轮流攻击，血量小于等于0就死每次你先出手，轮流攻击，血量小于等于0就死每次你先出手，轮流攻击，血量小于等于0就死
问不死的前提最多能打多少怪问不死的前提最多能打多少怪问不死的前提最多能打多少怪
不会死输出−1不会死输出-1不会死输出−1
题解：
首先不会死就说明，每次都能一次解决怪兽即a>=H首先不会死就说明，每次都能一次解决怪兽即a>=H首先不会死就说明，每次都能一次解决怪兽即a>=H
然后算怪兽每次的攻击次数，由于你是先手，所以最后一击怪兽不会还手然后算怪兽每次的攻击次数，由于你是先手，所以最后一击怪兽不会还手然后算怪兽每次的攻击次数，由于你是先手，所以最后一击怪兽不会还手
就算还差一次杀死怪兽的次数，乘上怪兽的攻击就算还差一次杀死怪兽的次数，乘上怪兽的攻击就算还差一次杀死怪兽的次数，乘上怪兽的攻击
在自己不死的前提看自己能承受多少次，就是杀死多少只怪兽在自己不死的前提看自己能承受多少次，就是杀死多少只怪兽在自己不死的前提看自己能承受多少次，就是杀死多少只怪兽
AC代码
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define endl '\n' typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; //const int mod=1e9+7; const int mod=998244353; const double eps = 1e-10; const double pi=acos(-1.0); const int maxn=3e6+10; const ll inf=0x3f3f3f3f; const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int t; cin>>t; while(t--){ int h,a,H,A; cin>>h>>a>>H>>A; if(a>=H)cout<<-1; else { int k=(H-1)/a; int p=A*k; cout<<(h-1)/p; } cout<<endl; } return 0; }
B.吃水果
题意：
有a个苹果和b个香蕉有a个苹果和b个香蕉有a个苹果和b个香蕉
每天必须同时吃掉1个苹果和1个香蕉每天必须同时吃掉1个苹果和1个香蕉每天必须同时吃掉1个苹果和1个香蕉
或者你可以使某个水果数量翻倍或者你可以使某个水果数量翻倍或者你可以使某个水果数量翻倍
问最少多天能让两个水果都没有问最少多天能让两个水果都没有问最少多天能让两个水果都没有
题解：
贪心+模拟贪心+模拟贪心+模拟
先让数量小的每次翻倍，直到翻倍后比另一个大先让数量小的每次翻倍，直到翻倍后比另一个大先让数量小的每次翻倍，直到翻倍后比另一个大
然后开始吃，吃到又可以翻倍的时候继续翻倍然后开始吃，吃到又可以翻倍的时候继续翻倍然后开始吃，吃到又可以翻倍的时候继续翻倍
直到a==b结束直到a==b结束直到a==b结束
AC代码
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define endl '\n' typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; //const int mod=1e9+7; const int mod=998244353; const double eps = 1e-10; const double pi=acos(-1.0); const int maxn=3e6+10; const ll inf=0x3f3f3f3f; const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int t; cin>>t; while(t--){ int a,b; cin>>a>>b; int ans=0; if(a>b)swap(a,b); while(1){ if(a==b){cout<<ans+a<<endl;break;} if(a*2<=b)a*=2,ans++; if(a*2>b)a--,b--,ans++; } } return 0; }
C.四个选项
题意：
12道选择题，每道答案可能是A,B,C,D12道选择题，每道答案可能是A,B,C,D12道选择题，每道答案可能是A,B,C,D
要求12道中有a道A，b道B，c道C，d道D要求12道中有a道A，b道B，c道C，d道D要求12道中有a道A，b道B，c道C，d道D
并且给出m个约束条件，每次保证给出的x和y具有相同答案并且给出m个约束条件，每次保证给出的x和y具有相同答案并且给出m个约束条件，每次保证给出的x和y具有相同答案
题解：
DFS+并查集DFS+并查集DFS+并查集
首先用并查集求出有多少个相同答案的集合首先用并查集求出有多少个相同答案的集合首先用并查集求出有多少个相同答案的集合
然后进行DFS，对每个集合进行赋予答案，并维护每个答案的状态然后进行DFS，对每个集合进行赋予答案，并维护每个答案的状态然后进行DFS，对每个集合进行赋予答案，并维护每个答案的状态
直到和题目要求相等ans++直到和题目要求相等ans++直到和题目要求相等ans++
剪枝：每次每个答案加的集合元素数量不能超过这道题的答案剪枝：每次每个答案加的集合元素数量不能超过这道题的答案剪枝：每次每个答案加的集合元素数量不能超过这道题的答案
AC代码
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define endl '\n' typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; //const int mod=1e9+7; const int mod=998244353; const double eps = 1e-10; const double pi=acos(-1.0); const int maxn=3e6+10; const ll inf=0x3f3f3f3f; const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; vector<int> v; int a,b,c,d,m,n; int fa[20],cnt[20],ans; int find(int x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]); } void dfs(int i,int xa,int xb,int xc,int xd){ if(xa==a&&xb==b&&xc==c&&xd==d)ans++; if(i==n)return; if(xa+v[i]<=a)dfs(i+1,xa+v[i],xb,xc,xd); if(xb+v[i]<=b)dfs(i+1,xa,xb+v[i],xc,xd); if(xc+v[i]<=c)dfs(i+1,xa,xb,xc+v[i],xd); if(xd+v[i]<=d)dfs(i+1,xa,xb,xc,xd+v[i]); } int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>a>>b>>c>>d>>m; for(int i=1;i<=12;i++)fa[i]=i; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; int p=find(x),q=find(y); fa[p]=q; } for(int i=1;i<=12;i++)cnt[find(i)]++; for(int i=1;i<=12;i++) if(cnt[i])v.pb(cnt[i]); n=v.size(); dfs(0,0,0,0,0); cout<<ans; return 0; }
D.最短路变短了
题意：
有n个点，m条有向边，每条边带权有n个点，m条有向边，每条边带权有n个点，m条有向边，每条边带权
问如果翻转某一条边，权值不变，起点终点互换，是否会让最短路变短问如果翻转某一条边，权值不变，起点终点互换，是否会让最短路变短问如果翻转某一条边，权值不变，起点终点互换，是否会让最短路变短
询问q次询问q次询问q次
题解：
先用dij算源点为1和源点为n开始的到每个点的最短路径先用dij算源点为1和源点为n开始的到每个点的最短路径先用dij算源点为1和源点为n开始的到每个点的最短路径
最初的最短路径也可以算出假设为dn最初的最短路径也可以算出假设为d_n最初的最短路径也可以算出假设为dn
如果想要某条路翻转会使得最短路变小如果想要某条路翻转会使得最短路变小如果想要某条路翻转会使得最短路变小
说明新的最短路一定会经过这条路说明新的最短路一定会经过这条路说明新的最短路一定会经过这条路
所以只需要用1到这条边新的起点的距离<mtext> </mtext>加上n到这条边新的终点的距离<mtext> </mtext>加上这条边的权值所以只需要用1到这条边新的起点的距离~~加上 n到这条边新的终点的距离~~加上这条边的权值所以只需要用1到这条边新的起点的距离 加上n到这条边新的终点的距离 加上这条边的权值
看这个值是否小于dn，即可判断看这个值是否小于d_n，即可判断看这个值是否小于dn，即可判断
AC代码
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define endl '\n' typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; //const int mod=1e9+7; const int mod=998244353; const double eps = 1e-10; const double pi=acos(-1.0); const int maxn=1e5+10; const ll inf=0x3f3f3f3f; const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; struct edge{ ll u,v,w; }e[200010]; int n,m; vector<pll> g1[maxn],g2[maxn]; ll d1[maxn],d2[maxn]; void dij(ll dis[],vector<pll> g[],int s){ for(int i=1;i<=n;i++)dis[i]=inf*inf; dis[s]=0; priority_queue<pll,vector<pll>,greater<pll> > q; q.push(mp(0,s)); while(!q.empty()){ pll p=q.top(); q.pop(); int u=p.se; if(dis[u]<p.fi)continue; for(auto i:g[u]){ int v=i.fi; ll w=i.se; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; q.push(mp(dis[v],v)); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>n>>m; for(int i=1;i<=m;i++){ ll u,v,w; cin>>u>>v>>w; g1[u].pb(mp(v,w)); g2[v].pb(mp(u,w)); e[i]={u,v,w}; } dij(d1,g1,1);dij(d2,g2,n); int q;cin>>q; while(q--){ ll x; cin>>x; if(d1[e[x].v]+d2[e[x].u]+e[x].w<d1[n])cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
京公网安备 11010502036488号