第一题 二分

题目意思：给定1 1 2 1 2 3 1 2 3 4..... 这样的序列求第n个位置数是哪一位 n范围直接到达 1e14

解题思路： 我们可以发现这是满足 1 2 3 的递增序列 数据范围这么大我们很容易可以想到使用二分
接着就是我们二分的是在哪一个数的时候我这个n在下一个序列里面(边界) 前面数的个数就是(1+n)*n/2
时间复杂度log(n)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define enl "\n"
const int N = 1000010,mod=1e9+7;
int n;
void solve(){
    cin>>n;
    auto check = [&](int x){
        return (x+1)*x/2<n;// 注意不能取等于我们要找的是前一整个位置
    };
    int l=0,r=1e9;
    while(l<r){
        int mid=l+r+1>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<n-(1+l)*l/2<<endl;
    return ;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    solve();
}

解题思路二：我们可以直接使用递减的方式来找到答案当当前序列无法满足我的要求的时候采用递减的方法求值
时间复杂度是sqrt(n)

void solve(){
    cin>>n;
    int i;
    for(i=1;i<n;i++) n-=i;
    cout<<i<<endl;
}

第二题 简单模拟 scanf 格式化读入

题目意思：给定电子表类型时间，求过了a分钟之后电子表时间
解题思路：使用scanf 格式化读入 取模以及注意进位即可
时间复杂度 1

#include <bits/stdc++.h>
using namespace std;
#define enl "\n"
const int N = 1000010,mod=1e9+7;

int h,m;
int a;
void solve(){
    scanf("%0d:%0d",&h,&m);
    cin>>a;
    int hh=a/60,mm=a%60;
    m=m+mm;
    h+= m >= 60;
    m%=60;
    h=(h+hh)%24;
    printf("%02d:%02d",h,m);
    return ;
}
signed main(){
    solve();
}

第三题 双指针 or dp

题目意思：对于给定序列多次询问在[l,r]中是否由与x不同的数有的话随意输出一个，否则-1

解题思路：首先不要想的太复杂往线段树啥的取思考，这又是一个区间问题，我们思考双指针
是否可以得到答案,一个区间是否是由不一样的我们就看这个区间是不是所有数都是x，就可以了
这启发我们把连续相等的数合并在一起并存下来其左右端点，给定查询的时候假设这个区间被
包含在一个区间里面我们就看是否都是x，假设不是被包含，那么就有解用左右端点来求即可
，我们如何判断是否被包含了?可以给每一个数所在的区间打上标记就可以了

时间复杂度o(n)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define enl "\n"
const int N = 1000010,mod=1e9+7;
int n,m;
int a[N];
int id[N];
int idx;
map<int,pair<int,int>> mp;
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        ++idx;//区间标记
        int j=i;
        while(j<=n&&a[j]==a[i]){
            j++;
        }
        j--;
        for(int k=i;k<=j;k++){
            id[k]=idx;
        }
        mp[idx]={i,j};// 区间左右端点
        i=j;
    }

    while(m--){
        int l,r,x; cin>>l>>r>>x;
        auto [_,rr]=mp[id[l]];
        if(rr>=r){// 都被包含了
            if(a[l]==x) cout<<-1<<endl;
            else cout<<l<<endl;
        }
        else{// 起码有两个数
            if(a[l]==x) cout<<rr+1<<endl;
            else cout<<l<<endl;
        }
    }
    return ;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    solve();
}

解题思路二：我们要考虑的是每一个数可以在连续相等的时候衍伸到的最远的右端点，那么是否可以从
后面来进行每一位相等的位置信息传递呢？我们可以考虑使用dp来从后面维护到前面相等的数的数量

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define enl "\n"
const int N = 1000010,mod=1e9+7;
int n,m;
int dp[N];
int a[N];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--){
        if(a[i]==a[i+1]) dp[i]=dp[i+1]+1;
        else dp[i]=1;
    }
    while(m--){
        int l,r,x; cin>>l>>r>>x;
        if(l+dp[l]-1>=r){
            if(a[l]==x) cout<<-1<<endl;
            else cout<<l<<endl;
        }
        else{
            if(a[l]==x) cout<<l+dp[l]<<endl;
            else cout<<l<<endl;
        }
    }

    return ;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    solve();
}

第四题 构造

题目意思：给定一个数字n对1-n中每一个数出现2次构造此序列满足 (1-n)Sn= (n-i)*|di+i-n| 其中di = |xi -yi|相等数的位置差

解题思路：1.首先我们无法满足经过推式子可以发现无法进行合并操作
2.我们通过模拟样例发现答案式0
3.启发我们是不是对于所有的数都可以出现答案是0的情况
4.开始手动模拟比如数字4
1 3 3 1 2 4 4 2 可以满足要求也就是要di+i-n=0
也就是di=n-i 每一个数要放在距离自己这么远的位置上
我们对于第一个位置填1 那么第4 个位置就是填1
我们看第二个位置填2 是没有对应位置的 因为他的di和1的di差值为1刚好就在对面1的位置要填2
我们可以知道当这个数是3的时候是满足要求的接着我们可以思考得到1 3 5 7.... 奇数排列在一起的
这个想法那么偶数排在一起也就是理所应当因为每一次都是位置间隔-2
对于最后一个数他的位置间隔是0那么我们把所有数都填上之后如果还有没填的就填上他就好

// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define int long long 
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)// c++ 保留小数
#define int long long 
typedef long long LL;
typedef pair<int, int> PII;
const int N=1000010,M=1010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
map<int,int> mp;
int t,n,m;

void solve(){
    int n;cin>>n;
    vector<int> a(n+1),b(n+1);
    for(int i=1,p=1;i<=n;i+=2,p++){
            a[p]=i; a[p+n-i]=i;
    }

    for(int i=2,p=1;i<=n;i+=2,p++){
            b[p]=i;b[p+n-i]=i;
    }
    for(int i=1;i<=n;++i){
        if(!a[i]) a[i]=n;
        cout<<a[i]<<' ';
    }
    for(int i=1;i<=n;++i){
        if(!b[i]) b[i]=n;
        cout<<b[i]<<' ';
    }

}
signed main ()
{
    ios// 不能有printf puts scanf
    solve();
}

第五题 dfs 树的深度

题目意思：每一个叶节点都有一只蚂蚁目标都是根节点1 根节点上可以站多只蚂蚁 其他的不可以求一次1s求最短时间
解题思路：首先我们不看1 那么就是一个森林结构每一个到顶的时间计算，我们可以处理出来每一个叶节点的深度
明显的最低的优先到最上面，那么下一个是一定要在上一个1s之后的，那么答案就明显的出来了对于每一个都求一次最长时间就好

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define enl "\n"
const int N = 1000010,mod=1e9+7;
vector<int> g[N];
int n;
vector<int> res;
int depth[N];

void dfs(int u,int fa){
    depth[u]=depth[fa]+1;
    for(auto&v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
    }
    if(g[u].size()==1)  res.push_back(depth[u]);
}
void solve(){
    cin>>n;
    n--;
    while(n--){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int ans=0;
    depth[1]=-1;//先不看1 
    for(auto&v:g[1]){
        res.clear();
        dfs(v,1);
        sort(res.begin(),res.end());
        for(int i=1;i<res.size();i++){
            res[i]=max(res[i],res[i-1]+1);
        }
        ans=max(ans,res.back());// 大家都一个一个到头的时间
    }
    cout<<ans+1<<endl;// 最后一步直接到1

    return ;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    solve();
}