题解报告（CDUT暑期集训——第四场）

谁践踏了优雅 2023-08-17 16:23 76阅读 0赞

# **题解报告（CDUT暑期集训——第四场）** #

--------------------

## **Problem D. Nothing is Impossible** ##

### [HDU - 6335][] ###

*  **思路：水题 排个序循环判断就出来了**
 *  AC代码

--------------------

## **Problem E. Matrix from Arrays** ##

### [HDU - 6336][] ###

*  **思路：照着题目中给出的代码 打出2L \* 2L的表 发现2L \* 2L的矩阵被分成了四个L \* L的完全相同的矩阵（由于输入的二维坐标数据较大 需要预处理左上角2L \* 2L的矩阵 然后计算就是了**
 *  AC代码

--------------------

#include<stdio.h> #include<iostream> #include<math.h> #include<algorithm> #include<string.h> #include<queue> #include<set> #include<string> #include<sstream> typedef long long ll; typedef unsigned long long ull; using namespace std; ll Pow_mod(ll a, ll b, ll c){ ll ans = 1; a %= c; while (b){ if (b & 1) ans = (ans * a) % c; a = (a * a) % c; b >>= 1; } return (ans % c); } int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); } const int N = 50; int t, l, q; int a[N]; ll M[N][N]; ll calc(int x, int y){ if (x < 0 || y < 0) return 0; return M[2 * l - 1][2 * l - 1] * (x / (2 * l)) * (y / (2 * l)) + M[2 * l - 1][y % (2 * l)] * (x / (2 * l)) + M[x % (2 * l)][2 * l - 1] * (y / (2 * l)) + M[x % (2 * l)][y % (2 * l)]; } void init(){ int cursor = 0; for (int i = 0; i < (l << 2); i ++ ){ for (int j = 0; j <= i; j ++ ){ M[j][i - j] = a[cursor]; cursor = (cursor + 1) % l; } } for (int i = 0; i < (l << 1); i ++ ){ for (int j = 0; j < (l << 1); j ++ ){ if (i) M[i][j] += M[i - 1][j]; if (j) M[i][j] += M[i][j - 1]; if (i && j) M[i][j] -= M[i - 1][j - 1]; } } } int main(){ scanf("%d", &t); while (t -- ){ scanf("%d", &l); for (int i = 0; i < l; i ++ ) scanf("%d", &a[i]); init(); scanf("%d", &q); while (q -- ){ int x0, y0, x1, y1; scanf("%d%d%d%d", &x0, &y0, &x1, &y1); printf("%lld\n", calc(x1, y1) - calc(x1, y0 - 1) - calc(x0 - 1, y1) + calc(x0 - 1, y0 - 1)); } } return 0; }

## **Problem J. Let Sudoku Rotate** ##

### [HDU - 6341][] ###

*  **思路：dfs 枚举每个4 \* 4 sudoku（老郭（不 矩阵旋转次数** 
 *  AC代码

--------------------

#include<stdio.h> #include<iostream> #include<math.h> #include<algorithm> #include<string.h> #include<queue> #include<set> #include<string> #include<sstream> typedef long long ll; typedef unsigned long long ull; using namespace std; ll Pow_mod(ll a, ll b, ll c){ ll ans = 1; a %= c; while (b){ if (b & 1) ans = (ans * a) % c; a = (a * a) % c; b >>= 1; } return (ans % c); } int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); } const int N = 20; const int M = 10; const int INF = 0x3f3f3f3f; int t, ans; int a[80]; char mp[N][N], tmp[M][M]; void rot(int x, int y){ for (int i = 0; i < 4; i ++ ) for (int j = 0; j < 4; j ++ ) tmp[i][j] = mp[4 * x - j - 1][4 * y + i - 4]; for (int i = 0; i < 4; i ++ ) for (int j = 0; j < 4; j ++ ) mp[4 * x + i - 4][4 * y + j - 4] = tmp[i][j]; } bool judge(int x, int y){ for (int i = 4 * x - 4; i < 4 * x; i ++ ){ memset(a, 0, sizeof(a)); for (int j = 0; j < 4 * y; j ++ ){ if (a[int(mp[i][j])] > 0) return false; a[int(mp[i][j])] ++; } } for (int i = 4 * y - 4; i < 4 * y; i ++ ){ memset(a, 0, sizeof(a)); for (int j = 0; j < 4 * x; j ++ ){ if (a[int(mp[j][i])] > 0) return false; a[int(mp[j][i])] ++; } } return true; } void dfs(int x, int y, int tot){ if (tot >= ans) return ; if (x == 5){ ans = min(ans, tot); return ; } if (y == 5){ dfs(x + 1, 1, tot); return ; } for (int i = 0; i < 4; i ++ ){ if (judge(x, y)) dfs(x, y + 1, tot + i); rot(x, y); } } int main(){ scanf("%d", &t); while (t -- ){ ans = INF; for (int i = 0; i < 16; i ++ ) scanf("%s", mp[i]); dfs(1, 1, 0); printf("%d\n", ans); } return 0; }

## **Problem K. Expression in Memories** ##

### [HDU - 6342][] ###

*  **思路：纯模拟 有一说一 模拟题脑壳痛（用递归优化了而已（然并卵**
 *  AC代码

--------------------

#include<stdio.h> #include<iostream> #include<math.h> #include<algorithm> #include<string.h> #include<queue> #include<set> #include<string> #include<sstream> typedef long long ll; typedef unsigned long long ull; using namespace std; ll Pow_mod(ll a, ll b, ll c){ ll ans = 1; a %= c; while (b){ if (b & 1) ans = (ans * a) % c; a = (a * a) % c; b >>= 1; } return (ans % c); } int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); } const int N = 510; int t; char s[N]; bool judge(char c){ if (c == '+' || c == '*') return true; return false; } bool flag(int l, int r){ if (l == r) return true; if (l > r) return false; if (s[l] != '0') return true; if (s[l + 1] != '?') return false; s[l + 1] = '+'; return flag(l + 2, r); } bool dfs(int l, int r){ if (l > r) return false; bool flag1, flag2; for (int i = l; i <= r; i ++ ){ if (judge(s[i])){ flag1 = dfs(l, i - 1); flag2 = dfs(i + 1, r); return flag1 && flag2; } } return flag(l, r); } int main(){ scanf("%d", &t); while (t -- ){ scanf("%s", s); if (dfs(0, strlen(s) - 1)){ for (int i = 0; i < strlen(s); i ++ ) if (s[i] == '?') s[i] = '1'; printf("%s\n", s); } else printf("IMPOSSIBLE\n"); } return 0; }

## **Problem L. Graph Theory Homework** ##

### [HDU - 6343][] ###

*  **思路：水题（没加abs贡献一发wa（该打**
 *  AC代码

--------------------

转载于:https://www.cnblogs.com/Misuchii/p/11276145.html

[HDU - 6335]: http://acm.hdu.edu.cn/showproblem.php?pid=6335
[HDU - 6336]: http://acm.hdu.edu.cn/showproblem.php?pid=6336
[HDU - 6341]: http://acm.hdu.edu.cn/showproblem.php?pid=6341
[HDU - 6342]: http://acm.hdu.edu.cn/showproblem.php?pid=6342
[HDU - 6343]: http://acm.hdu.edu.cn/showproblem.php?pid=6343