首页 > 其他分享 >10.5 模拟赛

10.5 模拟赛

时间:2022-10-05 16:11:50浏览次数:81  
标签:return int fa using 10.5 mod 模拟 define

\(\rm NOIP\) 模拟赛

\(\rm Date: 10.5\)

上次真是太变态了,这次就平和许多

另外,不要在意accoders那丧心病狂的评测机速度了

今天4道都是CF原题

\(T1\) CF1252G

一看上去居然没思路啊,于是就把T2做了,再回来看这题终于发现了做法。其实我们只用维护当前有多少人的能力值比自己小,如果太小了就寄了。拿线段树维护区间加区间最小即可。

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define rg register
#define emp emplace_back
using namespace std;
const int N = 1e5 + 5;

namespace Sg {
#define lsp p << 1
#define rsp p << 1 | 1
#define mid (t[p].l + t[p].r >> 1)
    struct T {
        int l, r, val; // Minimum
    }t[N << 2];
    int tag[N << 2]; // Num to add
    inline T operator + (T L, T R) {
        return {L.l, R.r, min(L.val, R.val)};
    }
    inline void pushup(int p) { t[p].val = min(t[lsp].val, t[rsp].val); }
    inline void fx(int p, int v) {
        t[p].val += v, tag[p] += v;
    }
    inline void pushdown(int p) {
        fx(lsp, tag[p]), fx(rsp, tag[p]), tag[p] = 0;
    }
    void build(int *arr, int p, int l, int r) {
        t[p] = {l, r}; if(l == r) return t[p].val = arr[l], void();
        build(arr, lsp, l, mid), build(arr, rsp, mid + 1, r); pushup(p);
    }
    void update(rg int p, rg int l, rg int r, rg int v) {
        if(l <= t[p].l && t[p].r <= r) return fx(p, v); pushdown(p);
        if(l <= mid) update(lsp, l, r, v); if(mid < r) update(rsp, l, r, v); pushup(p);
    }
    int query(int p, int l, int r) {
        if(l <= t[p].l && t[p].r <= r) return t[p].val; pushdown(p);
        if(r <= mid) return query(lsp, l, r); else if(l > mid) return query(rsp, l, r);
        else return min(query(lsp, l, r), query(rsp, l, r));
    }
}

int n, m, q, kk;
int b[N], c[N];
vector <int> a[N];

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
#endif
    scanf("%d %d %d", &n, &m, &q);
    for(int i = 0; i <= m; ++i) a[i].emp(0);
    for(int i = 1, x; i <= n; ++i) {
        scanf("%d", &x), a[0].emp(x);
        if(i == 1) kk = x;
        else {
            if(x < kk) ++b[0]; 
        }
    }
    //cout << kk << endl;
    c[0] = n;
    for(int i = 1, num; i <= m; ++i) {
        scanf("%d", &num);
        c[i] = num;
        for(int j = 1, x; j <= num; ++j) {
            scanf("%d", &x);
            a[i].emp(x);
            if(x < kk) ++b[i];
        }
    }
    //for(int i = 0; i <= m; ++i) cout << 
    //for(int i = 0; i <= m; ++i) cout << b[i] << ' ';
    //cout << endl;
    for(int i = 1; i <= m; ++i) b[i] = b[i - 1] - c[i] + b[i];
    for(int i = 0; i < m; ++i) b[i] -= c[i + 1];
    
    //for(int i = 0; i <= m; ++i) cout << b[i] << ' ';
    //cout << endl;
    
    Sg::build(b, 1, 0, m);
    for(int x, y, z; q--; ) {
        scanf("%d %d %d", &x, &y, &z);
        int val = a[x][y];
        //cout << a[x][y] << endl;
        if(val < kk && z > kk) Sg::update(1, x, m, -1);
        if(val > kk && z < kk) Sg::update(1, x, m, 1);
        if(Sg::t[1].val < 0) puts("0");
        else puts("1"); 
        a[x][y] = z;
        //printf(": %d\n", Sg::query(1, 2, 2));
    }
    return 0;
}

\(T2\) CF1515E

网上到处是 \(\mathcal{O(n^2)}\) 的做法还一个比一个奇怪,解释都不带解释的直接上柿子。哎,还是自己看得懂自己的解法

显然两端极长手开的电脑之间只会隔一个电脑,那么设 \(f[i, j]\) 表示考虑前 \(i\) 个电脑分 \(j\) 段手开,那么有转移:

\[f[i, j] = (\sum\limits_{x=1}^{i-2}f[i-x-1][j-1])\times C_{i-j+1}^x \times 2^{x-1} \]

\(\mathcal{O(n^3)}\),accoders上 \(100\to 25\)

#include <bits/stdc++.h>
#pragma GCC opimtize("Ofast")
#define rg register
using namespace std;
const int N = 405;
using LL = long long;
 
int n, mod;
// first i computers, j blocks -> total ways
int f[N][N];
LL jc[N], fjc[N], pw[N];
 
LL power(LL x, int y) {
    if(!y) return 1;
    LL t = power(x, y >> 1);
    return t * t % mod * (y & 1 ? x : 1) % mod;
}
 
inline void init() { 
    jc[0] = pw[0] = 1;
    for(int i = 1; i <= 400; ++i) jc[i] = 1LL * jc[i - 1] * i % mod;
    for(int i = 1; i <= 400; ++i) fjc[i] = power(jc[i], mod - 2);
    for(int i = 1; i <= 400; ++i) pw[i] = 2LL * pw[i - 1] % mod;
}
 
inline LL C(int x, int y) { // C(x, y) (x >= y)
    return jc[x] * fjc[y] % mod * fjc[x - y] % mod;
}

int g[N][N];
inline LL C_(int x, int y) {
    return g[x][y];
}
 
signed main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
#endif
    cin >> n >> mod;
    init();
    //printf("%d\n", C(5, 3));
    f[1][1] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            g[i][j] = C(i, j);
        }
    }
    for(rg int i = 2; i <= n; ++i) {
        f[i][1] = pw[i - 1];
        for(rg int j = 2; j <= n; ++j) {
            for(rg int x = 1; x < i - 1; ++x) {
                LL tmp = C_(i - j + 1, x) * pw[x - 1] % mod;
                //printf("i = %d, j = %d, tmp = %lld\n", i, j, tmp);
                //printf("from [%d, %d]\n", i - x - 1, j - 1);
                (f[i][j] += f[i - x - 1][j - 1] * tmp % mod) %= mod;
                //f[i][j] = (f[i][j] + )
                //f[i][j] = (f[i - x - 1][j - 1] + tmp) % mod;
            }
        }
    }
#if 0
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            printf("f[%d, %d] = %d\n", i, j, f[i][j]);
        }
    }
#endif
    LL ans = 0;
    for(int j = 1; j <= n; ++j) (ans += f[n][j]) %= mod;
    cout << ans;
    //cout << endl << clock();
    return 0;
}

\(T3\) CF1654F

当时发现一条性质就是 \(i\to i\ \text{xor}\ e\) 的时候 \(s_i\) 是有规律的交换的,然后luogu的题解就用了一个类似SA倍增的思路解决本题。

另一种思路就是预处理从 \(i\) 开始,变换 \(2^j\) 次的构成的字符串的哈希值(巧妙地利用了 \(i\to i\text{ xor }e\) 时“下一个字符”的变换规律),然后我们判断字典序就利用哈希值找到第一个不相同的字符的位置,从而判断两个生成串的字典序。

\(\mathcal{O(n\cdot2^n)}\)

#include <bits/stdc++.h>
#define rg register
#define BRUTE_FORCE 0
#define SOL 9
#pragma GCC optimize("Ofast")
using namespace std;
const int N = 3e5 + 5;

#if BRUTE_FORCE
string ret = "";
inline string Trans(string s, int val) {
    string ret = "";
    for(rg int i = 0; i < n; ++i) {
        ret += s[i ^ val];
        //cout << (i ^ val) << ' ';
    }
    //cout << endl;
    return ret;
}
inline char find(string s) {
    char ret = 'z';
    for(rg int i = 0; i < n; ++i) ret = min(ret, s[i]);
    return ret;
}
inline string solve(string s) {
    ret = Trans(s, 0);
    char ch = find(s);
    for(rg int i = 1; i < n; ++i) {
        if(s[i] != ch) continue;
        string tmp = Trans(s, i);
        if(ret > tmp) ret = tmp;
    }
    return ret;
}
#endif
#if SOL

using ULL = unsigned long long;
const ULL C[] = {998244353, ULL(1e9 + 7)};
ULL f[2][20][N];
ULL pw[2][N];
int n;
char s[N];

int cmp(int x, int y) {
    if(f[0][n][x] == f[0][n][y] && f[1][n][x] == f[1][n][y]) return 0;
    for(int j = n - 1; ~j; --j) 
        if(f[0][j][x] == f[0][j][y] && f[1][j][x] == f[1][j][y]) 
            x xor_eq 1 << j, y xor_eq 1 << j;
    return s[x] < s[y] ? -1 : 1;
}

void work() {
    cin >> n >> s;
    pw[0][0] = pw[1][0] = 1;
    for(int j = 0; j < 2; ++j) 
        for(int i = 1; i < (1 << n); ++i) pw[j][i] = pw[j][i - 1] * C[j];
    for(int i = 0; i < (1 << n); ++i) f[0][0][i] = f[1][0][i] = s[i] * s[i];
    for(int k = 0; k < 2; ++k) {
        for(int j = 1; j <= n; ++j) {
            for(int i = 0; i < (1 << n); ++i) 
                f[k][j][i] = f[k][j - 1][i] + f[k][j - 1][i ^ (1 << (j - 1))] * pw[k][1 << (j - 1)];
        }
    }
    int ans = 0;
    for(int i = 1; i < (1 << n); ++i) 
        if(cmp(ans, i) > 0) ans = i;
    for(int i = 0; i < (1 << n); ++i) putchar(s[ans ^ i]);
    return;
}

#endif

signed main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
#endif
    work(); 
}

\(T4\) CF1710D

*3400 诶 有人当场A了orzycy

这是他的代码

大概思路就是从小到大考虑每个极长连通块,他必然包含了若干个子连通块区间。
设我们考虑到了好区间 \([l,r]\),\(l\) 所在连通块为 \([l',x_1 ]\),\(r\) 所在连通块为 \([x_k+1,r']\),它们之间还有 \(k-1\) 个连通块 \([x_i+1,x_{i+1}]\)。满足 $l'\le l\le x_1<...<x_k\le r \le r'l $
且 \(k\ge 1\)。

容易发现 \(k=2\) 时无解。\(k=1\) 时直接连 \((l,r)\) 即可。\(k>2\) 时一种构造是连 \((l,r),(l,x_k)\) 以及 \((x_i,r)(2\le i<k)\)。

不写了

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5;

int n, T, flg = 0;
int fa[N];
char s[N][N];

signed work() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) fa[i] = i, scanf("%s", s[i] + i); 
    for(int i = 1; i <= n; ++i) 
        for(int j = i - 1; j >= 1; --j) 
            if(s[j][i] == '1' && fa[i] > j) {
                printf("%d %d\n", j, i);
                if(fa[fa[i] - 1] > j) {
                    printf("%d %d\n", j, fa[i] - 1);
                    for(int k = fa[fa[i] - 1] - 1; k >= j + 1; --k) 
                        if(fa[k] == k) printf("%d %d\n", k, i);
                }
                for(int k = j; k <= i; ++k) fa[k] = fa[j];
            }
    return 0;
}

int main() {
    if(!T && !flg) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("Ans.txt", "w", stdout);
#endif
        cin >> T, flg = 1;
    }
    if(!T && flg) return 0;
    work();
    --T;
    return main();
}

标签:return,int,fa,using,10.5,mod,模拟,define
From: https://www.cnblogs.com/into-qwq/p/16755719.html

相关文章

  • CSP-S 模拟赛 #2 题解
    300rk3。题面是本校OJ的,链接挂了找我。upd:T1被xiaopanda的hack数据卡了。T1-A-BProblem出题是一件痛苦的事情!题目看多了也有审美疲劳,于是我舍弃了大家所熟......
  • 2022.10.5 若干代数题
    链接对\(\foralla,b,c\ge0\)且满足\((a^2+b^2)(b^2+c^2)(c^2+a^2)=2\),求\(a+b+c\)的最值思考三元换二元链接对\(a,b,c\ge0\)且\(ab+bc+ca=1\),求\[P=\frac{a......
  • 2022.10.5 模拟赛
    T1签到题题面Description给定\(n\)个数,求出这\(n\)个数的一个非空子集,使得这个子集中的数的和能被\(n\)整除,无解输出\(-1\).Input第一行为数据组数\(T\)接下来\(T\)......
  • 2022.10.5java特性和优势
    Java构建工具:Ant,Maven,Jekins应用服务器:Tomcat,Jettty,Jboss,Websphere,weblogicWeb开发:Struts,Spring,Hibernate,myBatis开发工具:Eclipse,Netbean,intellij......
  • 原始递归函数及模拟运行的优化
    看到网上一个题目,证明x开y次方是原始递归函数(primitiverecursivefunction)。这个问题并不难,只要把x开y次方实现出来即可。于是,正好把《递归论》相关内容补一补。【......
  • CSP-S模拟14
    T1.考场:这不就单峰函数吗?我会3min后:这函数有相等区间啊!爬山3h后:woc这题写了3小时!赶紧去冲后几题暴力不过最后还是A了%:pragmaGCCoptimize(3)#include<bits/std......
  • [挑战记录]模拟/搜索题单
    2022100320:18[省选联考2022]预处理器\(\operatorname{string}\)科技题#include<cstdio>#include<cstring>#include<string>#include<iostream>#include<map>#de......
  • Cisco模拟器使用教程
    一、使用三层交换机实现跨VLAN间的通信1.vlan配置如图所示局域网,要将不同的PC机配置到不同的vlan下。在二层交换机的配置模式(即Switch(config)#)下:这里配置的端口是与P......
  • 43rd 2022/10/4 模拟赛总结30
    这次还行?rank5,其实也不是多高不可攀,就是认真打,暑假时就上过前五好多次其实比赛历程也很简单第一题很忽悠,思路乱的一批,但是这次冷静下来把思路理清就切了很简单的概率D......
  • 一个简单的模拟实例说明Task及其调度问题
    编者荐语:蒋老师只用短短的几百行样例代码就为大家解释清楚了在C#中至关重要的Task和其调度的原理,这是不可多得的高质量文章。Task对于.NET的重要性毋庸置疑。通过最近的一些......