A 打怪
题目描述戳我传送
你是一个勇士，现在你准备去森林刷毛球怪，你有两个属性（血量，攻击力），毛球怪也有这两个属性。当你遭遇一只毛球怪时你们会进入战斗，然后你和毛球怪轮流攻击（你先手），每次使对方的血量减去自己攻击力的数值，当一方的血量小于等于 0 时死亡。现在你想知道在自己活着的前提下最多杀死几只毛球怪。
输入描述
第一行一个正整数t，代表测试数据组数。
第二行四个正整数h，a，H，A，代表你的血量和攻击力以及毛球怪的血量和攻击力。
所有整数大小不超过1000。
输出描述
共 t 行，每行一个整数x，代表最多能杀死多少毛球怪。如果能杀死无数只，输出-1。
思路
因为是自己先出手，所以只要自己的攻击力 a 大于小怪的血量或者小怪攻击力为0打怪就不会扣血如果是这种情况输出-1就好。其他的情况就算出每回合扣的血量就好，注意如果自己的血量h是每回合扣的血的倍数大的小怪数要减一。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e8
const int mod = 1e9+7;
const int maxn = 1e5+5;
#define iss ios::sync_with_stdio(false)
inline ll read(){
ll s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
int main(){
int t;
cin>>t;
int h,a,H,A;
while(t--){
cin>>h>>a>>H>>A;
int ans = 0;
if(a>=H || A == 0) cout<<-1<<endl;
else{
int ans = H/a;//需要多少回合击杀小怪
if( H % a ) ++ans;//注意整数的除法
int cnt = h/((ans-1)*A);
if(h%((ans-1)*A)==0) cnt-=1;//如果血量是每回合少血的倍数
cout<<cnt<<endl;
}
}
} B 吃水果
题目描述戳我传送
最近米咔买了n个苹果和m个香蕉，他每天可以选择吃掉一个苹果和一个香蕉（必须都吃一个，即如果其中一种水果的数量为0，则他不能进行这个操作），或者使用魔法将某一种水果的数量翻倍。
现在米咔想吃西瓜了，但是他的主人赛小息不让他买新水果，除非苹果和香蕉没有了，即数量都是0了。
现在米咔想知道，最少用多少天他可以吃光苹果和香蕉。
可以证明的是，一定存在一种方案可以让米咔在若干天后吃光苹果和香蕉。
输入描述
第一行一个正整数T（T≤100），代表数据组数。
接下来T行每行两个正整数n，m（n，m ≤100000）。
输出描述
共T行，每行一个正整数代表答案。
思路
两种水果必须同时吃，而且增加水果数量要消耗一天，所以要尽量少的翻倍（心证），而且不能让一种水果数量太多，所以就是在少的水果为多的一半以下增加，于是给出代码：
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e8
const int mod = 1e9+7;
const int maxn = 1e5+5;
#define iss ios::sync_with_stdio(false)
inline ll read(){
ll s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
int main(){
int t;
cin>>t;
int n,m;
while(t--){
cin>>n>>m;
int ans = 0;
if(m>n) swap(n,m);
while(n){
++ans;
if(n>=2*m) m *= 2;
else {
--m;--n;
}
}
cout<<ans<<endl;
}
} C 四个选项
题目描述戳我传送
众所周知，高考数学中有一个题目是给出12个单项选择，每一个选择的答案是 A，B，C，D 中的一个。
网上盛传答案存在某种规律，使得蒙对的可能性大大增加。于是今年老师想让你安排这12个题的答案。但是他有一些条件，首先四个选项的数量必须分别为 na，nb，nc，nd。其次有 m 个额外条件，分别给出两个数字 x，y，代表第 x 个题和第 y 个题的答案相同。 现在你的老师想知道，有多少种可行的方案安排答案。
输入描述
第一行五个非负整数na，nb，nc，nd，m，保证na+nb+nc+nd=12，0≤m≤1000。
接下来m行每行两个整数x，y（1≤ x,y ≤12）代表第x个题和第y个题答案必须一样。
输出描述
仅一行一个整数，代表可行的方案数。
思路
用n【i】来存A，B，C, D四个选项的数量 并查集合并必须是相同选项的题目 接下来直接dfs爆搜即可
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e8
const int mod = 1e9+7;
const int maxn = 1e5+5;
#define iss ios::sync_with_stdio(false)
inline ll read(){
ll s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
int sum[15],fa[15];
int n[5],m;
int cnt = 0;//有多少独立的题目
ll ans = 0;
int findd(int x){
return fa[x] == x ? x : (fa[x] = findd(fa[x]));
}
void init(){//初始化
for(int i = 0 ; i < 15 ;++i){
sum[i] = 1;fa[i] = i;
}
}
void dfs(int x){
for(int i = 0 ; i < 4 ; ++i){
if(n[i] >= sum[x]){
n[i] -= sum[x];
if(x == cnt-1 ) ++ans;//x就是搜了多少节点如果等于cnt-1表示全部节点都已经分配完，结果加一
else dfs(x+1);
n[i] += sum[x];//回退状态
}
}
}
int main(){
init();
cin>>n[0]>>n[1]>>n[2]>>n[3]>>m;
sort(n,n+4,greater<int>());
int x,y;
while(m--){
cin>>x>>y;
int i = findd(x),j = findd(y);
fa[i] = j;//并查集合并选项
}
for(int i = 1 ; i <= 12 ;++i){
if(findd(i) == i) cnt++;//如果父亲节点是自己那就多了一个独立的节点
else sum[fa[i]]++;//有多少选项必须一样的个数
}
sort(sum,sum+15,greater<int>());//在前面的就表示合并后的节点
dfs(0);
cout<<ans<<endl;
} D 最短路变短了
题目描述
给定一个有向带权图，其中包括 n个城市，城市编号从1 到n，有向边的编号从 1 到 m，现在有一个人位于城市 1，并且想要到城市n旅游。现在政府正在决定将一条道路反向，这个人想知道在某一指定道路反向的情况到达城市n最短路径长度会不会变短。
保证开始给定的图从城市1可以到达城市n，若边反向后城市1不能到达城市n，我们视为最短路径长度没有变短。
输入描述戳我传送
第一行包括两个整数n，m（1≤n≤100000，1≤m≤200000)
接下来m行每行三个整数u，v，c (1≤u,v≤n, 1≤c≤10^9)，分别代表一条有向边的起点，终点和边权。保证没有自环。
接下来一行一个整数q（1≤q≤200000），代表查询组数，查询之间是独立的。
接下来q行每行一个整数x（1≤x≤m），代表询问将第x条边反向后到达城市n的最短路长度会不会变短。
输出描述
共q行，如果最短路变短输出YES，否则输出NO。
思路
这就是个带权值的有向图，问将一条边反向后能不能缩短路径，很明显反向后如果存在最短边那肯定是经过那条被反向的边，直接对比dis1[n]和disn[u]+dis1[v]+w
代码
#include<bits/stdc++.h>
#include<string>
using namespace std;
typedef long long ll;
#define INF 1e8
const int mod = 1e9+7;
const int maxn = 2e5+5;
#define iss ios::sync_with_stdio(false)
inline ll read(){
ll s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
struct Edge{
int v,w,next;
}edge[maxn<<1];
int head1[maxn],headn[maxn],top;
ll dis1[maxn],disn[maxn];
priority_queue<pair<ll,int> > q;
bool f[maxn];
void add(int u,int v,int w,int head[]){//构造带权值的图
edge[top].v = v; edge[top].w = w;
edge[top].next = head[u]; head[u] = top++;
}
void dij(int st,ll dis[],int head[]){//Dij算法
fill( f , f + maxn , 0 );
dis[st]=0;
q.push(make_pair(0,st));
while(q.size()){
int u=q.top().second; q.pop();
if(f[u]) continue;
f[u]=1;
for(int i = head[u];i != -1;i = edge[i].next){
int v = edge[i].v,w=edge[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(make_pair(-dis[v],v));
}
}
}
}
int U[maxn],V[maxn],W[maxn];
int n;
bool check(int id){
int u=U[id],v=V[id],w=W[id];
if(dis1[n]<=disn[u]+dis1[v]+w) return false;
return true;
}
int main(){
memset(dis1,0x3f,sizeof(dis1));
memset(disn,0x3f,sizeof(disn));
int m;
cin>>n>>m;
fill(head1 ,head1+maxn , -1);
fill(headn , headn+maxn , -1);
top=0;
for(int i = 1;i <= m; ++i){
cin>>U[i]>>V[i]>>W[i];
add(U[i],V[i],W[i],head1);
add(V[i],U[i],W[i],headn);
}
dij(1,dis1,head1);
dij(n,disn,headn);
int q,x;
cin>>q;
while(q--){
cin>>x;
if(check(x)) puts("YES");
else puts("NO");
}
}
京公网安备 11010502036488号