Atcoder ABC157 题解
键盘微凉 / 鼠标微凉 / 指尖流淌 / 代码千行
A - Duplex Printing
题意
给你一个数,一次能打印两面，问表示需要打印多少张才能将所有打印完。
思路
签到题，如果这个数是偶数, 输出n/2，如果这个数是奇数,输出n/2+1.
代码
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
if(n%2==0){
cout<<n/2;
}
else {
cout<<(n/2)+1;
}
return 0;
}
B - Bingo
题意
给一个 3 * 3 的矩阵,每个位置有一个数,之后再给你一些数,如果这些数在这个矩阵中并且所以数组合到一起可以使得 有一列或者有一行或者斜对角 都出现过,就输出 Yes,否则输出 No.
思路
模拟就好了，判断条件写起来麻烦一点就是
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[5][5],b[5][5];
int main(){
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
cin>>a[i][j];
}
}
int n;
cin>>n;
for(int i=1;i<=n;i++){
int x;cin>>x;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
if(a[i][j]==x){
b[i][j]=1;
}
}
}
}
int ok=0;
for(int i=1;i<=3;i++){
if(b[i][1]==b[i][2]&&b[i][2]==b[i][3]&&b[i][1]==1){
ok=1;break;
}
}
for(int i=1;i<=3;i++){
if(b[1][i]==b[2][i]&&b[2][i]==b[3][i]&&b[1][i]==1){
ok=1;break;
}
}
if(b[1][1]==1&&b[1][1]==b[2][2]&&b[2][2]==b[3][3]){
ok=1;
}
if(b[1][3]==1&&b[1][3]==b[2][2]&&b[2][2]==b[3][1]){
ok=1;
}
if(ok){
cout<<"Yes";
}
else cout<<"No";
return 0;
}
C - Guess The Number
题意
大概就是说给你一个不超过三位的一个数,然后这之后会有一些操作,可以指定某一位是多少,但是不允许有前导 0 ,同一个位置不能重复指定,否则会出现错误,除了指定的数外,还要保证最后得到的数是最小的。
思路
按照题意构造数，要注意的是不允许有前导零，但是单独一个零算数，所以要特判一下
代码
#include<cstdio>
#include<iostream>
using namespace std;
int a[10];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
a[i]=-1;
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
if(x>n){
cout<<"-1";
return 0;
}
if(a[x]<0){
a[x]=y;
}
else{
if(a[x]!=y){
cout<<"-1";
return 0;
}
}
}
if(n==1&&a[1]==0){
cout<<"0";
return 0;
}
if(n==1&&m==0){
cout<<"0";
return 0;
}
int ok=0;
for(int i=1;i<=n;i++){
if(ok==0){
if(a[i]==0){
cout<<"-1";
return 0;
}
else {
ok=1;
if(a[i]==-1) a[i]=1;
cout<<a[i];
}
}
else{
if(a[i]==-1) a[i]=0;
cout<<a[i];
}
}
return 0;
}
D - Friend Suggestions
题意
先给一些关系,表明两个数之间是朋友的关系,接着再给一些关系,表示这些人之间不是朋友的
关系,最后问你每个人可以有多少个人可以是自己的候选朋友(不包括已有的)，而且所有人跟
自己还必须是在同一个连通块内的。
思路
首先用带权并查集圈出朋友圈，对于每个人来说，候选朋友的个数即为所在朋友圈大小减去已经是朋友的和不能做朋友的和自己即可。
注意不能做朋友的部分，显然是在一个朋友圈的才需要减，所以先建好朋友圈，然后判断输入的敌对关系是不是在一个朋友圈即可。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
int n,m,k;
int f[maxn],sum[maxn],fre[maxn];
void init(){
for(int i=1;i<=n;i++){
f[i]=i;
sum[i]=1;
}
return ;
}
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx!=fy){
f[fy]=fx;sum[fx]+=sum[fy];
}
return ;
}
int main(){
cin>>n>>m>>k;
init();
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
fre[x]++;fre[y]++;
merge(x,y);
}
for(int i=1;i<=k;i++){
int x,y;
cin>>x>>y;
if(find(x)==find(y)){
fre[x]++;fre[y]++;
}
}
for(int i=1;i<=n;i++){
cout<<sum[find(i)]-fre[i]-1<<" ";
}
return 0;
}
E - Simple String Queries
题意
有一串字符,我们可以执行两种操作:
1、替换某个位置的字符
2、查询某一段区间不同字符的个数
思路
只需要把查询操作的复杂度降下来就好了，显然set比较方便
开一个set数组s[i],存储第i个字母所在的位置集合，每次修改就在原来字母的set中删去那个位置，再在新字母set中插入位置，查询操作就遍历26个字母，l为左边界，set.lower_bound(l) 会返回大于等于l的第一个指针，将它和r比较，如果比r小的话说明区间内有这个字母，ans++即可
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=500000+10;
set<int> s[30];
char ch[maxn];
int main(){
int n,q;
cin>>n>>ch+1>>q;
for(int i=1;i<=n;i++){
s[ch[i]-'a'].insert(i);
}
while(q--){
int t,x;cin>>t;
if(t==1){
char cc;cin>>x>>cc;
if(ch[x]!=cc) s[ch[x]-'a'].erase(x);
ch[x]=cc;
s[cc-'a'].insert(x);
}
else{
int ans=0,ll,rr;
cin>>ll>>rr;
for(int i=0;i<26;i++){
if(*s[i].lower_bound(ll)>=ll&&*s[i].lower_bound(ll)<=rr) ans++;
}
cout<<ans<<endl;
}
}
return 0;
}