可参考资料

来骗：

题解（C++版）

CSP认证高分经验分享视频

时间复杂度

using namespace std;别忘记加

刷题记录

2021年9月

这次考了190=100+70+0+20+0，下来做了做发现第二题差一点想法，拿70是真的亏

202109-1 数组推导

没什么好说的

202109-2 非零段划分

优化！还是TMD优化！

暴力只能70，想到了优化的方法才能100

还是和前缀和的思想很类似，后续计算可以用之前计算的中间结果推出来，从而降低复杂度

  • 前缀和思想

  • vector本质上还是数组，是内存中的连续空间，删除元素的复杂度最坏还是O(n) 参考

  • 一定注意题目的数据量要求，这道题没按常理出牌，数据大小是5e5，而不是1e5

  • 去重+有序可以用set实现，set插入自动有序

    因为set底层实现是红黑树，其查找、删除和插入时间复杂度都比顺序表要好 O(logn)

贴一下100分的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<vector>
#include<algorithm>
#include<iostream>
#include<unordered_map>
#include <set>

using namespace std;
const int N=1e6+10;
int n;
vector<int> v;
bool vis[N];//vis数组用来存放哪些位置还有值
unordered_map<int,vector<int>> mp;//值-在v中对应出现的下标
set<int> s;

int nums(vector<int> q)
{
    int cnt=0;
    bool tag=0;
    for(int i=1;i<n+2;i++)
    {
        if(q[i]!=0&&!q[i-1]&&tag==0)
            tag=1;
        else if(q[i]==0&&tag==1&&q[i-1]!=0)
        {
            tag=0;
            cnt++;
        }
    }
    return cnt;
}

int main() 
{
	cin>>n;
	v.push_back(0);
	for(int i=0;i<n;i++)
	{
		int a;
		cin>>a;
		v.push_back(a);
	}
	v.push_back(0);//读入
	for(int i=0;i<n+2;i++)
		s.insert(v[i]);//set在插入的时候就有序，所以可以同时实现 去重+有序
		//set中放了所有出现的元素，且已经去重排序完毕
	for(int i=0;i<n+2;i++)
		if(v[i]>0)
			vis[i]=1;
	for(int i=0;i<n+2;i++)
		mp[v[i]].push_back(i);//构建mp，mp中放的是	<key:元素int-value:该元素所有出现位置的下标vector>

	int ans=0,count=nums(v);
	set<int>::iterator it=s.begin();
	it++;
	for(;it!=s.end();it++)
	{
		for(auto i=mp[*it].begin();i!=mp[*it].end();i++)
		{
			vis[*i]=false;
			if(vis[*i-1]==1&&vis[*i+1]==1)
				count++;
			else if(vis[*i-1]==0&&vis[*i+1]==0)
				count--;
		}
		ans=max(ans,count);
	}
	cout<<ans;
	return 0;
}

202109-4 收集卡牌

这题考试嗯写了个DFS，水了20分

20分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <map>
#include <stdio.h>
using namespace std;

const int N=20;
double ans=0,pi[N];
int n,k;

int nums(bool card[N])
{
    int sum=0;
    for(int i=0;i<n;i++)
        if(card[i])
            sum++;
    return sum;
}

double dfs(int coin,bool card[N],double times,int u)
{
    if(k*(n-nums(card))<=coin||n==nums(card))
        return u*times;

    double sump=0;
    for(int i=0;i<n;i++)
        if(card[i])
            sump+=pi[i];

    double times1=0;
    if(nums(card))
        times1=dfs(coin+1,card,times*sump,u+1);

    double times2=0;
    for(int i=0;i<n;i++)
    {
        if(!card[i])
        {
            card[i]=1;
            times2+=dfs(coin,card,times*pi[i],u+1);
            card[i]=0;
        }
    }
    return times1+times2;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>pi[i];
    bool card[N]={0};
    cout<<dfs(0,card,1,0);
    return 0;
}

2021年4月

202104-1 灰度直方图

题目链接

202104-2 邻域均值

题目链接——二维前缀和

  • 初次尝试：

    无脑写了四层循环，这样写会超时，只能拿70，同时还出现如下的一些问题：

    • 循环的边界条件出错
    • 整型的/除法为整除，导致结果出现精度问题

  • 正解：

    二维前缀和，时间复杂度可以降到O(n^2)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include <iostream>
    using namespace std;
    const int N=1010;
    int q[N][N]={0},s[N][N]={0};//开二维数组的时候不能太大

    int main()
    {
        //输入部分
        int r,n,l,t;
        cin>>n>>l>>r>>t;
        int num=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&q[i][j]);
        //计算前缀和      
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+q[i][j];
        //计算结果    
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                double sum=0,count=0;//这里要声明为浮点类型：方便后续除法保留小数部分保留精度
                int x1=i-r,x2=i+r,y1=j-r,y2=j+r;//下标
                if(x1<1)
                    x1=1;
                if(y1<1)
                    y1=1;
                if(x2>n)
                    x2=n;
                if(y2>n)
                    y2=n;
                //计算区间和
                sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];//数组的下标还是易错
                count=(x2-x1+1)*(y2-y1+1);

                if(sum/count<=t)
                    num++;
            }
        printf("%d",num);
        return 0;
    }

    要注意的点：

202104-3 DHCP服务器

AcWing题解视频 代码

本题样例数据在1w左右，所以时间复杂度控制在n^2就可以

CSP考试时会有O2优化

这道题主要是搞清楚程序在什么时候应该干什么，相互之间的顺序

确定依照哪部分说明文字来写本道题也很重要，找对了按照正确顺序把文字翻译成代码即可

代码段复用cv的时候要注意是否要改参数

很大几率会由于题意理解偏差，导致一些难以发现的小问题，一定要多读题，理解题目意思

  • 结构体声明技巧：数组下标即可拿来当做ip地址

  • 明确时间关系和发送接收者的关系

    client和server都可以是发送者或者接受者，理解实际过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=10010;

struct IP//本题的C++结构体声明技巧！！！数组下标即为ip地址
{
    string owner;
    int state=0;//0 未分配  1 待分配  2 占用  3 过期
    int t=0;    //过期时间
}ip[N];
string h;
int n,t_def,t_max,t_min;//n是ip池大小
int m;//m是报文个数

int update_ips_state(int tc)
{
    for(int i=1;i<=n;i++)
    {
        if(ip[i].t&&ip[i].t<=tc)
        {
            if(ip[i].state==1)
            {
                ip[i].state=0;
                ip[i].owner="";
                ip[i].t=0;
            }
            else
            {
                ip[i].state=3;
                ip[i].t=0;
            }
        }
    }
}
int get_ip_by_owner(string client)
{
    for(int i=1;i<=n;i++)
        if(ip[i].owner==client)
            return i;
    return 0;
}
int get_ip_by_state(int state)
{
    for(int i=1;i<=n;i++)
        if(ip[i].state==state)
            return i;
    return 0;
}

int main()
{
    cin>>n>>t_def>>t_max>>t_min>>h;
    cin>>m;

    while(m--)
    {
        int tc,id,te;
        string client,server,type;
        cin>>tc>>client>>server>>type>>id>>te;

        if(server!=h&&server!="*")
            if(type!="REQ")
                continue;
        if(type!="REQ"&&type!="DIS")
            continue;
        if(server=="*"&&type!="DIS"||(server==h&&type=="DIS"))
            continue;

        update_ips_state(tc);
        
        if(type=="DIS")
        {
            int k=get_ip_by_owner(client);
            if(!k)
                k=get_ip_by_state(0);
            if(!k)
                k=get_ip_by_state(3);
            if(!k) continue;

            ip[k].state=1;
            ip[k].owner=client;
            if(!te) ip[k].t=tc+t_def;
            else
            {
                int t=te-tc;
                t=max(t_min,t),t=min(t_max,t);
                ip[k].t=tc+t;
            }
            cout<<h<<" "<<client<<" "<<"OFR"<<" "<<k<<" "<<ip[k].t<<endl;
        }
        else
        {
            if(server!=h)
            {
                for(int i=1;i<=n;i++)
                    if(ip[i].state==1&&ip[i].owner==client)
                    {
                        ip[i].state=0;
                        ip[i].owner="";
                        ip[i].t=0;
                        continue;
                    }
                continue;
            }
            if(!(id>0&&id<=n&&ip[id].owner==client))
            {
                cout<<h<<" "<<client<<" "<<"NAK"<<" "<<id<<" "<<0<<endl;
                continue;
            }
            else
            {
                ip[id].state=2;
                if(!te) ip[id].t=tc+t_def;
                else
                {
                    int t=te-tc;
                    t=max(t_min,t),t=min(t_max,t);
                    ip[id].t=tc+t;
                }  
                cout<<h<<" "<<client<<" "<<"ACK"<<" "<<id<<" "<<ip[id].t<<endl;
                continue;              
            }
        }
    }
    return 0;
}

本题初次耗时大约在1.5h~2h

202104-4 校门外的树

挺有价值的一道dp题

详见本题解

  • 预处理降时间复杂度
  • 需要一维dp才行

有进步，现在至少能写出来逻辑正确的代码，就是会超复杂度

2020年12月

202012-1 期末预测之安全指数

题目链接

202012-2 期末预测之最佳阈值

自己写了一下发现，这个题也不好写

  • 70分TLE版本

    • vector构造函数写法：vector(v.begin(), v.end());

      是将v[begin(), end()) 区间中 （前闭后开） 的元素拷贝给本身

      所以在下面第21行中vector<pair<int, int>>v(s,s+m);不用s+m-1

    • 二元组 有两种：map和pair，对应头文件分别为map和utility

      map有集合的性质，元素互斥，即map的key不能相同

      pair则只是普通的二元组

      pair使用sort()排序时默认按照first的值排序

      pair的排序写法见此文-是对sort()函数的改写

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <utility>//pair的头文件
    //#include <map>//map的头文件

    using namespace std;
    int m,cnt=0,theta=0;
    const int N=1e5+10;

    pair<int, int> s[N];//!!!
    bool cmp(pair<int,int> a, pair<int,int> b)
    {
        return a.first<b.first;//根据fisrt的值升序排序
    }
    int main()
    {
        cin>>m;
        for(int i=0;i<m;i++)
            scanf("%d %d",&s[i].first,&s[i].second);
        vector<pair<int, int>>v(s,s+m);//前闭后开！！！
        sort(v.begin(), v.end(), cmp);
        for(int i=0;i<m;i++)
        {
            if(i!=0&&v[i].first==v[i-1].first)
                continue;
            int count=0;
            for(int j=0;j<m;j++)
                if(v[j].first<v[i].first&&v[j].second==0||v[j].first>=v[i].first&&v[j].second==1)
                    count++;
            if(count>=cnt)
            {
                cnt=count;
                theta=v[i].first;
            }
        }
        cout<<theta;
        return 0;
    }

  • 满分版本

    害TMD是前缀和的应用——前缀和的应用场景可以总结一下

    注意：遇到s[i].first相同的学生时，应该按第一个考虑！！！

    参考题解

    一维前缀和可以将时间复杂度从O(n^2)降到O(nlogn)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <utility>//pair的头文件

    using namespace std;
    int m,cnt=0,theta=0;
    const int N=1e5+10;

    pair<int, int> s[N];//!!!
    int sum[2][N]={0};//可以称得上点睛之笔
    int main()
    {
        cin>>m;
        for(int i=1;i<=m;i++)
            scanf("%d %d",&s[i].first,&s[i].second);
        sort(s+1, s+m+1);//sort()依照pair的first排序
        for(int i=1;i<=m;i++)
        {
            sum[0][i]=sum[0][i-1]+(s[i].second==0);
            sum[1][i]=sum[1][i-1]+(s[i].second==1);
        }
        for(int i=1;i<=m;i++)
            if(s[i].first!=s[i-1].first && cnt<=sum[0][i-1]+sum[1][m]-sum[1][i-1])
            {
                cnt=sum[0][i-1]+sum[1][m]-sum[1][i-1];
                theta=s[i].first;
            }
        cout<<theta;
        return 0;
    }

2020年9月

202009-1 称检测点查询

题目链接

本题没什么代码细节，要注意的：

202009-2 风险人群筛查

题目链接

这题的AcWing有大问题，不看也罢，官网能过的正确答案AcWing过不了，有缺陷的官网过不了但AcWing能过就离谱

事实证明这种不起眼的小题目还是容易翻车

  • **翻车翻在**：

    一个人可能有多段滞留时长超过k的时段

    然而最初我没考虑这点，直接每当这个人停留时长>k时就cnt++；，后来才意识到上面的问题，修改后果然没问题了

    • 考虑情况不全面了属于是

100分AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
int n,k,t,xl,yd,xr,yu,pass_num[30]={0},stay_num=0;

int main()
{
    cin>>n>>k>>t>>xl>>yd>>xr>>yu;
    for(int j=n;j>0;j--)
    {
        int x,y,cnt=0,cnt_max=0;
        for(int i=0;i<t;i++)
        {
            scanf("%d %d",&x,&y);
            if(x>=xl&&x<=xr&&y>=yd&&y<=yu)
            {
                pass_num[j]++;
                cnt++;
            }
            else
                cnt=0;
            // if(cnt==k)！！！！！！！！！！！！！！！！！！
            //     stay_num++;
            cnt_max=max(cnt,cnt_max);
        }
        if(cnt_max>=k) stay_num++;
    }
    for(int i=1;i<=n;i++)
        if(pass_num[i]>0)
            pass_num[0]++;
    cout<<pass_num[0]<<endl<<stay_num;
    return 0;
}

2020年6月

202006-1 线性分类器

题目链接

自己写的也能拿100，见提交记录的WA提交，但是很繁琐，逻辑也不那么简单

可以看看这篇题解，代码量少很多，同时用到了set集合的特性

202006-2 稀疏向量

题目链接

  • 双指针算法
  • 用vector代替数组就不需要提前开很大的数组，而且可以用vector的许多方便的函数

可以参考这篇题解改一改代码规范

2019年12月

201912-1 报数

题目链接

把边界情况考虑完善就OK

201912-2 回收站选址

题目链接

暴力枚举 复杂度O(n^2)就够