赢的次数

思路:
偶数：除2
奇数: 除2+1

AC Code：

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
       int n;cin>>n;
       if(n%2==0)cout<<n/2<<endl;
       else
       {
               cout<<n/2<<' '<<n/2+1<<endl;
       }
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        solve();
        return 0;
}

子段和

思路:
首先将相同的数去重.
去重后.
如果 Size$\geq 3$显然相反数永远可以不相邻.
如果 Size$= 2$ 判断剩下的两个数是否是相反数.
特判下只有$0$,以及去重后长度为$1$的情况即可.

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
       int n;cin>>n;
       vector<int>a(n+1);
       bool ok=true;
       for(int i=1;i<=n;i++)
       {
               cin>>a[i];
               if(a[i]==0)
               {
                  ok=false;        
               } 
       }
       if(!ok)
       {
               cout<<"NO"<<endl;
               return;
       }
       sort(a.begin()+1,a.end());
       n=unique(a.begin()+1,a.end())-a.begin()-1;

       if(n>=3||n==1)cout<<"YES"<<endl;
       else if(a[1]+a[2]!=0)cout<<"YES"<<endl;
       else cout<<"NO"<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        solve();
        return 0;
}

英语作文

思路:
单独的把所有相同的单词,存放在一个集合里.
对于每一个集合.由于求的是距离$\leq k$,因此实际上,相当于找相同单词的集合中,两个下标只差$\leq k$,的右边界.
二分寻找一下,右边界即可.

AC Code：

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
vector<int>st[N];
map<string,int>mp;
map<string,bool>te;
int n,m;
void solve()
{
       cin>>n>>m;
       int res=0;
       for(int i=1;i<=n;i++)
       {
               string s;cin>>s;
               if(!te[s])mp[s]=++res,st[res].push_back(i),te[s]=true;
               else st[mp[s]].push_back(i);
       }
       ll ans=0;
       for(int i=1;i<=res;i++)
        if(st[i].size()>=2)
        {
                sort(st[i].begin(),st[i].end());//单独排序 
                for(int k=0;k<st[i].size();k++)
                {
                        int c1=st[i][k];
                        int l=k+1,r=st[i].size()-1;
                        while(l<r)
                        {
                                int mid=l+r+1>>1;
                                if(st[i][mid]-c1-1<=m)l=mid;
                                else r=mid-1;//二分出右边界 
                        }
                        if(st[i][r]-c1-1<=m&&r!=k)ans+=r-k;
                }
        }
        cout<<ans<<endl;
        return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    //    freopen("test.in","r",stdin);
        solve();
        return 0;
}

生活在树上

思路:
首先 最开始想从每一个点,DFS一遍.但是这样就相当于从每一个点出发跑一整张图.
实际时间复杂度就会是$O(n*m)$.
但是可以发现.这题的限制非常明显.对于所有$w\geq 2$的边而言.其只会对于边的两个端点贡献.
对于$w=1$的边而言,有一些特别.
不仅会对,边的端点$(l,r)$贡献.还会对于所有和$l,r$相连的$w=1$的点也有贡献.
因此可以考虑在图建立完以后,依次遍历每一条边.
记端点为$(l,r)$ 记$cnt$当前点连接到的所有边权为1的边
初始化一下.每一个点自己也是一个答案.因此最初所有$ans$为1
$w=1$ $ans_l=cnt_r + 1$. $ans_r=cnt_l + 1$
$w\geq 2$ $ans_l + 1,ans_r + 1$

AC Code；

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
struct edge{
        int l,r,w;
};
int ans[N];
int cnt[N];
void solve()
{
       int n;cin>>n;
       vector<edge>a;
       for(int i=2;i<=n;i++)
       {
               int f,w;
               cin>>f>>w;
               a.push_back({i,f,w});
               if(w==1)cnt[i]++,cnt[f]++;
       }//建图 
       for(int i=1;i<=n;i++)ans[i]=1;
       for(auto c:a)
       {//r 是父节点 
            if(c.w==2)ans[c.l]++,ans[c.r]++;
            else if(c.w==1)
            {
                     ans[c.r]+=cnt[c.l];
                     ans[c.l]+=cnt[c.r];  
            } 
       }
       for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        solve();
        return 0;
}

对决

思路:
记$x$为当前点.
首先必须保证,选手$x$参赛场次$\geq k$.
当满足,序列中$\leq x$的数$cnt \geq k$,只需要保证,最后一个和$x$对决的人严格小于等于$k$即可.
不过这一步注意.

此下两种情况:$x$的比赛场次数.$\geq k-1$
Case 1:直接使用两种道具 使得 $\lfloor \frac {Max}{2} \rfloor \leq x * 2$
Case 2:此时无法满足.需要从 严格大于$x$的数中找一个数 $tmp$,其满足.

$$ tmp * 2 \geq Max $$

$$tmp \leq 2*x + 1$$

Case 3: 在不考虑,比$x$大的数.只差两场.

$tmp$ 必须满足 小于等于$2*x$的数至少有1个,且
$$\lfloor \frac {Max}{2} \rfloor \geq x$$

AC Code:

#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII; 
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll  llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
       int n,k;
       cin>>n>>k;
       vector<ll>a(n+1);
       vector<ll>b(n+1);
       for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
       sort(a.begin()+1,a.end());
       ll Max=a[n];
       vector<int>ans(n+1,0);
       for(int i=1;i<=n;i++)
       {  
           int pos=--upper_bound(a.begin()+1,a.end(),b[i])-a.begin(); 
           if(pos-1>=k-1)
           {
                        int tmp=*--upper_bound(a.begin()+1,a.end(),2*b[i]+1);   
                        if(Max/2<=b[i]*2)ans[i]=1;
                        else
                        {
                            int cnt=*--upper_bound(a.begin(),a.end(),2*b[i]+1);
                            if(tmp*2>=Max)ans[i]=1;
                            else ans[i]=0;
                        }
           }else
           {
                   int res1=--upper_bound(a.begin()+1,a.end(),2*b[i])-a.begin();
                   if(k-(pos-1)==2&&Max/2<=b[i]&&res1-pos>=1)ans[i]=1;
           }
       }
       for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
       cout<<endl;
       return ;
}
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
      //  freopen("test.in","r",stdin);
        solve();
        return 0;
}