本文主要是介绍Summer training，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
补题内容:
1,当时没做出来的，必补
2，当时做出来但是感觉写的很挫，或者觉得出的很好的题
题意都不说，这篇博客的意义是让我踏实把这些题都弄透
Day1:
不容易系列之(4)——考新郎
这个另外一个博客中已经写了https://blog.csdn.net/swunHJ/article/details/81123246
记住并理解错排递推式f[n] = (n - 1) * (f[n-1] + f[n-2]);
Day2:
dfs, 没啥觉得很好的题
Day3:
bfs,A计划，这个还挺有意思的，补过，为了锻炼码力，再敲一遍试试。
解题思路：很明显的bfs，难点在于如何在两层之间变换，解决方案是开一个三维数组来保存这两层，然后注意一下层之间的切换和check的内容即可，噢，难点还在于不好写。
写代码的思路：还是按部就班地bfs，遇到了传送门就处理一下，再加上特判。
考虑如何处理传送：三维数组嘛，我们用0和1来表示两层，bfs的时候就分情况，是‘#’就采取floor = 1 - floor，就转换到处理另一层
考虑需要check的内容：
1，传送是否会撞墙,是否会死循环（两层的对应位置都是传送门）
2，基本的是否越界、是否可走、是否访问过
AC Code：
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define pb push_back
#define lowbit(x) x&(-x)
#define PII pair<int, int>
#define FAST ios::sync_with_stdio(false)
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = (int)1e9 + 7;
const int maxn = (int)2e5 + 5;
using namespace std;struct Point{int x, y, f, step;Point(int tx = 0, int ty = 0, int tf = 0, int tstep = 0){x = tx, y = ty, f = tf, step = tstep;}
};char G[2][15][15];
bool vis[2][15][15];
int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
int n, m, max_t;
queue<Point> q;
bool flag;bool check(Point P){if(P.x < 0 || P.x >= n || P.y < 0 || P.y >= m) return false;if(vis[P.f][P.x][P.y] || G[P.f][P.x][P.y] == '*') return false;return true;
}int bfs(){Point start;start.f = 0, start.x = 0, start.y = 0, start.step = 0;q.push(start);vis[0][0][0] = 1;while(!q.empty()){Point now = q.front(); q.pop();if(G[now.f][now.x][now.y] == 'P'){flag = true;if(now.step <= max_t) return 0 * puts("YES");else return 0 * puts("NO");}Point next;if(G[now.f][now.x][now.y] == '#'){next.f = 1 - now.f, next.x = now.x, next.y = now.y;if(check(next) && G[next.f][next.x][next.y] != '#'){next.step = now.step;q.push(next);vis[next.f][next.x][next.y] = 1;}}else {for(int i = 0; i < 4; i++){next.f = now.f, next.x = now.x + dir[i][0], next.y = now.y + dir[i][1];if(check(next)){next.step = now.step + 1;q.push(next);vis[next.f][next.x][next.y] = 1;}}}}
}int main()
{int t; scanf("%d", &t);while(t--){while(!q.empty()) q.pop();memset(vis, false, sizeof(vis));scanf("%d %d %d", &n, &m, &max_t);for(int i = 0; i < 2; i++){for(int j = 0; j < n; j++){scanf(" %s", G[i][j]);}}flag = false;bfs();if(!flag) puts("NO");}return 0;
}哈密顿绕行世界问题
一个体现dfs序的优越性的题目，控制优先级：编号从小到大，进行dfs即可
需要注意的就是输入的时候要排个序，不过这题数据很友好，排好了
考虑一下dfs思路：走完了一圈就输出
没走完继续找，注意标记，回溯完了得重新vis标为0，基本操作了，不多讲
AC Code：
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define pb push_back
#define lowbit(x) x&(-x)
#define PII pair<int, int>
#define FAST ios::sync_with_stdio(false)
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = (int)1e9 + 7;
const int maxn = (int)2e5 + 5;
using namespace std;int a[25][5], step[25];
bool vis[25];
int m, cnt;void dfs(int cur, int len){if(cur == m && len == 21){printf("%d: ", cnt);cnt++;for(int i = 1; i <= 21; i++){printf(" %d", step[i]);}puts("");return ;}for(int i = 1; i <= 3; i++){int t = a[cur][i];if(!vis[t]){vis[t] = 1;step[len+1] = t;dfs(t, len + 1);vis[t] = 0;}}
}int main()
{for(int i = 1; i <= 20; i++){for(int j = 1; j <= 3; j++){scanf("%d", &a[i][j]);}}while(~scanf("%d", &m) && m){cnt = 1;memset(vis, false, sizeof(vis));step[1] = m;dfs(m, 1);}return 0;
}
Day4:二分，快速幂，gcd一些杂东西
C. Success Rate
你现在提交了y份答案，x份是对的，你想把正确率变成p/q，问最少还要提交多少题
如下考虑：又提交了dy份，其中dx份是对的，那么(x + dx) / (y + dy) == p / q
考虑一个倍数k，那么x + dx = k * p, y + dy = k * q
这时候我们只需要二分枚举倍数k，即可获得正确答案ans = dy = k * q - y
再考虑二分的细节。首先，二分起点，题目中给的数据范围是1e9，那么init l = 0, r = 1e9
要求尽可能小的提交次数，那么k肯定越小越好，所以在右端点处更新ans
考虑check的内容，其实很简单，枚举了一个k，那么只需要满足dy >= dx >= 0即可
还有就是注意开ll，会爆int
Ac Code:
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#define pb push_back
#define lowbit(x) x&(-x)
#define PII pair<int, int>
#define FAST ios::sync_with_stdio(false)
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = (int)1e9 + 7;
const int maxn = (int)2e5 + 5;
using namespace std;ll x, y, p, q;bool check(ll k){ll dx = k * p - x, dy = k * q - y;if(dy >= dx && dx >= 0) return true;return false;
}int main()
{int t; scanf("%d", &t);while(t--){scanf("%I64d %I64d %I64d %I64d", &x, &y, &p, &q);ll ans = -1;ll l = 0, r = 1e9;while(l <= r){ll mid = (l + r) >> 1;if(check(mid)){r = mid - 1;ans = mid;}else l = mid + 1;}if(ans == -1) puts("-1");else printf("%I64d\n", ans * q - y);}return 0;
}其他没啥好说的
先到这，待我把昨天没打的cf给补了。。。
Day5:
这个G我是真的不想补。。。
这篇关于Summer training的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
![[论文解读]Genre Separation Network with Adversarial Training for Cross-genre Relation Extraction](https://i-blog.csdnimg.cn/blog_migrate/a81ef8f36f1400d5367d93036bc14ef7.png)
