练习地址
点此前往练习
修改大小写
在小美的国家，任何一篇由英文字母组成的文章中，如果大小写字母的数量不相同会被认为文章不优雅。
现在，小美写了一篇文章，并且交给小团来修改。小美希望文章中的大小写字母数量相同，所以她想让小团帮她把某些小写字母改成对应的大写字母，或者把某些大写字母改成对应的小写字母，使得文章变得优雅。
小美给出的文章一定是由偶数长度组成的，她想知道最少修改多少个字母，才能让文章优雅。
输入描述:
输入包含一个字符串S，仅包含大写字母和小写字母
输出描述:
输出包含一个整数，即最少需要修改的字符数。
输入例子1:
AAAb
输出例子1:
1
例子说明1:
修改为AaAb即可，也有其他两种修改方法：aAAb，AAab
思路：
写一个判断函数，对输入的字符串中的大写和小写字母分别计数。当二者不相等时，如果是大写字母数量多，对其做减法，对小写字母做加法，每计算一次计数+1；反之类似。直到二者相等，跳出循环。
代码：
#include<bits/stdc++.h>
using namespace std;
int Judge(string s)
{
int up=0,down=0,count=0;
for(int i=0;i<s.size();i++)
{
if('A'<=s[i]&&s[i]<='Z')
up++;
if('a'<=s[i]&&s[i]<='z')
down++;
}
while(up!=down)
{
if(up>down)
{
up--;
down++;
count++;
}
else
{
up++;
down--;
count++;
}
if(up==down)
break;
}
return count;
}
int main()
{
string s;
cin>>s;
int out=Judge(s);
cout<<out;
return 0;
}
式子求值
小团有一个序列a ，下标从1 开始直到n ，分别为 a1,a2,…,an。现在，小团定义了以下式子：
b
i
=
a
i
⊕
⊕
j
=
1
n
(
i
%
j
)
b_i=a_i⊕⊕_{j=1}^n(i\%j)
bi=ai⊕⊕j=1n(i%j)
现在小团想让小美回答
⊕
i
=
1
n
(
b
i
)
⊕_{i=1}^n(b_i)
⊕i=1n(bi)的值。
其中， ⊕代表异或运算，%代表求余运算。
请你帮助小美。
小提示：
b
i
=
a
i
⊕
⊕
j
=
1
n
(
i
%
j
)
=
a
i
⊕
(
i
%
1
)
⊕
(
i
%
2
)
⊕
(
i
%
3
)
…
⊕
(
i
%
n
)
b_i=a_i⊕⊕_{j=1}^n(i\%j)=a_i⊕(i\%1)⊕(i\%2)⊕(i\%3)…⊕(i\%n)
bi=ai⊕⊕j=1n(i%j)=ai⊕(i%1)⊕(i%2)⊕(i%3)…⊕(i%n)
输入描述:
输入第一行包含一个整数n，表示序列a的长度。
接下来一行n个数，空格隔开，第i个数表示ai。
输出描述:
输出包含一个数，即
⊕
i
=
1
n
(
b
i
)
⊕_{i=1}^n(b_i)
⊕i=1n(bi)的值。
输入例子1:
2
3 2
输出例子1:
0
例子说明1:
b
1
=
a
1
⊕
(
1
%
1
)
⊕
(
1
%
2
)
=
2
b
2
=
a
2
⊕
(
2
%
1
)
⊕
(
2
%
2
)
=
2
⊕
i
=
1
n
(
b
i
)
=
b
1
⊕
b
2
=
0
\begin{array}{ll}&b_1=a_1⊕(1\%1)⊕(1\%2)=2\\ &b_2=a_2⊕(2\%1)⊕(2\%2)=2\\ &⊕_{i=1}^n(b_i)=b_1⊕b_2=0\end{array}
b1=a1⊕(1%1)⊕(1%2)=2b2=a2⊕(2%1)⊕(2%2)=2⊕i=1n(bi)=b1⊕b2=0
思路：
根据题设公式两重循环会超时。
采用评论区中零葬的思路：
一个数和0异或的结果还是这个数，且异或满足交换律。因此先在ai输入时，将该值记录在输出结果中；接着只需要对剩下的余数进行异或即可。
对于这些余数i%j有如下的规律：
(1) 如果 n / i 为偶数，异或结果为1^ 2 ^ … ^(n%i)。
(2) 如果 n / i 为奇数，异或结果为1 ^ 2 ^ … ^ (n%i) ^ 0 ^ 1 ^ 2 ^ … ^ (i-1)。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int> a(n+1,0);
vector<int> b(n+1,0);
int out=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
out^=a[i];
b[i]=b[i-1]^i;
}
for(int i=1;i<=n;i++)
{
if((n/i)%2==0)
out^=b[n%i];
else
out^=b[n%i]^b[i-1];
}
cout<<out;
return 0;
}
争夺地盘
A国和B国正在打仗，他们的目的是n块土地。现在，A国和B国暂时休战，为了能合理分配这一些土地，AB国开始协商。
A国希望得到这n块土地中的p块土地，B国希望得到这n块土地中的q块土地。每个国家都将自己希望得到的土地编号告诉了小团和小美——两位战争调和人。
你需要帮小团和小美计算，有多少块土地是只有A国想要的，有多少块土地是只有B国想要的，有多少块土地是两个国家都想要的。
输入描述:
输入第一行包含三个整数n,p,q，含义如题意所示。接下来一行p个整数，空格隔开，第i个整数代表A国需要的土地编号。接下来一行q个整数，空格隔开，第i个整数代表B国需要的土地编号土地编号从q开始，n结束。
输出描述:
输出包含三个数，只有A国想要的土地数，只有B国想要的土地数，两个国家都想要的土地数。
输入例子1:
5 3 3
1 2 3
3 4 5
输出例子1:
2 2 1
例子说明1:
1,2号土地只有A想要，4,5号土地只有B想要，3号土地都想要
思路：
将A国想要的土地编号和B国想要的土地编号看作是两个集合。对这两个集合进行交集运算即可得到两个国家都想要的土地编号；再使用这个交集分别和A集合与B集合作差运算即可得到两个国家想要的土地编号，最后分别求集合大小即可。
代码：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,a,b;
cin>>n>>a>>b;
vector<int> A(n+1,0);
vector<int> B(n+1,0);
set<int> Sa;
set<int> Sb;
set<int> Sc;
set<int> Sca;
set<int> Scb;
set<int> Sab;
int sum1=0,sum2=0,sum3=0;
for(int i=0;i<a;i++)
{
cin>>A[i];
Sa.insert(A[i]);
}
for(int i=0;i<b;i++)
{
cin>>B[i];
Sb.insert(B[i]);
}
set_intersection(Sa.begin(),Sa.end(),Sb.begin(),Sb.end(),inserter(Sc,Sc.begin()));
set_difference(Sa.begin(),Sa.end(),Sc.begin(),Sc.end(),inserter(Sca,Sca.begin()));
set_difference(Sb.begin(),Sb.end(),Sc.begin(),Sc.end(),inserter(Scb,Scb.begin()));
sum1=Sca.size();
sum2=Scb.size();
sum3=Sc.size();
cout<<sum1<<" "<<sum2<<" "<<sum3;
return 0;
}
公司管理
在小团的公司中，有n位员工。除了最高领导——小团外，每位员工有且仅有一位直接领导。所以，公司内从属关系可以看成一棵树。
现在，公司接到一个项目，需要重新划分这n位员工的从属关系。新的划分描述如下：
1.每个人要么没有下属，要么有至少两个直接下属（即至少有两人的直接领导为这个人）
2.第i个人的下属（包括自己）有恰好ai个。
请注意，直接下属和下属（包括自己）可分别看做树上点的"儿子"和"子树"。
请问是否存在这么一种关系？注意，输入不会给出最高领导的编号。
输入描述:
输入包含多组数据。对于每组数据，第一行一个整数n，表示公司有n个人。接下来一行n个数，第i个数为ai，含义如题面所示。
输出描述:
对每组数据，输出一行"YES"或"NO"，代表是否存在这一种从属关系。
输入例子1:
3
1 1 3
2
1 2
输出例子1:
YES
NO
例子说明1:
对于第一组样例，1和2的直接领导均为3即可对于第二组样例，无法构造出符合题目要求的关系。注意每个有下属的人至少有2个直接下属。
思路：
参考评论区
代码：
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int maxn = 30;
int n, a[maxn];
bool ans, used[maxn];
void dfs(int t);
void solve(int s, int e, int c, int aa)
{
if (aa == 1)
{
if (c > 1) dfs(e + 1);
return;
}
for (int i = s; i < e; ++i)
{
if (a[i] + 1 > aa) break;
if (used[i]) continue;
if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;
used[i] = true;
solve(i + 1, e, c + 1, aa - a[i]);
if (ans) return;
used[i] = false;
}
}
void dfs(int t)
{
if (t >= n)
{
ans = true;
return;
}
solve(0, t, 0, a[t]);
}
int main()
{
while (scanf("%d", &n) != EOF)
{
ans = true;
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
if (a[i] < 1)
ans = false;
}
sort(a, a + n);
if (!ans || a[n - 1] != n)
{
printf("NO\n");
continue;
}
int i = 0;
for (; i < n; ++i)
if (a[i] > 1) break;
if (i < n / 2)
{
printf("NO\n");
continue;
}
memset(used, false, sizeof(used));
ans = false;
dfs(i);
if (ans) printf("YES\n");
else printf("NO\n");
}
return 0;
}
总结
第一题：
暂无。
第二题：
-
异或的运算法则：
- 归零律：a ^ a = 0
- 恒等律：a ^ 0 = a
- 交换律：a ^ b = b ^ a
- 结合律：a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
- 自反律：a ^ b ^ a = b
- 真值表：
| a |
b |
a ^ b |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
0 |
第三题：
-
C++中的set：集合（确定性、互异性、无序性）
- 头文件：
#include<set>
- 创建set对象：
set<T> set1;
-
set取并集、交集、差集：
- 头文件：
#include<algorithm>
- 取集合并集：
set_union(set1.begin(),set1.end(),set2.begin(),set2.end(),inserter(set3.begin()));其中set1和set2时需要作并集操作的两个集合，并集的结果放在set3中。
- 取集合交集：
set_intersection(set1.begin(),set1.end(),set2.begin(),set2.end(),inserter(set3.begin()));其中set1和set2时需要作交集操作的两个集合，交集的结果放在set3中。
- 取集合差集：
set_difference(set1.begin(),set1.end(),set2.begin(),set2.end(),inserter(set3.begin()));其中set1和set2时需要作差集操作的两个集合，差集的结果放在set3中。
- 取集合对称差集：A△B=（A-B）∪（B-A）
set_symmetric_difference(set1.begin(),set1.end(),set2.begin(),set2.end(),inserter(set3.begin()));其中set1和set2时需要作对称差集操作的两个集合，对称差集的结果放在set3中。
- 注：上述的函数中第五个参数也可以替换为：
ostream_iterator(cout," ")表示直接将集合计算结果输出，并以空格将各元素分隔开。
- 输出集合：
cout<<"{"
for(set<int>::iterator pos=set1.begin();pos!=set1.end();pos++)
{
if(pos!=set1.begin())
cout<<", "
cout<<*pos;
}
cout<<"}"<<endl;
- 集合的大小：
set1.size();
第四题：
-
C语言处理多组输入输出：
-
已知输入数据组数n
scanf("%d",&n);
while(n--)
{
//处理每一组输入，直接按格式输出
}
-
未知数据组数，以EOF结束
int n;
while(scanf("%d",&n)!=EOF)
{
//处理每一组数据,并输出
}
char ch;
while((ch=getchar())!=EOF) //读入一个字符
{
//处理每一组数据,并输出
}
string buf;
while(gets(buf)!=NULL) //读入一行
{
//处理每一组数据,并输出
}
-
未知数据组数，以0或-1结束
int n;
while(scanf("%d",&n),n!=0)
{
//处理每一组数据,并输出
}
-
C++处理输入输出：
-
cin读字符串时遇到空白符（空格、换行等）结束：
char str[BUFFER];
while(cin>>str)
{
//处理每一组数据,并输出
}
-
getline读字符串时遇到换行符结束,用于读一整行
char str[BUFFER];
while (cin.getline(str, BUFFER))
{
//处理每一组数据,并输出
}
string str;
while (getline(cin, str))
{
//处理每一组数据,并输出
}
-
cin/cout要比scanf/printf慢一些，尽可能使用scanf/printf以避免测试大量数据时因为输入输出慢而导致TLE。putchar/getchar要比scanf/printf更快。
