A_数字方阵
思路 假如 我们按照
1 2 3 4 5 6 7 8 9
就会发现 每一行 每一列 都不一样 但是 两条对角线上的元素是一样的
这样的话
1 2 7 3 4 8 5 6 9
我将前两列按照 这样的顺序 排 然后最后一排改一下 就可以了。
其实不一定是这样 还是有很多其它排列的方法的
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e3 + 10; const int MOD = 1e9 + 7; int G[maxn][maxn]; int main() { int n; scanf("%d", &n); int pos = 1; for (int i = 0; i < n; i++) for (int j = 0; j < n - 1; j++) G[i][j] = pos++; for (int i = 0; i < n; i++) G[i][n - 1] = pos++; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) printf("%d%c", G[i][j], (j == n - 1) ? '\n' : ' '); }B_小马过河
思路
其实问题就是 给出一个点P 给出一条线 L 找出一条线 L’ 使得 L’ 经过点P 并且垂直于线L 然后求出 两线交点就可以
假如线L 的一般式为 Ax+By+c = 0 那么垂直于线L的直线束就是 Bx - Ay + m = 0 那么把点P 代入直线束 就可以求出参数m 也就得到 两条线了 再求交就可以
那么问题来了 给出两点 怎么求一条线L的一般式呢
参考博客
http://www.cnblogs.com/DHUtoBUAA/p/8057056.html
A=Y2-Y1 B=X1-X2 C=X2*Y1-X1*Y2
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int MOD = 1e9 + 7; int main() { int t; cin >> t; while (t--) { double px, py, ux, uy, vx, vy; scanf("%lf%lf%lf%lf%lf%lf", &px, &py, &ux, &uy, &vx, &vy); double A = vy - uy; double B = ux - vx; double C = vx * uy - ux * vy; double m = A * py - B * px; double y = (A * m - B * C) / (A * A + B * B); double x = (A * y - m) / B; printf("%.7lf %.7lf\n", x, y); } }C_真真假假
思路 这个其实很简单 ，把所有头文件用map 标记一下 然后每次输入 都查找一下是否存在就可以了
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 20 + 10; const int MOD = 1e9 + 7; map <string, int> m; void init() { m["algorithm"] = 1; m["bitset"] = 1; m["cctype"] = 1; m["cerrno"] = 1; m["clocale"] = 1; m["cmath"] = 1; m["complex"] = 1; m["cstdio"] = 1; m["cstdlib"] = 1; m["cstring"] = 1; m["ctime"] = 1; m["deque"] = 1; m["exception"] = 1; m["fstream"] = 1; m["functional"] = 1; m["limits"] = 1; m["list"] = 1; m["map"] = 1; m["iomanip"] = 1; m["ios"] = 1; m["iosfwd"] = 1; m["iostream"] = 1; m["istream"] = 1; m["ostream"] = 1; m["queue"] = 1; m["set"] = 1; m["sstream"] = 1; m["stack"] = 1; m["stdexcept"] = 1; m["streambuf"] = 1; m["string"] = 1; m["utility"] = 1; m["vector"] = 1; m["cwchar"] = 1; m["cwctype"] = 1; } int main() { init(); int t; cin >> t; while (t--) { string s; cin >> s; puts(m[s]?"Qian":"Kun"); } }D_虚虚实实
思路 这个其实就是判断一下给的无向图是不是欧拉通路 只需要判断一下 点的度数为奇数的个数 是否等于0 或者 等于2 是的话 就是欧拉通路 不是的话 就不是 这个给出的图不一定是连通的
所以首先要判断一下图的连通性 如果图不连通 那肯定不是欧拉通路
用 DFS BFS 判断都可以
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back //#define bug puts("***bug***"); #define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 2e2 + 10; const int MOD = 1e9 + 7; int du[maxn]; int visit[maxn]; int G[maxn][maxn]; int flag; int n, m; void bfs() { queue <int> q; q.push(1); visit[1] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 1; i <= n; i++) { if (visit[i] == 0 && G[u][i] == 1) { visit[i] = 1; flag++; q.push(i); } } } } int main() { int t; cin >> t; while (t--) { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) du[i] = 0, visit[i] = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) G[i][j] = G[j][i] = 0; int x, y; for (int i = 0; i < m; i++) { scanf("%d%d", &x, &y); G[x][y] = G[y][x] = 1; du[x]++, du[y]++; } int tot = 0; flag = 1; bfs(); for (int i = 1; i <= n; i++) tot += (du[i] & 1); if ((tot == 0 || tot == 2) && flag == n) puts("Zhen"); else puts("Xun"); } }E_是是非非
思路 题目其实是Nim博弈的变形
我们知道 Nim 博弈的 判断方法 是将每堆石子的数量异或起来 如果最后异或值为0 那么先手的人就没有必胜策略 反之则有
这题中的意思是 每次更改其中一堆 然后再判断 如果每次更改一堆后 再重新异或判断 会T 那么怎么办呢 其实异或是有消去律的
也就是说 异或自己两次 就 相当于没有异或
所以 我们可以再输入过程中 先把所有的值都异或一遍 这样 我们就可以 在每次更改的基础上 先异或没有更改的那个值 来消去 再去更改那个值 再去异或 更改后的值 那么就是我们要的最终的异或值了
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int MOD = 1e9 + 7; int arr[maxn]; int main() { int n, q; scanf("%d%d", &n, &q); int ans = 0; for (int i = 1; i <= n; i++) { scanf("%d", &arr[i]); ans ^= arr[i]; } int x, y; while (q--) { scanf("%d%d", &x, &y); ans ^= arr[x]; arr[x] = y; ans ^= arr[x]; puts(ans ? "Kan" : "Li"); } }F_黑黑白白
思路
对于这个问题，我们可以一层一层的看
比如题目给出的样例当中
除了根节点
显然 偶数层 就是先手的人的选择 那么 奇数层 便是后手的人的选择
从奇数层下来 会有两条路 这时候 是先手的人选择 如果这个时候 有一条路是叶子节点了 那么先手的人就是可以胜利的 这个时候 就返回答案就可以了 不用再往下搜了
那么什么时候 是后手的人可以获胜的情况呢
就是 偶数层下来 两个方向 后手的人在其中一个方向可以获得胜利，那么先手的人是没有必胜策略的
比如下面这种情况
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e4 + 10; const int MOD = 1e9 + 7; vector <int> edge[maxn]; int n, r; bool dfs(int root, int pre) { int len = edge[root].size(); if (len == 0) return false; for (int i = 0; i < len; i++) { int v = edge[root][i]; if (v == pre) continue; if (dfs(v, root) == false) return true; } return false; } void clear() { for (int i = 1; i <= n; i++) edge[i].clear(); } int main() { int t; cin >> t; while (t--) { clear(); scanf("%d%d", &n, &r); int len = n - 1; int x, y; for (int i = 0; i < len; i++) { scanf("%d%d", &x, &y); edge[x].pb(y); edge[y].pb(x); } puts(dfs(r, -1) ? "Gen" : "Dui"); } }G_文
思路 这个保存一下正确答案 然后将选手的答案 一个一个去比对就可以了
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 20 + 10; const int MOD = 1e9 + 7; int main() { int n, m; scanf("%d%d", &n, &m); string sta; cin >> sta; string ans = "zzzzzzzzzzzzzzzzz", tmp, tmm; int Max = -INF; for (int i = 0; i < m; i++) { int tot = 0; cin >> tmp >> tmm; for (int j = 0; j < n; j++) if (tmm[j] == sta[j]) tot++; if (tot > Max || (tot == Max && tmp < ans)) { Max = tot; ans = tmp; } } cout << ans << endl; printf("%.2lf\n", Max * 1.0 / n * 100.0); }H_武
思路
跑一下 Djikstra 然后 将dist 排序 输出第K个就可以了
但是要注意 因为N比较大 所以要存边 然后用优先队列优化 就能过
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int MOD = 1e9 + 7; struct node { int v, c; node(int _v = 0, int _c = 0) : v(_v), c(_c) {} bool operator < (const node &r) const { return c > r.c; } }; struct Edge { int v, cost; Edge(int _v = 0, int _cost = 0) : v(_v), cost(_cost){} }; vector <Edge> E[maxn]; bool vis[maxn]; int dist[maxn]; void dijkstra(int n, int start) { CLR(vis, false); for (int i = 1; i <= n; i++) dist[i] = INF; priority_queue <node> que; while (!que.empty()) que.pop(); dist[start] = 0; que.push(node(start, 0)); node tmp; while (!que.empty()) { tmp = que.top(); que.pop(); int u = tmp.v; if (vis[u]) continue; vis[u] = true; int len = E[u].size(); for (int i = 0; i < len; i++) { int v = E[tmp.v][i].v; int cost = E[u][i].cost; if (!vis[v] && dist[v] > dist[u] + cost) { dist[v] = dist[u] + cost; que.push(node(v, dist[v])); } } } } void addedge(int u, int v, int w) { E[u].pb(Edge(v, w)); } int main() { int n, p, k; scanf("%d%d%d", &n, &p, &k); int len = n - 1; int u, v, w; while (len--) { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, w); } dijkstra(n, p); sort(dist + 1, dist + 1 + n); printf("%d\n", dist[k + 1]); }I_艺
思路 这个只需要判断一下 每分钟哪个节目的愉悦度高 就看哪个就好了 For 几遍 复杂度O(n) 但是要注意 如果两个愉悦度都是负的 那么可以选择这时刻不看 也就是 愉悦度为0
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int MOD = 1e9 + 7; struct node { int s, e, v; node() {} node(int _s, int _e, int _v) : s(_s), e(_e), v(_v) {} bool operator < (const node& r) const { return s < r.s; } void read() { scanf("%d%d", &s, &v); } }a[maxn], b[maxn]; int main() { int n, m, t; scanf("%d%d%d", &n, &m, &t); for (int i = 0; i < n; i++) a[i].read(); for (int i = 0; i < m; i++) b[i].read(); sort(a, a + n); sort(b, b + m); a[n].s = b[m].s = t; for (int i = 0; i < n; i++) a[i].e = a[i + 1].s; for (int i = 0; i < m; i++) b[i].e = b[i + 1].s; ll ans = 0; for (int i = 1, j = 0, k = 0; i <= t; i++) { if (a[j].e < i) j++; if (b[k].e < i) k++; ans += max(a[j].v, max(b[k].v, 0)); } cout << ans << endl; }J_美
思路
这个就是尽量让相邻的两个人帅气值尽量差距大就可以了 那么显然 先排序
先放一个最小的 再放一个最大的 这样放下去。。
比如 样例中 5 7 3 15 12 8
排序后就是
3 8 7 12 15
按照那种排放方式 排放下来就是
3 15 7 12 8
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back //#define bug puts("***bug***"); #define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int MOD = 1e9 + 7; int a[maxn], b[maxn]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); for (int i = 0, j = n - 1, pos = 0; pos < n; i++, j--) { b[pos++] = a[i]; if (pos < n) b[pos++] = a[j]; } ll ans = 0; for (int i = 1; i < n; i++) ans += abs(b[i] - b[i - 1]); ans += b[n - 1] - b[0]; printf("%lld\n", ans); }转载于:https://www.cnblogs.com/Dup4/p/9433087.html
相关资源：JAVA上百实例源码以及开源项目