这次博客写的好晚啊。。。。太忙了。。。太强了。。。

这次模拟赛打的有些不如意，本想着寒假做了挺多题，应该不错了，但是发现还是菜的一批

被C班霸霸们摁在鞋底摩擦啊。。。太强了。。。@丁思源

然后就是各种zz错误，可能是没有从OJ的从来不调代码这个习惯转成打OI赛制把。。。

T1：

最水的字符串判断题，但是最好不要用string，可能会爆。。。

然后zz的我把not成功的打成了no。。。。

code:

#include<bits/stdc++.h>
using namespace std;
int Q;
char s[10010];
int main(){
    freopen("acid.in","r",stdin);
    freopen("acid.out","w",stdout);
    scanf("%d",&Q);
    while(Q--){
        scanf("%s",s+1);
        int l=strlen(s+1);
        if(s[l-1]=='i'&&s[l]=='c'){
            if(s[1]=='h'&&s[2]=='y'&&s[3]=='d'&&s[4]=='r'&&s[5]=='o') puts("non-metal acid");
            else puts("polyatomic acid");
        }
        else puts("not an acid");
    }
    return 0;
}

T2：

这是一道贪心的题，考虑肯定每次关一扇门最劣，关两扇门最优

于是可以分别从左向右或者从右向左模拟关门，求出答案

code:

#include<bits/stdc++.h>
using namespace std;
int ans1,ans2,a[10010],n;
int main(){
    freopen("lock.in","r",stdin);
    freopen("lock.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),ans2+=a[i];
    for(int i=1;i<=n;i++){
        if(!a[i]) continue;
        ans1++;
        a[i]=0;
        a[i+1]=0;
    }
    printf("%d %d",ans1,ans2);
    return 0;
}

T3:

大模拟，暴力出奇迹。。。

code:

#include<bits/stdc++.h>
using namespace std;
int kx,ky,ans,T;
char mp[12][12];
int vis[12][12];
const int n=8,q=8,r=4,b=4,k=8;
const int qt[q][2]={1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1,0,1};
const int rt[r][2]={1,0,0,1,-1,0,0,-1};
const int bt[b][2]={1,1,1,-1,-1,-1,-1,1};
const int kt[k][2]={1,2,2,1,-1,2,2,-1,1,-2,-2,1,-1,-2,-2,-1};
bool check(int x,int y){return x>=1&&x<=n&&y>=1&&y<=n;}
bool solve(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
        if(mp[i][j]=='k') kx=i,ky=j;
        else if(mp[i][j]=='Q'){
            for(int k=0;k<q;k++)
                for(int x=i+qt[k][0],y=j+qt[k][1];check(x,y)&&(mp[x][y]=='#'||mp[x][y]=='k');x+=qt[k][0],y+=qt[k][1])
                    vis[x][y]=1;
        }else if(mp[i][j]=='R'){
            for(int k=0;k<r;k++)
                for(int x=i+rt[k][0],y=j+rt[k][1];check(x,y)&&(mp[x][y]=='#'||mp[x][y]=='k');x+=rt[k][0],y+=rt[k][1])
                    vis[x][y]=1;
        }else if(mp[i][j]=='B'){
            for(int k=0;k<b;k++)
                for(int x=i+bt[k][0],y=j+bt[k][1];check(x,y)&&(mp[x][y]=='#'||mp[x][y]=='k');x+=bt[k][0],y+=bt[k][1])
                    vis[x][y]=1;
        }else if(mp[i][j]=='K'){
            for(int k=0;k<k;k++)
                if(check(i+kt[k][0],j+kt[k][1]))
                    vis[i+kt[k][0]][j+kt[k][1]]=1;
        }else if(i>1&&mp[i][j]=='P'){
            if(check(i-1,j-1))    vis[i-1][j-1]=1;
            if(check(i-1,j+1))    vis[i-1][j+1]=1;
        }
    }    return vis[kx][ky];
}
int main(){
    freopen("check.in","r",stdin);
    freopen("check.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        ans=0;
        for(int i=0;i<=n+1;i++)
            mp[0][i]=mp[n+1][i]='#',
            mp[i][0]=mp[i][n+1]='#';
        for(int i=1;i<=8;i++)scanf("%s",mp[i]+1);
        ans=solve();
        for(int i=1;i<=8;i++){
            if(mp[1][i]=='#'&&mp[2][i]=='P'){
                mp[2][i]='#';mp[1][i]='P';
                mp[1][i]='Q',ans+=solve();
                mp[1][i]='R',ans+=solve();
                mp[1][i]='B',ans+=solve();
                mp[1][i]='K',ans+=solve(); 
                mp[1][i]='#',mp[2][i]='P';
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

T4：

考虑要让分解次数尽量多，肯定要分解成尽量大的质因子

所以可以暴力枚举出小的约数，然后除n就可以得出最大的质因子了。。。

不过貌似也可以从大向小枚举，没试过。。。

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,x;
ll ans;
ll calc(ll k){
    ll cnt=k;
    while(k>1){
        ll tot=-1;
        for(int i=2;i<=sqrt(k);i++)if(k%i==0){tot=i;break;}
        if(tot==-1){cnt++;break;}
        cnt+=k/tot;
        k/=tot;
    }
    return cnt;
}
int main(){
    freopen("sticks.in","r",stdin);
    freopen("sticks.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&x),ans+=calc(x);
    printf("%lld",ans);
    return 0;
}

T5:

首先可以得出一个n^2的DP：

#include <bits/stdc++.h>
#define mxn 100000
using namespace std;
typedef long long ll;
bool o[mxn|1];
ll rs,n,h[mxn|1],p[mxn|1],f[mxn|1];
int main() {
    freopen("race.in","r",stdin);
    freopen("race.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",h+i);
    for(int i=2;i<=n;i++)
        scanf("%lld",p+i);
    memset(f,0x3f,sizeof(f));
    f[1]=0;
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(h[j]>h[i]) {
                f[j]=min(f[j],f[i]+h[j]-h[i]+p[j]);
                o[i]=1;    break;
            } else {
                f[j]=min(f[j],f[i]+h[i]-h[j]+p[j]);
            }
    rs=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++)
        if(!o[i])    rs=min(rs,f[i]);
    printf("%lld\n",rs+n);
    return 0;
}

但是这样只有68分。。。

然后我们想到倒着转移，从n枚举到1

发现f[i]转移是从之前所有的f[j]中代价最小的那个转移过来的。。。

于是开一个单调栈来维护这一切。。。

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p[100010],f[100010];
ll st[100010][2],top;
ll h[100010];
int main(){
    freopen("race.in","r",stdin);
    freopen("race.out","w",stdout);
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
    for(int i=2;i<=n;i++)scanf("%lld",&p[i]);
    memset(f,127,sizeof(f));
    for(ll i=n;i>=1;i--){
        ll cnt=1e18;
        while(top&&h[st[top][0]]<=h[i]){
            cnt=min(st[top][1],cnt);
            f[i]=min(f[i],st[top][1]-i+h[i]);
            top--;
        }
        if(!top) f[i]=min(f[i],n-i+1);
        else f[i]=min(f[i],st[top][0]-i+f[st[top][0]]+h[st[top][0]]-h[i]+p[st[top][0]]);
        cnt=min(cnt,f[i]+i-h[i]+p[i]);
        st[++top][0]=i;
        st[top][1]=cnt;
    }
    printf("%lld",f[1]);
    return 0;
}