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
89
90
91
92
93
94

#include <iostream>
using namespace std;
char c;
char str1[10], str2[10];
bool vis[10000];
int ttt(char x) {
	if (x == 'A') return 1;
	if (x == 'B') return 2;
	if (x == 'C') return 3;
	return 0;
}
int S, T;
int q[10000];
int conv(int one, int two, int three, int four) {
	return one*1000+two*100+three*10+four;
}
void bfs(int S) {
	int head = 0;
	int tail = 1;
	q[0] = S;
	vis[S] = true;
	int now, tmp, pos;
	int one, two, three, four;
	while (head < tail) {
		now = q[head++];
		for (tmp = now, pos = 4; tmp % 10; tmp /= 10, --pos);
		tmp = now;
		four = tmp % 10; tmp /= 10;
		three = tmp % 10; tmp /= 10;
		two = tmp % 10; tmp /= 10;
		one = tmp;
		if (pos == 1) {
			tmp = conv(three, two, one, four);
			if (!vis[tmp]) {
				vis[tmp] = true;
				q[tail++] = tmp;
			}
			tmp = conv(two, one, three, four);
			if (!vis[tmp]) {
				vis[tmp] = true;
				q[tail++] = tmp;
			}
			continue;
		}
		if (pos == 2) {
			tmp = conv(two, one, three, four);
			if (!vis[tmp]) {
				vis[tmp] = true;
				q[tail++] = tmp;
			}
			tmp = conv(one, four, three, two);
			if (!vis[tmp]) {
				vis[tmp] = true;
				q[tail++] = tmp;
			}
			continue;
		}
		if (pos == 3) {
			tmp = conv(one, two, four, three);
			if (!vis[tmp]) {
				vis[tmp] = true;
				q[tail++] = tmp;
			}
			tmp = conv(three, two, one, four);
			if (!vis[tmp]) {
				vis[tmp] = true;
				q[tail++] = tmp;
			}
			continue;
		}
		if (pos == 4) {
			tmp = conv(one, four, three, two);
			if (!vis[tmp]) {
				vis[tmp] = true;
				q[tail++] = tmp;
			}
			tmp = conv(one, two, four, three);
			if (!vis[tmp]) {
				vis[tmp] = true;
				q[tail++] = tmp;
			}
			continue;
		}
	}
}
int main () {
	cin >> c;	str1[1] = c;	cin >> c;	str1[2] = c;	cin >> c;	str1[3] = c;	cin >> c;	str1[4] = c;
	cin >> c;	str2[1] = c;	cin >> c;	str2[2] = c;	cin >> c;	str2[3] = c;	cin >> c;	str2[4] = c;
	S = ttt(str1[1])*1000+ttt(str1[2])*100+ttt(str1[3])*10+ttt(str1[4]);
	T = ttt(str2[1])*1000+ttt(str2[2])*100+ttt(str2[3])*10+ttt(str2[4]);
	bfs(S);
	if (vis[T]) cout << "YES";
	else cout << "NO";
}

 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

#include <cstdio>
#include <map>
using namespace std;
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; c < '0' || c > '9'; c = getchar())if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
long long n, k, x, ans;
int main () {
	n = getint();
	k = getint();
	if (n == 1) {
		printf("0");
		return 0;
	}
	if (k >= (n/2)) {
		x = n;
		x = x * (x-1);
		x = x / 2;
		printf("%I64d", x);
		return 0;
	}
	ans = k * (n*2 - k*2 - 1);
	printf("%I64d",ans);
	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
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 <cstdio>
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; c < '0' || c > '9'; c = getchar())if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
int n, k, node = 0;
char str[100100];
int dis[100100];
int lookupless(int l, int r, int x) {
	int mid;
	while (l < r) {
		mid = (l+r+1)>>1;
		if (dis[mid] > x) r = mid-1;
		else l = mid;
	}
	if (dis[l] > x) return 0;
	return l;
}
int lookupgrea(int l, int r, int x) {
	int mid;
	while (l < r) {
		mid = (l+r)>>1;
		if (dis[mid] < x) l = mid+1;
		else r = mid;
	}
	if (dis[r] < x) return 0;
	return r;
}
bool check(int x) {
	for (int i = 1; i <= node; ++i) {
		int curr = 0, f;
		if (i < node) if (f = lookupless(i+1, node, dis[i]+x)) curr += (f - i);
		if (2 <= i) if (f = lookupgrea(1, i-1, dis[i]-x)) curr += (i - f);
		if (curr >= k) return true;
	}
	return false;
}
int main () {
	n = getint(); k = getint();
	scanf("%s", str);
	for (int i = 0; i < n; ++i)
		if (str[i] == '0') dis[++node] = i;
	int l = 1, r = n, mid;
	while (l < r) {
		mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid+1;
	}
	printf("%d", r);
}

 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

#include <cstdio>
int getint() {
	int r = 0, k = 1; char c = getchar();
	for (; c < '0' || c > '9'; c = getchar())if (c == '-') k = -1;
	for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
	return r * k;
}
int n, m;
const int maxn = 100100;
int A[maxn], B[maxn];
int sta[maxn], slen = 0;
int rd[maxn];
bool insta[maxn];
struct edge_type {
	int to, next;
} edge[maxn<<1];
int h[maxn], cnte;
void ins(int u, int v) {
	edge[++cnte].to = v;
	edge[cnte].next = h[u];
	h[u] = cnte;
}
void build(int x) {
	cnte = 1;
	for (int i = 1; i <= n; ++i) h[i] = rd[i] = 0;
	for (int i = 1; i <= x; ++i) { ins(A[i], B[i]); ++rd[B[i]]; }
}
bool check(int x) {
	build(x);
	slen = 0;
	for (int i = 1; i <= n; ++i) { insta[i] = false; if (rd[i] == 0) { sta[slen++] = i; insta[i] = true; } }
	int now;
	while (slen) {
		if (slen != 1) return false;
		now = sta[--slen];
		for (int i = h[now]; i; i = edge[i].next) {
			if (insta[edge[i].to]) return false;
			--rd[edge[i].to];
			if (!rd[edge[i].to]) {
				sta[slen++] = edge[i].to;
				insta[edge[i].to] = true;
			}
		}
	}
	return true;
}
int main () {
	n = getint(); m = getint();
	for (int i = 1; i <= m; ++i) { A[i] = getint(); B[i] = getint(); }
	int l = 1, r = m, mid;
	while (l < r) {
		mid = (l+r)>>1;
		if (check(mid)) r = mid;
		else l = mid+1;
	}
	if (check(r)) printf("%d", r);
	else printf("-1");
	return 0;
}