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

OIFC未来共同体20241030noip模拟四

时间:2024-11-01 21:31:54浏览次数:4  
标签:20241030noip register 共同体 int while read OIFC include getchar

T1

我们发现 \(1\) 其实根本没有用,只和一个连通块里的 \(0\) 的个数有关,直接 \(dfs\),判断即可。

#include<iostream>
#include<cstring>

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 = 110;
int T, n, m, sum, ans;
int a[N][N], dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
bool vis[N][N];
bool check(int x, int y){
    if (x < 1 || x > n || y < 1 || y > m || a[x][y] == -1) return 0;
    return 1;
}
void dfs(int x, int y){
    if (vis[x][y]) return;
    vis[x][y] = 1;
    if (a[x][y] == 0) sum++;
    for (int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if (!check(nx, ny)) continue;
        dfs(nx, ny);
    }
}
void solve(){
    n = read(), m = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            char c; cin >> c;
            if (c == 'X') a[i][j] = -1;
            else a[i][j] = c - '0';
        }
    bool flag = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (a[i][j] != -1 && !vis[i][j] && !flag){
                flag = 1, sum = 0;
                dfs(i, j);
                if (sum & 1) ans++;
            }else if (a[i][j] != -1 && !vis[i][j] && flag){
                cout << "No\n";
                ans = 0;
                memset(vis, 0, sizeof vis);
                memset(a, 0, sizeof a);
                return;
            }
        }
    }
    cout << (ans == 1 ? "Yes\n" : "No\n");
    ans = 0;
    memset(vis, 0, sizeof vis);
    memset(a, 0, sizeof a);
}

int main(){
    freopen("chess.in", "r", stdin);
    freopen("chess.out", "w", stdout);
    T = read();
    while (T--) solve();
    return 0;
}

T2

结论题,不为 \(1\) 的数的个数为奇数个就为 No,否则就为 Yes,其实也挺好证明的,这里略。

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

const int N = 5e5 + 10;
int T, n;
int a[N];
void solve(){
    n = read();
    int cnt = 0, el;
    for (int i = 1; i <= n; i++){
        a[i] = read();
        if (a[i] == 1) cnt++;
    }
    el = n - cnt;
    if (el & 1) cout << "Yes\n";
    else cout << "No\n";
}

int main(){
    freopen("delete.in", "r", stdin);
    freopen("delete.out", "w", stdout);
    T = read();
    while (T--) solve();
    return 0;
}

T3

将题目意思转化一下,就是求子序列和为 \(0\) 所在区间的个数,直接背包然后拆分贡献计算。

#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 = 1e3 + 10, M = 2e5 + 10, K = 1e5, mod = 998244353;
int n, ans;
int a[N], dp[M];

signed main(){
    freopen("seq.in", "r", stdin);
    freopen("seq.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 2; i <= n - 1; i++){
        if (a[i] >= 0){
            for (int j = K; j >= -K; j--)
                if (j - a[i] >= -K && j - a[i] <= K)
                    dp[j + K] = (dp[j + K] + dp[j + K - a[i]]) % mod;
        }else{
            for (int j = -K; j <= K; j++)
                if (j - a[i] >= -K && j - a[i] <= K)
                    dp[j + K] = (dp[j + K] + dp[j + K - a[i]]) % mod;
        }
        dp[a[i] + K] = (dp[a[i] + K] + i - 1) % mod;
        ans = (ans + dp[K]) % mod;
    }
    cout << (ans + n * (n + 1) / 2 % mod) % mod;
    return 0;
}

T4

不会。

标签:20241030noip,register,共同体,int,while,read,OIFC,include,getchar
From: https://www.cnblogs.com/bryceyyds/p/18521303

相关文章

  • OIFC未来共同体20241028noip模拟三
    T1状压\(dp\),两两之间有相同的位,那一位就为\(1\),否则就为\(0\),考虑哪些选法不合法,要在\(0\)的位上为\(1\),即只在\(1\)上选和不选都是不可以的,于是状压\(dp\)即可。#include<iostream>#defineintlonglongusingnamespacestd;inlineintread(){registerintx......
  • 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的数据类型成员......