---

layout: post

title: Codeforces Round 547 (Div. 3)

author: "luowentaoaa"

catalog: true

tags:

mathjax: true

- codeforces

---

（数学）

思路

首先分为情况

如果在第一轮内就打死

或者如果一整轮的伤害大于等于0那一轮相当于白费

如果小于0那就说明肯定可以把怪物打死

所以我们就枚举在第K论之后的哪一回合打死即可

#include
    
     using namespace std;const int maxn=2e5+50;typedef long long ll;ll H,n;ll d[maxn];ll mx=2e18+50;ll s[maxn];int main(){    std::ios::sync_with_stdio(false);    cin>>H>>n;    ll sum=0;    for(ll i=1;i<=n;i++)cin>>d[i],sum+=d[i],s[i]=s[i-1]+d[i];    for(ll i=1;i<=n;i++){        if(-s[i]>=H)mx=min(mx,i);    }    if(sum<0){        for(ll i=1;i<=n;i++){            ll now=sum+s[i];            now=-now;            //cout<<"i="<
     <<" now="<
      
       <
       
        =H)mx=min(mx,i+n);            else{                ll ned=-sum;                ll HH=H;                HH-=now;                ll time=HH/ned;                if(HH%ned)time++;                mx=min(mx,time*n+i+n);            }        }    }    if(mx==2e18+50)cout<<-1<
       
      
    

(贪心)

思路

首先枚举右端点 同时枚举左端点如果对于这一区间的权值保存的右端点比左端点还大那就加入他，同时更新答案

#include
    
     using namespace std;const int maxn=2e5+50;typedef long long ll;map
     
      
        >mp;///区间和，次数，最后一次右边界int sum[1550],a[1550];vector
       
        G;struct node{    int num;    int R;    vector
        
         
           >ve;}my[1500*1500/2+50];int id(int x){ return lower_bound(G.begin(),G.end(),x)-G.begin();}int main(){ std::ios::sync_with_stdio(false); int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i]; for(int i=1;i<=n;i++){ int sum=0; for(int j=i;j<=n;j++){ sum+=a[j]; G.push_back(sum); } } sort(G.begin(),G.end()); G.erase(unique(G.begin(),G.end()),G.end()); for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ int s=sum[i]-sum[j-1]; s=id(s); if(j>my[s].R){ my[s].R=i; my[s].num++; my[s].ve.push_back({j,i}); } } } int ans=0,p; for(int i=0;i
          
           ans){ ans=my[i].num; p=i; } } cout<
           
            <
           
          
         
        
       
      
     
    

(树)

思路

首先答案肯定是第k+1大的度数

然后就是构造这个树了，我们需要一个可以让颜色不重复的方案，那我们就直接bfs下去就行

#include
    
     using namespace std;typedef long long ll;const int maxn=2e5+50;int n,k;#define bug cout<<"he"<