NC54692. Alice's Army
描述
It is said that there are many spirits in Lotus Land like to hang out in winter. Now the winter is revealing, and many spirits are playing tricks in Lotus Land. Reimu, who should have to deal with it, is lying at home, entrusting this matter to Marisa. Unfortunately, Marisa is suddenly ill, so she entrusts this matter to Alice. Since it's Marisa’s invitation, Alice will certainly not refuse. Therefore, she is considering how to get rid of these spirits.
Alice has many puppet soldiers. She divides them into m armies based on their weapons. Each army has the same kind of weapon. There are three kinds of weapons: sword, shield and bow (respectively represented by S, D and B). Each army has two attribute values, which respectively represents the power and durability of the army. After investigation, Alice found that there are n spirits in total,each of which had its own power and weapon. The three kinds of weapons restrict each other (Sword restricts shield, shield restricts bow and bow restricts sword). When a weapon is restricted, the power of this party will be reduced by fifty percent during the battle.
For convenience, Alice wants to defeat them one by one, that is, if she wants to attack the kth sprite, he must defeat the (k-1)th sprite (k>1). If the power of Alice 's army is ai and the sprite’s power is bi, Alice 's army can win the battle only when ai ≥ bi. Each battle will consume one durability of the army. When the durability drops to 0 or Alice fails a battle, she must return to rectify and remake those soldiers (See the example below). Assume that Alice can only lead exactly one army to fight at a time and after each battle, Alice will repair her puppet soldiers immediately. The problem is, how many times does Alice have to return at least?
输入描述
The first line contains two integers n,m(1≤n,m≤1000). The next n lines, each line contains one integer bi and a character (1≤bi≤109), respectively represents the power and weapon of each sprite. Then, following m lines, each line contains two integers ai, di and a character (1≤ai≤109,1≤di≤n), respectively represents the power, the durability and the weapon of each army.
输出描述
If Alice can defeat all the sprites, print the minimum times she needs to return.
Otherwise print “ManShenChuangYi” in a single line.
示例1
输入:
5 2 4 S 7 S 99 S 10 B 1 S 10 4 S 100 1 S
输出:
4
说明:
In the first case, Alice can lead the first army to defeat two sprites at a time. But she can not defeat the third sprite. So, she needs to go back and lead the second army to defeat the third sprite. However, the second army’s durability turns to 0 so she must go back to remake them. The fourth sprite's bow restricts the first army’s sword,10*0.5=5.0<10, so she needs to lead the second army to defeat the fourth sprite.示例2
输入:
2 2 9 S 260817 D 999 1 B 9 2 D
输出:
ManShenChuangYi
说明:
In the second case, there is no army which can defeat the second sprite.示例3
输入:
5 2 4 S 17 D 99 B 5 S 1 B 10 3 S 50 1 D
输出:
3
说明:
In the third case, the first army can defeat the 1st 2nd 4th and 5th sprites. The second army can defeat all the sprites.
C++14(g++5.4) 解法, 执行用时: 27ms, 内存消耗: 4460K, 提交时间: 2020-01-11 16:44:33
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<cmath>
#define ll long long
using namespace std;
struct anm
{
int b;
char p;
}x[1010];
struct arm
{
int a,h;
char p;
}y[1010];
bool ke(char a,char b)
{
if(a=='S'&&b=='B') return 1;
if(a=='D'&&b=='S') return 1;
if(a=='B'&&b=='D') return 1;
return 0;
}
bool win(arm u,anm v)
{
if(ke(u.p,v.p)) return u.a>=v.b*2;
if(ke(v.p,u.p)) return u.a*2>=v.b;
return u.a>=v.b;
}
int n,m;
int dp[1010][1010];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
cin>>x[i].b>>x[i].p;
for(int i=1;i<=m;i++)
cin>>y[i].a>>y[i].h>>y[i].p;
for(int i=1;i<=m;i++)
for(int j=n;j>=1;j--)
{
if(win(y[i],x[j]))
dp[i][j]=min(dp[i][j+1]+1,y[i].h);
}
int ans=0;
int ad=1;
bool fd=1;
while(ad<=n)
{
int mx=0;
for(int i=1;i<=m;i++)
mx=max(mx,dp[i][ad]);
if(mx==0)
{
fd=0;
break;
}
ans++;
ad+=mx;
}
if(fd) printf("%d",ans);
else printf("ManShenChuangYi");
}
C++(clang++ 11.0.1) 解法, 执行用时: 13ms, 内存消耗: 432K, 提交时间: 2023-01-30 16:26:56
#include<bits/stdc++.h>
using namespace std;
struct kl
{
int p,d;
char w;
}b[1005];
struct bo
{
int p;
char w;
}a[1005];
int now,n,m,cnt;
bool Ch(int x,int y)
{
int t1=a[x].p,t2=b[y].p;
if(a[x].w=='S'&&b[y].w=='D') t1*=2;
if(a[x].w=='D'&&b[y].w=='B') t1*=2;
if(a[x].w=='B'&&b[y].w=='S') t1*=2;
if(a[x].w=='S'&&b[y].w=='B') t2*=2;
if(a[x].w=='D'&&b[y].w=='S') t2*=2;
if(a[x].w=='B'&&b[y].w=='D') t2*=2;
return t1<=t2;
}
int Fi(int x)
{
for(int i=now;i<=min(n-1,now+b[x].d-1);i++)
if(!Ch(i,x)) return i-now;
return min(n-now,b[x].d);
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i].p>>a[i].w;
for(int i=0;i<m;i++)
cin>>b[i].p>>b[i].d>>b[i].w;
now=0;
while(now<n)
{
int maxx=0;
for(int i=0;i<m;i++)
maxx=max(maxx,Fi(i));
if(!maxx) return printf("ManShenChuangYi\n"),0;
cnt++;
now+=maxx;
}
return printf("%d\n",cnt),0;
}