试题下载:https://download.csdn.net/download/ljw_study_in_CSDN/12950921
@

A题 门牌制作(5分)

#include <bits/stdc++.h>
using namespace std;
const int N=2020;
int f(int x)
{
    int cnt=0;
    while(x)
    {
        int r=x%10;
        if(r==2)cnt++; 
        x/=10;
    }
    return cnt;
}
int main() 
{
    int ans=0;
    for(int i=1;i<=N;i++)
        ans+=f(i);
    printf("%d\n",ans);
    return 0;
}

答案:624

B题 既约分数 (5分)

#include <bits/stdc++.h>
using namespace std;
const int N=2020;
int main() 
{
    int ans=0;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            int x=__gcd(i,j);
            if(x==1)ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}

答案:2481215

C题 蛇形填数(10分)

#include <bits/stdc++.h>
using namespace std;
const int N=110;
int a[N][N];
int main() 
{
    int cnt=0;
    for(int s=2;s<=40;s++)
    {
        if(s&1)
        {
            for(int i=1;i<s;i++)
            {
                int j=s-i;
                a[i][j]=++cnt;
            }
        }
        else 
        {
            for(int j=1;j<s;j++)
            {
                int i=s-j;
                a[i][j]=++cnt;
            }
        }
    }
    for(int i=1;i<=39;i++)
        for(int j=1;i+j<=40;j++)
            i+j==40?printf("%d\n",a[i][j]):printf("%d ",a[i][j]);
    printf("\nans=%d\n",a[20][20]);
    return 0;
}

答案:761

D题 七段码(10分)

思路:
- a\~g二极管看成点,对应编号0~6,连边建图。
- 二进制枚举放入集合的点,dfs求连通块大小,集合中的点全部连通则符合条件。
- 注意全0状态不用枚举。

#include <bits/stdc++.h>
using namespace std;
const int N=10;
int n,cnt,a[N][N];
bool vis[N],flag[N];
vector<int>g[N];
void dfs(int u)
{
    if(!flag[u])return;
    vis[u]=1;
    cnt++;
    int sz=g[u].size();
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(!vis[v])dfs(v);
    }
}
void add(int x,int y) // 双向边
{
    g[x].push_back(y);
    g[y].push_back(x);
}
int main() 
{
    add(0,1);add(0,5);
    add(1,2);add(1,6);
    add(2,3);add(2,6);
    add(3,4);add(4,5);
    add(4,6);add(5,6);
    int sum=0;
    for(int i=1;i<(1<<7);i++) // 不是从i=0(全0状态)开始
    {
        int k=0,sz=0;
        memset(flag,0,sizeof(flag));
        memset(vis,0,sizeof(vis));
        for(int j=0;j<7;j++)
        {
            if(i&(1<<j))
            {
                flag[j]=1; // 这个点被放入集合 
                k=j;
                sz++; // 集合大小 
            }
        }
        cnt=0; // 搜索到的连通块大小
        dfs(k);
        if(cnt==sz)sum++;
    }
    printf("%d\n",sum);
    return 0;
}

答案:80

【待补】E题 平面分割(15分)

【问题描述】 20 个圆和 20 条直线最多能把平面分成多少个部分?

F题 成绩分析(15分)

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,a[N];
int main() 
{
    ios::sync_with_stdio(false);
    cin>>n;
    int mx=-999,mi=999,sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mx=max(mx,a[i]);
        mi=min(mi,a[i]);
        sum+=a[i];
    }
    double ave=(double)sum/(double)n;
    printf("%d\n%d\n%.2f\n",mx,mi,ave);
    return 0;
}
/*
7 
80 92 56 74 88 99 10
ans:
99 
10 
71.29
*/

G题 回文日期(20分)

思路:
- 模拟,枚举从现在往后的每一年,然后求其回文表示月份日期,判断是否合法。
- 年相同时,特判其回文产生的月份日期是否在当前日期之后。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[12];
int a[12],ans1[12],ans2[12];
bool isrun(int x) // 是闰年 
{
    if(x%400==0||(x%100!=0&&x%4==0))return 1;
    else return 0;
}
bool ismonth(int x) // 月合法 
{
    if(x<=12&&x>=1)return 1;
    else return 0;
}
bool isday(int y,int m,int d) // 日合法 
{
    if(m>31||m<=0)return 0; // 最大区间1~31
    if(m==2) // 2月 
    {
        if(isrun(y)) // 是闰年 
        {
            return d<=29;
        }
        else
        {
            return d<=28;   
        } 
    }
    else 
    {
        if(m==1||m==3||m==5||m==7||m==8||m==10||m==12)
        {
            return d<=31;
        }
        else 
        {
            return d<=30;
        }
    }
}
bool isAB(int y) // 年是否为AB形 
{
    if(a[1]==a[3]&&a[2]==a[4]&&a[1]!=a[2])return 1;
    else return 0;
}
void get_a(int y) // 将y拆成int数组 
{
    int t=y;
    int cnt=4;
    while(t)
    {
        int r=t%10;
        a[cnt--]=r;
        t/=10;
    }
}
bool islater(int y,int m,int d,int by,int bm,int bd) // 回文产生的日期y/m/d在by/bm/bd之后 
{
    if(y!=by)return y>by;
    else if(m!=bm)return m>bm;
    return d>bd;
}
int main() 
{
    cin>>s+1;
    int by=0; 
    for(int i=1;i<=4;i++)
        by=by*10+(s[i]-'0');
    int bm=0;
    for(int i=5;i<=6;i++)
        bm=bm*10+(s[i]-'0');
    int bd=0;
    for(int i=7;i<=8;i++)
        bd=bd*10+(s[i]-'0');
    bool flag1=0,flag2=0;
    for(int y=by;y<=9999;y++)
    {
        get_a(y);
        int m=0;
        for(int i=4;i>=3;i--)
            m=m*10+a[i];
        int d=0;
        for(int i=2;i>=1;i--)
            d=d*10+a[i];
        if(!islater(y,m,d,by,bm,bd))continue;
        //printf("y=%d m=%d d=%d\n",y,m,d); // 年,回文产生的月,回文产生的日 
        if(flag1==0&&ismonth(m)&&isday(y,m,d))
        {
            for(int i=1;i<=4;i++)
            {
                ans1[i]=a[i];
                ans1[9-i]=a[i];
            }
            flag1=1;
        }
        if(flag2==0&&ismonth(m)&&isday(y,m,d)&&isAB(y))
        {
            for(int i=1;i<=4;i++)
            {
                ans2[i]=a[i];
                ans2[9-i]=a[i];
            }
            flag2=1;
        }
        if(flag1&&flag2)break;
    }
    for(int i=1;i<=8;i++)
        i==8?printf("%d\n",ans1[i]):printf("%d",ans1[i]);
    for(int i=1;i<=8;i++)
        i==8?printf("%d\n",ans2[i]):printf("%d",ans2[i]);
    return 0;
}
/*
20200202
ans:
20211202
21211212

82200221
ans:
82200228
90900909

21211211
ans:
21211212
21211212

21211213
ans:
21300312
30300303
*/

H题 子串分值(20分)

只写了个O(n^2^)暴力...(能水个60%数据)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
char s[N];
int vis[32];
int main() 
{
    ios::sync_with_stdio(false);
    cin>>s+1;
    int n=strlen(s+1);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        ll cnt=0;
        for(int j=i;j<=n;j++)
        {
            int x=s[j]-'a';
            vis[x]++;
            if(vis[x]==1)cnt++;
            else if(vis[x]==2)cnt--;
            ans+=cnt;
        }   
    }
    printf("%lld\n",ans);
    return 0;
}
/*
ababc
ans:21
*/

补题:正确思路

考虑计数每个位置的字符所能影响到的子串的个数。

字符s[i]有贡献的子串为从[last[i]+1,i]取出子串和从[i,next[i]-1]取出子串,连接后组成的字符串,其中last[i]表示s[i]字符上一次出现的位置,next[i]表示s[i]字符下一次出现的位置,字符串长度为n,那么答案为:$$ans=\sum_{i=1}^{n}(i-last[i])*[next[i]-i]$$

举个例子abaca,假设下标从1开始,当我们遍历到i=3时,字符为a,上一次出现此字符位置为1,下一次出现此字符位置为5,则计数ans+=(3-1)*(5-3)=4,也就是统计了ba, a, ac, bac这四个子串,它们都包含i=3的字符s[3],对它们来说s[3]这个字符是有效的贡献。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int K=30,N=1e5+10;
vector<ll>pos[K]; // 存每个字母存在的所有位置
char s[N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>s+1;
    int n=strlen(s+1);
    for(int i=0;i<26;i++)
        pos[i].push_back(0);
    for(ll i=1;i<=n;i++)
    {
        int x=s[i]-'a'; // a-z -> 0-25
        pos[x].push_back(i); // 存字母x存在的所有位置
    }
    ll ans=0;
    for(int i=0;i<26;i++)
    {
        if(pos[i].size()==1)continue;
        pos[i].push_back(n+1);
        int sz=pos[i].size();
        for(int j=1;j<sz-1;j++)
        {
            ll p1=pos[i][j-1];
            ll p2=pos[i][j];
            ll p3=pos[i][j+1];
            ans+=(p2-p1)*(p3-p2);
        }
    }
    printf("%lld\n",ans);
    return 0;
}

【待补】 I题 荒岛探测(25分)

【待补】J题 字串排序(25分)