头像

iuk11




离线:5小时前


最近来访(45)
用户头像
小玖-igniber
用户头像
怀中人
用户头像
LLLHHH
用户头像
一个老实人
用户头像
嗨害嗨来了啊
用户头像
Redamancy_7
用户头像
筑梦师
用户头像
10_2
用户头像
老师我要是上黑板
用户头像
ℒℴѵℯ时光荏苒
用户头像
Tequila
用户头像
yxc
用户头像
青灯
用户头像
a碟


iuk11
11天前

最长上升子序列 LIS 优化 二分与贪心 单调队列

数据范围 1e6,如果用普通的LIS会超时。
现在介绍优化版本:在单调队列中,保证所有字符串按照字典序单增。首先对题目进行字符串处理,按照顺序依次入队。
入队满足两个条件:

  • 当前元素比队尾元素大,直接入队;
  • 当前元素比队尾元素小,二分找到第一个大于等于该元素的元素,替换它。

最终的队列长度一定是该序列的最长子序列长度。(结论1)

在每一次入队操作时,同时更新len序列(表示以第i个元素结尾的序列的最长子序列的长度):

  • 当前元素比队尾元素大,长度为队列长度;
  • 当前元素比队尾元素小,二分找到第一个大于等于该元素的下标,长度为下标+1(当且仅当下标从0开始)。

在处理完这些操作后,我们得到了 len序列(回溯用) 以及 最终的 单调队列(没啥用)
因为题目要求输出最长子序列的每个元素,所以根据长度序列进行回溯,找到每个元素。
设最长子序列长度为 m ,有 m=q.size() ,见结论1.
从后往前判断以每个元素结尾,能得到的最长子序列长度,如果正好为当前m的值,记录一下当前元素为最长子序列中的元素。然后m--(因为已经又确定了一个元素)。直到m=0找完所有最长子序列中的元素。
倒序找,要倒序输出,越先找到的元素字典序越大,从小到大输出结果。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
int main(){
    string s;
    cin>>s;
    vector<string> str;
    string tem;
    s+="A";
    str.push_back("*");
    tem+=s[0];
    for(int i=1;i<s.size();i++){
        if(s[i]>='A'&&s[i]<='Z'){
            str.push_back(tem);
            tem="";
            tem+=s[i];
        }else{
            tem+=s[i];
        }
    }
    vector<string> q;
    vector<int> len;
    q.push_back(str[1]);
    len.push_back(1);
    for(int i=2;i<str.size();i++){
        if(str[i]>q.back()){
            q.push_back(str[i]);
            len.push_back(q.size());
        }
        else{
            int l=0,r=q.size()-1;
            while(l<r){
                int mid=(l+r)>>1;
                if(q[mid]>=str[i]){
                    r=mid;
                }else{
                    l=mid+1;
                }
            }
            //int l=lower_bound(q.begin(),q.end(),str[i])-q.begin();
            q[l]=str[i];
            len.push_back(l+1);
        }
    }
    vector<string> res;
    for(int i=str.size()-1,m=q.size();m>0;i--){
        if(len[i]==m){
            res.push_back(str[i+1]);
            m--;
        }
    }
    for(int i=res.size()-1;i>=0;i--) cout<<res[i];
    return 0;
}



iuk11
20天前
#include<bits/stdc++.h>
using namespace std;
const int N=110;
const double eps=1e-8;
int n;
int a[N][N];
int gauss(){
    int c,r;//r行 c列
    for(c=0,r=0;c<n;c++){
        int t=r;
        for(int i=r;i<n;i++){
            if(a[i][c]){
                t=i;
            }
        }
        if(!a[t][c]) continue;
        for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]);
        for(int i=r+1;i<n;i++){
            if(a[i][c]){
                for(int j=n;j>=c;j--){
                    a[i][j]^=a[r][j];
                }
            }
        }
        r++;
    }
    if(r<n){
        for(int i=r;i<n;i++){
            if(a[i][n]){
                return 2;
            }
        }
        return 1;
    }
    for(int i=n-1;i>=0;i--){
        for(int j=i+1;j<n;j++){
            a[i][n]^=a[i][j]*a[j][n];
        }
    }
    return 0;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n+1;j++){
            cin>>a[i][j];
        }
    }
    int t=gauss();
    if(t==2) cout<<"No solution";
    else if(t==1) cout<<"Multiple sets of solutions";
    else{
        for(int i=0;i<n;i++){
           cout<<a[i][n]<<"\n";
        }
    }
    return 0;
}



iuk11
20天前
#include<bits/stdc++.h>
using namespace std;
const int N=110;
const double eps=1e-8;
int n;
double a[N][N];
int gauss(){
    int c,r;//r行 c列
    for(c=0,r=0;c<n;c++){
        int t=r;
        for(int i=r;i<n;i++){
            if(fabs(a[i][c])>fabs(a[t][c])){
                t=i;
            }
        }
        if(fabs(a[t][c])<eps) continue;
        for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]);
        for(int i=n;i>=c;i--) a[r][i]/=a[r][c];
        for(int i=r+1;i<n;i++){
            if(fabs(a[i][c])>eps){
                for(int j=n;j>=c;j--){
                    a[i][j]-=a[r][j]*a[i][c];
                }
            }
        }
        r++;
    }
    if(r<n){
        for(int i=r;i<n;i++){
            if(fabs(a[i][n])>eps){
                return 2;
            }
        }
        return 1;
    }
    for(int i=n-1;i>=0;i--){
        for(int j=i+1;j<n;j++){
            a[i][n]-=a[i][j]*a[j][n];
        }
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n+1;j++){
            scanf("%lf",&a[i][j]);
        }
    }
    int t=gauss();
    if(t==2) cout<<"No solution";
    else if(t==1) cout<<"Infinite group solutions";
    else{
        for(int i=0;i<n;i++){
            if(fabs(a[i][n])<eps) a[i][n]=0;
            printf("%.2lf\n",a[i][n]);
        }
    }
    return 0;
}


活动打卡代码 AcWing 1088. 旅行问题

iuk11
1个月前
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
ll p[N],d[N];
ll w[N*2];
ll q[N];
int mark[N];
int n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i]>>d[i];
    }
    //顺
    for(int i=1;i<=n;i++){
        w[i]=w[i+n]=p[i]-d[i];
    }
    for(int i=1;i<=2*n;i++){
        w[i]+=w[i-1];
    }
    int hh=0,tt=-1;
    for(int i=2*n;i>=1;i--){
        if(hh<=tt&&q[hh]>=i+n-1) hh++;
        while(hh<=tt&&w[q[tt]]>=w[i]) tt--;
        q[++tt]=i;
        if(i<=n&&w[q[hh]]>=w[i-1]) mark[i]=1;
    }
    //逆
    d[0]=d[n];//s[1]计算的时候需要
    for(int i=1;i<=n;i++){
        w[i]=w[i+n]=p[i]-d[i-1];
    }
    for(int i=2*n;i>=0;i--){
        w[i]+=w[i+1];
    }
    hh=0,tt=-1;
    for(int i=1;i<=2*n;i++){
        if(hh<=tt&&q[hh]>=i+n-1) hh++;
        while(hh<=tt&&w[q[tt]]>=w[i]) tt--;
        q[++tt]=i;
        if(i>n&&w[q[hh]]>=w[i+1]) mark[i-n]=1;
    }
    for(int i=1;i<=n;i++){
        if(mark[i]) cout<<"TAK"<<endl;
        else cout<<"NIE"<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 885. 求组合数 I

iuk11
2个月前
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
const int mod=1e9+7;
int c[N][N];
void init(){
    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(!j) c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
}
int main(){
    init();
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1087. 修剪草坪

iuk11
2个月前
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
typedef long long ll;
const ll INF=1e18;
ll s[N],q[N];
ll dp[N];
int n,k;
int hh,tt;
ll get(int j){
    if(!j) return 0;
    return dp[j-1]-s[j];
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
    }
    for(int i=1;i<=n;i++){
        if(i-k>q[hh]) hh++;
        dp[i]=max(dp[i-1],get(q[hh])+s[i]);
        while(hh<=tt&&get(i)>=get(q[tt])) tt--;
        q[++tt]=i;
    }
    cout<<dp[n]<<endl;
    return 0;
}


活动打卡代码 AcWing 135. 最大子序和

iuk11
2个月前
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+100;
const int INF=1e18;
typedef long long ll;
ll s[N],q[N];
int hh,tt;
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
    }
    ll res=-INF;
    for(int i=1;i<=n;i++){
        while(hh<=tt&&i-q[hh]>m) hh++;
        res=max(res,s[i]-s[q[hh]]);
        while(hh<=tt&&s[i]<=s[q[tt]]) tt--;
        q[++tt]=i;
    }
    cout<<res<<endl;
    return 0;
}



iuk11
2个月前

第一次在acwing写题解。比赛的时候以为ac有戏,赛后发现差一截。
题意
给定长度为 $n$ 的整数序列 {$a_n$} 以及 $t$ ,求满足$\sum_{i=l}^ra_i<t$的个数有多少。
题解
首先先算出数组前缀和。
设 $[1,i]$ 的前缀和为 $S_i$ ,有 $S_r-S_{l-1}<t$ ,整理有 $S_r-t<S_{l-1}$ ,可以把值域分成两部分: $S_r-t$ , $S_{l-1}$ ,这时值域个数为 $2n$ ,因为值分散,要进行离散化,用vector(基础课有板)。
然后对离散化后的值域排序,去重。
开始动态的向树状数组中加入值,每个值加入的时候权值为1,表示这个值出现了一次。
在动态更新时累加每个 $[l-1,inf)$ 区间里的个数和(树状数组查询) 即为最终答案,所有满足条件的个数数量。
查询的时候二分找到离散化下标,当然所有步骤都要二分找一下离散化下标。

总结错误
1.赛中算的所有 $(l,r)$ 有 $n(n-1)$ 对,没想到用前缀和去把对数缩减到 $2n$ .(这就已经寄了,也没有离散化啥事了)
2.有点遗忘树状数组,可以定个大点的终点(有限的正无穷/最大值),然后求 $[l-1,inf)$ 区间里的个数和。
3.我离散化首选的是map,map不好排序啊。

代码(参考了PrinceS题解)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+100;
const int INF=5e5;
ll n,t;
ll b[N],s[N];
vector<ll> nums;//离散化
ll lowbit(ll x){
    return x&-x;
}
void update(ll i,ll x){
    while(i<=INF){
        b[i]+=x;
        i+=lowbit(i);
    }
}
ll get(ll x){
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin()+1;
}
ll sum(ll x){
    ll res=0;
    while(x>=1){
        res+=b[x];
        x-=lowbit(x);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
    }
    for(int i=0;i<=n;i++){
        nums.push_back(s[i]);
        nums.push_back(s[i]-t);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    ll res=0;
    update(get(s[0]),1);
    for(int i=1;i<=n;i++){
        res+=sum(INF)-sum(get(s[i]-t));
        update(get(s[i]),1);
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 321. 棋盘分割

iuk11
2个月前
#include<cstring>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=15,M=10;
const double INF=1e9;
double tot[M][M];
double v;
double X;
double dp[M][M][M][M][N];
int n;
double get(int x1,int y1,int x2,int y2){
    double sum=tot[x2][y2]-tot[x2][y1-1]-tot[x1-1][y2]+tot[x1-1][y1-1]-X;
    sum=sum*sum/n;
    return sum;
}
double DP(int x1,int y1,int x2,int y2,int k){//记忆化搜索
    double &v=dp[x1][y1][x2][y2][k];//别名
    if(v>=0) return v;
    if(k==1) return v=get(x1,y1,x2,y2);
    v=INF;
    for(int i=x1;i<x2;i++){//按行分割
        v=min(v,DP(x1,y1,i,y2,k-1)+get(i+1,y1,x2,y2));//留着上面,算出下面的值
        v=min(v,DP(i+1,y1,x2,y2,k-1)+get(x1,y1,i,y2));//留着下面,算出上面的值
    }
    for(int i=y1;i<y2;i++){//按列分割
        v=min(v,DP(x1,y1,x2,i,k-1)+get(x1,i+1,x2,y2));//留着左面,算出右边的值
        v=min(v,DP(x1,i+1,x2,y2,k-1)+get(x1,y1,x2,i));//留着右边,算出左边的值
    }
    return v;
}
int main(){
    cin>>n;
    int m=8;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            cin>>tot[i][j];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            tot[i][j]+=tot[i-1][j]+tot[i][j-1]-tot[i-1][j-1];
        }
    }
    memset(dp,-1,sizeof(dp));//-NAN
    X=tot[m][m]/n;
    printf("%.3lf\n",sqrt(DP(1,1,8,8,n)));
    return 0;
}



iuk11
2个月前
#include<bits/stdc++.h>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dis[N];
int vis[N];
int prim(){
    memset(dis,INF,sizeof(dis));
    int res=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&(t==-1||dis[t]>dis[j])){
                t=j;
            }
        }
        if(i&&dis[t]==INF) return INF;
        if(i) res+=dis[t];
        vis[t]=1;
        for(int j=1;j<=n;j++){
            dis[j]=min(dis[j],g[t][j]);
        }
    }
    return res;
}
int main(){
    cin>>n>>m;
    memset(g,INF,sizeof(g));
    for(int i=0;i<m;i++){
        int a,b,w;
        cin>>a>>b>>w;
        g[a][b]=g[b][a]=min(g[a][b],w);
    }
    int t=prim();
    if(t==INF) cout<<"impossible"<<endl;
    else cout<<t<<endl;
    return 0;
}