首页 > 其他分享 >2023.1.12

2023.1.12

时间:2023-01-14 00:33:41浏览次数:51  
标签:cnt 12 const int lim codeforces 2023.1 Statement

A.Odd Divisor

https://codeforces.com/contest/1475/problem/A

Statement

给定一个正整数 \(n \ (2 \leq n \leq 10 ^ {14})\) ,判断其是否至少有一个大于 \(1\) 的奇因子。

Solution

若 \(n\) 为奇数,那 \(n\) 本身就是一个符合条件的奇因子。

考虑偶数的情况:偶数可以由两个偶数相乘得到,也可以通过一奇一偶相乘得到。能被表示成 \(2\) 的 \(x\) 次幂的 \(n\) 只会属于第一种情况,其他则可以表示为第二种。判断 \(n\) 是否为 \(2\) 的 \(x\) 次幂有两种方法:(1) 看 \(n \& (n - 1)\) 是否为 \(0\)。(2)不断除 \(2\) 直至最后变成 \(1\),途中不出现奇质因子。

B.Advertising Agency

https://codeforces.com/contest/1475/problem/E

Statement

给定 \(n\) 个数,从中选 \(k\) 个,要求 \(\sum _{i = 1} ^ {k} a_i\) 最大,求方案数。

Solution

由于 \(sum\) 最大且固定,那么所有方案本质上都是相同的。(反证法:将 \(a_1, a_2, \cdots a_n\) 按降序排序,若存在 \(a_j (k < j \leq n)\) 使得方案更优,说明 \(a_j > a_k\), 那其必定排在前 \(k\) 大,与已知条件矛盾)。

故答案取决于前 \(k\) 大的数中,最小的那个数 \(x\) 的个数。令 \(cnt_x\) 表示 \(n\) 个数中 \(x\) 出现的次数,\(cnt_y\) 表示前 \(k\) 大的数中严格大于 \(x\) 的个数,易得答案为 \(\binom{cnt_x}{k - cnt_y}\)。

Code

#include <bits/stdc++.h>
const int lim = 1000;
const int mod = 1e9 + 7;
using namespace std;

int T, n, k, a[lim + 5], c[lim + 5][lim + 5];

void init() {
    c[0][0] = 1;
    for (int i = 1; i <= lim; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
}

int main() {
    ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	freopen("in","r", stdin);
    cin >> T;
    init();
    while (T--) {
        cin >> n >> k;
        for (int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1, greater<int>());
        int cnt1 = 0, cnt2 = 0, minn = a[k];
        for (int i = 1; i <= n; i++) {
            cnt1 += (a[i] == minn);
            cnt2 += (a[i] > minn);
        }
        cout << c[cnt1][k - cnt2] << "\n";
    }
	return 0;
}

C.Perfect Keyboard

https://codeforces.com/contest/1303/problem/C

Statement

给定一个仅包含小写字母且相邻字母不一样的字符串 \(s\),将 abcdefg...xyz 重排,重排后的字符串为 \(t\) ,询问是否能使得 \(s\) 中相邻的字母在 \(t\) 中也全部相邻,若可以则输出方案。

Solution

将 \(s\) 中相邻的字母进行连边(始终保证由字典序小的连接字典序大的),不难发现若出现度数大于 \(2\) 的节点或有环出现时,则答案不存在。否则可以从度数为 \(1\) 的点出发,对树进行深度优先遍历并记录路径,得到的答案序列则是符合条件的。

Code

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

string s;
int T, deg[N];
bool vis[N], g[N][N];

void dfs(int x, string &ans) {
    vis[x] = 1;
    ans += (char)('a' + x - 1);
    for (int i = 1; i <= 26; i++) {
        if ((!g[x][i]) || (vis[i]))
            continue;
        dfs(i, ans);
    }
}

int main() {
    ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	freopen("in","r", stdin);
    cin >> T;
    while (T--) {
        cin >> s;
        if ((int)s.length() == 1) {
            cout << "YES" << endl;
            for (char c = 'a'; c <= 'z'; c++) cout << c;
            cout << endl;
            continue;
        }
        for (int i = 0; i < (int)s.length() - 1; i++)
            g[s[i] - 'a' + 1][s[i + 1] - 'a' + 1] = g[s[i + 1] - 'a' + 1][s[i] - 'a' + 1] = 1;
        for (int i = 1; i <= 26; i++) {
            for (int j = i + 1; j <= 26; j++) {
                if (g[i][j]) {
                    deg[i]++;
                    deg[j]++;
                }
            }
        }
        bool flag = 0;
        for (int i = 1; i <= 26; i++)
            flag |= (deg[i] > 2);
        string ans = "";
        bool sign = 0;
        for (int i = 1; i <= 26; i++) {
            if (deg[i] == 1 && (!vis[i])) {
                sign = true;
                dfs(i, ans);
            }
        }
        if (flag || (!sign))
            cout << "NO" << endl;
        else {
            cout << "YES" << endl;
            for (char c = 'a'; c <= 'z'; c++) {
                if (!vis[c - 'a' + 1])
                    ans += c;
            }
            cout << ans << endl;
        }
        memset(g, 0, sizeof(g));
        memset(deg, 0, sizeof(deg));
        memset(vis, 0, sizeof(vis));
    }
	return 0;
}

标签:cnt,12,const,int,lim,codeforces,2023.1,Statement
From: https://www.cnblogs.com/BeyondLimits/p/17051042.html

相关文章

  • 等式的根-XJOIp1241
    题目描述:有这样一个式子   x2+S(x)∗x−n=0    x,n都是正整数, S(x)为x所有十进制数位的和 ,现在给你一个n,你需要找到最小的x使得等式成立。输入格式:输入一......
  • 干货|一图搞懂有源晶振和无源晶振的12点区别
     一、什么是晶振晶振是在电路中提供频率基准的被动元器件,它能产生频率高度稳定的交流信号,使得电路工作在一个稳定的频率范围内,广泛应用于汽车、数字、电子等行业。晶振可分......
  • 电动滑板车出欧盟EN17128:2020标准测试
    EN17128:2020《载人和货物及相关设施运输的轻型机动车辆,未经道路使用类型批准-轻型电动车辆(PLEV)》于2020年10月21日发布,该标准由技术委员会CEN/TC354负责编写,由法国标......
  • cef浏览12306网站不正常问题
    cef版本:​​cef_binary_3.2623.1401.gb90a3be_windows32.7z​​使用cef时,浏览其它网站正常,唯独浏览器www.12306.cn时不正常,真是不可思议,cefclien......
  • 前端Aes-128-ecb加密解密
    安装:npminstallcrypto-js  注意密码需要16位importutf8from'crypto-js/enc-utf8';importaesfrom'crypto-js/aes';importecbfrom'crypto-js/mode......
  • 12 图像色彩空间转换 - 进阶
    12图像色彩空间转换-进阶opencv知识点:色彩空间转换-cvtColor()提取指定色彩范围区域-inRange()更换图像背景-copyTo的mask用法本课所解决的问题:如何提取......
  • leetcode_数据结构_入门_121. 买卖股票的最佳时机
    121.买卖股票的最佳时机  问题:给定一个数组prices,它的第 i个元素 prices[i]表示一支给定股票第i天的价格。只能选择某一天买入这只股票,并选择在未来的某......
  • 【题解】P4126 [AHOI2009]最小割
    题意求最小割和可行边和必须边。思路清真,清真,还是**的清真。考虑可行边的充要条件:满流不存在另一条\(u,v\)间的最短路,即在残量网络上不存在包含\(u,v\)......
  • 1.12刷题记录
    1.[XMAN2018排位赛]通行证打开附件看出里面这是base64加密于是去解密然后又得到了新的密码--kanbbrgghjl{zb____}vtlaln这是栅栏密码然后一系列操作kzna{blnl_ab......
  • 闲话/社论 23.1.12
    u群看到的一道题挺好玩的,写篇博客参考资料:20210620省队互测-qwaszx题解,qwaszx;某篇没有链接的知乎回答,EI,Rebelz.定义一个\(1,2,\cdots,n\)的排列是好的,当......