曾迷途才怕追不上满街赶路人 无人理睬如何求生
Div1 Day1
首先通过手玩可以知道，在 $pos = i$ 插入一个 $a_1$ 实际上只会造成一个集合价值的修改。这个操作我们显然可以通过 set 来动态维护每个集合的大小。如果我们这里大力做，枚举所有 $k | n$ 的话那时间复杂度会退化到 $O(n\log ^2 n)$。
但是我们实际上可以发现，我们考虑分组大小为 $ck(c\in N,c > 1)$ 时候答案显然是不如大小为 $k$ 的时候的。可以通过以下证明：
$$
令 s_1,s_2为最大和次大，r_1,r_2为最小和次小，那么有:\
v1 = \frac{s_1}{r_1},v2 = \frac{s_1+s_2}{r_1 + r_2}\
不难证明v_1<v_2
$$
也就是说我们考虑所有质数即可，感觉很小（）所以复杂度就 $O(n\log n)$ 了
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
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
const int N = 1e6 + 10;
struct fc {
ll x,y;
fc(ll a = 0,ll b = 0){x = a,y = b;}
friend inline bool operator < (const fc &a,const fc &b) {
return (ll)a.x * b.y < (ll)b.x * a.y;
}
}ans;
ll a[N],n,x;
void work(int k) {
multiset <ll> s;
vector <ll> sum(k,0);
for (int i = 1;i < n;++i) {
sum[i % k] += a[i];
}
sum[0] += x;
for (int i = 0;i < k;++i) s.insert(sum[i]);
ll minn = *s.begin(),maxx = *s.rbegin();
fc now = fc(maxx,minn);
if (now < ans) ans = now;
int np = 0;
for (int i = 1;i < n;++i) {
s.erase(s.find(sum[np]));
sum[np] += a[i];sum[np] -= x;
s.insert(sum[np]);
++np;np %= k;
s.erase(s.find(sum[np]));
sum[np] -= a[i];sum[np] += x;
s.insert(sum[np]);
ll minn = *s.begin(),maxx = *s.rbegin();
fc now = fc(maxx,minn);
if (now < ans) ans = now;
}
}
bool vis[1000010];
void solve() {
cin >> n >> x;
ans.x = 0x3f3f3f3f,ans.y = 1;
for (int i = 1;i < n;++i) {
cin >> a[i];
}
for (int k = 2;k <= n;++k) {
if (n % k == 0) {
if (!vis[k] || n == k) work(k);
}
}
int gccc = __gcd(ans.x,ans.y);
ans.x /= gccc,ans.y /= gccc;
cout << ans.x << " " << ans.y << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
for (int i = 2;i <= 1000000;++i) {
if (!vis[i]) {
for (int j = i*2;j <= 1000000;j += i) {
vis[j] = 1;
}
}
}
int T;cin >> T;
while (T--) solve();
return 0;
}
|
Div 1 Day 2
简单构造，考虑每一个连续段，记连续段长度为 $len$.当 $len \bmod k \not= 0$ 时候，直接把 $ck$ 这个位置的反转即可。否则考虑把$c(k-1)$ 这个反转，因为你考虑类似 $11100,k = 3$ 这样的情况，反转一下可能会产生新的连续段，相当于你要强制一个东西作为隔断。另外 $k=2$ 的时候特别判断一下就OK，因为只有两种序列。
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
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
const int N = 1e5 + 10;
int k,n;
string s;
signed main() {
int ans = 0;
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> k >> s;n = s.size();
if (k == 2) {
int typ = 0,ans1 = 0,ans2 = 0;
for (int i = 0;i < n;++i) {
if (s[i] != typ + '0') ++ans1;
typ ^= 1;
}
typ = 1;
for (int i = 0;i < n;++i) {
if (s[i] != typ + '0') ++ans2;
typ ^= 1;
}
if (ans1 < ans2) {
ans = ans1;
typ = 0;
} else {
ans = ans2;
typ = 1;
}
for (int i = 0;i < n;++i) {
s[i] = typ + '0',typ ^= 1;
}
} else {
int lst = 0,typ = s[0] - '0';
for (int i = 1;i < n;++i) {
if (s[i] - '0' != typ) {
int len = i - lst;
if (len >= k) {
if (len % k == 0) {
for (int j = lst + k - 2;j < i;j += k) {
if (s[j] == '0') s[j] = '1';
else s[j] = '0';
}
} else {
for (int j = lst + k -1;j < i;j += k) {
if (s[j] == '0') s[j] = '1';
else s[j] = '0';
}
}
ans += len / k;
}
lst = i,typ = s[i] - '0';
}
}
int len = n - lst;
if (len >= k) {
if (len % k == 0) {
for (int j = lst + k - 2;j < n;j += k) {
if (s[j] == '0') s[j] = '1';
else s[j] = '0';
}
} else {
for (int j = lst + k -1;j < n;j += k) {
if (s[j] == '0') s[j] = '1';
else s[j] = '0';
}
}
ans += len / k;
}
}
cout << ans << " " << s;
return 0;
}
|
手玩出来的神秘结论……首先我们把相切的两个圆建边。
首先你考虑有环肯定不行，有一条偶链肯定也不行，因为偶链中增加的点数恰好等于减少的点数。
不难发现只有奇链对我们的答案有贡献，那么其实本质上就是一个判断二分图的过程，对于每个连通块判断一下就OK。
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
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
const int N = 1e3 + 10;
struct poi {
ll x,y,r;
}p[N];
int n;
vector <int> G[N];
int col[N],cnt[3];
bool vis[N],flag;
ll dis(poi a,poi b) {
ll x = a.x - b.x,y = a.y - b.y;
return x * x + y * y;
}
void dfs(int x,int c) {
col[x] = c;cnt[c]++;
for (auto y : G[x]) {
if (!col[y]) {
dfs(y,3-c);
} else {
if (col[y] == col[x]) {
flag = 1;
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n;
for (int i = 1;i <= n;++i) {
cin >> p[i].x >> p[i].y >> p[i].r;
}
for (int i = 1;i <= n;++i) {
for (int j = i + 1;j <= n;++j) {
if (dis(p[i],p[j]) == (p[i].r + p[j].r) * (p[i].r + p[j].r)) {
G[i].push_back(j);G[j].push_back(i);
}
}
}
bool qwq = 1;
for (int i = 1;i <= n;++i) {
if (!col[i]) {
flag = 0;cnt[2] = cnt[1] = 0;
dfs(i,1);
if (!flag && cnt[1] != cnt[2]) {
qwq = 0;
}
}
}
if (qwq) cout << "NO";
else cout << "YES";
return 0;
}
|
EG神人tv题。