A.字符串拼接
直接拼接两个字符串即可,注意的是字符串可能包含空格,因此需要使用getline
函数进行输入。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, s2;
getline(cin, s1);
getline(cin, s2);
cout << s1 + s2 << endl;
return 0;
}
B.差值
注意到,题目需要求出任意两个数的差值的最小值,我们知道,差值最小的情况就是两个数越接近越好,因此我们可以将数组排序,然后求相邻两个数的差值的最小值即可。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
int ans = INT_MAX;
for (int i = 1; i < n; i++) {
ans = min(ans, a[i] - a[i - 1]);
}
cout << ans << endl;
}
C.红色和紫色
可以证明:当且仅当 \(n,m\) 都是奇数时,小红可以获胜。否则一定是紫获胜。
证明如下:
如果 \(n\) 和 \(m\) 都是奇数,那么 \(n*m\) 是奇数,存在一个中心的方格。小红只需要第一步给中间染色,之后紫在任意地方染色,小红只需要在紫染色的方格中心对称的位置染上和紫上次操作相同的颜色即可。这样一定是紫最先无法行动。
如果 \(n\) 和 \(m\) 不全是奇数,说明不存在中心的方格。紫只需要在每次小红染色后,在中心对称的位置上染上和小红上次操作不同的颜色(显然,这样一定是合法的)。如此最后不能操作的一定是小红。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
if (n % 2 == 1 && m % 2 == 1) {
cout << "akai" << endl;
} else {
cout << "yukari" << endl;
}
return 0;
}
D.abb
对于每个字符 \(c\),可以先利用后缀和统计出在该字符后有多少个与 \(c\) 不同的字符,那么对于每种不同的字符,\(c\) 能够就从他们中任意选取2个构成一个合法的abb串
,那么答案就是 \(C_n^2\),其中 \(n\) 表示该种字符在 \(c\) 后出现的个数,因此当前位置能够构成的答案数量就是 \(\sum C_{n_i}^2\),也就是不同于 \(c\) 的所有字符可以提供的贡献之和。最后枚举每个位置即可得到答案。
#include<bits/stdc++.h>
using namespace std;
// sum(i,j)表示在i位置后j字符的个数
long long sum[101010][26];
int main(){
int n,i,j;
string s;
cin>>n>>s;
for(i=n-1;i>=0;i--){
for(j=0;j<26;j++)sum[i][j]=sum[i+1][j];
sum[i][s[i]-'a']++;
}
long long res=0;
for(i=0;i<n;i++){
for(j=0;j<26;j++){
// 对于当前位置,枚举每个不等于当前位置的字符,计算能够构成的abb串数量
if(j!=s[i]-'a'){
// C_n^2 = n*(n-1)/2
res+=sum[i+1][j]*(sum[i+1][j]-1)/2;
}
}
}
cout<<res;
}
E.kotori和素因子
观察到数据范围很小,因此暴力枚举所有方案即可。
#include<stdio.h>
#define N 1010
int prime[168] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
bool st[168]; //第几个素数被用过了
int f[10][100]; //第i个数的质因子有第几个素数
int n,cnt[10]; //第i个数有几个质因子
int ans = 0x3f3f3f3f;
void dfs(int num, int sum)
{
if(num == n){
if(sum < ans) ans = sum;
return;
}else{
for(int i = 0; i < cnt[num]; i ++)
{
if(!st[f[num][i]]){
st[f[num][i]] = true;
dfs(num + 1, sum + prime[f[num][i]]);
st[f[num][i]] = false;
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i = 0; i < n; i ++)
{
int a;
scanf("%d",&a);
for(int j = 0; a != 1; j ++)
{
if(a % prime[j] == 0)
{
f[i][cnt[i]++] = j; //质因子有第几个素数
while(a % prime[j] == 0)
a /= prime[j];
}
}
}
dfs(0,0);
if(ans == 0x3f3f3f3f) ans = -1;
printf("%d",ans);
return 0;
}
F. 红和蓝
对于叶子节点来说,他的周围只有一个点,即为他的父节点,因此为了满足条件,他必须要和父亲节点同色,此时,我们将他和他的父亲染上相同的颜色。染色后,我们可以看成被染色的点已经从树上去掉,因此此时会出现新的"叶子节点",重复上述过程,直到所有点都被染色即可,同时,如果染色中间出现了冲突(即一个节点同时被染上两种颜色),则说明无解,同时,如果最后没有点能帮助根节点染色,也无解。最后根据染色情况,计算答案即可。
#include <bits/stdc++.h>
using namespace std;
int n, tot = 0;
int head[100010];
struct ty
{
int t, next;
}edge[200010];
int f[100010];
int col[100010];
int cnt = 0;
bool boo = 1;
void addedge(int x, int y)
{
edge[++tot].t = y;
edge[tot].next = head[x];
head[x] = tot;
}
void dfs1(int x, int fa)
{
int son = 0;
for (int i = head[x]; i != -1; i= edge[i].next)
{
if (edge[i].t == fa) continue;
son++;
dfs1(edge[i].t, x);
}
// 如果是叶子节点
if (son == 0 || f[x] == 0)
{
// 如果他的父亲已经被染上颜色,而此时当前节点又要给父亲节点染色,说明发生冲突,无解
if (f[fa] != 0) {boo = 0; return ;}
// 将他和他的父亲染上相同颜色
f[x] = f[fa] = ++cnt;
}
}
void dfs2(int x, int fa) //计算答案
{
for (int i = head[x]; i != -1; i= edge[i].next)
{
if (edge[i].t == fa) continue;
if (f[edge[i].t] == f[x]) col[edge[i].t] = col[x];
else col[edge[i].t] = col[x] ^ 1;
dfs2(edge[i].t, x);
}
}
int main()
{
memset(head, -1, sizeof(head));
memset(edge, -1, sizeof(edge));
scanf("%d", &n);
for (int i =1; i < n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
addedge(x, y);
addedge(y, x);
}
dfs1(1, 0);
// 如果之前染色发生冲突或者根节点没有被染色,无解
if (f[0] != 0 || boo == 0)
{
printf("-1\n"); return 0;
}
col[1] = 1;
dfs2(1, 0);
for (int i = 1; i <= n;i++)
{
if (col[i] == 1) printf("R");
else printf("B");
}
return 0;
}
标签:传智杯,num,int,题解,ans,初赛,++,edge,染色
From: https://www.cnblogs.com/orangecodelog/p/18456203