这个题目真的是太长了，长到让人不想看完题目，看完后不想写的地步了，当时比赛的时候又是中午，没有睡午觉更是没心思看题了，好在最后还是耐下心来看题目，按照题目的意思一遍一遍的敲下来，发现题目也并不是很难，只是一道稍微复杂的题目，写完代码一交，wa了。仔细一看，是多组，需要初始化，加一下一交，又wa了，接下来就是漫长的debug，但我坚信代码没有错，于是不知道wa了多少发 ，一个多1小时过去了，数不尽的wa，我开始对代码产生了怀疑，便按照网上的题解去改，改的面目全非，还是wa，wa，wa。我TM就不信了，不做不来不吃饭！！！就这样时间来到了八点一十，一不小心，欸？我看到了一个double，难道记分规则的第四条要用double，答案显然是的，改一下一交，AC了，此时的代码已经面目全非了，我拿这第一次交的代码改一下类型，一交，欸？欸？AC了。我吐了
题目分析：题目很长，那不妨我们理一下思路，把题目所给的信息一步一步的写在抄稿纸上，理一下题目其实不难
算分的规则： 1. 如果你所在的队伍获得一等奖，那么你+36分 如果你所在的队伍获得二等奖，那么你+27分 如果你所在的队伍获得一等奖，那么你+18分 2. 女选手+33分 3. 在MaoMao Selection做的题目+2.5分 在Old Surgeon Contest做的题目+1.5分 不在这两个OJ但是题目序号是素数的+1分 其余的题目+0.3分 4. 你参加的比赛场次如果大于等于三场 那么取分数第三高的分数 加上max(0, (r - 1200) / 100) * 1.5分数
题目分析：题目的意思就是把两个数中的其中一个数拆开分成三个数，求的是三个数能够组成多少个不同的数，求所有情况中的最大值，也就是最多的不相同的数。暴力求解，暴力还是能做很多事情的，我们定义一个函数，把每种情况都存进一个数组里面，并且把存进去的数据标记一下，最后统计一下标记取最大值就行，但是在循环拆数的时候，我们只需要考虑前半部分降低时间复杂度！
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int num[maxn]; int solve(int a, int b, int c) { int cnt = 0; memset(num, 0, sizeof(num)); cnt = 0; num[a] = 1; num[b] = 1; num[c] = 1; num[a + b] = 1; num[a + c] = 1; num[b + c] = 1; num[a + b + c] = 1; num[abs(a - c)] = 1; num[abs(a - b)] = 1; num[abs(b - c)] = 1; num[abs(a - b - c)] = 1; num[abs(b - c - a)] = 1; num[abs(c - a - b)] = 1; for (int i = 1; i <= 200; ++i) cnt += num[i]; return cnt; } int main() { int t, n, m; scanf("%d", &t); while (t--) { int ans = 0; scanf("%d%d", &n, &m); for (int i = 1; i <= n / 2; ++i) ans = max(ans, solve(i, n - i, m)); // ans = 0; for (int i = 1; i <= m / 2; ++i) ans = max(ans, solve(i, n, m - i)); printf("%d\n", ans); } return 0; }果断放弃贴一下大佬的代码
矩阵快速幂
题解参考链接 主要看思路，
#include <iostream> #include <numeric> #include <cstring> #include <stack> #include <algorithm> using namespace std; const int N = 2e7 + 10; typedef long long ll; int num[N], ncnt; struct EulerSieve { static const int MAXN = 2e7 + 10; int pri[MAXN], vis[MAXN] = {1, 1}, phi[MAXN] = {0, 1}, cnt; void work() { for (int i = 2; i < MAXN; i++) { if (!vis[i]) { pri[++cnt] = i; phi[i] = i - 1; } for (int j = 1; j <= cnt && (ll)i * pri[j] < MAXN; j++) { vis[i * pri[j]] = 1; if (i % pri[j] == 0) { phi[i * pri[j]] = phi[i] * pri[j]; break; } phi[i * pri[j]] = phi[i] * phi[pri[j]]; } } } } eulerSieve; struct Matrix { int m[3][3]; } I, mat; int MOD, n; void init() { for (int i = 1; i <= 2; i++) { for (int j = 1; j <= 2; j++) { if (i == j) I.m[i][j] = 1; } } mat.m[1][1] = 1; mat.m[1][2] = 1; mat.m[2][1] = 1; } struct Matrix operator*(struct Matrix &a, struct Matrix &b) { struct Matrix tmp; for (int i = 1; i <= 2; i++) { for (int j = 1; j <= 2; j++) { int sum = 0; for (int k = 1; k <= 2; k++) { sum = (sum + (ll)a.m[i][k] * b.m[k][j]) % MOD; } tmp.m[i][j] = sum; } } return tmp; } int qpow(int q, int m) { if (q == 1 || q == 2) return 1; q -= 2; MOD = m; Matrix res = I, rem = mat; while (q) { if (q & 1) res = res * rem; rem = rem * rem; q >>= 1; } int x = 0; for (int i = 1; i <= 2; i++) x = (x + res.m[1][i]) % MOD; return x; } int main() { eulerSieve.work(); num[++ncnt] = 3; num[++ncnt] = 4; for (int i = 5; i < N; i++) { if (!eulerSieve.vis[i]) { num[++ncnt] = i; } } init(); int T; scanf("%d", &T); while (T--) { int k, x, m; scanf("%d %d %d", &k, &x, &m); for (int i = num[k];; i++) { int res = qpow(i, x); if (res == 0) { printf("%d\n", qpow(i, x * m) / x); break; } } } return 0; }简单的模拟题
题目分析：题目有点长，但是题目的意思不难理解就是说给出传输线和总线，求出传输线和总线的比例，并且如果有重复的只计算其中的一条，我们用一个二维数组去记录每条边的信息，如果这条边没有出现过，那么就记录一下，为了防止后序有重复的边加进来，我们每次加边的时候都存两次，一个正向，一个反向，最后我们只需要计算一下加进来的边就行
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int maxn = 1e3 + 10; int a[maxn], pre[maxn], b[maxn], sum[maxn][maxn]; int main() { int t; scanf("%d", &t); while (t--) { memset(sum, 0, sizeof(sum)); int n, m; int cnt = 0; scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++i) scanf("%d", &a[i]); for (int i = 1; i <= m; ++i) scanf("%d", &b[i]); for (int i = 1; i <= m; ++i) { if (sum[a[i]][b[i]] == 0 && sum[b[i]][a[i]] == 0) { sum[a[i]][b[i]] = 1; sum[b[i]][a[i]] = 1; ++cnt; } } // cout << cnt << endl; double ans = (double)((cnt)*1.0 / n); printf("%.3lf\n", ans); } }模拟题
题目分析：刚开始的时候，我以为是一个并查集，因为涉及到朋友之间的关系嘛，然后写着写着发现不对，这个题目中朋友之间的关系没有直接传递性，并且题目让我们求的就是传递性，就是说如果两个人有共同的朋友的个数超过k个那么经过一段时间他们就是成为新的好朋友。
这个题目是队友做的，后面比赛结束之后我看了代码，有两个地方可能需要仔细琢磨，下面我给出自己的想法
while循环的问题
起初我不是很理解为什么要加一个while，我觉得直接判断，遍历完之后然后就知道答案，其实不是这样的，我们每加进来一对关系都会对之前的关系产生影响，也就是说while循环在这里的作用就是反复遍历，直到不能产生新的关系为止，一直到产生不了新的关系为止才是答案，这样flag就等于1就可以跳出循环了
判断条件tot>=k的位置
起初我把判断是否有超过k个共同的朋友放到if条件语句里面了，这样是错误的，放到里面虽然样例是过了，但是我们都知道过了样例不一定会过题，也就是说下面的代码是错误的，我们少考虑了一种情况，就是当不需要创建新的关系，也就是说原先的朋友关系以及存在共同好友大于等于k的情况，这样我们就直接加一，并且把他们标记为好朋友，否则不这样的话就会出错
错误判断代码
if (dp[i][no] == 1 && dp[j][no] == 1) { tot++; if (tot >= k) { sum++; flag = 0; dp[i][j] = 1; dp[j][i] = 1; break; } }正确判断代码
for (int no = 0; no < a; no++) { if (dp[i][no] == 1 && dp[j][no] == 1) tot++; if (tot >= k) { sum++; flag = 0; dp[i][j] = 1; dp[j][i] = 1; break; } }AC代码：
#include <bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; int dp[110][110]; int main() { int t; scanf("%d", &t); while (t--) { int a, b, k; scanf("%d%d%d", &a, &b, &k); memset(dp, 0, sizeof(dp)); for (int i = 1; i <= b; i++) { int q, p; scanf("%d%d", &q, &p); dp[q][p] = 1; dp[p][q] = 1; } int sum = 0; while (1) { int flag = 1; for (int i = 0; i < a; i++) for (int j = 0; j < a; j++) if (dp[i][j] == 0 && i != j) { int tot = 0; for (int no = 0; no < a; no++) { if (dp[i][no] == 1 && dp[j][no] == 1) tot++; if (tot >= k) { sum++; flag = 0; dp[i][j] = 1; dp[j][i] = 1; break; } } } if (flag) break; } printf("%d\n", sum); } }题目大意：
a做坏事的条件：在寝室连续呆了T分钟，或者被阻止后T分钟 a不做坏事的条件：离开寝室或者被阻止
已知门开关m次的时间，但不知道谁进出
dp[i] [j] [k] [l] i表示第i次开门 j用二进制表示a,b在不在 k表示开始玩游戏的时间 l表示剩下几次阻止
#include<bits/stdc++.h> using namespace std; int T, N, M, K; int arr[110]; double dp[110][4][110][110];//00 no a, b 01 a 10 b 11 a, b int main() { int t; scanf("%d", &t); while(t--) { scanf("%d %d %d %d", &T, &N, &M, &K); for(int i = 1; i <= N; ++i) scanf("%d", arr + i); memset(dp, 0, sizeof dp); dp[0][0][0][M] = 1.0; for(int i = 1; i <= N; ++i) { int sub = arr[i] - arr[i - 1]; //0 for(int j = 0; j <= M; ++j) { dp[i][0][0][j] += dp[i - 1][0][0][j] * (K - 2.0) / K; dp[i][1][0][j] += dp[i - 1][0][0][j] * 1.0 / K; dp[i][2][0][j] += dp[i - 1][0][0][j] * 1.0 / K; } //1 for(int j = 0; j <= T; ++j) { for(int k = 0; k <= M; ++k) { dp[i][0][0][k] += dp[i - 1][1][j][k] * 1.0 / K; dp[i][1][min(T, j + sub)][k] += dp[i - 1][1][j][k] * (K - 2.0) / K; if(j + sub >= T) { dp[i][3][0][max(0, k - 1)] += dp[i - 1][1][j][k] * 1.0 / K; } else { dp[i][3][j + sub][k] += dp[i - 1][1][j][k] * 1.0 / K; } } } //2 for(int j = 0; j <= M; ++j) { dp[i][0][0][j] += dp[i - 1][2][0][j] * 1.0 / K; dp[i][2][0][j] += dp[i - 1][2][0][j] * (K - 2.0) / K; dp[i][3][0][j] += dp[i - 1][2][0][j] * 1.0 / K; } //3 for(int j = 0; j <= T; ++j) { for(int k = 0; k <= M; ++k) { dp[i][1][(j + sub) % T][max(0, k - (j + sub) / T)] += dp[i - 1][3][j][k] * 1.0 / K; dp[i][2][0][max(0, k - (j + sub) / T)] += dp[i - 1][3][j][k] * 1.0 / K; dp[i][3][(j + sub) % T][max(0, k - (j + sub) / T)] += dp[i - 1][3][j][k] * (K - 2.0) / K; } } } int sub = 1440 - arr[N]; double ans = 0; for(int i = 0; i < 4; ++i) { for(int j = 0; j <= T; ++j) { for(int k = 0; k <= M; ++k) { if(i != 3) ans += dp[N][i][j][k] * k; else ans += dp[N][i][j][k] * max(0, k - (j + sub) / T); } } } printf("%.6f\n", ans); } return 0; }简单的模拟题
题目大意：计算公式，算最大最小
当时脑子一抽，没想打好的方法就一步一步。。。。的写了下来，还挺不容易的，最大的话那就把大的数放在后面相乘，最小的话就把大的数放在前面就行
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int maxn = 1e6 + 10; int a[maxn], pre[maxn]; int main() { int t; scanf("%d", &t); while (t--) { int a, b, c; scanf("%d%d%d", &a, &b, &c); int aa = a, bb = b, cc = c; int aaa = a, bbb = b, ccc = c; int maxx = 0, minn = 0; while (a) { minn += 300 * ((a - 1) * 2 + 1); a--; } while (b) { minn += 100 * ((aa + b - 1) * 2 + 1); b--; } while (c) { minn += 50 * ((aa + bb + c - 1) * 2 + 1); c--; } while (ccc) { maxx += 50 * ((ccc - 1) * 2 + 1); ccc--; } while (bbb) { maxx += 100 * ((cc + bbb - 1) * 2 + 1); bbb--; } while (aaa) { maxx += 300 * ((cc + bb + aaa - 1) * 2 + 1); aaa--; } printf("%d %d\n", minn, maxx); } }代码二：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <cstdlib> #include <queue> #include <stack> #include <vector> using namespace std; int a[4]; int b[4] = {0, 300, 100, 50}; int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d%d", &a[1], &a[2], &a[3]); int sum = -1, sum2 = -1; int minn = 0, maxx = 0; for (int i = 1; i <= 3; i++) { for (int j = 1; j <= a[i]; j++) { sum++; minn += b[i] * (sum * 2 + 1); } } for (int i = 3; i >= 1; i--) { for (int j = 1; j <= a[i]; j++) { sum2++; maxx += b[i] * (sum2 * 2 + 1); } } printf("%d %d\n", minn, maxx); } }简单的进制转换问题
题目的意思可能看不懂，其实我刚开始也没看懂，不过后面看了网上的题解就慢慢理解了，但是网上的代码都是不能ac的，因为现在的zoj不支持gets这个玄学的东西，所以我们只能用string去定义了，但是用string去定义的时候就输出的时候稍微有点麻烦，因为它不像C语言的输入输出一样可以用X，想要大写那么X就大写。小写的话就x，所以输出的时候我们需要处理一下，接下来就是题目主要的意思了
首先，我们要获取字符串的长度，然后按照十六进制输出这个长度其次我们对于每一位的字符都要按照十六进制输出，并且每一位占两个字符，不足的地方用0来填充那么我们该如何按照题目的意思来呢，首先题目需要先转化成二进制然后转换成十六进制，其实不用这么麻烦，我们直接对128取模就是前面七位，如果取余之后还有数字说明要在第八位加上一个1，二进制的第八位就是128，所以我们直接加上128就行，这样就省去了中间二进制的转换
#include <bits/stdc++.h> using namespace std; string str; void put16(int x) { if (x <= 9) cout << char(x + '0'); else cout << char(x - 10 + 'A'); } void put256(int x) { put16(x / 16); put16(x % 16); } int main() { int T; cin >> T; getchar(); while (T--) { getline(cin, str); int len = str.length(); if (len == 0) { cout << "00" << endl; continue; } while (len) { int rem = len % 128; len /= 128; if (len) rem += 128; put256(rem); } for (int i = 0; i < str.size(); i++) put256(str[i]); cout << endl; } return 0; }简单模拟题
由于刚刚开始没有仔细看清题目的意思，以为就是一个简单的求前缀和的题目，但是其实不是这样的，题目的意思是，每个人都有一个数，然后这些人围城一个圈，老师会从n个人里面连续的请出几位同学，求取出的最大值是多少，因为数据比较小，完全可以暴力求解，我们依次遍历每一个数，并在每一个数往后m个数字求和，遍历完之后取最大值就是答案，但是这里因为是一个圈，所以我们需要对其作出取余处理，保证不越界。
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> using namespace std; typedef long long ll; const int maxn = 1e6 + 10; int a[maxn]; int main() { int n, m, t, ans; scanf("%d", &t); while (t--) { int sum = 0; scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < n; ++i) { ans = 0; for (int j = i; j < i + m; ++j) ans += a[j % n]; if (sum < ans) sum = ans; } printf("%d\n", sum); } return 0; }题意:有个小屁孩想当班级扛把子 他可以用糖果收买别人 最后要求他的票数是最多的，其他人都比他少 。我们就能枚举假设他K票当选 则其他人票数一定小于K。我们让超过K票的人票数变为K-1 多的票给1号 。若是现在都小于K然而1的票还是少于K则从花费最少糖果且未被标记的人那边拿票直至等于K；至于会不会出现他是K其余都是k-1 然后他投给别人使存在俩个K是不可能的 因为 假设每个人都投给自己则每人都是1 小屁孩至少是从2 开始枚举 说明至少有一个人为0票
#include <bits/stdc++.h> using namespace std; const int maxn = 1e3 + 10; struct node { int c, f; bool operator<(const node x) const { return c < x.c; } } a[maxn], b[maxn]; int cnt[maxn], c[maxn], n, vis[maxn]; int main() { int t; scanf("%d", &t); while (t--) { scanf("%d", &n); int ans = 0x3f3f3f3f; memset(cnt, 0, sizeof(cnt)); for (int i = 2; i <= n; ++i) scanf("%d", &a[i].f), cnt[a[i].f]++; for (int i = 2; i <= n; ++i) scanf("%d", &a[i].c); for (int k = max(1, cnt[1]); k <= n; ++k) { memset(vis, 0, sizeof(vis)); int sum = cnt[1], tans = 0; for (int i = 2; i <= n; ++i) { if (cnt[i] >= k) { sum += cnt[i] - k + 1; int len = 0; for (int j = 2; j <= n; ++j) { if (a[j].f == i) b[++len].c = a[j].c, b[len].f = j;//这里要记录的是已经买的编号，不是之前投票人的编号了 } sort(b + 1, b + len + 1); for (int j = 1; j <= cnt[i] - k + 1; ++j) { tans += b[j].c; vis[b[j].f] = 1;//记录已经买了哪些人 } } } int len = 0; for (int i = 2; i <= n; ++i) { if (!vis[i] && a[i].f != 1) c[++len] = a[i].c;//不支持自己，并且自己没有贿赂的人 } sort(c + 1, c + len + 1); for (int i = 1; i <= k - sum; ++i)//票数不够的情况就继续贿赂 tans += c[i]; ans = min(tans, ans); } printf("%d\n", ans); } return 0; } 路遥曾言：“人处在这种默默奋斗的状态，精神就会从琐碎生活中得到升华” 。