NOIP系列题目

· · 个人记录

1表示没看题解，2表示看了题解

NOIP2023 三值逻辑

赛场上没写出来。无语。一等没了。

观察到可以模拟前面赋值的过程，然后连边。

记得连双向边！这不会对判环造成影响！赛场就在这里写错了。

发现每个点的出边数量\leq 1。

所以每个连通块同边数\leq siz，要么为siz，要么为siz-1。

可以发现，边数为siz-1的连通块一定不会出现矛盾的关系，所以只需要看这个连通块由U组成还是T\F组成，并计算答案即可。

对于边数为siz的情况，发现一定没有点被提前赋值，说明我们对于其中任意一个点，赋上F/T遍历一次连通块，只要没有出现不合法的环，就没有矛盾，否则这整个连通块都必须是U。根据这个计算答案就行。

计算siz可以用并查集，最好别用dfs暴力找，我考场就是这样挂的。

时间复杂度合理的情况下，应该使用适当的方法降低代码实现难度才对。

## NOIP2022 [种花](https://www.luogu.com.cn/problem/P8865) 考虑$O(N^2)$做。 发现可以预处理一个点向右和向下拓展到的第一个障碍或边界，是$O(N^2)$的。 这样就可以算出C形的答案。 设设状态就可以简单计数得到。 记以一个点为左上角的C形答案为$g_i,_j

发现F形其实是C形向上延申，反过来想，F形只需要将右侧长度乘上下方C形的总方案数即可，十分容易计算。

设一个点向右拓展的最大长度为q_i,_j，g_i,_j向上做前缀和记为s(i,j)，可以得到一个点F形的答案为q_i,_j*s(i+1,j)

O(N^2)

清数组的时候注意，多清空几位不会怎么样，不要因为访问了n+1和0，并且默认它们是0而挂分，实在不行就memset。(1)

NOIP 2012 国王游戏

(2)

NOIP 2000 乘积最大

考虑dp，设f_i,_j为到第i位为止，恰好分成了j部分的最大答案，转移是O(n)的，状态有O(nk)个,可是，还是要高精，不想写了，上题写累了。(1)

NOIP 2007 矩阵取数游戏

不想改题了，本来想认真做道蓝题。但是这题实在是评不上蓝题。

发现行与行之间独立，考虑分开做，发现只从左右两边选数，直接区间dp是很快的。

具体的，设f_l,_r为取到剩余数字的区间为[l,r]的最大答案。

显然最后这一行的答案就是\max_1^m f_i,_i+a_i*2^m

考虑转移。

不想动脑。。。

记搜！！

这样搜到l=r的时候就可以直接统计答案，不需要考虑枚举l,r的顺序和特判之类的，无脑，代码短，上"__int128_t"即可。

必须贴一个我5min码完一发A的代码。

#include<bits/stdc++.h>
using namespace std;
#define ll __int128_t 
const int N=101;
int n,m;
int a[N];
ll f[N][N],sum;
inline ll get(int b){
    ll res=1,a=2;
    while(b){
        if(b&1)res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
inline ll maxx(ll A,ll B){return A>B?A:B;}
inline void dfs(int l,int r,int step,ll nsum){
    if(f[l][r]>=nsum)return ;
    f[l][r]=nsum;
    if(l==r){sum=maxx(sum,f[l][r]+a[l]*get(step));return ;}
    dfs(l+1,r,step+1,f[l][r]+a[l]*get(step));
    dfs(l,r-1,step+1,f[l][r]+a[r]*get(step));
}
#define pc putchar
inline void wt(ll x){
    if(x<10)pc(x+'0');
    else wt(x/10),pc(x%10+'0');
}
int main(){
    scanf("%d%d",&n,&m);
    ll ans=0;
    while(n--){
        for(int i=1;i<=m;++i)scanf("%d",&a[i]);
        memset(f,-1,sizeof f);
        sum=0;
        dfs(1,m,1,0);
        ans+=sum;
    }
    wt(ans);
    return 0;
}

没看题解 111

不知道为什么最后一个点983ms，可能get函数里面不写logn的就会TLE。

NOIP 2020 排水系统

今天模拟赛做NOIP2020。

开题就发现这题拓扑，这也太明显了吧，水从入度为0的点流入。

考虑拓扑推答案，直接暴力推都是O(n)的。

比赛的时候开了ll没开__int128_t

100->60 麻

NOIP 2020 字符串匹配

比赛的时候被卡常了。麻。

S=(AB)^i * C

令D=AB

有S=D^i*C

考虑先枚举D，那么D^i以后的部分都是C。

考虑枚举i，这样C的左端点自然就出来了。

可以预处理出每个前后缀的f函数。是O(n)的。

然后问题就变成了，对于前len_D-1个前缀A，有多少个满足F(A)\leq F(C)

典！GDKOI没写的问题现在又遇到了。

直接上树状数组即可，十分的“快”。

乍一看，这复杂度O(n^2logn)只能过48分，怎么办呢，拼暴力拼上68分？

就在我苦思冥想的时候，回来认真看了一下复杂度，我靠，O(n*ln(n)*log_2n)！

枚举i,D的时间是\sum_1^n n/i=n\sum_1^n1/i=n*ln(n)

BIT查询是log级别。

算了一下感觉可能可以

于是没有卡常dop

只拿到了84。

后来发现F(s)最大是26

时间就可以变成O(n*ln(n)*log_226)

可是怎么92分？咦？96？？？

评测机波动？

卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡卡常常常常常常常常常常常常常常常常

luogu上过了，gmoj没过，这是为什么捏？

后来还是把BIT删了，修改可以O(|\sum|)，查询就变成O(1)

这样时间就是O(n*ln(n)+n*|\sum|)

但是由于我人傻常数大，还是跑了793ms，别人比我快百倍，怎么办我好菜。

(2)

附：

BIT代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+2;
#define ll long long 
#define ull unsigned long long 
#define re register 
int T,n;
char s[N];
ll ans;
inline int read(){
    int res=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
    return res*f;
}
const ull base=41;
int f[N],g[N];
ull h[N],b[N];
int t[31];
struct BIT{
    int tr[N];
    inline void clear(){for(re int i=0;i<=n;++i)tr[i]=0;}
    inline int lowbit(re int x){return x&(-x);}
    inline void ins(re int x){if(x==0){tr[0]++;return ;}while(x<=31){tr[x]++;x+=lowbit(x);}}
    inline int qry(re int x){re int res=0;while(x){res+=tr[x];x-=lowbit(x);}return res+tr[0];}
}xxh;
int main(){
    T=read();
    b[0]=1;
    for(re int i=1;i<=N;++i)b[i]=b[i-1]*base;
    while(T--){
        scanf("%s",s+1);
        n=strlen(s+1);
        for(re int i=1;i<=n;++i)h[i]=h[i-1]+b[i]*(s[i]-'a');
        f[0]=0,g[n+1]=0;
        for(re int i=0;i<=30;++i)t[i]=0;
        for(re int i=1;i<=n;++i){
            f[i]=f[i-1];
            t[s[i]-'a']++;
            if(t[s[i]-'a']%2==0)f[i]--;
            else f[i]++;
        }
        for(re int i=0;i<=30;++i)t[i]=0;
        for(re int i=n;i>=1;--i){
            g[i]=g[i+1];
            t[s[i]-'a']++;
            if(t[s[i]-'a']%2==0)g[i]--;
            else g[i]++;
        }
        vector<int>xh;
        ans=0ll;
        xxh.ins(f[1]);
        for(re int i=2;i<n;++i){
            re int len=i;
            re int nxtl=i+1,nxtr=i+i;
            xh.clear();
            xh.push_back(i+1);
            while(nxtr<=n){
                if((h[i]-h[0])*b[nxtl]==(h[nxtr]-h[nxtl-1])*b[1])xh.push_back(nxtr+1),nxtl+=i,nxtr+=i;
                else break;
            }
            for(re int j:xh)if(j<=n)ans+=xxh.qry(g[j]);
            xxh.ins(f[i]);
        }
        printf("%lld\n",ans);
        xxh.clear();
    }
    return 0;
}

无BIT代码

#pragma GCC optimize(2)
%:pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+2;
#define ll long long 
#define ull unsigned long long 
#define re register 
int T,n;
char s[N];
ll ans;
inline int read(){
    int res=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
    return res*f;
}
const ull base=41;
int f[N],g[N];
ull h[N],b[N];
int t[31];
int tr[N];
#define pc putchar
inline void wt(ll x){
    if(x<10)pc(x+'0');
    else wt(x/10),pc(x%10+'0');
}
int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    T=read();
    b[0]=1;
    for(re int i=1;i<=N;++i)b[i]=b[i-1]*base;
    while(T--){
        scanf("%s",s+1);
        n=strlen(s+1);
        for(re int i=1;i<=n;++i)h[i]=h[i-1]+b[i]*(s[i]-'a');
        f[0]=0,g[n+1]=0;
        for(re int i=0;i<=30;++i)t[i]=0;
        for(re int i=1;i<=n;++i){
            f[i]=f[i-1];
            t[s[i]-'a']++;
            if(t[s[i]-'a']%2==0)f[i]--;
            else f[i]++;
        }
        for(re int i=0;i<=30;++i)t[i]=0;
        for(re int i=n;i>=1;--i){
            g[i]=g[i+1];
            t[s[i]-'a']++;
            if(t[s[i]-'a']%2==0)g[i]--;
            else g[i]++;
        }
        ans=0ll;
        for(re int i=f[1];i<=26;++i)tr[i]++;
        for(re int i=2;i<n;++i){
            re int nxtl=i+1,nxtr=i+i;
            ans+=tr[g[i+1]];
            while(nxtr<n){
                if((h[i]-h[0])*b[nxtl]==(h[nxtr]-h[nxtl-1])*b[1])ans+=tr[g[nxtr+1]],nxtl+=i,nxtr+=i;
                else break;
            }
            for(re int j=f[i];j<=26;++j)tr[j]++;
        }
        wt(ans),puts("");
        clear();
    }
    return 0;
}