博客

第一次CCF计算机软件能力认证

  • Post author:
  • Post category:其他



感受：


又是收获满满（

啥也不会

）的一套题呢 _(xз」∠)_

感觉自己的效率不高，没能按照目标做到一天一套题目加解析。

主要是因为刷题太少导致对常用函数不熟悉、经典思路没见过，所以做题慢，希望后面能够提高效率。

还有一个花时间较长的原因是T1、T2 这种简单题目在写的时候采用的是复杂度比较高的做法，因为数据小所以怎么都能过，但是听完答案在写题解的时候还是会重写一遍更优的做法。


主要收获：

题目编号 题目名称 知识点
T3 201403-3 命令行选项 字符串处理（getline()、getchar() 等）
T4 201403-4 无线网络 拆点+BFS
T5 201403-5 任务调度 动态规划



201403-1 相反数

简单题，一开始写是用两层 for 循环遍历，计算每两个数之间的和是否等于0，同时统计答案，复杂度是



O

(

N

2

)

O(N^2)






O


(



N










2









)





的。

标算是直接开一个桶统计等于该绝对值的数的个数，最后扫一遍桶，若有两个数的绝对值相同则答案+1。复杂度是



O

(

N

)

O(N)






O


(


N


)





的。

代码： 

#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=1005;

int n,a[maxn],cnt;

int main()
{
	cin>> n;
	for(int i=0,x;i<n;i++) cin>>x,a[abs(x)]++;
	for(int i=0;i<maxn;i++)
		if(a[i]==2) cnt++;
	cout<<cnt<<'\n';
	return 0;
}



201403-2 窗口

emmm 这题我比较憨，直接开了屏幕像素那么大的二维数组（



2560

×

1440

2560\times 1440






2560




×








1440





）每个像素模拟，还好数据小能过。

更好的做法是记录每个窗口的两个角，然后据此边界判断和模拟，比较简单就不细说了，直接放代码： 

#include <iostream>
using namespace std;
const int maxn=15; 

struct Window{
	int x1,x2,y1,y2,id;
}w[maxn];

int n,m;

int get(int x,int y){
	for(int i=n;i>0;i--)
		if(w[i].x1<=x && w[i].x2>=x && w[i].y1<=y && w[i].y2>=y)
			return i;
	return 0;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>w[i].x1>>w[i].y1>>w[i].x2>>w[i].y2;
		w[i].id=i;
	}
	while(m--){
		int x,y;
		cin>>x>>y;
		int t=get(x,y);
		if(!t) puts("IGNORED");
		else{
			cout<<w[t].id<<'\n';
			auto r=w[t];
			for(int i=t;i<n;i++) w[i]=w[i+1];
			w[n]=r;
		} 
	}
	return 0;
}



201403-3 命令行选项

模拟题，因为是早年题，所以还没有像近几年的大模拟这么变态，坑点是命令的参数有可能和命令长得一样，比如 -a，- -，-1a，1-1 这些都算合法的参数。

改了一会，反复读了好几次题，稀里糊涂也算过了，代码比较丑： 

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

string cmd,name,s; 
int arg[30],t,kase;
vector<string> line;

void solve(){
	bool vis[30]={0};
	string val[26];
	int sz=line.size();
	for(int i=1;i<sz;i++){
		if(line[i][0]!='-') break;
		if( !(line[i].size()==2 && line[i][1]-'a'>=0 && line[i][1]-'a'<26) ) break;
		if(arg[line[i][1]-'a']==-1) break;
		if(i==sz-1){
			if(!arg[line[i][1]-'a']) vis[line[i][1]-'a']=1;
			break;
		}
		vis[line[i][1]-'a']=1;
		if(arg[line[i][1]-'a']){
			val[line[i][1]-'a']=line[i+1];
			i++;
		}
	}
	cout<<"Case "<<++kase<<": ";
	for(int i=0;i<26;i++){
		if(vis[i]){
			cout<<'-'<<char('a'+i)<<' ';
			if(arg[i]) cout<<val[i]<<" ";
		}
	}
	cout<<'\n';
	return;
}

int main()
{
	cin>>cmd;
	memset(arg,-1,sizeof arg);
	int sz=cmd.size();
	for(int i=0;i<sz;i++){
		if(cmd[i]==':') continue;
		if(i==sz-1) {
			arg[cmd[i]-'a']=0;
			continue;
		}
		if(cmd[i+1]==':') arg[cmd[i]-'a']=1;
		else arg[cmd[i]-'a']=0;
	}
	cin>>t;
	
	cin.ignore();
	char rec[256];
	while(t--){
		cin.getline(rec, 256);
		char* p = strtok(rec, " ");
		while(p){
			line.push_back(p);
			p = strtok(NULL, " ");
		}
		solve();
		line.clear();
	}
	return 0;
}

我认为此题中涉及到的对字符串处理的常用函数的掌握更为关键，所以这里记录一下常用的函数及它们的用法。

一、cin、getline()、cin.getline() 这三个的用法

这里推荐

一篇不错的博客


用法总结：

  • cin 读入字符串或者字符数组的时，遇到空格、tab、回车后结束读入数据流。
  • cin.getline(字符指针(char*),字符个数N(int),结束符(char));

    共有3个参数，当第三个参数省略时，系统默认为’\0’

    此函数读到字符串中的空格时，将继续读取，直到它读取至最大指定的字符数，或直到按下回车键。

    【用法举例】cin.getline(a, n, ‘结束符’)，a是字符数组，不能是字符串，最后读入n-1个字符，最后一个是’/0’默认结束符是’/n’。

    具体比如 cin.getline(m, 5, ‘a’); 当输入 jlkjkljkl 时输出 jklj ，输入 jkaljkljkl 时，输出 jk
  • getline(cin, str) 读入一整行的字符串，包括空格也读入，第二个参数为string类型，而不是char*

    【注意】同时用cin和getline时，要在getline前加getchar() 清空缓存（也可用其他方法），否则getline() 读入的并不是用户的输入而是一个回车。

    其实还有第三个参数 getline(istream &is , string &str , char delim); delim为终结符，表示遇到这个字符停止读入，不指定时默认为‘\n’。

二、stringstream

使用时要包含头文件 #include <sstream>，主要的用处：

1、在数字和字符串之间的转换时有奇效（类似 Python 中 eval 函数）：

博客链接（看用例）


2、用于分割被空格、制表符等符号分割的字符串：

知乎链接（看用例）

对于 T3 这道题，可以配合getline() （别忘了getchar）读入整行的命令及参数，再通过stringstream以空格分割字符串，重新读入到vector中便于后续处理。 

......
getchar();  // 将n后面的回车过滤掉
for (int C = 1; C <= n; C ++ )
{
    getline(cin, str);
    stringstream ssin(str);  //ssin是变量名，可随意更改 
    vector<string> ops; //options
    while (ssin >> str) ops.push_back(str);
    solve(ops);
}

三、strtok()

那么有没有一个函数可以像Python中split函数一样，更普适的、可以自己指定分割符的函数呢？

答案就是 strtok()，使用时要包含头文件 #include <string>

函数原型为 char *strtok(char s[], const char *delim);

分解字符串为一组字符串。s为要分解的字符串，delim为分隔符字符串。首次调用时，s指向要分解的字符串，之后再次调用要把s设成NULL


多次调用strtok的详细讲解

这里给出用例： 

#include <stdio.h>  
#include <string.h>  
int main ()  
{  
  char str[] ="- This, a sample string.";  
  char * pch;  
  printf ("Splitting string \"%s\" into tokens:\n",str);  
  pch = strtok (str," ,.-");  
  while (pch != NULL)  
  {  
    printf ("%s\n",pch);  
    pch = strtok (NULL, " ,.-");  
  }  
  return 0;  
} 
/*  输出：
This
a
sample
string
*/



201403-4 无线网络

这道题目一开始读题后就想到用BFS，具体是先按照距离判断连边建图，之后从1号点开始BFS，在压入队列时判断一下走到当前点经过的新增设路由器数目，若超过 k 则不压入队列；同时已经访问过的点也不再压入队列（正常BFS的判断条件）。

后面仔细一想发觉

有问题

：以3号结点为途径结点举例，有可能存在更长的路径到达3号点，这条路径比1到3的最短路的 新增设路由器数目要少，但是因为已经通过短的那条路访问过3号结点，因此无法记录这条路径，而最短路有可能在后续搜索时因为经过的新增设路由器太多而被剪掉，这条长路径反而有可能是正确答案。

写上面的错解交了一发，在CSP官网拿了90分，后来再读题时发现计算距离要转换成 long long，又交了一发拿了100，然而同样的代码在AcWing上提交就WA了，可见CSP的数据有多水。

正解是

拆点+BFS

拆点这一步之前没见过，想不出来…

拆点法BFS是广搜的一种变化形式。如限制某些特殊状态最多不能经历K次，这种形势下，为了到达目标状态，并且所经历的路径符合要求，往往需要重复遍历已经访问过的状态，因此，我们需要把原问题的单个状态点拆分成更多的基于此状态的不同状态，形如 [状态i，经历了k个特殊点]，方便问题的求解。

具体到这道题目是开一个 dis[id][cnt] 数组，记录从 1 号点到 id 号点恰经过k个新路由器的最短路长度，相当于将原本一个编号为 id 的点拆成 k+1 个点，在这个新的图中进行 BFS，最后统计 dis[2][i]



0

≤

i

≤

k

 

~0\leq i \leq k~








0




≤








i




≤








k







的最大值即可

【注】题目规定1号点是起点，2号点为终点。

代码如下： 

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=205;

struct Point{int x, y;}p[maxn];
struct Node{int id,cnt;}; //cnt是使用增设的新路由器数目 

int m,n,k,r;
int dis[maxn][105]; // id, cnt 从 1 号点到id号点经过k个新路由器的最短路长度 
vector<int> g[maxn];

bool check(Point p1,Point p2){
	ll dx=p1.x-p2.x;
	ll dy=p1.y-p2.y;
	return (ll)r*r>=dx*dx+dy*dy;
}

int BFS(){
	memset(dis,0x3f,sizeof dis);
	queue<Node> q;
	q.push(Node{1,0});
	dis[1][0]=0;
	while(!q.empty()){
		Node u=q.front();
		q.pop();
		for(int x:g[u.id]){
			int tim=u.cnt;
			if(x>n) tim++;
			if(tim<=k){
				if(dis[x][tim]>dis[u.id][u.cnt]+1){
					dis[x][tim]=dis[u.id][u.cnt]+1;
					q.push(Node{x,tim});
				}				
			}
		}
	}
	int res=INF;
	for(int i=0;i<=k;i++) 
		res=min(res,dis[2][i]);
	return res-1;
}

int main()
{
	cin >> n >> m >> k >> r;
	for(int i=1;i<=n+m;i++)
		cin>>p[i].x>>p[i].y;
	for(int i=1;i<=m+n;i++)
		for(int j=1;j<i;j++)
			if(check(p[i],p[j])){
				g[i].push_back(j);
				g[j].push_back(i);
			}
	cout << BFS() << '\n';
	return 0;
}

其实T4也可以看作一道DP题，毕竟 DP 问题是特殊的最短路问题（拓扑图上的最短路问题），而这里权值为1就退化为可用BFS求解



201403-5 任务调度

比较难的一道DP，推荐一篇大佬的

题解


在给出状态含义和状态转移方程之前，首先要发现3个性质：

  • 性质1：两个CPU 和 两个CPU加GPU 一样，都是占用全部机器，没法和别的兼容同时执行，因此可以取这两个调度时间的最小值，记为调度3（占用全部设备）。规定 ：

    调度1为占用一个CPU （CPU1或CPU2）

    调度2为占用一个CPU和一个GPU（CPU1+GPU或CPU2+GPU）

    调度3为占用全部设备
  • 性质2：调度3可以放在其它所有任务之后执行，不会影响整体时间（这种占据所有资源，所以直接将占用时间累加到总时间上即可）
  • 性质3：假设所有使用调度1和2的任务 占用CPU1总时间为 i，CPU2总时间为 j，GPU总时间为 k，则一定存在一种调度顺序满足使用总时间的最小值为max(i, j, k)。

    主要矛盾为 调度2和调度2会由于争夺GPU而产生冲突，可以通过分类讨论



    k

    <

    max

    ⁡

    (

    i

    ,

    j

    )

    k<\max(i,j)






    k




    <








    max


    (


    i


    ,




    j


    )





    和



    k

    >

    max

    ⁡

    (

    i

    ,

    j

    )

    k>\max(i,j)






    k




    >








    max


    (


    i


    ,




    j


    )





    两种情形，两个CPU错峰使用GPU即可，不会对最少总时间有影响。

f[u][i][j][k]表示只考虑前u个任务，在CPU1使用总时间 i，CPU2使用总时间 j,GPU使用总时间 k 时，调度3占用时间的最小值，状态转移可以通过任务u的调度选择来完成。

需要使用滚动数组节省空间，否则会MLE。 

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int INF=0x3f3f3f3f; 
const int maxn=205;

int f[2][maxn][maxn][maxn];
int n,c[maxn][3];
 
int main()
{
	cin>>n;
	int m=0;
	for(int i=1;i<=n;i++){
		int x,y,z,w;
		cin>>x>>y>>z>>w;
		c[i][0]=x, c[i][1]=z, c[i][2]=min(y,w);
		m+=x;
	}
	m=(m+1)/2; // m表示所有任务均只使用一个CPU的总时间，也就是所有任务要完成的最大时间，有两个CPU，所以可以除以2，由于C++除法特性，所以先+1
	memset(f,0x3f,sizeof f);
	f[0][0][0][0]=0;
	for(int u=1;u<=n;u++){
		register int x=c[u][0],y=c[u][1],z=c[u][2], w=(u-1)&1;
		for(int i=0;i<=m;i++)
			for(int j=0;j<=m;j++)
				for(int k=0;k<=m;k++){
					int &v=f[u&1][i][j][k];
					v=f[w][i][j][k]+z; //任务u选择调度3
					if(i>=x) v=min(v,f[w][i-x][j][k]); //任务u选择CPU1
					if(j>=x) v=min(v,f[w][i][j-x][k]); //选择CPU2
					if(i>=y && k>=y) v=min(v,f[w][i-y][j][k-y]); //选CPU1和GPU
					if(j>=y && k>=y) v=min(v,f[w][i][j-y][k-y]); //选CPU2和GPU
				}
	}
	int res=INF,w=n&1;
	for(int i=0;i<=m;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<=m;k++)
				res=min(res, f[w][i][j][k]+max({i,j,k}));//总时间要算加上调度1，2时间：max(i,j,k)
	cout<<res<<'\n';	
	return 0;
}

为了检验自己是否学会（

抄明白

）这道题，练习一道类似的题目

luogu P2224

这道题目看似是T5的弱化版，同为进程调度DP 并且机器数是2比T5要少，然而模仿着T5写出如下代码后： 

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int INF=1e5;
const int maxn=6e3+5;
const int N=1e4+5;

int n, c[maxn][3];
int f[2][N][N],t1,t2,t3;

int main()
{
	cin >> n;
	int m=0;
	for(int i=1;i<=n;i++){
		cin>>t1>>t2>>t3;
		c[i][0]=(t1?t1:INF);
		c[i][1]=(t2?t2:INF);
		c[i][2]=(t3?t3:INF);
		m+=min({c[i][0],c[i][1],c[i][2]});
	}
	memset(f,0x3f,sizeof f);
	f[0][0][0]=0;
	for(int u=1;u<=n;u++){
		register int x=c[u][0],y=c[u][1],z=c[u][2],w=(u-1)&1;
		for(int i=0;i<=m;i++)
			for(int j=0;j<=m;j++){
				int &v=f[u&1][i][j];
				v=f[w][i][j]+z;
				if(i>=x) v=min(v,f[w][i-x][j]);
				if(j>=y) v=min(v,f[w][i][j-y]);
			}
	}	
	int res=INF,w=n&1;
	for(int i=0;i<=m;i++)
		for(int j=0;j<=m;j++)
			res=min(res,f[w][i][j]+max(i,j));
	cout<<res<<'\n';
	return 0;
}

提交评测一下，我们可以惊喜的发现 既 MLE 又 TLE …

当然，代码的正确性是肯定的，毕竟做法没问题。后来看了大佬们的

题解

之后。才学会这个玄妙的状态表示：




f

[

i

]

[

j

]

f[i][j]






f


[


i


]


[


j


]





表示处理前



i

i






i





个任务，第一台机器耗时为



j

j






j





时第二台机器的最小耗时，状态转移方程为：




f

[

i

]

[

j

]

=

min

⁡

{

f

[

i

−

1

]

[

j

]

+

t

2

[

i

]

,

f

[

i

−

1

]

[

j

−

t

1

[

i

]

]

,

f

[

i

−

1

]

[

j

−

t

3

[

i

]

]

+

t

3

[

i

]

}

f[i][j]=\min\{f[i−1][j]+t_2[i],f[i−1][j−t_1[i]],f[i−1][j−t_3[i]]+t_3[i]\}






f


[


i


]


[


j


]




=








min


{



f


[


i




−








1


]


[


j


]




+









t










2





​












[


i


]


,




f


[


i




−








1


]


[


j




−









t










1





​












[


i


]]


,




f


[


i




−








1


]


[


j




−









t










3





​












[


i


]]




+









t










3





​












[


i


]}




最后要求的答案为



min

⁡

0

≤

i

≤

m

{

max

⁡

{

f

[

n

]

[

i

]

,

i

}

}

\underset{0\leq i \leq m}{\min}\{\max\{ f[n][i] , i \} \}
















0


≤


i


≤


m










min






​












{



max


{



f


[


n


]


[


i


]


,




i


}}





(m为上界)

AC代码： 

// luogu P2224 
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=6e3+5;

int n, c[maxn][3], f[2][maxn*5];

int main()
{
	cin >> n;
	for(int i=1;i<=n;i++) 
		cin>> c[i][0] >> c[i][1] >> c[i][2];
	memset(f,0x3f,sizeof f);
	f[0][0]=0;
	int m=0;
	for(int u=1;u<=n;u++){
		memset(f[u&1],0x3f,sizeof f[u&1]); //记得每次都要初始化数组！ 
		register int t1=c[u][0],t2=c[u][1],t3=c[u][2],w=(u-1)&1;
		m+=max(t1,t3); //前 u 个任务时间上界至多为 m 
		for(int i=0;i<=m;i++){
			int& v=f[u&1][i];
			if(t1 && i>=t1) v=min(v,f[w][i-t1]); //选择A机器
			if(t2) v=min(v,f[w][i]+t2); //选择B机器
			if(t3 && i>=t3) v=min(v,f[w][i-t3]+t3);	//选择A B机器
		}
	}
	int res=INF,w=n&1;
	for(int i=0;i<=m;i++)
		res=min(res, max(f[w][i],i));
	cout<<res<<'\n';
	return 0;
}

这道题还可以进一步将



f

[

]

f[ ]






f


[


]





数组压至一维（内层循环倒着扫即可），并且还可以优化枚举的下界，具体做法都可以在上面的题解链接中找到。

总的来说，这种把数组下标当作最优状态求答案的DP比较少见。


版权声明：本文为weixin_46286993原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。