A-细胞分裂
题目描述
CB不光是ACM大佬，同时也是生物领域的知名专家。现在，他正在为一个细胞实验做准备工作：培养细胞样本。
CB博士手里现在有N种细胞，编号从1~N，一个第i种细胞经过1秒钟可以分裂为Si个同种细胞（Si为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入M个试管，形成M份样本，用于实验。CB博士的试管数M很大，普通的计算机的基本数据类型无法存储这样大的M值，但万幸的是，M总可以表示为m1的m2次方，即M=m1^m2 ，其中m1，m2 均为基本数据类型可以存储的正整数。
注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有4个细胞，Hanks博士可以把它们分入2个试管，每试管内2个，然后开始实验。但如果培养皿中有5个细胞，博士就无法将它们均分入2个试管。此时，博士就只能等待一段时间，让细胞们继续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。
为了能让实验尽早开始，CB博士在选定一种细胞开始培养后，总是在得到的细胞“刚好可以平均分入M个试管”时停止细胞培养并开始实验。现在博士希望知道，选择哪种细胞培养，可以使得实验的开始时间最早。
输入描述:
每组输入数据共有三行。第一行有一个正整数N，代表细胞种数。第二行有两个正整数m1，m2，以一个空格隔开，m1^m2即表示试管的总数M。第三行有N个正整数，第i个数Si表示第i种细胞经过1秒钟可以分裂成同种细胞的个数。对于所有的数据，有1≤N≤10000，1≤m1≤30000，1≤m2≤10000，1≤Si≤2,000,000,000。输出描述:
每组输出共一行，为一个整数，表示从开始培养细胞到实验能够开始所经过的最少时间（单位为秒）。如果无论CB博士选择哪种细胞都不能满足要求，则输出整数-1。示例1
输入
2
24 1
30 12输出
2说明
下面是对样例数据的解释：第1种细胞最早在3秒后才能均分入24个试管，而第2种最早在2秒后就可以均分（每试管144/(241)=6 个）。故实验最早可以在2秒后开始。题目大意 : 有三个数N , M1, M2，N表示接下来有N个细胞，M1^M2表示试管数目， 输出所有细胞中最快可以实现 细胞数目 | (M1^M2)
思路 ： 质因子分解，用邻接表存储M1^M2的质因子，只分解M1， 用M2 * 分解的数目来表示质因子的数目， 然后遍历每个细胞，将每个细胞对应的每个质因子所需要的因子数目记录下来，求最大值，再求每个细胞最大值的最小值 （有点绕，具体看代码把QAQ）
AC代码 ：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e4 + 5;struct node
{int x, y; // x 表示质因子， y表示数目
};
ll p[MAXN], n, m1, m2, ans;
vector <node> e;int main()
{while (~scanf("%lld%lld%lld", &n, &m1, &m2)) {e.clear();for (int i = 0; i < n; i++) scanf("%lld", &p[i]);if (m1 == 1) { cout << 0 << endl; continue; }for (int i = 2; i <= m1; i++) {if (m1 % i == 0) {int num = 0;while (m1 % i == 0) {num++;m1 /= i;}e.push_back({ i, num * m2 });}} // 分解质因子ans = 0x3f3f3f3f; // 最终数据for (int i = 0; i < n; i++) {ll flag = 1, cnt = 0;for (int j = 0; j < e.size(); j++) {int x = e[j].x, y = e[j].y, tot = 0;if (p[i] % x != 0) { flag = 0; break; }//无法整除直接passwhile (p[i] % x == 0) {tot++; // tot表示需要多少个，与y比较p[i] /= x;}ll ma = y / tot;if (y % tot != 0) ma++; // 刚好不够 + 1cnt = max(cnt, ma);}if (!flag) cnt = 0x3f3f3f3f;ans = min(ans, cnt);}if (ans == 0x3f3f3f3f) cout << -1 << endl;else cout << ans << endl;}return 0;
}
B-A题
题目描述
A要去B的城市游玩，A在城市1居住，B在城市X居住，现在有一些神奇的传送门和一些奇神的传送门。
已知，神奇的传送门可以从编号小的城市传送往编号大的城市，奇神的传送门可以从编号大的城市传送往编号小的城市，但是在某些城市没有某种传送门。
那么已知数组a，其中ai代表着城市i是否有神奇的传送门(ai=1代表有，ai=0代表没有)，以及数组b，其中bi代表着城市i是否有奇神的传送门。
神奇的海螺想知道A能不能去B的城市玩。
输入描述:
多组测试样例。
每组测试样例的第一行有两个数字N和X，代表了城市的数量和B的居住地址（2 <= N <= 1000 2 <= X <= 1000）
第二行给出数组a，第三行给出数组b。输出描述:
可行，则输出YES
否则，输出NO示例1
输入
5 3
1 1 1 1 1
1 1 1 1 1
5 4
1 0 0 0 1
0 1 1 1 1
5 2
0 1 1 1 1
1 1 1 1 1输出
YES
YES
NO说明
第二组样例路线:1->5->4
题目大意 ： 输入两个数组，a【i】 为1表示可以从i 到达N之间任意城市， b【i】为1表示可以从i 到达1之间任意城市，起点为1，终点为X，输出能否由起点到达终点
思路 ： 先把特殊情况给判定了，首先是a【1】 == 0，这样从1就无法到达任意一个城市，其次是a【x】== b【x】 == 0，这样城市x就无法被到达；如果a【x】== 1， 那么1一定可以到达他。如果必须经过其他城市到达x的话，需要遍历x之后的城市，看是否可以双向到达
AC代码 ：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;bool a[MAXN], b[MAXN];
int n, x;int main()
{while (~scanf("%d%d", &n, &x)) {for (int i = 1; i <= n; i++) scanf("%d", &a[i]);for (int i = 1; i <= n; i++) scanf("%d", &b[i]);if (!a[1]) cout << "NO" << endl;else if (!a[x] && !b[x]) cout << "NO" << endl;else if (a[x]) cout << "YES" << endl;else {bool flag = 0;for (int i = x + 1; i <= n; i++) {if (a[i] && b[i]) { flag = 1; break;}}if (flag) cout << "YES" << endl;else cout << "NO" << endl;}}return 0;
}C-均分糖果
题目描述
有N堆糖果，编号分别为1，2，…，N。每堆上有若干个，但糖果总数必为N的倍数。可以在任一堆上取若干个糖果，然后移动。
移动规则为：在编号为1的堆上取的糖果，只能移到编号为2的堆上；在编号为N的堆上取的糖果，只能移到编号为N-1的堆上；其他堆上取的糖果，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上糖果数都一样多。
例如N=4，4堆糖果数分别为：
① 9 ② 8 ③ 17 ④ 6
移动3次可达到目的：
从③取4个糖放到④（9 8 13 10）->从③取3个糖放到②（9 11 10 10）->从②取1个糖放到①（10 10 10 10）。
输入描述:
每个测试文件包含多组测试数据，每组输入的第一行输入一个整数N（1<=N<=100），表示有N堆糖果。接下来一行输入N个整数A1 A2...An，表示每堆糖果初始数，1<=Ai<=10000。输出描述:
对于每组输入数据，输出所有堆均达到相等时的最少移动次数。示例1
输入
4
9 8 17 6输出
3题目大意 ： 一共有N个人，每个人手中的糖果不一样，需要实现所有人均分所有糖果，除1和N之外，所有人都只可以向两边发糖果，输出最少经过几次可以实现糖果均分
思路 ： 从第一个人开始，如果他手中糖果数目少于 sum / n， 那么向右边借（右边为负也没关系， 因为总会有人多出来），如果大于 sum / n， 那么就将多余的给右边的
AC代码 ：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 5;
int p[MAXN], n, m, ans;int main()
{while (cin >> n) {m = ans = 0;for (int i = 0; i < n; i++) {cin >> p[i];m += p[i];}m /= n;for (int i = 0; i < n; i++) {if (p[i] > m) { // 给右边p[i + 1] += (p[i] - m);ans++;}else { // 向右边借if (p[i] < m) {p[i + 1] += p[i] - m;ans++;}}}cout << ans << endl;}return 0;
}D-B题
题目描述
有一个连通图 包含 n 个点 n 条无向边 其中每个点都与其他的两个点直接相连 (即这是一个环)
现在这个环的边变成了有向边 变成了有向边后得到的有向图不一定是强连通的
(强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径及v2到v1的路径的图)
所以现在给出 n 条有向边和把某条有向边转换方向后的代价, 问要使输入的有向图变成一个强连通图
例如输入
3
1 3 1
1 2 1
3 2 1
表示有一条有向边 1 -> 3 如果把这条边变成 3 -> 1 的代价是 1
表示有一条有向边 1 -> 2 如果把这条边变成 2 -> 1 的代价是 1
表示有一条有向边 3 -> 2 如果把这条边变成 2 -> 3 的代价是 1
对于输入的这个有向图是不存在 2 -> 3 的路径的 所以可以把 有向边 1 -> 2 变为 2 -> 1 这样图中任意两点均相互可达
输入描述:
多组测试数据。第一行给出数字n，代表顶点数量 (3 ≤ n ≤ 100）。接下来n行给出路径。每行给出三个数字ai, bi, ci (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ci ≤ 100) — 代表ai指向bi。代价是ci。输出描述:
输出最小代价示例1
输入
3
1 3 1
1 2 1
3 2 1
3
1 3 1
1 2 5
3 2 1
6
1 5 4
5 3 8
2 4 15
1 6 16
2 3 23
4 6 42输出
1
2
39题目大意 ： 输入一张有向图（如果将所有边都变成无向那么将会是一个环），每条边对应一个权值，表示将这条边方向反过来需要该值，输出最小需要多少花费，才可以将有向图变成强连通图
思路 ： 有向图强连通，就是一个环，所以分两种情况，逆时针走和顺时针走。输入的时候开两个数组，一个记录正向边权值，一个记录反向边权值，再用bfs存一下形成环的路径，一次正向一次逆向，输出最小值即可
AC代码 ：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 5;int u[MAXN], v[MAXN], w, n;
int pre[MAXN], p1[MAXN][MAXN], p2[MAXN][MAXN], X;
bool vis[MAXN];
void init() {memset(u, 0, sizeof(u));memset(v, 0, sizeof(v));memset(p1, 0, sizeof(p1));memset(p2, 0, sizeof(p2));memset(vis, 0, sizeof(vis));memset(pre, 0, sizeof(pre));X = 0;
}
void bfs() { // 记录成环路径memset(vis, 0, sizeof(vis));queue <int> q;vis[1] = 1;q.push(1);while (!q.empty()) {int now = q.front();q.pop();for (int i = 1; i <= n; i++) {if (!vis[i]) {if (u[i] == pre[X]) vis[i] = 1, pre[++X] = v[i], q.push(i);else if (v[i] == pre[X]) vis[i] = 1, pre[++X] = u[i], q.push(i);}}}
}int main()
{while (~scanf("%d", &n)) {init();for (int i = 1; i <= n; i++) {scanf("%d%d%d", &u[i], &v[i], &w);p1[u[i]][v[i]] = w; // 正向权值p2[v[i]][u[i]] = w; // 反向权值}pre[++X] = u[1], pre[++X] = v[1]; bfs();int ans = 0, tot = 0;X --;for (int i = 1; i <= X; i++) {ans += p1[pre[i]][pre[i + 1]]; // 记录两个权值tot += p2[pre[i]][pre[i + 1]];}cout << min(ans, tot) << endl;}return 0;
}E-很简单的题。。。。。。
题目描述
统计某个给定范围[L, R] 的所有整数中，数字2出现的次数。比如给定范围[2, 22] ，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。
输入描述:
每组输入数据共1行，为两个正整数L和R，之间用一个空格隔开。（1≤L≤R≤10000）输出描述:
每组输出共1行，表示数字2出现的次数。示例1
输入
2 100输出
20思路 ： 暴力就能过
AC代码 ：
#include<bits/stdc++.h>
using namespace std;int n, m, ans;int main()
{while (cin >> n >> m) {ans = 0;for (int i = n; i <= m; i++) {int temp = i;while (temp) {int w = temp % 10;if (w == 2) ans++;temp /= 10;}}cout << ans << endl;}return 0;
}
F-最大公约数和最小公倍数
题目描述
输入2个正整数x0，y0（2<=x0<100000，2<=y0<=1000000），求出满足下列条件的P，Q的个数。
条件：
1. P，Q是正整数；
2. 要求P，Q以x0为最大公约数，以y0为最小公倍数。
试求：
满足条件的所有可能的两个正整数的个数。
输入描述:
每个测试文件包含不超过5组测试数据，每组两个正整数x0和y0（2<=x0<100000，2<=y0<=1000000）。输出描述:
对于每组输入数据，输出满足条件的所有可能的两个正整数的个数。下面是对样例数据的说明：输入3 60此时的P Q分别为:3 60
15 12
12 15
60 3所以，满足条件的所有可能的两个正整数的个数共4种。示例1
输入
3 60输出
4思路 ： 也是直接暴力就能过
AC代码 ：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;ll x, y, ans;
ll gcd(ll a, ll b) {if (!b) return a;else return gcd(b, a % b);
}int main()
{while (~scanf("%lld%lld", &x, &y)) {ll temp = x * y;ans = 0;for (ll i = x; i * i <= temp; i++) {if (temp % i == 0) {ll c = temp / i;if (gcd(c, i) == x && gcd(c, i) * y == temp) ans++;}}cout << ans * 2 << endl;}return 0;
}G-毕业生的纪念礼物
题目描述
现在有n个纪念品，每个纪念品都有一个种类r[i]，现在要求对每个毕业生分发三个种类不同的纪念品，现在需要你来计算下共可以发给多少个毕业生？
输入描述:
第一行一个整数n，1≤n≤100000，代表纪念品的个数；
第二行包含n个整数，分别是r[1], r[2], r[3]......r[n]，1≤r[i]≤1e9，表示每个纪念品所属的种类。输出描述:
输出一个整数，代表最多能够分发给的毕业生人数。示例1
输入
14
1 1 2 2 3 3 4 4 4 4 5 5 5 5输出
4示例2
输入
7
1 2 3 4 5 6 7输出
2题目大意 ： 如题目所说
思路 ：用map将所有的种类保存下来，再用队列记录，每次弹出三个最大的并更新次数即可
AC代码 ：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAXN = 1e5 + 5;ll n, m, ans;
map <ll, ll> mp;
priority_queue <ll, vector <ll>, less <ll> > q;int main()
{cin >> n;for (int i = 0; i < n; i++) {cin >> m;mp[m]++;}for (auto it : mp) q.push(it.second);while (q.size() >= 3) {ll ai = q.top();q.pop();ll bi = q.top();q.pop();ll ci = q.top();q.pop();ai--, bi--, ci--;if (ai) q.push(ai);if (bi) q.push(bi);if (ci) q.push(ci);ans++;}cout << ans << endl;return 0;
}H-毕业生的序列游戏
这个不会。。。T_T
I-你的粪坑v1
题目描述
剪刀石头布，谁输谁吃屎。
输入描述:
第一行一个整数T，代表测试数据个数。每个测试数据包括两行数据。第一行数据为两个字符串A，X1，代表A同学的出拳为X1。第二行数据为两个字符串B，X2，代表B同学的出拳为X2。其中A,B是字符串，长度为[0,10]，代表同学名字。其中X1,X2是字符串，内容为"jiandao","shitou","bu"三者之一。输出描述:
对每个测试数据A同学赢输出"{$B} chishi."，其中{$B}代表B同学名字B同学赢输出"{$A} chishi."，其中{$A}代表A同学名字如果平局，输出"yi qi chi shi."示例1
输入
3
jiang jiandao
wang shitou
jiang bu
wang jiandao
jiang shitou
wang shitou输出
jiang chishi.
jiang chishi.
yi qi chi shi.说明
注意空格思路 ： 直接模拟就好
AC代码 ：
#include<bits/stdc++.h>
using namespace std;int T;
string c1, str1, c2, str2;int main()
{cin >> T;while (T--) {cin >> c1 >> str1 >> c2 >> str2;if (str1 == str2) cout << "yi qi chi shi." << endl;else {if (str1 == "jiandao") {if (str2 == "shitou") cout << c1 << " chishi." << endl;else if (str2 == "bu") cout << c2 << " chishi." << endl;}else if (str1 == "shitou") {if (str2 == "jiandao") cout << c2 << " chishi." << endl;else if (str2 == "bu") cout << c1 << " chishi." << endl;}else if (str1 == "bu") {if (str2 == "jiandao") cout << c1 << " chishi." << endl;else if (str2 == "shitou") cout << c2 << " chishi." << endl;}}}return 0;
}
J-你的粪坑v2
题目描述
一听说这是一场正经比赛，都没人用昵称了？好吧，那就用“你”吧，请自行代入聚聚名字！
这是一道充满味道的题目。
今天举办程序设计比赛，2点30分开始，然而你睡到了2点25分，紧张的你将头发梳成大人模样，敷上一层最贵的面膜，穿着滑板鞋，以飞一般的速度奔向计算机学院准备参加程序设计竞赛！冠军是你的！
然而路上稍不留神，你不小心掉进了一个大粪坑，大粪坑是一个N*N的方格矩阵，每个方格存在着X坨粪，一开始你处在A11的粪坑位，你可以选择向下移动或者向右移动，目标是逃离大粪坑到达ANN。
此外！！敲重点！！每经过一个粪坑，你会触及粪量X（粗俗的说法叫做吃shi），而且每更改一次方向，传说中的粪皇会向你丢粪！！
粪皇是个学过二进制的优雅美男子，所以他丢粪也是相当的儒雅随和。第一次他会向你丢1坨，第二次他会向你丢2坨哦，第三次他会向你丢4坨哦！第四次他会向你丢8坨哦！第五次他会向你丢16坨哦！….，第N次他会向你丢2N-1坨哦！嘤嘤嘤～～～～～～～
机智的你绝不会向粪皇低头！所以你拿起手中的笔记本，打开Codeblocks，写下#include<bits/stdc++.h>，开始计算如何掉最少的发，吃最少的shi，冲出粪坑，到达计院，拿下冠军！
输入描述:
第一行是一个整数T，代表测试数据个数。
对每个测试数据第一行是一个整数N，代表粪坑大小为N*N (1 ≤ N ≤ 100) 。
接下来N行每行N个整数，代表粪坑矩阵A中每个粪坑位的粪量(1 ≤ Aij ≤ 100)。
输出描述:
最少吃shi量示例1
输入
1
3
1 4 6
1 1 3
6 1 1输出
10题目大意 ： 题目太恶心。。我换个方式表达吧QAQ， 起点为（1， 1） 终点为 （n， m）， 只可向下或向右走，并且每次换方向时都会附加一些权值，大小为2^(换方向次数 – 1)， 输出最小权值和
思路 ： 用dp写，一共有四种状态， 1 ：方向向右往右走，这种的权值就是上一步权值 + p【i】【j】 2 ： 方向向右往下走，这时候权值就是上一步权值 + 2^（上一步换方向次数 – 1） + p【i】【j】。另一种也是一样的道理
AC代码 ：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e2 + 5;
const int INF = 0x3f3f3f3f;int dp[MAXN][MAXN][MAXN][2], p[MAXN][MAXN]; // dp【i】【j】【换方向次数】【方向】
int n, T; // 0表示向右，1表示向下int main()
{cin >> T;while (T--) {scanf("%d", &n);memset(dp, INF, sizeof(dp));for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) scanf("%d", &p[i][j]);}dp[1][1][0][1] = dp[1][1][0][0] = p[1][1]; // 初始化for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) { // 换方向次数太多的话就不划算了for (int k = 0; k <= min(20, n); k++) { dp[i][j][k][0] = min(dp[i][j][k][0], dp[i - 1][j][k][0] + p[i][j]);if (k)dp[i][j][k][0] = min(dp[i][j][k][0], dp[i][j - 1][k - 1][1] + p[i][j] + (1 << (k - 1)));dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j - 1][k][1] + p[i][j]);if (k)dp[i][j][k][1] = min(dp[i][j][k][1], dp[i - 1][j][k - 1][0] + p[i][j] + (1 << (k - 1)));}}}int ans = INF; // 由于无法确定你换了多少次方向，所以要遍历换方向次数求最小for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {for (int k = 0; k <= min(20, n); k++)ans = min({ ans, dp[n][n][k][1], dp[n][n][k][0] });}}cout << ans << endl;}return 0;
}
K-你的Alice
题目描述
今天你Bob和你的Alice进行一场比赛。
有N根棒，你和你的Alice轮流取棒，规定你们每人一次取K个，当不够K个的时候，你们把余下的扔掉并停止游戏。
你比较疼你的Alice，所以Alice先取，问最终Alice能否取得更多？
输入描述:
单组测试数据。包括2个整数N和K，代表有N根棒，以及Alice和Bob每次取K个棒。1<=N<=1000000000001<=k<=100输出描述:
如果Alice最终拥有更多的棒，输出YES，否则输出NO。（全大写）示例1
输入
10 4输出
NO题目大意 ： 如题目所说QAQ
思路 ： 分两种情况，一种是可以整除，那整除后为奇数的话一定是第一个人多拿了一份。如果不可整除，如果除完之后的数为奇数的话一定是第二个人会少拿一部分
AC代码 ：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;ll n, k;int main()
{cin >> n >> k;ll temp = n % k, ans = n / k;if (!temp) { // 可以整除if (ans & 1) cout << "YES" << endl; // 奇数的话第一个人一定多拿else cout << "NO" << endl;}else { // 无法整除if (temp & 1) cout << "YES" << endl; // 奇数的话第二个人拿的少else cout << "NO" << endl;}return 0;
}