csp-202006

2020-08-16

20200601（线性分类器）

思路

我们要设计一个函数classify 用来根据输入的点和直线确定点在这个直线的哪个区域：0/1。我们设置一个数组duiying[][]，duiying[i][j] 表示第i条直线在第j条区域应该是分类A还是分类B，对于每个直线，我们考虑每个点，计算出它在该直线下的区域，然后该区域下对应的类型和该点的类型是否相同。

代码1

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1005
#define MAXM 25

int n, m;
array<int, 3> points[MAXN]; //点
array<int, 3> lines[MAXM]; //线
int duiying[MAXN][2]; //每个线的0/1区域对应哪个类型（0表示对应A，1表示对应B）
bool flag[MAXM]; //表示每个线是否是分类器，默认是

//根据点和线，知道点在线的哪一个区域: 0/1
int classify(int x, int y, int a, int b, int c)
{
    if(b == 0)
    {
        double temp = -(double)a / c;
        return (double)y < temp ? 1 : 0;
    }
    else if(c == 0)
    {
        double temp = -(double)a / b;
        return (double)x > temp ? 1 : 0;
    }
    else if((b > 0 && c < 0) || (b < 0 && c > 0))
    {
        double temp = -(double)b * x / c - (double)a / c;
        return (double)y > temp ? 0 : 1;
    }
    else
    {
        double temp = -(double)b * x / c - (double)a / c;
        return (double)y > temp ? 1 : 0;
    }
}

int main()
{
    //freopen("D://input.txt","r",stdin);
    //init
    memset(duiying, -1, sizeof(duiying));
    for(int i = 0; i < MAXM; i++) flag[i] = true;

    //input points and lines
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        int x, y;
        char type;
        cin >> x >> y >> type;
        points[i] = {x, y, type == 'A' ? 0 : 1};
    }
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        lines[i] = {a, b, c};
    }

    int x, y, a, b, c;
    for(int j = 0; j < m; j++)
    {
        a = lines[j][0];
        b = lines[j][1];
        c = lines[j][2];
        for(int i = 0; i < n; i++)
        {
            x = points[i][0];
            y = points[i][1];
            int area = classify(x, y, a, b, c);
            if(duiying[j][area] == -1)
            {
                duiying[j][area] = points[i][2];
            }
            else if(duiying[j][area] != points[i][2])
            {
                flag[j] = false;
                break;
            }
        }
    }

    //output
    for(int i = 0; i < m; i++)
    {
        if(flag[i] == false)
        {
            cout << "No" << endl;
        }
        else
        {
            cout << "Yes" << endl;
        }
    }

    return 0;
}

20200602（稀疏向量）

代码1

把(index, value)记录在数组当中，这样两个向量就用两个数组vec1, vec2表示了，用i, j 表示两个数组的下标，若两个index相同，则累加结果，然后i++, j++，否则，较小的index对应的数组下标递增。

//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

int n,a,b;
vector<array<int,2>> vec1,vec2; //不要用普通数组，因为不知道数组的大小应该设为多大，若设为最大1e9，则空间炸了

int main(){
	//freopen("D://input.txt","r",stdin);
	//input
	cin>>n>>a>>b;
	//init
	vec1.resize(a);
	vec2.resize(b);
	//input
	int index,value;
	for(int i=0;i<a;i++){
        scanf("%d%d",&index,&value);
		vec1[i] = {index,value};
	}
	for(int i=0;i<b;i++){
        scanf("%d%d",&index,&value);
		vec2[i] = {index,value};
	}

	int p1,p2,i=0,j=0;
	long long sum=0;
	while(i<a&&j<b){ //两个向量的元素都没有遍历完
		p1 = vec1[i][0];
		p2 = vec2[j][0];
		if(p1==p2){
			sum+=(long long)vec1[i][1]*vec2[j][1];
			i++;
			j++;
		}else if(p1<p2){
			i++;
		}else{
			j++;
		}
	}
	//output
	cout<<sum<<endl;

	return 0;
}

超时了，80分。原因是，用cin进行输入，在数据量很大时, cin比scanf慢了很多倍。

20200603（Markdown渲染器）

代码1

我将计算段落和项目的行数的任务交给了dealSeg(int beg, int ed)函数和dealItem(int beg, int ed)函数，只要给出输入的段落或项目所在的开始行和结束行，就可以正确算出来，前提是不要把开始行和结束行输入错了。接着，就可以把精力集中在段与段，段与项目，项目与项目之间该如何处理了。我们用pre标识前面处理了什么类型，pre=-1表示前面什么都没处理，也就是说刚开始，pre=0表示前面处理了段落，pre=1表示前面处理了一个项目。其实，在我的设计中，如果很多个连续的项目后跟了至少一个空行，那么这些项目可以看做是段落，见代码的109行。

若遇到了段落，则只要pre!=-1，就无脑递增行数
若遇到了项目。若前面发现有空行，如108-111行所示，且前面处理了项目，则递增行数；若前面处理了段落，则递增行数。

对于dealSeg与dealItem函数，注意去掉每行的收尾的连续空格。

//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

vector<string> inputs; //所有的行
int w;
int ans=0; //结果，共有多少行
int pre=-1; //
int dealSeg(int beg, int ed){
    int line=0, col=0; //当前正在填写第几行第几列，col是[0,w-1]
    for(int i=beg;i<=ed;i++){
        if(i!=beg){ //新的一行开始了，先加上空格
            if(col!=0){
                col++;
                if(col==w){
                    line++;
                    col=0;
                }
            }
        }
        //去掉每行收尾的连续空格
        int lineBeg=0,lineEd=inputs[i].size()-1;
        while(inputs[i][lineBeg] == ' ') lineBeg++;
        while(inputs[i][lineEd] == ' ') lineEd--;

        for(int j=lineBeg;j<=lineEd;j++){
            if(inputs[i][j] != ' '){
                col++;
                if(col==w){
                    line++;
                    col=0;
                }
            }else{
                if(col != 0){
                    col++;
                    if(col==w){
                        line++;
                        col=0;
                    }
                }
            }
        }
    }
    if(col==0) return line;
    else return line+1;
}
int dealItem(int beg,int ed){
    int line=0,col=0; //由于项目的一行要先输出三个空格，所以col=[0,w-4]
    for(int i=beg;i<=ed;i++){
        if(i != beg){ //新的一行开始了，先加上空格
            if(col!=0){
                col++;
                if(col==w-3){
                    line++;
                    col=0;
                }
            }
        }
        //去掉每行收尾的连续空格
        int lineBeg=2,lineEd=inputs[i].size()-1;
        while(lineBeg<inputs[i].size() && inputs[i][lineBeg] == ' ') lineBeg++;
        while(lineEd>=0 && inputs[i][lineEd] == ' ') lineEd--;

        for(int j=lineBeg;j<=lineEd;j++){
            if(inputs[i][j] != ' '){
                col++;
                if(col==w-3){
                    line++;
                    col=0;
                }
            }else{
                if(col != 0){
                    col++;
                    if(col==w-3){
                        line++;
                        col=0;
                    }
                }
            }
        }
    }
    if(col==0){
        if(line==0) return 1; //这是一个空项目（特判）
        else return line;
    }
    else return line+1;
}
bool isSpaceLine(string& str){
    for(int i=0;i<str.size();i++){
        if(str[i]!=' ')
            return false;
    }
    return true;
}
int main(){
    //freopen("D://input.txt","r",stdin);
    //input, 输入w和inputs
    ios::sync_with_stdio(false);
    cin>>w;
    cin.get();
    string line;
    while(getline(cin,line)){
        inputs.push_back(line);
    }

    int i=0,j;
    while(i<inputs.size()){
        while(i<inputs.size() && isSpaceLine(inputs[i])){
            i++;
            if(pre==1) pre=0; //空行使得段的分隔，前面的项目已经完结，成为一个段落。
        }
        if(i>=inputs.size()) break;
        if(inputs[i].size()>=2 && inputs[i].substr(0,2)=="* "){ //是项目
            //找到j，使得[i,j)是一个项目
            j = i+1;
            while(j<inputs.size() && !isSpaceLine(inputs[j]) && inputs[j].size()>=2 && inputs[j].substr(0,2)=="  "){
                j++;
            }
            //检查是否用多输出一个空行
            if(pre == 0) ans++;

            ans+=dealItem(i,j-1);
            //cout<<"ITEM:"<<"i="<<i<<" j-1="<<j-1<<" "<<dealItem(i,j-1)<<endl;//////
            i = j;
            pre = 1;
        }else{ //是段落
            //找到j，使得[i,j)是一个段落
            j = i+1;
            while(j<inputs.size() && !isSpaceLine(inputs[j]) && !(inputs[j].size()>=2 && inputs[j].substr(0,2)=="* ")){
                //不是空白行，不是项目的开头行，则是属于段落
                j++;
            }
            if(pre==0 || pre==1) ans++;
            ans+=dealSeg(i,j-1);
            i = j;
            pre = 0;
        }
    }
    cout<<ans<<endl;
}

超时，80分。原因是输入太慢了，用ios::sync_with_stdio(false)

20200604（1246）

代码1

通过一个循环，计算出第n秒的串是什么（我知道，存储容量肯定不够，2的10亿次方，自己算一下这有多大），然后用正则表达式计算包含了多少个S串。

//freopen("D://input.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;

string str = "1"; //保存每个经过以2为底的幂运算的结果
int n;
string S;
long long ans = 0;

int main(){
    //input
    cin>>n>>S;

    for(int i=0;i<n;i++){
        string temp;
        for(int j=0;j<str.size();j++){
            if(str[j]=='1'){
                temp += "2";
            }else if(str[j]=='2'){
                temp += "4";
            }else if(str[j] == '4'){
                temp += "16";
            }else{
                temp += "64";
            }
        }
        str = temp;
    }
    regex e(S);
    smatch sm;
    string::const_iterator iterBeg = str.begin();
    string::const_iterator iterEnd = str.end();
    while(regex_search(iterBeg, iterEnd, sm, e)){
        ans++;
        ans %= 998244353;
        iterBeg = sm[0].second;
    }
    cout<<ans<<endl;
}
//---------------------------------------------------------------------------------------------------------------------------------

超时，32分。

代码2

数字中只可能函数有1, 2, 4, 6，根据观察只可能产生的1数位和2数位是{1,2,4,6,16,26,41,42,44,46,61,62,64,66}。因此我们就对一个串，比如6416，看它可能产生哪些数位，以6416为例，6可以产生6,4,64; 4可以产生1,6,16; 1可以产生2; 6可以产生6,4,64; 64可以产生6,4,1,6,64,41,16,但是其中的6,4,64,1,6,16和6与4产生的重合了，所以就只剩下41; 41可以产生1,6,2,16,62,但是1,6,16,2和4与1产生的重合了，所以就剩下62; 16可以产生2,6,4,26,64，但是2,6,4,6,4和1与6产生的重合了，所以就剩下了26。所以最终结果是1,4,4,6,6,6,16,26,41,62,64,64，观察6416的下一个串6416264，结果一模一样。

我们可以设置一个矩阵mat，(14,14)的，保存每个数位在经过一次变换后得到的数位，比如16经过变换后得到26（要去掉与1和6重合的部分，所以才只有26一个）。我们可以设置1的id是0, 2的id是1, 4的id是2，等等，这样就可以方便将变换关系保存在mat中。

经过每次变换，我们都保存结果串中每种数位有多少个，比如说16对应的就是，1有1个, 6有1个，16有1个。这样，可以用一个数组int initMat[14] 来保存这个信息。如何计算每次变换后，每种数位有多少个呢？我们有变换矩阵，有目前每种数位有多少个（intMat），可以计算出来的。经过思考，initMat*mat 就是可以产生这个结果。如果要经过n次变换，就让initMat乘以n个mat。

为了效率，我们可以快速幂的方法加速上述运算。

//freopen("D://input.txt","r",stdin);
//ios::sync_with_stdio(false);
#include<bits/stdc++.h>
using namespace std;

int n,M = 998244353;
string s;
int baseEle[14] = {1,2,4,6,16,26,41,42,44,46,61,62,64,66};
vector<int> convert[14] = {{2},{4},{1,6,16},{4,6,64},{26},{46},{62},{64},{61},{66},{42},{44},{41},{46}}; //error: 最后一个46写成41了
unordered_map<int,int> mp = {{1,0},{2,1},{4,2},{6,3},{16,4},{26,5},{41,6},{42,7},{44,8},{46,9},{61,10},{62,11},{64,12},{66,13}};
int initMat[14];
int mat[14][14];

void mult1(int a[], int b[][14]){
    //init
    int c[14];
    memset(c,0,sizeof(c));

    for(int j=0;j<14;j++){
        for(int i=0;i<14;i++){
            long long temp = (long long)a[i]*b[i][j];
            int temp2 = (int)(temp%M);
            c[j] += temp2;
            c[j] %= M;
        }
    }

    //out
    for(int i=0;i<14;i++){
        a[i] = c[i];
    }
}
void mult2(int a[][14]){
    //init
    int b[14][14];
    memset(b,0,sizeof(b));

    for(int i=0;i<14;i++){
        for(int j=0;j<14;j++){
            for(int k=0;k<14;k++){
                long long temp = (long long)a[i][k]*a[k][j];
                int temp2 = (int)(temp%M);
                b[i][j] += temp2;
                b[i][j] %= M;
            }
        }
    }

    //out
    for(int i=0;i<14;i++){
        for(int j=0;j<14;j++){
            a[i][j] = b[i][j];
        }
    }
}
int main(){
    //init
    memset(initMat,0,sizeof(initMat));
    initMat[0] = 1;
    memset(mat,0,sizeof(mat));
    for(int i=0;i<14;i++){
        for(int j=0;j<convert[i].size();j++){
            int k = mp[convert[i][j]]; //error
            mat[i][k] = 1;
        }
    }

    cin>>n>>s;
    while(n>0){
        if(n%2==1){
            mult1(initMat,mat);
        }
        mult2(mat);
        n = n>>1;
    }
    cout<<initMat[mp[stoi(s)]];
}

96分。果然这题，又涉及到long long相关的错误。

20200605（乔乔与牛牛逛超市）

代码1

这题的做法可以总结为“水平选择，纵向贪心”。我们用邻接表发来建立商品与商品之间的关系，若有（x->y，1）边，则意味着必须有y，才能有x；若有边（x->y，2）边，则意味着必须要有y，x才能买正好$L_y$ 和 $R_y$ 件。我们建立一个vector\ itemNum，表示已经考虑了哪些商品并且买了多少件，itemNum[1]=0表示考虑了1商品并且1商品的个数为0，已经考虑好的商品不要去改个数。采用回溯法，向下深挖时将商品添加到itemNum中，回溯时将商品从itemNum中删除。从第1个商品开始考虑，进行回溯法，然后考虑第2个商品，若第2个商品在回溯时，需要第i个商品且第i个商品被考虑过且第i个商品的个数为0，则这是要继续考虑第i个商品但是不要再从i商品继续向下考虑了，否则，不再继续考虑，然后是第3，第4个…….

只有x被购买了，y才能被购买 意思不是先买了x，再买y，而是x和y可以同时买，也满足这个条件。

代码2

代码1的思路没法做，原因是每个点可能依赖很多个点，而且有不同的依赖类型，没法向下做了。