签到题
1
2
3
4
5
6
7
|
int a,b;
int main()
{
cin>>a>>b;
cout<<ceil((double)a/(double)b)<<endl;
return 0;
}
|
签到+1
1
2
3
4
5
6
7
8
9
10
11
12
13
|
int a,n,sum;
int main()
{
cin>>a>>n;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
sum+=x;
}
if(sum>=a) puts("Yes");
else puts("No");
return 0;
}
|
签到+2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int n,k;
int a[maxn];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) read(a[i]);
sort(a+1,a+n+1);
if(k>=n) puts("0");
else
{
ll sum=0;
for(int i=1;i<=n-k;i++) sum+=a[i];
cout<<sum<<endl;
}
return 0;
}
|
一个怪物有$n$点血量，假如血量为$0$死亡，假如怪物血量为$1$攻击一次直接死亡，否则会分裂为两个怪物血量都为$\lfloor \frac{n}{2}\rfloor$，问至少多少次能将怪物全杀死
其实就是一个递归树，每一层都是上一层的一半，只要找到比$n$小的最大的$2^x$，答案就是递归树求和为$2^{x+1}-1$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
ll n;
int main()
{
cin>>n;
ll x=1,i=0;
while(x<=n)
{
i++;
x=(1ll<<i);
}
i--;
cout<<(1ll<<(i+1))-1<<endl;
return 0;
}
|
一个怪物有$H$点血量，假如血量小于等于$0$死亡，勇士有$n$种攻击方式，每种方式产生$A_i$的攻击（每种攻击可以使用任意次），会消耗$B_i$的力量，请问至少消耗多少力量能让怪物死亡
完全背包的变形，总体积看起来不确定，不过我们可以分析一下，设所有攻击方式中最耗体力的值为$maxx$，那么背包体积为$H+maxx$即可，因为再插入显然会比原来更多，所以这是最大的可能的情况，然后跑一个完全背包即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
const int maxn=1050;
const int maxm=20000010;
int h,n,v[maxn],w[maxn],f[maxm],maxx;
int main()
{
cin>>h>>n;
memset(f,0x3f,sizeof(f));
f[0]=0;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i],maxx=max(v[i],maxx);
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=h+maxx;j++)
f[j]=min(f[j],f[j-v[i]]+w[i]);
}
int ans=inf;
for(int i=h;i<=h+maxx;i++) ans=min(ans,f[i]);
cout<<ans<<endl;
return 0;
}
|
有$n$个怪物，每个怪物的坐标为$X_i$，血量为$H_i$，在$X$处施展一次攻击会对$X-d$到$X+d$的左边产生$A$的攻击，怪物血量小于等于$0$死亡，求至少攻击多少次所有怪物都能死亡
这是一个贪心题，一开始可能无从下手，不妨先排序一下，首先攻击的顺序肯定是不重要的，而最左边的点假如要被消灭的话一定会被攻击$\lfloor \frac{H_i+A-1}{A} \rfloor$次，把攻击的血量累计到总伤害，然后后面$2\cdot d$的距离都会收到影响，我们需要知道最近的不受影响的点，这可以二分一下，距离大于$2\cdot d$的最小的点，然后可以运用差分的思想建一个数组，把这个坐标的值加扣的血量，每次到一个点我们的总伤害先减去差分数组，这样就能维护当前被影响的血量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
const int maxn=200050;
ll n,d,t,c[maxn];
PLL a[maxn];
int main()
{
cin>>n>>d>>t;
for(int i=1;i<=n;i++)
{
read(a[i].first);read(a[i].second);
}
sort(a+1,a+n+1);
ll i=1;
ll temp=0,ans=0;
d*=2;
while(i<=n)
{
temp-=c[i];
a[i].second-=temp;
if(a[i].second>0)
{
ll tt=(a[i].second+t-1)/t;
ans+=tt;
temp+=t*tt;
int l=0,r=n+1;
while(l<r)
{
int mid=l+r>>1;
if(a[mid].first>a[i].first+d) r=mid;
else l=mid+1;
}
if(l!=n+1) c[l]+=t*tt;
}
i++;
}
cout<<ans<<endl;
return 0;
}
|