A

题意

用 $n$ 个编号分别为 $1$ ~ $n$ 的长为 $\lfloor \frac i 2 \rfloor$ ，宽为 $1$ 的长方形拼一个正方形。

要拼成的正方形边长尽可能大，但是不能旋转，可以不用到所有长方形。

思路

找规律，发现答案就是长方形数（ $n$ ）除以二（下取整）

代码

#include<bits/stdc++.h>
using namespace std;
int T;
void work()
{
    int x;
    cin>>x;
    cout<<(x+1)/2<<"\n";
    return;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        work();
    }
    return 0;
}

B

题意

输出每个串（只包括 0 到 9）中多样化的字串。

多样化：每个字符出现次数不超过不同字符数量。

思路

出现次数只要看最多的即可，因为最多的不超过小的也不会，超过了那就直接不行。

由于长度最多有 $10^5$

所以考虑前缀和优化，枚举起始点 $i$，然后 $j$ 从 $i$ 枚举累加并判断即可。

依旧 $\texttt{TLE}$

由于只有 0 到 9

所以不同字符数量最多为 $10$

所以每个出现次数最多为 $10$

$10$ 个数也就是 $10 \times 10 = 100$ 个

所以只要 $j$ 从 $i$ 开始枚举到 $min\{i+99,n\}$ 即可

代码

#include<bits/stdc++.h>
using namespace std;
int T,n,a[10],maxn,ss,ans;
char s[100010];
void work()
{
    ans=0;
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        a[0]=a[1]=a[2]=a[3]=a[4]=a[5]=a[6]=a[7]=a[8]=a[9]=0;maxn=0;ss=0;//初始化
        for(int j=i;j<=min(n,i+99);j++)
        {
            if(a[s[j]-48]==0) ss++;//如果这个数以前没出现就累加数字个数
            a[s[j]-48]++;//累加该数字出现个数
            maxn=max(maxn,a[s[j]-48]);//统计出现最多的数字的出现个数
            if(maxn<=ss) ans++;//符合性质就累加答案
            //cout<<maxn<<" "<<ss<<"\n";
        }
        
    }
    //cerr<<"--"<<ans<<"\n";
    printf("%d\n",ans); 
    return;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        work();
    }
    return 0;
}

C

题意

给你一个数组 $a$

问你一共有多少个 $i (1 \le i \le n)$ 满足 $\sum_{j=1}^{i} = 0$

其中你可以将数组中为 $0$ 的修改成任意数（不限次数）

问最多能获得多少个那样的 $i$

思路

数据过大！

DP？贪心？

都有后效性，但没有前效性！

于是可以倒着，找到每一个 $0$ 所在的位置，记录下来

依次找到最大的位置然后用一个 $\texttt{map}$ 统计出现个数

枚举范围 位置 $+1$ 到 上一个位置 $-1$

还要把 $0$ 出现的次数 $+1$ 因为可以使到这个位置和为 $0$

将最多次数的累加到答案中

对于第一个 $0$ 之前的（或者一个 $0$ 都没有）

我们可以直接累加统计和 $0$ 的个数

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,a[200010],lst,n,st[200010],top;
map <int,int> m;
void work()
{
    int ans=0,llll=-114514;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        if(a[i]==0)
        {
            if(top==0)
            {
                llll=i-1;//如果第一个之前的要另外算，记录一下
            }
            st[++top]=i;
        }//记录 0 的位置
    }
    if(llll==-114514)
    {
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            cnt+=a[i];
            if(cnt==0) ans++;
        }
        printf("%d\n",ans);
        return;
    }//整个没有 0
    if(llll!=0)
    {
        int cnt=0;
        for(int i=1;i<=llll;i++)
        {
            cnt+=a[i];
            if(cnt==0) ans++;
        }
    }//第一个之前的
    lst=n;
    while(top)
    {
        m.clear();
        int cnt=0;
        int l=st[top];
        top--;
        for(int i=l+1;i<=lst;i++)
        {
            cnt+=a[i];
            m[cnt]++;
        }//统计个数
        map<int,int> :: iterator it;
        int s0=m[0]+1;
        int ms=0,id=0;
        for(it=m.begin();it!=m.end();it++)
        {
            if(it->second>ms)
            {
                id=it->first;
                ms=it->second;
            }
        }//打擂
        if(s0>ms)
        {
            ans+=s0;
        }
        else
        {
            ans+=ms; 
        }
    //累加
        lst=l-1;//记录下一轮的界限        
    }
    printf("%lld\n",ans);
    return;
}
signed main()
{
    scanf("%lld",&T);
    while(T--)
    {
        work();
    }
    return 0;
}