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

OIFC未来共同体20241028noip模拟三

时间:2024-11-01 21:20:54浏览次数:1  
标签:rs int tag 共同体 20241028noip ls OIFC now mod

T1

状压 \(dp\),两两之间有相同的位,那一位就为 \(1\),否则就为 \(0\),考虑哪些选法不合法,要在 \(0\) 的位上为 \(1\),即只在 \(1\) 上选和不选都是不可以的,于是状压 \(dp\) 即可。

#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;}

const int N = 3e3 + 10, M = 25;
int n, m, ans = 0x7fffffff;
char c[N][M];
bool flag[(1 << M)];
int sum[M];
void solve(){
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++){
            int p = 0;
            for (int k = 0; k < m; k++)
                if (c[i][k] == c[j][k]) p |= (1 << k);
            flag[p] = 1;
        }
    for (int i = (1 << m) - 1; i >= 0; i--){
        if (flag[i])
            for (int j = 0; j < m; j++)
                if (i & (1 << j)) flag[i ^ (1 << j)] = 1;
        int res = 0;
        if (!flag[i]){
            for (int j = 0; j < m; j++)
                if (i & (1 << j)) res++;
            if (res <= ans) ans = res, sum[ans]++;
        }
    }
    cout << ans << ' ' << sum[ans] << '\n';
}

signed main(){
    freopen("guess.in", "r", stdin);
    freopen("guess.out", "w", stdout);
    n = read(), m = read();
    for (int i = 1; i <= n; i++) cin >> c[i];
    solve();
    return 0;
}

T2

找性质,发现一个连通块,即包括有顺序的 XYD,只会全部是竖的,要么全部是横的。

直接维护连通块的横与竖的权值即可。

#include<iostream>

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;}

const int N = 3e3 + 10;
int n, ans;
char a[N][N];
int turn(int x, int y){
    return (x - 1) * n + y;
}
int fa[N * N];
int find(int x){
    return (x == fa[x] ? fa[x] : fa[x] = find(fa[x]));
}
int x[N * N], y[N * N];
void merge(int a, int b){
    int fx = find(a), fy = find(b);
    if (fx == fy) return;
    fa[fy] = fx;
    x[fx] += x[fy];
    y[fx] += y[fy];
}

int main(){
    freopen("match.in", "r", stdin);
    freopen("match.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];
    for (int i = 1; i <= n * n; i++) fa[i] = i;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if (a[i][j] == 'X'){
                if (a[i + 1][j] == 'Y' && a[i + 2][j] == 'D'){
                    merge(turn(i, j), turn(i + 1, j));
                    merge(turn(i, j), turn(i + 2, j));
                    y[find(turn(i, j))]++;
                }
                if (a[i][j + 1] == 'Y' && a[i][j + 2] == 'D'){
                    merge(turn(i, j), turn(i, j + 1));
                    merge(turn(i, j), turn(i, j + 2));
                    x[find(turn(i, j))]++;
                }
            }
        }
    }
    for (int i = 1; i <= n * n; i++)
        if (fa[i] == i) ans += max(x[i], y[i]);
    cout << ans;
    return 0;
}

T3

发现每个人要从时间最少的饮水机那里接水才最优,每次将一个人加入接水时间的饮水机处,由于一个人加入后,这个饮水机的时间一定会比其它所有饮水机的等待时间长,那么直接从 \(1\) 到 \(n\) 加入人,对于同样时间的人线段树优化贪心即可。

#include<iostream>
#include<algorithm>
#define ls now << 1
#define rs now << 1 | 1
#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;}

const int N = 3e5 + 10, M = 1e6 + 10, mod = 1e9 + 7;
int n, m, ans;
struct node{
    int a, t;
    bool operator < (const node &b) const{
        return t < b.t;
    }
}p[N];
struct tree{
    int sum, tag, l, r;
}t[M << 2];
void pushup(int now){
    t[now].sum = (t[ls].sum + t[rs].sum) % mod;
}
void pushdown(int now){
    int l = t[now].l, r = t[now].r, mid = (l + r) >> 1;
    t[ls].sum = (t[ls].sum + t[now].tag * (mid - l + 1) % mod) % mod;
    t[rs].sum = (t[rs].sum + t[now].tag * (r - mid) % mod) % mod;
    t[ls].tag = (t[ls].tag + t[now].tag) % mod;
    t[rs].tag = (t[rs].tag + t[now].tag) % mod;
    t[now].tag = 0;
}
void build(int now, int l, int r){
    t[now] = (tree){0, 0, l, r};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(now);
}
void modify(int now, int x, int y, int k){
    int l = t[now].l, r = t[now].r;
    if (x <= l && r <= y){
        t[now].sum = (t[now].sum + (r - l + 1) * k % mod) % mod;
        t[now].tag = (t[now].tag + k) % mod;
        return;
    }
    pushdown(now);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(ls, x, y, k);
    if (mid + 1 <= y) modify(rs, x, y, k);
    pushup(now);
}
int query(int now, int x, int y){
    int l = t[now].l, r = t[now].r;
    if (x <= l && r <= y){
        return t[now].sum;
    }
    pushdown(now);
    int mid = (l + r) >> 1, res = 0;
    if (x <= mid) res = (res + query(ls, x, y)) % mod;
    if (mid + 1 <= y) res = (res + query(rs, x, y)) % mod;
    return res;
}
int work1(int &pos, int k, int t){
    int l = min(m - pos + 1, k);
    ans = (ans + query(1, pos, pos + l - 1)) % mod;
    modify(1, pos, pos + l - 1, t % mod);
    pos = ((pos + l) % m == 0 ? m : (pos + l) % m);
    return l;
}
void work2(int turn, int t){
    ans = (ans + query(1, 1, m) * turn % mod) % mod;
    ans = (ans + ((turn - 1) * turn / 2) % mod * t % mod * m % mod) % mod;
    modify(1, 1, m, turn * t % mod);
}
void work3(int &pos, int more, int t){
    ans = (ans + query(1, 1, more)) % mod;
    modify(1, 1, more, t % mod);
    pos = more + 1;
}

signed main(){
    freopen("water.in", "r", stdin);
    freopen("water.out", "w", stdout);
    n = read(), m = read();
    for (int i = 1; i <= n; i++) p[i].a = read(), p[i].t = read();
    sort(p + 1, p + n + 1);
    build(1, 1, m);
    int pos = 1;
    for (int i = 1; i <= n; i++){
        int k = p[i].a, t = p[i].t;
        k -= work1(pos, k, t);
        if (pos != 1) continue;
        int turn = k / m, more = k % m;
        if (turn) work2(turn, t);
        if (more) work3(pos, more, t);
    }
    cout << ans;
    return 0;
}

T4

不会。

标签:rs,int,tag,共同体,20241028noip,ls,OIFC,now,mod
From: https://www.cnblogs.com/bryceyyds/p/18521241

相关文章

  • OIFC未来共同体20241023noip模拟二
    T1考虑从后往前去做,随机化字母权值,考虑两个字符,一个设为正的权值,一个设为负的权值,两两就可以抵消,若有一个后缀权值等于另一个后缀权值且长度为偶数,就肯定有一个回文串,若有一个后缀权值等于另一个后缀权值加减一个字母的权值且长度为奇数,就也肯定有一个回文串,存下来,离散化即可。#......
  • 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的数据类型成员......