首页 > 其他分享 >Codeforces Round 939 (Div. 2) E1-E2

Codeforces Round 939 (Div. 2) E1-E2

时间:2024-04-25 22:12:42浏览次数:18  
标签:int ll Codeforces 法术 939 solve 怪物 ans Div

Codeforces Round 939 (Div. 2)

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

相关文章

  • Codeforces Round 892 (Div. 2) E
    E的话一眼dp,然后观察一下方程,\(f[i][j]表示前i个位置已经选了长度为j的区间,且第i个位置已经被选上时,能够获得的最大值\)\[f[i][j]=\displaystyle\max_{1\leqk\leqmin(i,j)}(f[i-k][j-k]+calc(i-k+1,j))\\calc(l,r)=|b_l-a_r|+|b_r-a_l|\]这样的dp是\(O(n^2k)\)的,而\(1\leqk......
  • cf 1601B Frog Traveler Codeforces Round 751 (Div. 1)
     Problem-1601B-Codeforces BFS然后每次上升可以的范围是一个区间,然后每次都遍历这个区间的所有点,那么超时。用set等方式,合并这些区间,之前没遍历过的范围才更新(加入BFS需要遍历的队列里)。但是区间的更新特别容易写错…… 我的代码和造数据1/**2记录两个vi......
  • Codeforces Round 940 (Div. 2) and CodeCraft-23 题解
    CodeforcesRound940(Div.2)andCodeCraft-23题解题目链接A.Stickogon贪心#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#definepbpush_back#defineall(u)u.begin(),u.end()#defineendl'\n'#definedebu......
  • Educational Codeforces Round 164 (Rated for Div. 2)
    A.PaintingtheRibbon题意:n个物体,m个颜色,alice要给每个物体任意涂一个颜色。bob可以给k个物体涂色,问alice能否阻止bob让所有的物体颜色都相同。思路:思维题。如果m=1,那么无解。如果m>1,那么bob如果想要染成同一个颜色,alice可以让bob需要染色的数量最多。如果染色的数量最多,那......
  • Codeforces Round 906 (Div. 2) E1
    时隔了不知道多久的补题。两个月吧,这是可是寒假的比赛。但是补题的时候还是遇到了很多问题。很重要的有一些地方能够简化,一些条件没有充分的利用上,导致了我很多地方考虑的太复杂。这些能够简化的地方全部利用上我觉得才算是写出来了这道题目,否则这题会复杂到我赛时写不完,而且特......
  • CodeForces 115D Unambiguous Arithmetic Expression
    洛谷传送门CF传送门直接区间dp可以做到\(O(n^3)\),卡常可过,在此就不赘述了。为了方便先把连续的数字缩成一段。我们考虑直接从前往后扫,扫的过程中dp。设\(f_{i,j}\)为考虑了\([1,i]\),还有\(j\)个没配对的左括号的方案数。但是我们发现我们不知道一个数字前要添加几......
  • CRound927__Div3__C
    这道题涉及到两个部分,先是逆向思维,正着做一定会无比困难,而倒过来想就会好做,也比较难想到逆向思维,见识又少了,倒着思考就得先找到最后一个移除的元素include<bits/stdc++.h>usingnamespacestd;defineforn(i,n)for(inti=0;i<int(n);i++)intmain(){intt;cin......
  • 给定两个数x和y(长度相等),让它们可以交换各个位上的数字(位对应交换),求让两数乘积最大的
    如题,给出x=73,y=31,如何让两数乘积最大?位数定义:各个位上的数字例73,位数有7,3当前,只有一种交换策略,x=71,y=33,发现交换以后有:x+y=x'+y',如果抽象成求最大面积就好办了,可能一下想不到,还得多积累经验,不是你不知道是你想不到是你见得少,没见识...当是正方形的时候面积最大小学......
  • Codeforces Round 940 (Div. 2) and CodeCraft-23
    A.Stickogon#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;usingi64=longlong;#defineinti64usingvi=vector<int>;constintN=3e5,mod=1e9+7;voidsolve(){ vicnt(101); intn; cin>>n; for(i......
  • Codeforces Round 892 (Div. 2) 复盘
    A没啥好说的。B也是,很简单的贪心。但是AB都因为读题导致的理解误差wa了一发。哎,读题读错,只能说英语还得练。C,赛时没做出来,后面的也是。这个题目其实思路已经有了,cf的这种题,还放在C题,那就是很明显那种能打标看出规律的东西。就算知道了是打表能看出来的,我懒得写暴力,所以就一直......