文章目录

• A (1). Ashy与几何(贪心+几何)
• B (2). One eye question of hengheng(前缀和)
• C Fox hate oranges(模拟)
• D KingZhang's Similar pair (思维)
• E (5). 38秒你敢交我A题？
• F (6). How many numbers are there
• G (7). Jump lattice (思维)
• H (8). CCoolGuang Conjecture(数论)
• I (9). Cutele想去打篮球(排序 ， 思维)
• J (10). The most difficult question
• K (11). 异世相遇
• L (12). 绘制图像
• M (13). UpMing的CrossFire幻境

A (1). Ashy与几何(贪心+几何)

求最小移动次数，我们的思路肯定是贪心的去移动，每次销都放在起点与终点的连线上，这样保证了要移动的距离最短，那如果起点与中点的距离不是我们移动距离的倍数，那么我们需要额外花费一次移动次数

就像这样 ， 我们要从 A - B , 但是A - B 圆心之间的距离不够 2r ， 我们借助一下C ， 先把A转移到C，在转移到B即可。

那么最后的答案就是 ceil(dis(a,b) /(2 * r))

double r , a , b , c , d;int main(){cout << fixed ;cin >> r >>  a >> b >> c >> d;double x1 = abs(a - c);double x2 = abs(b - d);double sumx = sqrt(x1 * x1 + x2 * x2);int ans = ceil(sumx / (2 * r));cout << ans;return 0;
}

B (2). One eye question of hengheng(前缀和)

可以暴力做 ， 但是这是个前缀和算法的裸题，在这里给出前缀和算法，前缀和算法可以把时间复杂度优化到O(n)

int n , q , a[N] , sum[N];int main(){cin >> n;for(int i=1;i<=n;i++){cin >> a[i];sum[i] = sum[i-1] + a[i];} int l , r;cin >> q;while(q--){cin >> l >> r;cout << sum[r] - sum[l-1] << "\n" ;}return 0;
}

C Fox hate oranges(模拟)

这个题出的很怪，怪就怪在讨厌句子的人手里会有橘子，但是这不妨碍我们做题
模拟一下即可，要注意的就是当我手里没有橘子的时候，我去讨厌橘子的人哪里是不会战斗的，这是个大坑点

int n , m , k;
int a[101];
bool vis[101];int main(){cin >> n >> m >> k;for(int i=1;i<=m;i++) cin >> a[i];for(int i=1;i<=k;i++){int id;cin >> id;vis[id] = 1;//标记讨厌橘子的人}for(int i=1;i<=m;i++){if(!vis[i]){//这个人喜欢橘子if(n > a[i]) n -= a[i]; //橘子够 ， 给他橘子else{a[i] = n;n = 0;//橘子不够 ， 全给他}}else{//讨厌橘子if(n == 0) continue; //我没有橘子，不战斗else if(n >= a[i]){//我有橘子，战斗我赢a[i] += n / 2;n -= n / 2;}else{//我有橘子，战斗我输n += a[i] / 2;a[i] -= a[i] / 2;}}}cout << n << "\n" ;for(int i=1;i<=m;i++) cout << a[i] << " " ;return 0;
}

D KingZhang’s Similar pair (思维)

要满足条件首先数字的个数一定要是偶数个，这是毋庸置疑的，这样的话，情况就很好讨论了

1. 奇数和偶数都是偶数个

这样必然能分组成功

2. 奇数和偶数都是奇数个

这样的话，找一个奇数和一个偶数满足差为 1即可
我的查找方法是先排序找相邻数的差，怎么找都行

int n , k;
int a[N] , cnt1 , cnt2;int main(){cin >> n;if(n % 2 != 0){cout << "NO\n";return 0;}for(int i=1;i<=n;i++){cin >> a[i];if(a[i] % 2) cnt1++;else cnt2++;}sort(a+1,a+1+n);if(cnt1 % 2 == 0){//都是偶数个cout << "YES" ;}else{//否则找有没有差是1的bool f= 0;for(int i=1;iif(a[i+1] - a[i] == 1){f = 1;break;}}if(f){cout << "YES";}else{cout << "NO";}	}return 0;
}

E (5). 38秒你敢交我A题？

水题 ， 记下数就行

int n , t , a[N];int main(){cin >> n;for(int i=1;i<=n;i++) cin >> a[i];sort(a+1,a+1+n);int k = a[n/2+1];int cnt = 0;for(int i=1;i<=n;i++){if(a[i] == k) cnt++;}if(cnt == 1){cout << "Fox%xoF " << k;}else{cout << "Bad%daB" ;}return 0;
}

F (6). How many numbers are there

水题 ， 搞一个桶，存进去遍历一下就可

int n , t , a[N] , id;int main(){cin >> n;for(int i=1;i<=n;i++){cin >> id;a[id] = 1;}int cnt = 0;for(int i=1;i<=100000;i++){if(a[i] == 1) cnt++;}cout << cnt;return 0;
}

G (7). Jump lattice (思维)

要找最小的D，只要每次跳都是在 1 的左边一个 2的位置跳，那么答案就是最长的连续 1 的个数 + 1

int n , k;
int a[N],cnt = 1 , max1 = -inf;int main(){cin >> n;for(int i=1;i<=n;i++){cin >> k;if(k == 2){max1 = max(cnt , max1);cnt = 1;}else{cnt++;}}max1 = max(cnt  , max1);cout << max1 ;return 0;
}

H (8). CCoolGuang Conjecture(数论)

这是2020CCPC威海站D题数据弱化版，防AK的，有够难，难为验题的我了

首先看 rad 的定义 ， rad( c ) 是 c的质因子乘积
首先我们可以发现性质1

1. 根据唯一分解定理，每一个数都可以分解为质因子的乘积
   如果一个数的质因子分解后幂次都是 1 ， 那么满足 rad( c ) == c
   但是如果分解后出现幂次大于 1 的数，那肯定满足 rad( c ) < c
   所以我们把 c 质因子分解后 ， 如果幂次都是 1,那么rad( abc ) >= c , 不可能出现 rad( abc ) < c

然后就是一个数质因子分解后如果有一个质因子幂次大于 1 ， 这样必然存在 a , b 满足rad( abc ) >= c且 a + b == c , 为什么呢 ， 我们来证明一下

假如 c == 75 ， 分解后就是 5 * 5 * 7
我们必然能拆掉那个出现多次的质数 5 * 5 * 7 -> (1 + 4) * 5 * 7
a = 1 * 5 * 7
b = 4 * 5 * 7
那么 a * b * c 的质因数就是 2 5 7 必然小于 5 * 5 * 7

我举这个例子的意思就是 ， 一个重复的质因子拆分相乘后，生成的新的质因子一定小于拆分的质因子，因此得证。

对所给数质因子分解 ， 分解后幂次都是 1 的数满足条件

int p[N] , cnt , t , n;bool isp(int n){if(n < 2) return 0;for(int i=2;i*i<=n;i++)if(n % i == 0) return 0;return 1;
}int main(){for(int i=1;i<=100;i++) if(isp(i)) p[++cnt] = i;cin >> t;while(t--){cin >> n;bool f = 0;for(int i=1;i<=cnt;i++){int cnt = 0;while(n % p[i] == 0){cnt++;n /= p[i];}if(cnt > 1){f = 1;break;}}if(f) cout << "yes\n";else cout << "no\n";}return 0;
}

I (9). Cutele想去打篮球(排序 ， 思维)

我们给所有的数排个序 ， 可以发现我么要找的这两个数一定是相邻的数，非相邻的数间距一定会大于相邻的数，而且相邻的数恰好可以满足题目中的条件，所以题目就变成了找相邻数的最小值问题

int n , t , a[N] , id;int min1 = inf;int main(){cin >> n;for(int i=1;i<=n;i++) cin >> a[i];sort(a+1,a+1+n);for(int i=1;imin1 = min(min1 , abs(a[i] - a[i+1]));}cout << min1 ;return 0;
}

J (10). The most difficult question

const int inf = 1e9 + 10;
int n , t , a[N] , id;ll ans = 1;int main(){cin >> n;for(int i=1;i<=n;i++) ans = ans * i % p;cout << ans; return 0;
}

K (11). 异世相遇

注意用星尘抽卡后还会获得星辰

int n , t , a[N] , m;
int ans = 0;
int main(){cin >> n >> m;while(n >= 160 || m >= 75){int k1 = n / 160; //原石抽卡次数ans += k1;n -= k1 * 160; //剩余原石数量m += k1 * 15;//星辰数量int k2 = m / 75; //星辰抽卡次数ans += k2;m -= k2 * 75;m += k2 * 15;//剩余星辰数量}cout << ans;return 0;
}

L (12). 绘制图像

主对角线是 i == j . 副对角线是 i+j==n+1i+ j == n + 1i+j==n+1

int n;
char c[100][100];
char a , b , s;int main(){cin >> n >> a >> b >> s;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i == 1 || i == n) c[i][j] = a;else if(j == 1 || j == n) c[i][j] = b;else if(i == j || i + j == n + 1) c[i][j] = s;else c[i][j] = ' ';cout << c[i][j];}cout << "\n" ;}return 0;
}

M (13). UpMing的CrossFire幻境

先全换成小写 ， 然后搜索一下就行

int n;
string s;
int a[N],cnt;int main(){cin >> n >> s;int len = s.size();for(int i=0;iif(s[i] == 'a' && s[i+1] == 'c' && s[i+2] == 'm'){a[++cnt] = i;}}cout << cnt << "\n" ;for(int i=cnt;i>=1;i--) cout << a[i] << "  "[i != 1];return 0;
}