曾迷途才怕追不上满街赶路人 无人理睬如何求生

Div1 Day1

A

首先通过手玩可以知道,在 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)

/*
Undo the destiny.
*/
#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) {
    // cerr << "nowk:" << k << "\n";
    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;
        // cerr << "debug:" << i << "\n";
        // cerr << "np:" << np << "\n";
        // cerr << "now:" << now.x << "  " << now.y << "\n";
        // for (int j = 0;j < k;++j) cerr << sum[j] << " ";
        // cerr << "\n";
    }
}

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);//cout.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

K

简单构造,考虑每一个连续段,记连续段长度为 len.当 len \bmod k \not= 0 时候,直接把 ck 这个位置的反转即可。否则考虑把c(k-1) 这个反转,因为你考虑类似 11100,k = 3 这样的情况,反转一下可能会产生新的连续段,相当于你要强制一个东西作为隔断。另外 k=2 的时候特别判断一下就OK,因为只有两种序列。

/*
Undo the destiny.
*/
#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;
                // cerr << "len:" << len << "i,lst:" << i << " " << lst << "\n"; 
                if (len >= k) {
                    //11111100 3
                    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;
        // cerr << "len:" << len << "i,lst:" << n << " " << lst << "\n"; 
        if (len >= k) {
            //11111100 3
            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;
}

I

手玩出来的神秘结论……首先我们把相切的两个圆建边。

首先你考虑有环肯定不行,有一条偶链肯定也不行,因为偶链中增加的点数恰好等于减少的点数。

不难发现只有奇链对我们的答案有贡献,那么其实本质上就是一个判断二分图的过程,对于每个连通块判断一下就OK。

/*
Undo the destiny.
*/
#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]) {
                // cerr << i << "\n";
                // cerr << flag << " " << cnt[1] << " " << cnt[2] << "\n";
                qwq = 0;
            }
        }
    }
    if (qwq) cout << "NO";
    else cout << "YES";
    return 0;
}

EG神人tv题。