1. 最小互质数

1.1. 题目

链接：https://ac.nowcoder.com/acm/problem/214048
来源：牛客网

题目描述
我们定义两个数互质当且仅当gcd(a, b) = 1。

现在qcjj手里有n个数，分别为a_1, a_2, a_3 \dots a_{n - 1}, a_{n}a
1,a2,a3…an−1,an。问，没有在这n个数中出现过并且与这n个数都互质的最小的数是多少。
qcjj觉得这个问题太简单了，于是她把这个问题交给你来解决。

输入描述:
第一行一个数n(1≤n,ai≤105)，接下来n行，每行一个数，分别代表a1,a2 ,a3…an−1,an。

输出描述:
输出一行代表答案。

1.2. 样例输入&&样例输出

1
2

5
1 2 3 4 5

1

7

说明

1
2

没有在这n个数中出现的数有：6，7，……
6与2， 3， 4不互质，最小的与这n个数互质的数就是7了。

1.3. 思路

没想到暴力算法就能过😔

1.4. 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
33
34
35
36
37
38
39
40

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 1000000;
#define INF 2e9
int a[maxn],vis[maxn];
typedef long long ll;
#define sc(n) scanf("%d",&n)

int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}

int main(){
    int n;cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        vis[a[i]]=1;
    }
    int cnt=0;
    for(int i=0;;i++){
        if(!vis[i]){
            cnt=0;
            for(int j=0;j<n;j++){
            if(gcd(i,a[j])==1){
                cnt++;
            }else break;
            }
        }
        if(cnt==n){
            cout<<i;
            system("pause");
            return 0;
        }
    }
    system("pause");
    return 0;
}

1. GCD

1.1. 题目

链接：https://ac.nowcoder.com/acm/contest/9667/D
来源：牛客网

题目描述
牛牛有一个集合 S 包含 1 至 n 所有的数， 现在他想让你找一个最小的数 k ， 使得在 S 中任意找一个子集 T ， T 集合中的元素个数为 k ， T 中都存在两个数 x ， y ，且 gcd(x,y) > 1 . 如果找不到满足题目条件的 k ，就输出 -1 ,否则输出 k .

gcd(x, y) 为求 x y 的最大公约数。

输入描述:
一个数字 n ( 1 ≤ n ≤ 1e5 )

输出描述:
如果找不到满足题目条件的 k ，就输出 -1 ,否则输出 k .

1.2. 样例输入&&样例输出

样例1

1

3

1

-1

样例2

1

6

1

5

1.3. 思路

数学题，当n<4时 找不到输出-1当n>4时，根据抽屉原则，
把这个区间之内的所有的质数全部放到子集 T 中，
再添加一个非 1 并且没有出现过的数字，必定存在两个数的 gcd 不为 1 。
所以素数筛这个区间的素数，最后的结果加 2 即可。

1.4. 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
33
34

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 3e6+5;
#define INF 2e9
int f[maxn];
typedef long long ll;
#define sc(n) scanf("%d",&n)

bool isprime(int x){
    for(int i=2;i<sqrt(x);i++){
        if(x%i==0)return 0;
    }
    return 1;
}

int main(){
    int n;cin>>n;
    if(n<4)cout<<-1;
    else{
        int cnt=0;
        for(int i=2;i<=n;i++){
            if(!f[i])cnt++;
            for(int j=i+i;j<=n;j+=i){
                f[j]=1;
            }
        }
        cout<<cnt+2;
    }
    system("pause");
    return 0;
}

1. CCA的图

1.1. 题目

链接：https://ac.nowcoder.com/acm/problem/213878
来源：牛客网

题目描述
是不是经常向往外面的天空呢？那就来一场说走就走的旅行吧！
你现在在 s 号城市，想去 t 号城市，城市间有双向道路，保证任意两座城市可以通过这些道路相互到达。
但是出去的人太多了，以至于政府不得不给每条道路打上标记，这个标记是一个数字，政府会规定人们只能走标记在 [L , R] 内的道路。
现在你想求出在 L，R 分别等于多少时，你可以顺利到达 t 号城市，要求 L 尽可能大，在 L 最大的情况下 R 尽可能小 。

输入描述:
第一行四个正整数，n , m , s , t ，分别表示城市数量，道路数量和起点、终点城市编号 。
接下来的 m 行，每行三个正整数 u , v , w ，表示有一条连接 u，v 的双向道路，其标记为 w 。

输出描述:
一行，两个正整数，表示最大的 L 和 在 L 最大的情况下最小的 R 。

1.2. 样例输入&&样例输出

1
2
3
4
5

4 4 1 4
1 3 3
1 2 2
3 4 2
1 4 1

1

2 3

1

n <= 10^6 , m <= 3 × 10^6 ， s,t,u,v <= n , w <= 10^9

1.3. 思路

并查集的应用，还以为是每并一个dfs一次，没想到直接并就行了，
每一次并就检查一下是否联通，L从最大开始并,R从L之后开始并
没看清题目限制数据WA了N发，第二是没有注意到节点是从1开始的又WA了N发
第三则是输入输出的时间限制也被卡了，也WA了N发-_-真是无奈呢😔

1.4. 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
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<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 3e6+5;
#define INF 2e9
int f[maxn];
typedef long long ll;
#define sc(n) scanf("%d",&n)
struct node{
    int x,y,w;
    bool operator<(const node &x)const{
        return w<x.w;
    }
};

node a[maxn];
int find(int x){
    if(x!=f[x])
    f[x]=find(f[x]);
    return f[x];
}

void unionset(int a,int b){
    int fa=find(a);
    int fb=find(b);
    f[fa]=fb;
}

int n,m,s,t,ansl,ansr,L,R;
void init(){
    for(int i=1;i<=n;i++)f[i]=i;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",a[i].x,a[i].y,a[i].w);
    }
    sort(a+1,a+m+1);
    init();
    int S=find(s),T=find(t);
    for(int i=m;i>0;i--){
        unionset(a[i].x,a[i].y);
        if(find(s)==find(t)){
            L=i;
            ansl=a[i].w;
            break;
        }
    }
    init();
    for(int i=L;i<=m;i++){
        unionset(a[i].x,a[i].y);
        if(find(s)==find(t)){
            R=i;
            ansr=a[i].w;
            break;
        }
    }
    printf("%d %d",ansl,ansr);
    system("pause");
    return 0;
}

1. 锦标赛

1.1. 题目

链接：https://ac.nowcoder.com/acm/problem/13223
来源：牛客网

组委会正在为美团点评CodeM大赛的决赛设计新赛制。

比赛有 n 个人参加（其中 n 为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为 m/2 组，每组恰好 2 人，m/2 组的人分别厮杀。我们假定积分高的人肯定获胜，若积分一样，则随机产生获胜者。获胜者获得参加下一轮的资格，输的人被淘汰。重复这个过程，直至决出冠军。

现在请问，参赛者小美最多可以活到第几轮（初始为第0轮）？

输入描述:
第一行一个整数 n (1≤n≤ 2^20)，表示参加比赛的总人数。

接下来 n 个数字（数字范围：-1000000…1000000），表示每个参赛者的积分。

小美是第一个参赛者。
输出描述:
小美最多参赛的轮次。

1.2. 样例输入&&样例输出

1
2

4
4 1 2 3

1

2

1.3. 思路

这题的思想比较巧妙，因为数据只需要读取一次即可，没有必要储存
首先是比小美分数小的才需要统计，再加上小美本人，对统计结果取log2即可

1.4. AC代码

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

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 10000
#define INF 2e9
int a[maxn],b[maxn];
typedef long long ll;

int main(){
    int n,a,cnt=0;cin>>n>>a;
    for(int i=0;i<n-1;i++){
        int b;cin>>b;
        if(b<a)cnt++;
    }
    cout<<(int)log2(++cnt);
    system("pause");
    return 0;
}

1. 锦标赛

1.1. 题目

链接：https://ac.nowcoder.com/acm/problem/13223
来源：牛客网

组委会正在为美团点评CodeM大赛的决赛设计新赛制。

比赛有 n 个人参加（其中 n 为2的幂），每个参赛者根据资格赛和预赛、复赛的成绩，会有不同的积分。比赛采取锦标赛赛制，分轮次进行，设某一轮有 m 个人参加，那么参赛者会被分为 m/2 组，每组恰好 2 人，m/2 组的人分别厮杀。我们假定积分高的人肯定获胜，若积分一样，则随机产生获胜者。获胜者获得参加下一轮的资格，输的人被淘汰。重复这个过程，直至决出冠军。

现在请问，参赛者小美最多可以活到第几轮（初始为第0轮）？

输入描述:
第一行一个整数 n (1≤n≤ 2^20)，表示参加比赛的总人数。

接下来 n 个数字（数字范围：-1000000…1000000），表示每个参赛者的积分。

小美是第一个参赛者。
输出描述:
小美最多参赛的轮次。

1.2. 样例输入&&样例输出

1
2

4
4 1 2 3

1

2

1.3. 思路

这题的思想比较巧妙，因为数据只需要读取一次即可，没有必要储存
首先是比小美分数小的才需要统计，再加上小美本人，对统计结果取log2即可

1.4. AC代码

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

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 10000
#define INF 2e9
int a[maxn],b[maxn];
typedef long long ll;

int main(){
    int n,a,cnt=0;cin>>n>>a;
    for(int i=0;i<n-1;i++){
        int b;cin>>b;
        if(b<a)cnt++;
    }
    cout<<(int)log2(++cnt);
    system("pause");
    return 0;
}

题目描述
n个点，m条边，每条边分为黑边和白边，现在需要挑一些边出来，使得n个点可以两两联通。由于牛牛特别讨厌白边，所以在挑中的边中，让白边最少，输出白边的条数，如果不能两两联通，输出−1.
输入描述:
第一行两个整数n,m. 1≤n,m≤2e5

接下来 m 行， 每行三个整数 x,y,z 代表xy之间有一条边。z的值为0或1，0 代表黑边，1代表白边

输出描述:
一行一个整数， 表示最少的白边数量。如果不能满足题目条件，输出 -1
示例1
输入
复制
4 4
1 2 0
2 3 0
3 4 1
1 4 0
输出
复制
0

看了下自己的博客还是有很多弄得不是很好的地方
接下来几天慢慢把它给装修好吧

1. 题目

Given a sequence of K integers { N​1​​ , N​2​​ , …, N​K​​ }. A continuous subsequence is defined to be { N​i​​ , N​i+1​​ , …, N​j​​ } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

2. 样例输入

10 -10 1 2 3 4 -5 -23 3 7 -21

3. 样例输出

10 1 4

4. 思路

这一题是在慕课上讲过的
所以思路非常简单,寻找最长连续子列和就从做往右一直加,如果小于零了就舍弃进一步,然后就可以辣
还有就是注意审题,题目说如果找不到就输出第一和最后一个数字,之前的代码就是卡在这里

5. 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

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n; cin >> n;
    vector<int>v(n);
	int Thissum = 0, result = -1, head = 0, tail = n-1, temphead=0, temp=0;
	for (int i = 0; i < n; i++) {
		scanf("%d",&v[i]);
        temp+=v[i];
        if(temp<0){
            temp=0;
            temphead=i+1;
        }else if(temp>result){
            result=temp;
            head=temphead;
            tail=i;
        }
	}
	if(result<0)result=0;
	printf("%d %d %d",result,v[head],v[tail]);
    system("pause");
	return 0;
}

1. 题目

At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in’s and out’s, you are supposed to find the ones who have unlocked and locked the door on that day.

Input Specification:
Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format:

ID_number Sign_in_time Sign_out_time
where times are given in the format HH:MM:SS, and ID_number is a string with no more than 15 characters.

Output Specification:
For each test case, output in one line the ID numbers of the persons who have unlocked and locked the door on that day. The two ID numbers must be separated by one space.

Note: It is guaranteed that the records are consistent. That is, the sign in time must be earlier than the sign out time for each person, and there are no two persons sign in or out at the same moment.

2. 样例输入

3 CS301111 15:30:28 17:00:10 SC3021234 08:00:00 11:25:25 CS301133 21:45:00 21:58:40

3. 样例输出

SC3021234 CS301133

4. 思路

被自己以前写的烂代码给惊到……
其实就是比较时间的大小罢了
其实可以转化成秒钟来比较
用不着这么麻烦(((φ(◎ロ◎;)φ)))

5. 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
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

#include <iostream>
#include <vector>
using namespace std;

struct staff {
	string ID;
	string to;
	string off;
};
struct man {
	string ID;
	string time;
};

bool max(string A,string B) {
	int tempA, tempB; tempA = tempB = 0;
	tempA = ((A[0] - '0') * 10) + (A[1] - '0'); tempB = ((B[0] - '0') * 10) + (B[1] - '0');
	if (tempA > tempB) {
		return true;
	}
	else if (tempA < tempB)return false;
	else {
		tempA = tempB = 0;
		tempA = ((A[3] - '0') * 10) + (A[4] - '0'); tempB = ((B[3] - '0') * 10) + (B[4] - '0');
		if (tempA > tempB) {
			return true;
		}
		else if (tempA < tempB)return false;
		else {
			tempA = tempB = 0;
			tempA = ((A[6] - '0') * 10) + (A[7] - '0'); tempB = ((B[6] - '0') * 10) + (B[7] - '0');
			if (tempA > tempB) {
				return true;
			}
			else return false;
		}
	}
}

bool min(string A, string B) {
	int tempA, tempB; tempA = tempB = 0;
	tempA = ((A[0] - '0')*10) + (A[1] - '0'); tempB = ((B[0] - '0')*10) + (B[1] - '0');
	if (tempA < tempB) {
		return true;
	}
	else if (tempA > tempB)return false;
	else {
		tempA = tempB = 0;
		tempA = ((A[3] - '0')*10) + (A[4] - '0'); tempB = ((B[3] - '0')*10) + (B[4] - '0');
		if (tempA < tempB) {
			return true;
		}
		else if(tempA > tempB)return false;
		else {
			tempA = tempB = 0;
			tempA = ((A[6] - '0')*10) + (A[7] - '0'); tempB = ((B[6] - '0')*10) + (B[7] - '0');
			if (tempA < tempB) {
				return true;
			}
			else return false;
		}
	}
}

int main() {
	int N; cin >> N;
	vector<staff>person;
	for (int n = 0; n < N; n++) {
		staff temp;
		cin >> temp.ID >> temp.to >> temp.off;
		person.push_back(temp);
	}
	man Max, Min;
	Max.ID = Min.ID = person[0].ID;
	Max.time = person[0].off; Min.time = person[0].to;
	for (int n = 1; n < person.size(); n++) {
		if (min(person[n].to, Min.time)) {
			Min.ID = person[n].ID;
			Min.time = person[n].to;
		}
		if (max(person[n].off, Max.time)) {
			Max.ID = person[n].ID;
			Max.time = person[n].off;
		}
	}
	cout << Min.ID << " " << Max.ID;
	return 0;
}

下面放柳神的简单代码

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

#include <iostream>
#include <climits>
using namespace std;
int main() {
    int n, minn = INT_MAX, maxn = INT_MIN;
    scanf("%d", &n);
    string unlocked, locked;
    for(int i = 0; i < n; i++) {
        string t;
        cin >> t;
        int h1, m1, s1, h2, m2, s2;
        scanf("%d:%d:%d %d:%d:%d", &h1, &m1, &s1, &h2, &m2, &s2);
        int tempIn = h1 * 3600 + m1 * 60 + s1;
        int tempOut = h2 * 3600 + m2 * 60 + s2;
        if (tempIn < minn) {
            minn = tempIn;
            unlocked = t;
        }
        if (tempOut > maxn) {
            maxn = tempOut;
            locked = t;
        }
    }
    cout << unlocked << " " << locked;
    return 0;
}

1. 题目

Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English.

Input Specification:
Each input file contains one test case. Each case occupies one line which contains an N (≤10​100​​ ).

Output Specification:
For each test case, output in one line the digits of the sum in English words. There must be one space between two consecutive words, but no extra space at the end of a line.

2. 样例输入

12345

3. 样例输出

one five

4. 思路

简单的字符串转化输出
还是非常容易的

5. AC代码

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

#include <iostream>
using namespace std;
string arr[10]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
int main() {
	string number,result; cin >> number;
	int temp = 0;
	for (int n = 0; n < number.size(); n++) {
		temp += (number[n] - '0');
	}
    string s=to_string(temp);
    cout<<arr[s[0]-'0'];
	for(int i=1;i<s.size();i++){
        cout<<" "<<arr[s[i]-'0'];
    }
    system("pause");
	return 0;
}