AtCoder Beginner Contest 157
分类:
IT文章
•
2023-11-28 17:29:49
传送门
A - Duplex Printing
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
//freopen("in.txt","r",stdin);
int n;
scanf("%d",&n);
printf("%d
",(n+1)/2);
return 0;
}
A.cpp
B - Bingo
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[5][5];
bool vis[5][5];
int main() {
//freopen("in.txt","r",stdin);
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
scanf("%d",&a[i][j]);
}
}
int n;
scanf("%d",&n);
for(int i=0,x;i<n;i++) {
scanf("%d",&x);
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
if(a[i][j]==x) vis[i][j]=true;
}
}
}
bool f=false;
for(int i=0;i<n;i++) {
if(vis[i][0]&&vis[i][1]&&vis[i][2]) f=true;
if(vis[0][i]&&vis[1][i]&&vis[2][i]) f=true;
}
if(vis[0][0]&&vis[1][1]&&vis[2][2]) f=true;
if(vis[0][2]&&vis[1][1]&&vis[2][0]) f=true;
printf("%s
",f?"Yes":"No");
return 0;
}
B.cpp
C - Guess The Number
题意:有M个要求,从高位起第si位为ci,找最小的不包含前导零的N位数,若不存在,输出-1。
数据范围:$1 leq N leq 3,1 leq M leq 5,1 leq si leq N,0 leq ci leq 9$
题解:讨论起来太麻烦了,很多神奇的样例卡,数据范围小,可以直接暴力枚举每个值,然后判断是否合法即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,x[10],y[10];
int cal() {
if(n==1) {
for(int i=0;i<10;i++) {
bool f=true;
for(int j=0;j<m;j++) {
if(i!=y[j]) f=false;
}
if(f) return i;
}
return -1;
}
if(n==2) {
for(int i=10;i<100;i++) {
bool f=true;
for(int j=0;j<m;j++) {
if(x[j]==1&&i/10!=y[j]) f=false;
if(x[j]==2&&i%10!=y[j]) f=false;
}
if(f) return i;
}
return -1;
}
for(int i=100;i<1000;i++) {
bool f=true;
for(int j=0;j<m;j++) {
if(x[j]==1&&i/100!=y[j]) f=false;
if(x[j]==2&&(i/10)%10!=y[j]) f=false;
if(x[j]==3&&i%10!=y[j]) f=false;
}
if(f) return i;
}
return -1;
}
int main() {
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++) {
scanf("%d%d",&x[i],&y[i]);
}
printf("%d
",cal());
return 0;
}
C.cpp
D - Friend Suggestions
题意:N个人,有M个朋友关系,K个敌对关系,定义候选朋友关系为存在不同的两人a,b,a和b没有朋友和敌对关系,且a和b存在间接的朋友关系,求每个人的候选朋友关系个数。
数据范围:$2 leq N leq 10^{5},0 leq M,K leq 10^{5}$
题解:并查集求出每个人的直接间接的朋友数求出来,然后减去直接朋友数和自己本身,然后遍历敌对关系,判断两个是否存在间接朋友关系,若有,则两人数目减1。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int f[N],a[N],ma[N],ans[N];
int Find(int x) {
if(x==f[x]) return x;
return f[x]=Find(f[x]);
}
int main() {
//freopen("in.txt","r",stdin);
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=0,x,y;i<m;i++) {
scanf("%d%d",&x,&y);
a[x]++,a[y]++;
f[Find(x)]=Find(y);
}
for(int i=1;i<=n;i++) {
ma[Find(i)]++;
}
for(int i=1;i<=n;i++) {
ans[i]=ma[f[i]]-a[i]-1;
}
for(int i=0,x,y;i<k;i++) {
scanf("%d%d",&x,&y);
if(f[x]==f[y]) ans[x]--,ans[y]--;
}
for(int i=1;i<=n;i++) {
printf("%d%c",ans[i],i==n?'
':' ');
}
return 0;
}
D.cpp
E - Simple String Queries
题意:有一个长度为N的字符串(只包含小写字母),现有Q个操作,操作1是把第x位的字符改成y,操作2是查询[l,r]内去重后有多少个字符。
数据范围:$1 leq N leq 5 imes 10^{5},1 leq Q leq 2 imes 10^{4}$
题解:由于只有小写字母,可以对每一个字母进行讨论,那么就是一个单点修改,区间查询的问题,用树状数组进行维护。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
char s[N],ss[5];
int f[N][26];
int n,q;
void update(int id,int pos,int val) {
for(int i=pos;i<=n;i+=(i&-i)) {
f[i][id]+=val;
}
}
int query(int id,int pos) {
int ans=0;
for(int i=pos;i;i-=(i&-i)) {
ans+=f[i][id];
}
return ans;
}
int main() {
//freopen("in.txt","r",stdin);
scanf("%d%s%d",&n,s+1,&q);
for(int i=1;i<=n;i++) {
int x=s[i]-'a';
update(x,i,1);
}
for(int i=0,op,x,y;i<q;i++) {
scanf("%d",&op);
if(op==1) {
scanf("%d%s",&x,ss);
update(s[x]-'a',x,-1);
update(ss[0]-'a',x,1);
s[x]=ss[0];
}
else {
scanf("%d%d",&x,&y);
int ans=0;
for(int j=0;j<26;j++) {
if(query(j,y)-query(j,x-1)) ans++;
}
printf("%d
",ans);
}
}
return 0;
}
E.cpp
可以二分答案,进而转化成N个圆,每个圆的半径为t/Ci,判断是否存在一点使得至少有K个圆覆盖到。可以画图观察到能被最多圆覆盖的点,肯定存在于每个圆的圆心和两圆交点之间。
#include <bits/stdc++.h>
using namespace std;
const int N=65;
const double eps=1e-9;
int n,k;
double x[N],y[N],c[N],r[N];
double dis(pair<double,double> a,pair<double,double> b) {
return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
vector<pair<double,double> > cal(double x1,double y1,double r1,double x2,double y2,double r2) {//两圆交点
x1-=x2,y1-=y2;
double S=x1*x1+y1*y1,a=(S+r2*r2-r1*r1)/2,D=S*r2*r2-a*a;
if(D<0) return {};
double A1=a*x1,B1=y1*sqrt(D);
double A2=a*y1,B2=x1*sqrt(D);
return {{(A1+B1)/S+x2,(A2-B2)/S+y2},{(A1-B1)/S+x2,(A2+B2)/S+y2}};
}
bool check(double t) {
for(int i=0;i<n;i++) r[i]=t/c[i];
vector<pair<double,double> > vec;
for(int i=0;i<n;i++) {
vec.push_back({x[i],y[i]});
for(int j=i+1;j<n;j++) {
auto v=cal(x[i],y[i],r[i],x[j],y[j],r[j]);
for(auto it:v) vec.push_back(it);
}
}
for(auto it:vec) {
int cnt=0;
for(int i=0;i<n;i++) {
if(r[i]+eps>=dis(it,{x[i],y[i]})) cnt++;
}
if(cnt>=k) return true;
}
return false;
}
int main() {
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) {
scanf("%lf%lf%lf",&x[i],&y[i],&c[i]);
}
double L=0,R=1e9;
for(int i=0;i<100;i++) {
double mid=(L+R)/2;
if(check(mid)) R=mid;
else L=mid;
}
printf("%.12f
",R);
return 0;
}