Loading [MathJax]/jax/output/CommonHTML/config.js
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【算法竞赛】AtCoder Beginner Contest 171F 172E 172F

【算法竞赛】AtCoder Beginner Contest 171F 172E 172F

作者头像
Livinfly
发布于 2023-01-10 07:03:52
发布于 2023-01-10 07:03:52
25400
代码可运行
举报
文章被收录于专栏:LivinflyLivinfly
运行总次数:0
代码可运行

171F - Strivore

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e6+10, P = 1e9+7;

int n, m;
string s;
int fact[N], factInv[N];

int qpm(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = (LL)ans*a%P;
        a = (LL)a*a%P;
        b >>= 1;
    }
    return ans;
}
void PrevCalu() {
    fact[0] = 1;
    for(int i = 1; i <= n+m; i ++)
        fact[i] = (LL)fact[i-1]*i%P;
    factInv[n+m] = qpm(fact[n+m], P-2);
    for(int i = n+m-1; i >= 0; i --)
        factInv[i] = (LL)factInv[i+1]*(i+1)%P;
}
int C(int n, int m) {
    return (LL)fact[n]*factInv[n-m]%P*factInv[m]%P;
}
void solve() {
    cin >> m >> s;
    n = s.size();
    PrevCalu();
    int res = 0;
    for(int i = n; i <= n+m; i ++) {
        res = ((LL)res+(LL)qpm(26, n+m-i)*qpm(25, i-n)%P*C(i-1, n-1)%P)%P;
    }
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}

/*
C(i-1, n-1) 最后一位的位置确定了

n+|s|的字符串的子序列有s的个数
求方案,假设得到最终子串,贪心地选,即取连续的子串的第一个字母
xxxxxx|xxxx
子序列的最后到|的前一位,后面都有26种选法,前面都有25种选法
*/

172E - NEQ

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 5e5+10, P = 1e9+7;

int n, m;
int fact[N], factInv[N];

int qpm(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = (LL)ans*a%P;
        a = (LL)a*a%P;
        b >>= 1;
    }
    return ans;
}
void PrevCalu() {
    fact[0] = 1;
    int mx = max(n, m); // ...
    for(int i = 1; i <= mx; i ++) 
        fact[i] = (LL)fact[i-1]*i%P;
    factInv[mx] = qpm(fact[mx], P-2);
    for(int i = mx-1; i >= 0; i --)
        factInv[i] = (LL)factInv[i+1]*(i+1)%P;
}
int A(int n, int m) {
    return (LL)fact[n]*factInv[n-m]%P;
}
int C(int n, int m) {
    return (LL)fact[n]*factInv[n-m]%P*factInv[m]%P;
}
void solve() {
    cin >> n >> m;
    PrevCalu();
    int res = 0;
    for(int i = 0; i <= n; i ++) {
        int x = (LL)C(n, i)*A(m, i)%P*A(m-i, n-i)%P*A(m-i, n-i)%P;
        res = ((LL)res + ((i&1) ? -1 : 1)*x)%P;
        res = ((LL)res+P)%P;
    }
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}
/*


从全错排的推导可以过来
https://zhuanlan.zhihu.com/p/133818995

1. 容斥原理
    也先和普通的全错排证明一样,先确定某几个位置A, B相同 a_i == b_i --- C(n, i)
    在把这i个数填上                                              --- A(m, i)
    在剩下的位置A和B都随便放                                      --- A(m-i, n-i) * A(m-i, n-i)


(DP我现在也不是很看得懂,只先写了普通错排的DP)
2. DP
    f[i], 为i位错排的方案数
    对即将要放的数,同普通的全错排的考虑
    将i放在k的位置,若k在i的位置,那么就不用考虑i和k了,剩下的错排
    再考虑有i-1种可能这样的情况                                   --- (i-1)*f[i-2]
    将i放在k的位置,而k不在i的位置,那么不管i(i已经合法,即已经错排)
    而这种情况,我们预设k不在i,那就可以把i的位置当作k的原本的位置
    除i外的i-1个数错排的方案数                                    --- (i-1)*f[i-1]
*/

172F - Unfair Nim

需要先知道Nim的结论

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#pragma GCC optimize(2)

#include <bits/stdc++.h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int n;

void solve() {
    cin >> n;
    vector<LL> a(n);
    for(auto &x : a) cin >> x;
    LL Xor = 0, And = 0, Add = a[0]+a[1];
    for(int i = 2; i < n; i ++) Xor ^= a[i];
    // a+b = a^b + 2*(a&b)
    And = Add-Xor;
    // Xor是期望的值,而不是式子里确定的值,导致以下不合法的情况,包括下面需要判断的不合法也是因为这个
    if(Xor > Add || And % 2) {
        cout << "-1\n";
        return;
    }
    And /= 2;
    /*
        a^b a&b     a   b
         0   0  ->  0   0
         1   1  ->  x   x   (不合法)
         0   1  ->  1   1
         1   0  ->  不 同
    */
    LL ans = And;
    for(int i = 60; i >= 0; i --) {
        int xx = Xor>>i&1, yy = And>>i&1;
        if(xx && yy) {
            cout << "-1\n";
            return;
        }
        if(xx && !yy && (ans|1LL<<i) <= a[0]) {
            ans |= 1LL<<i;
        }
    }
    if(!ans || ans > a[0]) {
        cout << "-1\n";
        return;
    }
    cout << a[0]-ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023年01月09日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
codeforces 1335E1+E2(思维)
数字出现的次数,这样就可以方便的找到出现次数最多的数字。然后枚举第一个和第三个区间即可,中间区间数字的个数也可以通过前缀和来计算
dejavu1zz
2020/10/23
2.6K0
codeforces 1335E1+E2(思维)
AtCoder Beginner Contest 177 A ~ E
C 思路:数据范围比较大,O(n^n)的复杂度肯定不可以,那么我们要分析式子 假设有一组数据:
杨鹏伟
2020/09/10
4120
【算法竞赛】分块入门九题题解
原文连接:「分块」数列分块入门1 – 9 by hzwer - 分块 - hzwer.com
Livinfly
2023/05/16
7060
AtCoder Beginner Contest 166 A ~~E
A 水题: #include<iostream> using namespace std; int main(){ string s; cin>>s; if(s=="ABC") cout<<"ARC"<<endl; else cout<<"ABC"<<endl; return 0; } B 水题: 主要是看懂就行,两个单词容易混淆,所以看样例理解比较好 #include<iostream> #define maxn 105 using namespace std; bool a[ma
杨鹏伟
2020/09/10
3290
【算法竞赛】Namomo Winter 2023 Day 3 Div 2
Dashboard - 2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest - Codeforces
Livinfly
2023/01/11
3660
AtCoder Beginner Contest 174 A ~ E
我看有人用指针来做的,其实道理是一样的,就是字符串中所有的R都在左边,然后所有的W都在右边就行了。
杨鹏伟
2020/09/10
3540
【算法竞赛】AtCoder Beginner Contest 284 D, F
赛时并没有意识到枚举范围在三次根号n里,加上自己手写的二分sqrt挂了(丢人),一直没过去,后面把sqrt部分改好也就过了。
Livinfly
2023/01/08
3300
AtCoder Beginner Contest 160 A ~ E
C 水题 题意:一开始没看懂题,就是围绕园的最北的那个点的距离,我一直看成了点都在池塘北面,在一条直线上!害
杨鹏伟
2020/09/11
2550
AtCoder Beginner Contest 160  A ~ E
AtCoder Beginner Contest 185 (手速场)
直接算C ( l − 1 , l − 12 )即可。由于题目中没有模数,偷懒使用了JAVA的大整数
dejavu1zz
2020/12/16
3350
AtCoder Beginner Contest 185 (手速场)
【算法竞赛 - 数据结构】数据分割
给T组数据,要把这些数据分割成,合法+非法(1个)。 输出,分割的组数,和每组组内的数据组数
Livinfly
2022/10/26
2660
【算法竞赛】CF #816 (Div. 2) A-D Rethink
因为是下取整,所以,如果从sum里分出的[x/k]结果大于0的话,其实是相当于没分出去。
Livinfly
2022/10/26
2270
【算法竞赛】CF #817(Div.4) A-G Rethink
呜,AB还好,C卡了一会儿(由于题意理解错误),D可以做差sort做,却模拟做,还WA了一发。
Livinfly
2022/10/26
2760
codeforces 1353E(dp)
题意描述 思路 image.png AC代码 #include<bits/stdc++.h> #define x first #define y second #define PB push_back
dejavu1zz
2020/10/23
3570
codeforces 1353E(dp)
AtCoder Beginner Contest 284(A~F)
A - Sequence of Strings ---- Original Link 题目大意: 输入 N 个字符串,倒序输出。 ---- 思想: 签到题。 ---- 代码: #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #include <queue> #include <stack> #i
浪漫主义狗
2023/02/18
4290
2020ICPC·小米 网络选拔赛热身赛
使用一个字符串来储存删除过后的字符串序列,使用一个变量来表示删除后的字符串下标。每次符合条件时,变量都要向前移3位,模拟这个过程即可。
dejavu1zz
2020/11/12
3030
2020ICPC·小米 网络选拔赛热身赛
【算法竞赛 - 搜索】Eight II
只是缺少了始末状态一致的数据,导致我血压高了几小时。(和标程对拍没有问题,交上去就WA)
Livinfly
2022/10/26
2280
AtCoder Beginner Contest 273(A~D)
A - A Recursive Function ---- Origional Link 题目大意: 求 f(k) 如下: f(0) = 1; f(k) = k \times f(k - 1) ---- 思想: 签到题。 ---- 代码: #include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <sstream> #include <vector> #
浪漫主义狗
2022/10/28
3210
2020年第一届辽宁省大学生程序设计竞赛
可以使用一个 p a i r pair pair数组来保存< i n t , s t r i n g int,string int,string>对,排序后按题意模拟即可。注意输出队员姓名的顺序是按照排名从大到小排列,并且要开 3 3 3倍 n n n的空间。
dejavu1zz
2020/11/24
5890
2020年第一届辽宁省大学生程序设计竞赛
【算法竞赛 - 搜索】Black And White
n*m的棋盘,用k种颜色(每种颜色可以染Ci次)染完,且没有十字相邻格子的颜色一致。
Livinfly
2022/10/26
3160
Codeforces Round #677 (Div. 3)
显然,如果最大值和最小值相同,则肯定不满足题意。否则,一定存在一个值mx,它的左右两边存在一个小于它的数。此时,该位置的鱼满足题意。
dejavu1zz
2020/10/21
5870
Codeforces Round #677 (Div. 3)
相关推荐
codeforces 1335E1+E2(思维)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档