首页 > 其他分享 >OIFC未来共同体20241023noip模拟二

OIFC未来共同体20241023noip模拟二

时间：2024-11-01 20:43:27浏览次数：1  
标签：20241023noip int sum 权值 共同体 mp && ans OIFC

T1

考虑从后往前去做，随机化字母权值，考虑两个字符，一个设为正的权值，一个设为负的权值，两两就可以抵消，若有一个后缀权值等于另一个后缀权值且长度为偶数，就肯定有一个回文串，若有一个后缀权值等于另一个后缀权值加减一个字母的权值且长度为奇数，就也肯定有一个回文串，存下来，离散化即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10, M = 28;
int n, m, ans;
char c[N];
int val[M], sum[N], p[N], mp[N][2];
mt19937 rd(40491522);
void solve(){
    for (int i = 0; i < 26; i++) val[i] = rd();
    for (int i = n; i >= 1; i--){
        p[i] = sum[i] = sum[i + 1] + val[c[i] - 'a'];
        val[c[i] - 'a'] = -val[c[i] - 'a'];
    }
    sort(p + 1, p + n + 1);
    m = unique(p + 1, p + n + 1) - p - 1;
    for (int i = n; i >= 1; i--){
        int k = lower_bound(p + 1, p + m + 1, sum[i]) - p;
        if (mp[k][i & 1]) ans = max(ans, mp[k][i & 1] - i);
        if (((n - i + 1) & 1) == 0 && !sum[i]) ans = max(ans, n - i + 1);
        for (int d = 0; d < 26; d++){
            int y = sum[i] - val[d];
            k = lower_bound(p + 1, p + m + 1, y) - p;
            if (p[k] == y && mp[k][(i & 1) ^ 1]) ans = max(ans, mp[k][(i & 1) ^ 1] - i);
            if ((n - i + 1) & 1 && !y) ans = max(ans, n - i + 1);
            y = sum[i] + val[d];
            k = lower_bound(p + 1, p + m + 1, y) - p;
            if (p[k] == y && mp[k][(i & 1) ^ 1]) ans = max(ans, mp[k][(i & 1) ^ 1] - i);
            if ((n - i + 1) & 1 && !y) ans = max(ans, n - i + 1);
        }
        k = lower_bound(p + 1, p + m + 1, sum[i]) - p;
        if (!mp[k][i & 1]) mp[k][i & 1] = i;
    }
    cout << ans;
}
signed main(){
    freopen("easygame.in", "r", stdin);
    freopen("easygame.out", "w", stdout);
    ios::sync_with_stdio;
    cin.tie(0);cout.tie(0);
    cin >> (c + 1);
    n = strlen(c + 1);
    solve();
    return 0;
}

T2

从 \(1\) 号节点开始间隔染色，圆点都在叶子上，对于每个方点最少连一个环的边双，最多能连一个竞赛图，于是直接暴力连边即可。

#include<iostream>
#define int long long

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 1e6 + 10;
int n, m, k;//m点，k边
struct edge{
    int v, nxt;
}e[N << 1];
int head[N], cnt;
void add(int u, int v){
    e[++cnt] = (edge){v, head[u]};
    head[u] = cnt;
}
int p[N], top, q[N], toq, dep[N], sw[N];//p white q black
bool vis[N], son[N];
void col(int u, int fa, bool c){
    if (c) q[++toq] = u;
    else p[++top] = u;
    dep[u] = dep[fa] + 1;
    int tot = 0;
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].v;
        if (v == fa) continue;
        col(v, u, c ^ 1);
        tot++;
    }
    if (!tot) son[u] = 1;
}
int stk[N], t, ID[N];

signed main(){
    freopen("blocktree.in", "r", stdin);
    freopen("blocktree.out", "w", stdout);
    n = read(), m = read(), k = read();
    for (int i = 1; i < n; i++){
        int u = read(), v = read();
        add(u, v), add(v, u);
    }
    col(1, 0, 0);
    int maxn = 0;
    for (int i = 1; i <= n; i++) maxn = max(maxn, dep[i]);
    for (int i = 1; i <= n; i++){
        if (son[i] && (maxn & 1) != (dep[i] & 1)){
            cout << "No";
            return 0;
        }
    }
    if (!(maxn & 1)){
        for (int i = 1; i <= top; i++) sw[i] = p[i];
        for (int i = 1; i <= toq; i++) p[i] = q[i];
        for (int i = 1; i <= top; i++) q[i] = sw[i];
        swap(top, toq);
    }
    if (top != m){
        cout << "No";
        return 0;
    }
    int res1 = 0, res2 = 0;
    for (int u = 1; u <= toq; u++){
        int tot = 0;
        for (int i = head[q[u]]; i; i = e[i].nxt) tot++;
        if (tot != 2) res1 += tot, res2 += tot * (tot - 1) / 2;
        else res1++, res2++;
        vis[q[u]] = 1;
    }
    if (k < res1 || k > res2){
        cout << "No";
        return 0;
    }
    cout << "Yes\n";
    int id = 0;
    for (int i = 1; i <= n; i++){
        if (vis[i]) cout << 0 << ' ';
        else cout << (ID[i] = ++id) << ' ';
    }
    cout << '\n';
    bool f = 0;
    for (int u = 1; u <= toq; u++){
        for (int i = head[q[u]]; i; i = e[i].nxt) stk[++t] = e[i].v;
        for (int i = 1; i < t; i++) cout << ID[stk[i]] << ' ' << ID[stk[i + 1]] << '\n';
        if (t != 2){
            cout << ID[stk[t]] << ' ' << ID[stk[1]] << '\n';
        }
        for (int i = 1; i <= t; i++){
            if (f) break;
            for (int j = i; j <= t; j++){
                if (i == j || j == i + 1 || (j == t && i == 1)) continue;
                if (k > res1) cout << ID[stk[i]] << ' ' << ID[stk[j]] << '\n', k--;
                else{
                    f = 1;
                    break;
                }
            }
        }
        t = 0;
    }
    return 0;
}

T3

显然有一个二维数点的做法，接下来就只需要考虑如何求出这样的点，设 \(x = p_1^{\alpha_1}p_2^{\alpha_2}\dots p_n^{\alpha_n}\)，\(y = p_1^{\beta_1}p_2^{\beta_2}\dots p_n^{\beta_n}\)，等价于 \(\gcd(\max(\alpha_1, \beta_1),\dots ,\max(\alpha_n, \beta_n))\not= 1\)，于是写一个搜索就行了。

#include<iostream>
#include<algorithm>

using namespace std;

inline int read(){register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9'){if (c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return x * f;}
inline void write(int x){if (x < 0) putchar('-'), x = -x;if (x > 9) write(x / 10);putchar(x % 10 + '0');}

const int N = 1e6 + 10, M = 1e6;
int T, ans[N];
int p[N], cnt;
bool prime[N];
int gcd(int a, int b){
    return (b == 0 ? a : gcd(b, a % b));
}
void pri(){
    for (int i = 2; i <= 1e3; i++){
        if (!prime[i]) p[++cnt] = i;
        for (int j = 1; j <= cnt && i * p[j] <= 1e3; j++){
            prime[i * p[j]] = 1;
            if (i % p[j] == 0) break;
        }
    }
}
struct node{
    int x, y, type, id;
    bool operator < (const node &b) const{
        return (x != b.x ? x < b.x : type < b.type);
    }
}q[N * 8];
int opt;
int GCD[25][25];
void dfs(int x, int y, int g, int lst){
    if (lst == cnt + 1 || x * p[lst] > M && y * p[lst] > M){
        q[++opt] = (node){x, y, 0, 0};
        return;
    }
    long long res1 = 1;
    for (int i = 0; x * res1 <= M; i++, res1 *= p[lst]){
        long long res2 = 1;
        for (int j = 0; y * res2 <= M; j++, res2 *= p[lst]){
            int G = GCD[g][max(i, j)];
            if (G == 1) continue;
            dfs(x * res1, y * res2, G, lst + 1);
        }
    }
}
void init(){
    pri();
    for (int i = 0; i <= 23; i++)
        for (int j = 0; j <= 23; j++) GCD[i][j] = gcd(i, j);
    dfs(1, 1, 0, 1);
}
int t[N];
int lowbit(int x){return x & (-x);}
void add(int x, int k){
    for (int i = x; i <= M; i += lowbit(i)) t[i] += k;
}
int query(int x){
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += t[i];
    return res;
}

int main(){
    freopen("unnamed.in", "r", stdin);
    freopen("unnamed.out", "w", stdout);
    init();
    T = read();
    for (int i = 1; i <= T; i++){
        int a = read(), b = read(), c = read(), d = read();
        q[++opt] = (node){b, d, 1, i};
        q[++opt] = (node){a - 1, d, 2, i};
        q[++opt] = (node){b, c - 1, 2, i};
        q[++opt] = (node){a - 1, c - 1, 1, i};
    }
    sort(q + 1, q + opt + 1);
    for (int i = 1; i <= opt; i++){
        if (q[i].type == 0) add(q[i].y, 1);
        if (q[i].type == 1) ans[q[i].id] += query(q[i].y);
        if (q[i].type == 2) ans[q[i].id] -= query(q[i].y);
    }
    for (int i = 1; i <= T; i++) cout << ans[i] << '\n';
    return 0;
}

T4

不会。

标签：20241023noip,int,sum,权值,共同体,mp,&&,ans,OIFC
From： https://www.cnblogs.com/bryceyyds/p/18521209

相关文章

  • OIFC未来共同体20241021noip模拟一
    T1建边，发现要找偶环，但两个奇环也可以拼在一起，于是按照上面的思路模拟即可。但是挂了一个点，不知道为啥。#include<iostream>#include<vector>#include<cstring>usingnamespacestd;inlineintread(){registerintx=0,f=1;registercharc=getchar();while(c<......
  • NOI 2024省选OIFC模拟21 T1（思维题）
    原我觉得非常有思维含量的一题没看懂题解，大佬讲的还是没有看懂对于一个集合S，不妨设要将这个集合设为蓝色，考虑一个包含元素最多的一个为蓝色的子集T，那么在包含有S-T集合中的元素的集合必定为红色，因为如果有一个为蓝色，那么这个与前面那个极大蓝色集合交一下就会有一个更大的蓝......
  • 2024省选OIFC模拟T1
    题意:给定k颗有n个点的树对于每个点对(i,j)，求出其在每棵树上的路径经过的点（含端点）的并集大小。做法:一个比较简单的想法是搞出每个(i,j)在第k颗树上的点的集合，然后所有树并一下，这个再用bitset优化一下，然后有人就过了，而我这位大常数选手就没过。首先容斥为求不经过点的交。考......
  • NOI 2024省选OIFC模拟21 蒲巴巴 超繁做法
    题目描述一年一度的PuBaBa杯开始了！今年的PuBaBa杯总共有\(n\)个选手来参加，编号分别为\(1,2,\cdots,n\)，他们的水平按编号依次递增，所以他们过的题目数量单调不降。作为本场比赛的出题人，PuBaBa总共出了\(m\)道题，他希望第\(i\)道题至少有\(l_i\)个选手通过，至多有\(......
  • 《细菌:我们的生命共同体》 - 书摘
    出版说明在今天三联书店的前身——生活书店、读书出版社和新知书店的出版史上，介绍新知识和新观念的图书曾占有很大比重。了解这种知识成果的内容，思考其与我们生活的关系，固然是明了社会变迁趋势的必需，但更为重要的，乃是通过知识演进的背景和过程，领悟和体会隐藏其中的理性精神和科......
  • 共同体
    共同体定义共同体的语法：union共同体名{成员一的数据类型成员名一;成员二的数据类型成员名二;成员三的数据类型成员名三;......成员n的数据类型成员......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99