2021CCPC online网络赛

1001、Cut The Wire

签到题，按照题意来思考就行

开题时间：0:05

交题时间：0:39

问题：手速慢了，其次就是思考分类时过于复杂了，但又不能快速想清楚

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


int main(){
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        ll n;
        cin>>n;
        if (n%2==0)//偶数
        {
            ll even=ceil(n/2.0);
            ll t=ceil((n-1)/3.0);
            if (t%2==0) t+=1;
            if (3*t+1==n) t+=1; 
            ll odd=(n-1-t)/2+1;
            cout<<even+odd<<endl;
        }
        else
        {
            ll even=ceil(n/2.0);
            ll t=ceil((n-1)/3.0);
            if (t%2==0) t+=1;
            ll odd=(n-t)/2+1;
            cout<<even+odd<<endl;
        }
    }

    return 0;
}

1002、Time-division Multiplexing

开题时间：2:000前后

标签：字符串、双指针、滑动窗口

相关题：

难点：读题，转化题意

赛中出现的问题：读题太慢，没选取正确的代码(原来是二分)，导致一直TLE，误以为是构造串的地方出了锅，这题拖延了整体比赛节奏

题意

这一题有一定的工科背景，大概含义就是，n行字符串都有一个指针，每次从第一行到最后一行取当前指针下标的字符，并且将指针后移一位，当指针指向了行末的下一位，那就回到0下标，依次重复构成一个循环串，求一个最短子串的长度，该串能包含所有出现过的字符。

思路

用双指针来解决最短子串，右指针每次放入，当左右指针的区间内包含的不同字符数等于所有出现过的字符数，那么就更新答案，左指针向右

重点：构造出来的串需要s+=s，原因是我们的答案，会出现在两个串交界的地方，这也是比赛时没想到的地方

代码

#include <bits/stdc++.h>
using namespace std;
string str[105];
int p[105], n;
int leng[105];
const int INF=0x3f3f3f3f;
bool fun()
{
    for (int i = 1; i <= n; i++)
        if (0 != p[i])
            return false;
    return true;
}
int vis[30];
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        int maxn = -1, pos;
        string s = "";
        int gcd;
        for (int i = 1; i <= n; i++)
        {
            cin >> str[i];
            int len = str[i].size();
            
            if (maxn < len)
                maxn = len, pos = i;
            p[i] = 0;
            leng[i] = len;
        }
        int sum=0;
        memset(vis,0,sizeof vis);
        do
        {
            for (int i = 1; i <= n; i++)
            {
                int now = p[i];
                p[i]++;
                if (p[i] >= leng[i])
                    p[i] = 0;
                s += str[i][now];
                if (vis[str[i][now]-'a']==0)
                    sum++;
                vis[str[i][now]-'a']=1;
            }
        } while (!fun());
        //构造出来的字符串为s
        //cout<<s<<endl<<s.size()<<endl;
        s+=s;
        memset(vis,0,sizeof vis);
        int cnt=0,len=s.size(),res=INF;
        for(int i=0,j=0;j<len;j++)
        {
            if (vis[s[j]-'a']==0)
                cnt++;
            vis[s[j]-'a']++;
            while(cnt==sum)
            {
                res=min(j-i+1,res);
                if (--vis[s[i]-'a']==0)
                    cnt--;
                i++;
            }
        }
        cout<<res<<endl;
    }

    return 0;
}

1006、Power Sum

开题：0:50前后

提交：1:28

队友做的，但在思考时，想到了相邻两对平方差的和等于4这个结论，也想到了只要能特殊构造出1,2,3，再不停地加上4就可以了。(但队友手速太快了直接切了%%%)

1: $$1^2$$

2: $$-1-4-9+16$$

3: $$-1+4$$

4: $$1-4-9+16$$

题意

给定n，让我们通过以下式子，其中$$a_i$$可为1或者-1

得到1~k的加减平方数的和，其和等于n，求出k和$$a_i$$的结果

代码

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        int n,k=0;
        cin>>n;
        int cnt=n/4;
        n%=4;
        string str="";

        if (n==1)
            str="1",k=1; 
        else if (n==2)
            str="0001",k=4;
        else if (n==3)
            str="01",k=2;
         for(int i=0;i<cnt;i++)
                str+="1001";
        k+=cnt*4;
        cout<<k<<endl<<str<<endl;
    }


    return 0;
}

还没有补完题，预计会将后三题补掉