happy question round1 题解

Simon439747 · 2026-06-13 09:26:19 · 个人记录

比赛链接

我是一部分题的出题人，写个题解。

T1 ~ T3 由作者编写。

T4 由 Kai29 编写

T5~T6 也为作者编写。 :::::info[T1]

T1 超过他

我出的一道题，复杂的分支结构，适合签到这个位置。

::::info[思路] 思路为：先判断 x>y，若满足。输出 2；

在判断 m>y ，若满足，输出 1；

然后判断 m=y \lor x=y，若满足输出 0；

反之输出 1；

O(1)

::::

::::success[AC Code]

//警示后人：十年OI一场空，不开long long见祖宗
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using pll=pair<int,int>;
template<typename T>
inline void readinVector(vector<T>& vec,int l,int r){
    for(int i=l;i<=r;i++)cin>>vec[i];
}
template<typename T>
class matvec{
public:
    vector<vector<T> >mat;
    matvec(){}
    matvec(int n){
        mat.resize(n+1);
    }
    void rs(int n){
        mat.resize(n+1);
    }
    matvec(int n,int m){
        mat.resize(n+1,vector<int>(m+1));
    }
    vector<int>& operator[](int i){
        return mat[i];
    }
    void p_b(const vector<int>&vec){
         mat.push_back(vec);
    }
};
int T=1;
void solve(){
    int x,y,m;
    cin>>x>>y>>m;
    if(x>y)cout<<2<<endl;
    else if(m>y)cout<<1<<endl;
    else if(x==y||y==m)cout<<0<<endl;
    else cout<<1<<endl; 
}
signed main(){
//  freopen("xxx.in","r",stdin);
//  freopen("xxx.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//  cin>>T;
    while(T--)solve();
    return 0;
}

:::: ::::: :::::info[T2]

T2 拓展斐波那契数列

放在 T2 不过分吧~

::::info[思路] 思考一般的斐波那契数列

0& 1 \\ 1& 1 \end{vmatrix} \begin{vmatrix} F_{n-1}\\ F_{n} \end{vmatrix}=\begin{vmatrix} F_{n}\\ F_{n+1} \end{vmatrix}

扩展一维，有：

0& 1& 0 \\ 0& 0& 1 \\ 1& 1& 1 \end{vmatrix} \begin{vmatrix} F_{n-2}\\ F_{n-1}\\ F_{n} \end{vmatrix}=\begin{vmatrix} F_{n-1}\\ F_{n}\\ F_{n+1} \end{vmatrix}

明显，转移矩阵的最后一行全是 1，前面的 n-1 行中的第 i 行是第 n-i 位置是 1，其余为 0 的矩阵。所以有：

vector<vector<int> >base(k,vector<int>(k));
for(int i=0;i<k-1;i++){
  base[i][i+1]=1;
}
for(int i=0;i<k;i++){
  base[k-1][i]=1; 
}

来初始化的矩阵，再乘上一个列向量。

O(k^3\log (n-k))

:::: ::::success[AC Code]

//警示后人：十年OI一场空，不开long long见祖宗
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using pll=pair<int,int>;
template<typename T>
inline void readinVector(vector<T>& vec,int l,int r){
    for(int i=l;i<=r;i++)cin>>vec[i];
}
const int mod=1e9+7;
template<typename T>
class marix{
public:
    ll row,col;
    vector<vector<T> >m;
    marix():row(0),col(0){}
    ~marix(){}
    marix(ll x):row(x),col(x){
        m.resize(row,vector<T>(col,0));
        for(ll i=0;i<row;i++) m[i][i]=1;
    }
    marix(ll x,ll y):row(x),col(y){
        m.resize(row,vector<T>(col,0));
        for(ll i=0;i<min(x,y);i++) m[i][i]=1;
    }
    marix(const vector<vector<T> >&a){
        m=a;
        if(a.empty())row=col=0;
        else{
            row=a.size(); col=a[0].size();
            for(const vector<T>&i:a) if(i.size()!=col)throw invalid_argument("it`s not regularly!");
        }   
    }
    marix trans(){
        marix ret(col,row);
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                ret.m[j][i]=this->m[i][j];
            }
        }
        return ret;
    }
    marix operator+(const marix& other)const{
        if(this->row!=other.row||this->col!=other.col)throw invalid_argument("they can't add!");
        marix ret; ret.row=this->row; ret.col=this->col; ret.m=this->m;
        for(ll i=0;i<row;i++) for(ll j=0;j<col;j++) ret.m[i][j]+=other.m[i][j];
        return ret;
    }
    marix operator-(const marix& other)const{
        if(this->row!=other.row||this->col!=other.col)throw invalid_argument("they can't subtract!");
        marix ret; ret.row=this->row; ret.col=this->col; ret.m=this->m;
        for(ll i=0;i<row;i++) for(ll j=0;j<col;j++) ret.m[i][j]-=other.m[i][j];
        return ret;
    }
    marix operator*(const marix& other)const{
        if(this->col!=other.row)throw invalid_argument("they can't multiply!");
        marix ret; ret.row=this->row; ret.col=other.col; ret.m.resize(this->row,vector<T>(other.col,0));
        for(ll i=0;i<this->row;i++)
            for(ll k=0;k<this->col;k++){
                T aik=m[i][k]%mod;
                for(ll j=0;j<other.col;j++)ret.m[i][j]=(ret.m[i][j]+aik*other.m[k][j]%mod)%mod; 
            }
        return ret;
    }
    marix operator*(const T& o)const{
        marix ret(this->m);
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                ret.m[i][j]*=o;
            }
        }
        return ret;
    }
    void del(int y1,int y2,int x){
        T coe=m[y2][x]/m[y1][x];
        for(int i=0;i<col;i++)
            m[y2][i]-=coe*m[y1][i];
    }
    void GoshDel(){
        int n=row;
        for(int x=0;x<n;x++){
            int p=x;
            while(p<n&&abs(m[p][x])<1e-9)
                p++;
            if(p>=n)
                continue;
            swap(m[x],m[p]);
            T div=m[x][x];
            for(int i=x;i<col;i++)
                m[x][i]/=div;
            for(int i=0;i<n;i++){
                if(i!=x&&abs(m[i][x])>1e-9)
                    del(x,i,x);
            }
        }
    }
    T getDet()const{
        if(this->row!=this->col)throw invalid_argument("it hasn't det!");
        if(this->row==1)return (this->m[0][0]);
        T det=1;
        marix tmp=*this;
        tmp.GoshDel();
        for(int i=0;i<row;i++) det=det*tmp.m[i][i];
        return det;
    }
    friend ostream& operator<<(ostream& os, const marix<T>& mat) {
        for(ll i=0;i<mat.row;i++){
            for(ll j=0;j<mat.col;j++){
                os << mat.m[i][j];
                if(j!=mat.col-1)os << " ";
            } os << endl;
        }
        return os;
    }
    friend istream& operator>>(istream& is, marix<T>& mat) {
        is >> mat.row >> mat.col;
        mat.m.resize(mat.row,vector<T>(mat.col));
        for(ll i=0;i<mat.row;i++) for(ll j=0;j<mat.col;j++) is >> mat.m[i][j];
        return is;
    }
}; 

template<typename T>
marix<T> fpow(marix<T> base,ll times){
    marix<T> ret(base.row);
    while(times){
        if(times&1)ret=ret*base;
        base=base*base;
        times>>=1;
    }
    return ret;
} 

template<typename T>
T fpow(T base,ll times){
    T ret=1;
    while(times){
        if(times&1)ret=ret*base;
        base=base*base;
        times>>=1;
    }
    return ret;
} 
int T=1;
void solve(){
    int n,k;
    cin>>n>>k;
    vector<vector<int> >vec(k,vector<int>(1));
    vec[0][0]=1;
    vec[1][0]=1;
    for(int i=2;i<k;i++){
        vec[i][0]=2*vec[i-1][0]%mod;
    }
    marix<int>mat(vec);
    vector<vector<int> >base(k,vector<int>(k));
    for(int i=0;i<k-1;i++){
        base[i][i+1]=1;
    }
    for(int i=0;i<k;i++){
        base[k-1][i]=1; 
    }
    marix<int>bases(base);
    bases=fpow(bases,n-k);
    mat=bases*mat;
    cout<<mat.m[k-1][0]<<endl;
}
signed main(){
//  freopen("xxx.in","r",stdin);
//  freopen("xxx.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//  cin>>T;
    while(T--)solve();
    return 0;
}

:::: :::::

:::::info[T3]

T3我要开花

::::info[思路] 考虑DP

定义 dp_i 为到达 i 点的最大收益。

对于一个点 i，我们可以有

dp_i=\max_{u \in father}dp_u +a_i

但是枚举肯定没戏。因为 father=[l_i,r_i] 所以考虑维护区间最大值。

想到线段树。

这里采用动态开点线段树，个人觉得好写。

O(n\log n)

:::: ::::success[AC Code]

//警示后人：十年OI一场空，不开long long见祖宗
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using pll=pair<int,int>;
template<typename T>
inline void readinVector(vector<T>& vec,int l,int r){
    for(int i=l;i<=r;i++)cin>>vec[i];
}
template<typename T>
class matvec{
public:
    vector<vector<T> >mat;
    matvec(){}
    matvec(int n){
        mat.resize(n+1);
    }
    void rs(int n){
        mat.resize(n+1);
    }
    matvec(int n,int m){
        mat.resize(n+1,vector<T>(m+1));
    }
    vector<T>& operator[](int i){
        return mat[i];
    }
    void p_b(const vector<T>&vec){
         mat.push_back(vec);
    }
};
const int inf=1e18;
struct DynaSegTree {
    DynaSegTree* lc,*rc;
    int l,r;
    int v;
    DynaSegTree(int ll,int rr):l(ll),r(rr),v(-inf),lc(nullptr),rc(nullptr){}
    void modify(int pos,int val){
        if(l==r){
            v=val;
            return;
        } 
        int mid=l+r>>1;
        if(mid<pos){
            if(!rc)rc=new DynaSegTree(mid+1,r);
            rc->modify(pos,val);
        }else{
            if(!lc)lc=new DynaSegTree(l,mid);
            lc->modify(pos,val); 
        }
        int lv=(lc!=nullptr?lc->v:-inf);
        int rv=(rc!=nullptr?rc->v:-inf);
        v=max(lv,rv);
    }
    int query(int ll,int rr){
        if(rr<l||ll>r)return -inf;
        if(ll<=l&&r<=rr)return v;
        int res=-inf;
        if(lc)res=max(res,lc->query(ll,rr));
        if(rc)res=max(res,rc->query(ll,rr));
        return res;
    }
};
int T=1;
void solve(){
    int n;
    cin>>n;
    vector<int>a(n+1);
    readinVector(a,1,n);
    vector<int>dp(n+1);
    dp[1]=a[1];
    DynaSegTree *root=new DynaSegTree(1,n);
    root->modify(1,a[1]);
    for(int i=2;i<=n;i++){
        int l,r;
        cin>>l>>r;
        dp[i]=root->query(l,r)+a[i];
        root->modify(i,dp[i]);
    } 
    cout<<root->query(1,n)<<endl;
}
signed main(){
//  freopen("xxx.in","r",stdin);
//  freopen("xxx.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//  cin>>T;
    while(T--)solve();
    return 0;
}

:::: ::::: :::::info[T4]

T4 求根要求全

::::info[思路]

字符串解析
- 依次读取 a, b, c。
- 每个系数前可能带有 + 或 -，先确定符号。
- 然后尝试读入数字：若读到数字（包括 0），则返回带符号的该数字；若没有读到数字（说明系数为 \pm 1），返回符号本身。
- 关键：-0 必须被识别为 0，因此需要区分“是否读到了数字”而非仅判断 v 是否为 0。
解方程
- 若 a = 0，退化为一次方程 bx + c = 0，根为 \dfrac{-c}{b}（两个根相同）。
- 否则判别式 d = b^2 - 4ac：
排序与格式化
- 排序规则：先按虚部降序，若虚部之差小于 10^{-9} 则按实部降序。
- 格式化：
  - 实数（虚部绝对值小于 0.005）：调用保留两位小数的函数，并将 "-0.00" 替换为 "0.00"。
  - 复数：虚部系数为 \pm 1 时，分别输出 "i" 或 "-i"；否则输出系数和 "i"。再根据实部是否非负决定是否添加 "+"，最后拼接实部。

:::: ::::success[AC Code]

代码


#include <bits/stdc++.h>

using namespace std;

int G(const string* s, int* p) {

    int sign = 1;

    if ((*s)[*p] == '+' || (*s)[*p] == '-')

        sign = ((*s)[(*p)++] == '-') ? -1 : 1;

    int v = 0;

    bool has = false;

    while (*p < (int)s->size() && isdigit((*s)[*p])) {

        v = v * 10 + (*s)[(*p)++] - '0';

        has = true;

    }

    return has ? sign * v : sign;

}

string F(double x) {

    char buf[20];

    sprintf(buf, "%.2f", x);

    string res(buf);

    return res == "-0.00" ? "0.00" : res;

}

string R(complex<double> z) {

    double r = z.real(), i = z.imag();

    if (abs(i) < 0.005) return F(r);

    string is;

    if (abs(i - 1.0) < 0.005)      is = "i";

    else if (abs(i + 1.0) < 0.005) is = "-i";

    else                           is = F(i) + "i";

    return is + (r >= 0 ? "+" : "") + F(r);

}

int main() {

    string s;

    cin >> s;

    int p = 0;

    int a = G(&s, &p);

    if (s[p] == 'x') p++;

    if (s[p] == '^') p++;

    if (s[p] == '2') p++;

    int b = G(&s, &p);

    if (s[p] == 'x') p++;

    int c = G(&s, &p);

    complex<double> x1, x2;

    if (a == 0) {

        double root = -1.0 * c / b;

        x1 = x2 = {root, 0};

    } else {

        long long d = 1LL * b * b - 4LL * a * c;

        if (d >= 0) {

            double sd = sqrt((double)d);

            x1 = {(-b - sd) / (2.0 * a), 0};

            x2 = {(-b + sd) / (2.0 * a), 0};

        } else {

            double rp = -b / (2.0 * a);

            double ip = sqrt(-d) / (2.0 * a);

            x1 = {rp, ip};

            x2 = {rp, -ip};

        }

    }

    if (x1.imag() < x2.imag() ||

        (abs(x1.imag() - x2.imag()) < 1e-9 && x1.real() < x2.real()))

        swap(x1, x2);

    cout << R(x1) << " " << R(x2) << '\n';

    return 0;

}

:::: ::::: :::::info[T5]

T5 前缀

::::info[思路] 这题主要是 LCP+ST 表，难点其实就是 ST 表（~~好久没写了，所以这对我有点难，勿喷~~）。

LCP

指最长公共前缀。LCP 的解法提供两种：

1.朴素循环

直接遍历最短字符串，然后如果字符不一样就跳出即可。

代码如下：

int lcp(const string& s1,const string& s2){
    int i=0;
    for(;i<min(s1.size(),s2.size());){
        if(s1[i]==s2[i])i++;
        else break;
    }
    return i;
}

敲黑板，划重点。

这里要写成 const string& s，这样更快。

2.B 函数

借用下 KMP 中的 Border 函数，一般在代码中称之为 b。

他是干什么的呢？

求最长的子串使得其同时为字符串的前、后缀。

具体的参照 https://www.luogu.com.cn/problem/P3375 此题。

此时我们进行一下流程：

1.拼接。将两字符串短的在前，长的在后拼接，中间以 # 分隔。

2.求出 Border，设短的长度为 len_{s1}，则只需求到第 2len_{s1}+1 位即可。

此时，b_{2len_{s1}+1} 即为 LCP。

没写代码，请读者自行思考。

倍增 ST

见 https://www.luogu.com.cn/problem/P3865 。

我的见解：就是 DP。

我们这个基于二进制，于是要处理数组 log_2。

然后，建立数组 st_{i,j} 表示第 i 项往后延伸 2^j 项的区间最值。

所以有转移方程 st_{i,j}=\min(st_{i,j-1},st_{i+2^{j-1},j-1})。

初值嘛……

对于 st_{i,0},i\in[1,n-1],st_{i,0}=\operatorname{LCP}(strs_i,strs_{i+1})

对于 O(1) 的查询，我们用到如此式子，以覆盖到所有位置（log_2 r-l+1 会丢精度）：

min(st[l][len],st[r-(1<<len)+1][len])

PS:先要 r-1\to r

这样就完事啦！ :::: ::::success[AC Code]

//警示后人：十年OI一场空，不开long long见祖宗
#include <bits/stdc++.h>
using namespace std;
//#define int long long
using ll=long long;
using pll=pair<int,int>;
template<typename T>
inline void readinVector(vector<T>& vec,int l,int r){
    for(int i=l;i<=r;i++)cin>>vec[i];
}
template<typename T>
class matvec{
public:
    vector<vector<T> >mat;
    matvec(){}
    matvec(int n){
        mat.resize(n+1);
    }
    void rs(int n){
        mat.resize(n+1);
    }
    matvec(int n,int m){
        mat.resize(n+1,vector<T>(m+1));
    }
    matvec(int n,int m,T v){
        mat.resize(n+1,vector<T>(m+1,v));
    }
    vector<T>& operator[](int i){
        return mat[i];
    }
    void p_b(const vector<T>&vec){
         mat.push_back(vec);
    }
};
int lcp(const string& s1,const string& s2){
    int i=0;
    for(;i<min(s1.size(),s2.size());){
        if(s1[i]==s2[i])i++;
        else break;
    }
    return i;
}
int T=1;
void solve(){
    int n,q;
    cin>>n>>q;
    vector<string>strs(n+1);
    readinVector(strs,1,n);
    vector<int>log_2(n+1);
    log_2[1]=0;
    for(int i=2;i<=n;i++)log_2[i]=log_2[i/2]+1;
    matvec<int>st(n,log_2[n]);
    for(int i=1;i<n;i++)st[i][0]=lcp(strs[i],strs[i+1]);
    for(int j=1;j<=log_2[n];j++){
        for(int i=1;i+(1<<j)<=n;i++){
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        if(l==r){
            cout<<strs[l].size()<<endl;
            continue;
        }
        r--;
        int len=log_2[r-l+1];
        cout<<min(st[l][len],st[r-(1<<len)+1][len])<<endl;
    }
}
signed main(){
//  freopen("xxx.in","r",stdin);
//  freopen("xxx.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//  cin>>T;
    while(T--)solve();
    return 0;
}

:::: ::::: :::::info[T6]

T6 infty or only ONE

::::info[思路] 这是贝特朗悖论。

有人证明他是有无穷解的。

所以这题的 subtask1 就直接输出 yes 即可。

而最后有人用题目里的最后一个条件证明只有 0.5 才是正解。于是我们有代码。 :::: ::::success[AC Code]

//警示后人：十年OI一场空，不开long long见祖宗
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using pll=pair<int,int>;
template<typename T>
inline void readinVector(vector<T>& vec,int l,int r){
    for(int i=l;i<=r;i++)cin>>vec[i];
}
template<typename T>
class matvec{
public:
    vector<vector<T> >mat;
    matvec(){}
    matvec(int n){
        mat.resize(n+1);
    }
    void rs(int n){
        mat.resize(n+1);
    }
    matvec(int n,int m){
        mat.resize(n+1,vector<T>(m+1));
    }
    matvec(int n,int m,T v){
        mat.resize(n+1,vector<T>(m+1,v));
    }
    vector<T>& operator[](int i){
        return mat[i];
    }
    void p_b(const vector<T>&vec){
         mat.push_back(vec);
    }
};
int T=1;
void solve(){
    int sub;
    double p;
    cin>>sub>>p;
    if(sub==1)cout<<"yes"<<endl;
    else if(p==0.5)cout<<"yes"<<endl;
    else cout<<"no"<<endl;
}
signed main(){
//  freopen("xxx.in","r",stdin);
//  freopen("xxx.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
//  cin>>T;
    while(T--)solve();
    return 0;
}

:::: :::::