E1. Nene vs. Monsters (Easy Version)
题意:
有n个怪物,能量等级为\(a_i\),现在可以使用一种法术,使第1个怪物攻击第2个怪物,第2个怪物攻击第3个怪物……第n个怪物攻击第1个怪物,当能量等级为x的怪物攻击能量等级为y的怪物时,怪物y->max(y-x,0),在经过\(10^{100}\)攻击后,剩下几个怪物能量等级大于0,升序输出他们的下标
思路:
假设三个连续的数x,y,z,在经过1000次法术后,z必然变为0。这点可以证明,若z不为0,当x为1,y为1001时,z最小,通过程序可以得到z最小为500500,因为\(0 \le a_i \le 2 \cdot 10^5\),所以z再经过1000次法术后必然为0。则数组中最多只有两个连续正整数,0xy0,那么这个y最后也会变成0.
证明程序:
void solve(){
ll ans=0;
for(int i=1000;i>=1;i--){
ans+=i;
}
cout<<ans<<endl;
}
代码:
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=1000;i++){
for(int j=2;j<=n;j++){
a[j]=max((a[j]-a[j-1]),0);
}
a[1]=max(0,a[1]-a[n]);
}
for(int i=1;i<n;i++){
if(a[i]>0){
if(a[i+1]>0){
a[i+1]=0;
}
i++;
}
}
if(a[n]>0){
if(a[1]>0){
a[1]=0;
}
}
vector<int > ans;
for(int i=1;i<=n;i++){
if(a[i]>0){
ans.push_back(i);
}
}
cout<<ans.size()<<endl;
for(auto t: ans){
cout<<t<<" ";
}
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
E2. Nene vs. Monsters (Hard Version)
思路:
假设三个连续的数x,y,z,w,在经过2000次法术后,w必然变为0。这点可以证明,若w不为0,当x为1,y为2001时,z为\(\sum_{i=1}^{2001} i\)时w最小,通过程序可以得到w最小为1335334000,因为\(0 \le a_i \le 10^9\),所以w再经过2000次法术后必然为0。则数组中最多只有三个连续正整数,0xyz0,这个y最后会变成0,但z是否会变成0需要判断,每次法术,y需要先减去x,z再减去y,可以知道这是一个等差数列,求和公式(y-x)/xx+((y-x)/x)((y-x)/x-1)/2x+((y-x)/x+1)(y%x),若z小于等于这个结果,则z会变为0,反之不为0
证明程序:
void solve(){
ll ans=0;
for(int i=2000;i>=1;i--){
for(int j=1;j<=i;j++){
ans+=j;
}
}
cout<<ans<<endl;
}
代码:
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=2000;i++){
for(int j=2;j<=n;j++){
a[j]=max((a[j]-a[j-1]),0);
}
a[1]=max(0,a[1]-a[n]);
}
for(int i=1;i<=n;i++){
if(a[i]==0){
if(a[(i+1-1)%n+1]>0&&a[(i+2-1)%n+1]>0){
if(a[(i+3-1)%n+1]>0){
ll x=a[(i+1-1)%n+1];
ll y=a[(i+2-1)%n+1];
ll t=0;
if(y>x){
t=(y-x)/x*x+((y-x)/x)*((y-x)/x-1)/2*x+((y-x)/x+1)*(y%x);
}
if((i+2-1)%n+1==1){
t+=y;
}
if(a[(i+3-1)%n+1]<=t){
a[(i+3-1)%n+1]=0;
}
a[(i+2-1)%n+1]=0;
i=i+3;
}else{
a[(i+2-1)%n+1]=0;
i=i+2;
}
}
}
}
vector<int > ans;
for(int i=1;i<=n;i++){
if(a[i]>0){
ans.push_back(i);
}
}
cout<<ans.size()<<endl;
for(auto t: ans){
cout<<t<<" ";
}
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
先写这么多,剩下的以后再补(
标签:int,ll,Codeforces,法术,939,solve,怪物,ans,Div From: https://www.cnblogs.com/beater/p/18158726