ZZJC新生训练赛第八场题解
难度分类：
-
简单：A,D,F
-
普通：B,G,H
-
困难：E
-
看情况：C
A-解题思路：
根据题意可得只要当前年份减去1949。
A-代码实现：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n;
void matt(){
cin >> n;
cout << n - 1949 ;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
matt();
}
return 0;
}
D-解题思路：
根据题目，直接将前50个斐波那契数求出。
注意数据范围大小
D-代码实现：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n , a[N];
void matt(){
a[1] = a[2] = 1;
for (int i = 3; i < 51; i++)
{
a[i] = a[i - 1] + a[i - 2];
}
cin >> n;
cout << a[n];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
matt();
}
return 0;
}
F-解题思路：
根据题意直接写判断。
F-代码实现：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n , a[N];
void matt(){
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
if(x == 10) cout << "SSS\n";
else if(x >= 8) cout << "SS\n";
else if(x >= 5) cout << "S\n";
else if(x >= 1) cout << "A\n";
else cout << "B\n";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
matt();
}
return 0;
}
B-解题思路：
看到这种题目一开始想到的是递归，但是题目空间有限制，用递归写的话会错，所以得换个思路。建立一个数组a，前4位分别存{0 , 1 , 2 , 3}，后面每项a[i]填a[i – 1] + a[i – 3]的值。
B-代码实现：
#include<bits/stdc++.h>
#define int long long
#define PII pair<int , int>
using namespace std;
const int N = 1e7 + 10;
int mid = 1e9 + 7;
int n , m , a[N];
void matt(){
cin >> n;
for (int i = 0; i < N; i++)
{
if(i <= 3) a[i] = i;
else a[i] = (a[i - 1] + a[i - 3]) % mid;
}
cout << a[n];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
matt();
}
return 0;
}
G-解题思路：
根据题意，先通分，加减之后，分子分母除以两者最大公约数，得出最简分数。
G-代码实现：
#include<bits/stdc++.h>
#define int long long
#define PII pair<int , int>
using namespace std;
const int N = 1e6 + 10;
int n , m , a[N];
int mid = 1e9 + 7;
void matt(){
int op , a , b , c , d;
cin >> op >> a >> b >> c >> d;
a *= d , c *= b;
int y = b * d , x;
if(op == 1) x = a + c;
else x = a - c;
if(x < 0) cout << '-' , x = -x;
int z = __gcd(x , y);
cout << x / z << '/' << y / z << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T--)
{
matt();
}
return 0;
}
H-解题思路：
因为ai = gcd(p1 , p2 , p3 , …… ,pi)，所以ai <= a[i – 1]。并且a[i – 1] 一定是ai的倍数，且p1 = a1。所以不符合以上两点的数组a一定是无解的，例如a = {4 , 3}。
我们用数组b存放我们要输出的数字顺序。
因为是排列P（每个数字只能出现一次），所以用数组t开判断该数是否出现过（出现过为1，否则为0）。
用数组c来存放我下次再遇到a[i]时该填入的数字。设上次遇到a[i]时填入的数字为x(x为a[i]的倍数),那么下次遇到a[i]时填入的数字就是x+a[i],只有这样gcd(x , a[i] + x) = a[i]。
但是我们下次遇到a[i]时应该填入的数字可能之前已经填过了，所以要while循环一下。
H-代码实现：
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<int>a(n + 1) , b(n + 1) , t(n + 1) , c(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
c[i] = i;
}
b[1] = c[a[1]];
c[a[1]] += a[1];
t[b[1]] = 1;
for (int i = 2; i <= n; i++)
{
if(a[i] > a[i - 1] || a[i] < a[i - 1] && a[i - 1] % a[i] != 0){
cout << -1;
return 0;
}//判断数组a是否符合以上两点
else if(a[i] < a[i - 1]){
b[i] = c[a[i]];
c[a[i]] += a[i];
t[b[i]] = 1;
}//如果符合将数字填入数组b
else{
int s = 0;
while(t[c[a[i]]] == 1){
c[a[i]] += a[i];
if(c[a[i]] > n){
s = 1;
break;
}
}
if(s) {
cout << -1;
return 0;
}//如果填入的数字大于n,那么数组a不符合条件输出-1
b[i] = c[a[i]];
t[b[i]] = 1;//如果符合，将数字填入数组b
}
}
for (int i = 1; i <= n; i++)
{
cout << b[i] << ' ';
}//输出
return 0;
}
C-解题思路
这是一道博弈题，只要找规律就行，枚举前30个发现，只有n是3的倍数的时候Frame获胜，否则Alan获胜。
C-代码实现
#include<bits/stdc++.h>
#define int long long
#define PII pair<int , int>
using namespace std;
const int N = 1e6 + 10;
int n , m , a[N];
int mid = 1e9 + 7;
void matt(){
cin >> n;
if(n % 3 == 0) cout << "Frame\n";
else cout << "Alan\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while (T--)
{
matt();
}
return 0;
}
E-解题思路：
这是一道防AK题，反正难写就完了。如果你做出来了恭喜你出师了。如果你想学的话就去看看求最短路径的算法题
E-代码实现：
#include<bits/stdc++.h>
#define int long long
#define PII pair<int , int>
using namespace std;
const int N = 2e5 + 10;
int n , m , idx , inf = 4e18;
int mid = 1e9 + 7;
int dist[N];
bool st[N];
struct E
{
int x , w;
};
vector<E>a[N];
int dijkstra(){
fill(dist, dist + N, inf);
dist[1] = 0;
priority_queue<PII , vector<PII> , greater<PII>>heap;
heap.push({0 , 1});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second , distance = t.first;
if(st[ver]) continue;
st[ver] = true;
for (auto [x , w] : a[ver])
{
if(!st[x] && dist[x] > dist [ver] + w){
dist[x] = dist [ver] + w;
heap.push({dist[x] , x});
}
}
}
if(dist[n] < inf) return dist[n];
else return -1;
}
void matt(){
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u , v , w;
cin >> u >> v >> w;
if (u != v) {
a[u].push_back({v , w});
a[v].push_back({u , w});
}
}
int x = dijkstra();
if(x == -1) cout << "qwb baka";
else cout << x;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
matt();
}
return 0;
}