20200601 线性分类器

解题思路

  • 通过直线分类，点不会出现在直线上，在上方时表达式大于零。
  • 建立struct描述点，建立数组存储点。
  • 判断是否每个点都被分类正确

代码

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
#include <bits/stdc++.h>
using namespace std;

struct dian{
	int x;
	int y;
	char type;
};

int main(){
	int num1,num2;
	cin>>num1>>num2;
	dian kkk[num1];
	for(int i = 0;i<num1;i++){
		cin>>kkk[i].x>>kkk[i].y>>kkk[i].type;
	}
	for(int i = 0;i<num2;i++){
		char up,down;
		bool panduan = true;
		up = 'c';
		down = 'c';
		int a,b,c;
		cin>>a>>b>>c;
		for(int k = 0;k<num1;k++){
			if(a+b*kkk[k].x+c*kkk[k].y>0){
				if(up == 'c'){
					up = kkk[k].type;
				}
				else if(up != kkk[k].type){
					cout<<"No"<<endl;
					panduan = false;
					break;
				}
			}
			if(a+b*kkk[k].x+c*kkk[k].y<0){
				if(down == 'c'){
					down = kkk[k].type;
				}
				else if(down != kkk[k].type){
					cout<<"No"<<endl;
					panduan = false;
					break;
				}
			}
			
		}
		if(panduan){
			cout<<"Yes"<<endl;
		}
	}
	return 0;
}

20200602 稀疏向量

解决

  • 最快的方式是使用map来进行解决，但由于对map库不是很熟练没有使用
  • 注意阅读题目要求，发现最终结果可能数字很大，会超出int类型的限制，所以一定要使用longlong类型，否则正确率只有60
  • 采用接收、配对，类似于merge的方法求和，注意不能使用双层循环，会超时
  • 题目感觉比第一题难度还低

    代码

    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
    #include <bits/stdc++.h>
    using namespace std;

    struct xiangl{
    	int u;
    	int v;
    };

    int main(){
    	int len,l1,l2;
    	cin>>len>>l1>>l2;
    	xiangl p1[l1];
    	xiangl p2[l2];
    	long long juanji = 0;
    	for(int i = 0;i<l1;i++){
    		cin>>p1[i].u>>p1[i].v;
    	}
    	for(int i = 0;i<l2;i++){
    		cin>>p2[i].u>>p2[i].v;
    	}
    	int i1 = 0;
    	int i2 = 0;
    	while(true){
    		if(i1>=l1||i2>=l2){
    			break;
    		}
    		else if(p1[i1].u == p2[i2].u){
    			juanji += p1[i1].v*p2[i2].v;
    			i1++;
    			i2++;
    		}
    		else if(p1[i1].u < p2[i2].u){
    			i1++;
    		}
    		else{
    			i2++;
    		}
    	}
    	cout<<juanji;
    	return 0;
    }
    /*
    10 3 4
    4 5
    7 -3
    10 1
    1 10
    4 20
    5 30
    7 40
    输出：-20
    */