DYH
关于 文章 标签 分类 随想 导航 清单 时光 CS
DYH
/images/avatar.png

^_^

abc184

 发布于  收录于 Abc

A - Determinant

题意

求二阶行列式

题解

1
2
3
4
5
6
7
8
9

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << a * d - c * b << endl;
    return 0;
}

B - Quizzes

题意

给n个问题，和答题情况，答对加1，答错减1（为0不扣分），初始分数x，求最终分数

阅读全文
 Cpp, Bfs, Dp, Binary_search

李群与李代数

 发布于  收录于 Note Slam

群

与视觉slam有关的群

三维旋转矩阵构成了特殊正交群(special orthogonal group)

$$S O(3)=\left\{R \in \mathbb{R}^{3 \times 3} \mid R R^{T}=I, \operatorname{det}(R)=1\right\}$$

三维变换矩阵构成了特殊欧氏群（special euclidean group）

$$SE(3)=\left\{T=\left[\begin{array}{cc}R & t \\0^{T} & 1\end{array}\right] \in \mathbb{R}^{4 \times 4} \mid R \in SO(3), t \in \mathbb{R}^{3}\right\} $$

阅读全文
 Slam

三维空间的刚体运动

 发布于  收录于 Note Slam

内积与外积

内积

https://img-blog.csdnimg.cn/2020102318240476.png#pic_center

外积

定义 ^ 符号

https://img-blog.csdnimg.cn/20201023183806952.png#pic_center

https://img-blog.csdnimg.cn/2020102318262943.png#pic_center

欧氏变换

euclidean transform

单次欧氏变换

同一个向量在两个坐标系中的表示，坐标系的变换包括一次旋转和一次平移

阅读全文
 Slam

今天你也要来点cmake吗

 发布于  收录于 Note Slam

前言

很早就想写cmake，但是一直懒得写

今天也随便写点cmake

官方对cmake的解释

CMake is an open-source, cross-platform family of tools designed to build, test and package software. CMake is used to control the software compilation process using simple platform and compiler independent configuration files, and generate native makefiles and workspaces that can be used in the compiler environment of your choice. The suite of CMake tools were created by Kitware in response to the need for a powerful, cross-platform build environment for open-source projects such as ITK and VTK.

阅读全文
 Cpp, Slam

Codeforces Round #672 (Div. 2) A~D

 发布于  收录于 Codeforces

A. Cubes Sorting

题意

对于一个数列，每次操作交换相邻的两个数，问是否需要达到n(n-1)/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

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
int main() {
    int _;
    cin >> _;
    while (_--) {
        vector<int> vt;
        int n;
        cin >> n;
        for(int i = 0; i < n; ++i){
            int u;
            cin >> u;
            vt.push_back(u);
        }
        bool ok = false;
        for(int i = 0; i < n - 1; i ++){
            if(vt[i] > vt[i + 1]) continue;
            else {
                ok = true;
                break;
            }
        }
        if(ok) puts("YES"); else puts("NO");
     }
    return 0;
}

B. Rock and Lever

题意

给一数列，判断有多少对数满足 x & y >= x ^ y

阅读全文
 Cpp, Greedy, Data_structure, Dp, Bit, Counting

FFT & NTT

 发布于  收录于 Algorithm

前言

一篇没什么用的文章，记录一下FFT和NTT的板子

fft和ntt的原理参考FFT & NTT

概述

fft和ntt差不多，基础用法就是加速多项式乘法，把多项式从系数表示转成点值表示来方便计算，而要转成点值表示，不能选择任意点。有些点的若干次方是1（实际上可以是-1,+i,-i等等），这样不需要做所有的次方运算，而这些点在复平面单位圆上。在ntt中是拿原根替换fft的单位根。 它们的时间复杂度都是O(nlgn)

阅读全文
 Cpp, Number_theory

无聊的做题记录

 发布于  收录于 Problemlist

数学公式

题目

题解

错排公式

Dn = floor(n!/e + 0.5) = (n - 1) * (Dn-1 + Dn-2)

D1 = 0 , D2 = 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

//457ms/1000ms  488k/32768k
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll mod = 998244353;
int main() {
    ll n;
    cin >> n;
    ll one = 0, to = 1;
    ll ans = 0;
    for(int i = 2; i < n; ++i){
        ans = i * (one + to);
        ans %= mod;
        one = to;
        to = ans;
    }
    cout << ans ;
    return 0;
}

===============================================================

阅读全文
 Cpp, Problemlist

hhu_spider

 发布于  收录于 Python Web

hhu健康打卡脚本（返校版）

环境

必装环境 python， requests

推荐环境 anaconda, pycharm

功能说明

定时打卡、同时多人打卡、发邮件反馈打卡信息、失败重新打卡

（为什么不用发信息，国内手机号在twilio上不能用了）

阅读全文
 Python

Python爬虫

 发布于  收录于 Python Web

urllib模块

不使用

requests模块

获得网页源码

1
2
3
4

import requests
url = 'https://dyhgo.fun'
response = requests.get(url)
print(response.text)

带参数的url和UA伪装

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#测试一下带参数的url和ua伪装
import requests
url = 'https://www.baidu.com/s'
name = input('输入您要搜索的内容，我们将返回百度搜索该信息的网页源码')
params = {
    'wd' : name
}
headers = {
    'User-Agent' : 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/84.0.4147.89 Safari/537.36'
}
response = requests.get(url=url, params=params, headers=headers)
print(response.text)

案例：有道翻译查词

 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

#有道翻译的结果获取，查询look单词并将结果存储
import requests
import json
params = {
    'i': 'look',
    'from': 'AUTO',
    'to': 'AUTO',
    'smartresult': 'dict',
    'client': 'fanyideskweb',
    'salt': '16119129043609',
    'sign': '288cdf16af5fa68411381ba3c9f7f874',
    'lts': '1611912904360',
    'bv': '44a53b4124e8b822ebfd881c5a599938',
    'doctype': 'json',
    'version': '2.1',
    'keyfrom': 'fanyi.web',
    'action': 'FY_BY_REALTlME'
}
url = 'http://fanyi.youdao.com/translate_o?smartresult=dict&smartresult=rule'
headers = {
    'User-Agent' : 'Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/84.0.4147.89 Safari/537.36'
}
response = requests.post(url=url, data=params, headers=headers)
f = open('look.json', 'w', encoding='utf-8')
json.dump(response.json(), fp=f, ensure_ascii=False)
f.close()
print(response.json())

案例：获取豆瓣影单

网站链接

阅读全文
 Python

abc173

 发布于  收录于 Abc

A - Payment

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include<bits/stdc++.h> 
using namespace std;
int main(){
	int n;
	cin>>n;
	int i=1000;
	while(i<n){
		i+=1000;
	}
	cout<<i-n;
	return 0;
}

B - Judge Status Summary

题解

 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<bits/stdc++.h> 
using namespace std;
const int maxn = 1e5+2;
int wa,tle,ac,re;
int main(){
	int n;
	cin>>n;
	while(n--){
		string s;
		cin>>s;
		switch(s[0]){
			case 'A':{
				ac++;
				break;
			}
			case 'W':{
				wa++;
				break;
			}
			case 'T':{
				tle++;
				break;
			}
			default:{
				re++;
				break;
			}
		}
	}
	cout<<"AC x "<<ac<<endl<<"WA x "<<wa<<endl<<"TLE x "<<tle<<endl<<"RE x "<<re<<endl;
	return 0;
}

C - H and V

题解

 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

#include<bits/stdc++.h> 
using namespace std;

char a[7][7];
char b[7][7];
int n,m;int k;
void row(int x){
	for(int i=0;i<m;i++){
		b[x][i] = '.';
	}
}

void col(int x){
	for(int i=0;i<n;i++){
		b[i][x] = '.';
	}
}


void sol(int x,int y){
	for(int i=0;i<n;i++){
		if(x>>i&1){
			row(i);
		}
	}
	
	for(int j=0;j<m;j++){
		if(y>>j&1){
			col(j);
		}
	}
}

int cal(){
	int ans =0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(b[i][j] == '#') ans++;
		}
	}
	return ans;
}

int main(){
	cin>>n>>m;cin>>k;
	char c;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			
		}
	}
	int ans = 0;
	for(int i=0;i<(1<<n);i++){
		for(int j=0;j<(1<<m);j++){
			memcpy(b,a,sizeof(a));
			sol(i,j);
			if (cal() == k) ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

D - Chat in a Circle

题解

 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

#include<bits/stdc++.h> 
using namespace std;
using ll = long long;
ll a[200005];
ll n;
int main(){
	cin>>n;
	for(ll i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n,[](int a,int b){return a>b;});
	if(n==2) {
		cout<<a[0]<<endl;
		exit(0);
	}
	n--;
	ll t;
	ll q = n;
	if(n&1){
		t = (n-1)/2;
		t++;
	}
	else{
		n++;
		t = (n-1)/2;
		t++; 
	}
	ll ans = a[0];
	for(ll i=1;i<t;i++){
		ans += 2LL * a[i];
	}
	if(q%2 == 0){
		ans -= a[t-1];
	}
	cout<<ans<<endl;
	return 0;
}

E - Multiplication 4

题解

 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

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
ll a[200005];
ll n,k;
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a,a+n);
	int L = 0,R = n-1;
	if(k&1){
		if(a[n-1] < 0){
			ll ans = 1;
			for(int i=n-1;i>=n-k;i--){
				ans *= a[i];
				ans %= mod;
			}
			if(ans < 0) cout<<ans+mod<<endl;else cout<<ans<<endl;
			exit(0);
		}
		
		R--,k--;
	}
	while(k){
		ll lv = a[L] * a[L+1];
		ll rv = a[R] * a[R-1];
		
		if(lv < rv){
			R -= 2;
		}	else L += 2;
		k -= 2;
	}
	ll ans = 1;
	for(int i=0;i<L;i++){
		ans *= a[i];
		ans %= mod;
	}
	for(int i=R+1;i<n;i++){
		ans *= a[i];
		ans %= mod;
	}
	if(ans < 0) cout<<ans+mod<<endl;
	else cout<<ans<<endl;
	return 0;
}

F - Intervals on Tree

题解

对于一个森林，点和边对连通图个数的贡献是每个点+1，每条边-1

阅读全文
 Cpp, Graph_theory

某不科学的暑假做题记录

 发布于  收录于 Problemlist

简单思维

题目

题解

直接法，注意数组大小爆long long

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include<bits/stdc++.h>
using ll = long long;
const ll  mod = 1e6+3;
ll fac[mod+2];
int main(){
	fac[0] = 1LL;
	fac[1] = 1LL;
	for(ll i=2;i<mod+2;i++){
		fac[i] = i*fac[i-1];
		fac[i] %= mod;
	}
	ll n;
	while(std::cin>>n){
		if(n>=mod) puts("0");else
		std::cout<<fac[n]<<std::endl;
	}
	return 0;
}

===========================================================================================================

阅读全文
 Cpp, Problemlist