Contest - 2021-07-12 个人排位赛1
A Awkward Digits
题意
给你一个数n 的二进制表示和三进制表示，二进制表示和三进制表示中都有一个数错误，让你求原来的n是什么。
其中 0 < = n < = 1 e 9 0<=n<=1e9 0<=n<=1e9
Solution
暴力枚举二进制数中的某一位错误，三进制数中的某一位错误，将其修正后，看看二进制数和三进制数是否相等，若相等，转换为十进制得到答案。（这个方法需要较多的特判）
暴力枚举二进制数中的某一位错误，改正后转化为三进制，与原来的三进制数比较，看其是否只有一位不同，若是，转换为十进制即是答案。(更为简单的方法，特判少一点)
代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
string s1,s2;
int n,m;
ll a[50],b[50];
ll x=0,y=0;
int main()
{
cin>>s1>>s2;
n=s1.length();
m=s2.length();
a[0]=b[0]=1;
for(int i=1;i<=40;i++)
{
a[i]=1ll*a[i-1]*2;
b[i]=1ll*b[i-1]*3;
}
for(int i=0;i<n;i++)x+=(s1[i]-'0')*a[n-1-i];
for(int i=0;i<m;i++)y+=(s2[i]-'0')*b[m-1-i];
for(int i=0;i<n;i++)
{
x-=(s1[i]-'0')*a[n-1-i];
for(int j=0;j<m;j++)
{
y-=(s2[j]-'0')*b[m-1-j];
if(s1[i]=='0')
{
if(s2[j]=='0')
{
if(x+a[n-1-i]==y+b[m-1-j])
{
cout<<(x+a[n-1-i]);
return 0;
}
else if(x+a[n-1-i]==y+2*b[m-1-j])
{
cout<<(x+a[n-1-i]);
return 0;
}
}
else if(s2[j]=='1')
{
if(x+a[n-1-i]==y)
{
cout<<(x+a[n-1-i]);
return 0;
}
else if(x+a[n-1-i]==y+2*b[m-1-j])
{
cout<<(x+a[n-1-i]);
return 0;
}
}
else
{
if(x+a[n-1-i]==y+b[m-1-j])
{
cout<<(x+a[n-1-i]);
return 0;
}
else if(x+a[n-1-i]==y)
{
cout<<(x+a[n-1-i]);
return 0;
}
}
}
else
{
if(s2[j]=='0')
{
if(x==y+b[m-1-j])
{
cout<<(x);
return 0;
}
else if(x==y+2*b[m-1-j])
{
cout<<(x);
return 0;
}
}
else if(s2[j]=='1')
{
if(x==y)
{
cout<<(x);
return 0;
}
else if(x==y+2*b[m-1-j])
{
cout<<(x);
return 0;
}
}
else
{
if(x==y+b[m-1-j])
{
cout<<(x);
return 0;
}
else if(x==y)
{
cout<<(x);
return 0;
}
}
}
y+=(s2[j]-'0')*b[m-1-j];
}
x+=(s1[i]-'0')*a[n-1-i];
}
return 0;
}
B Above the Median
题意
给定一个长度为n，一个数x，接下来给定长度为n的数组数组，求这个数组内，有多少个区间的中位数大于等于n。
中位数：假设区间长度为k，那么中位数就是区间内的数排序过后的第 ⌊ k + 1 2 ⌋ \lfloor \frac{k+1}{2} \rfloor ⌊2k+1⌋个
Solutin
先预处理这个数组，将数组中小于x的数记为-1，大于等于x的数记为1，中位数大于x即区间内1的个数大于等于-1，即区间和大于等于0，设一个变量rela来记录0的相对位置，如果当前要加的值为1，说明将之前所有的区间和都加上1，即相对位置rela左移1位，再往rela右边一个位置加上1，如果当前要加的值为-1，说明之前所有和都减少1，即相对位置右移一位，再往rela左边一个位置加上1，然后通过树状数组查询有多少个值大于等于0的数。
代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int n,x;
int a[100005];
int tree[400005];
const int N=1e5+10;
int lowbit(int x){
return x&(-x);}
void update(int x,int val)
{
for(int i=x;i<=400000;i+=lowbit(i))tree[i]+=val;
}
int query(int x)
{
int res=0;
while(x)
{
res+=tree[x];
x-=lowbit(x);
}
return res;
}
int main()
{
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]>=x)a[i]=1;
else a[i]=-1;
}
int rela=0;
ll res=0;
for(int i=1;i<=n;i++)
{
if(a[i]>0)rela--;
else rela++;
update(rela+a[i]+N,1);
res+=query(400000)-query(rela+N-1);
}
printf("%lld",res);
return 0;
}
C Moo Sick
题意
给了A和B两个序列，问A中有多少个长得向B的序列，并且输出长像的序列在A中的起始位置
长得像是指满足一下条件
1.区间长度与B的长度一致
2.整体加或减某个数后，经过重新排列能跟B完全一致
Soltion
暴力枚举区间，排序后判断差值是否一致
代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int n,m;
int a[20005];
int b[15],c[15];
vector<int>res;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d",&b[i]);
sort(b+1,b+1+m);
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
{
c[j+1]=a[i+j];
}
sort(c+1,c+1+m);
int d=b[1]-c[1];
bool flag= true;
for(int j=2;j<=m;j++)
{
if(d!=b[j]-c[j])
{
flag=false;
break;
}
}
if(flag)res.push_back(i);
}
printf("%d\n",res.size());
for(int i=0;i<res.size();i++)
printf("%d\n",res[i]);
return 0;
}
D Cow Lineup
题意
n头牛，给出这n头牛的位置和品种，找到最小的区间长度，满足这个区间内包含了所有品种的牛。
Solution
暴力枚举右端点，然后再枚举左端点，只要左端点所处位置的那个品种的牛出现两次及以上，就增大左端点大小，如果此时包含所有品种的牛，则更新答案，取最小值。
代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int n;
vector<P>e;
int a[50005];
int vis[50005];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int x,y;scanf("%d%d",&x,&y);
e.push_back(P(x,y));
a[i]=y;
}
sort(e.begin(),e.end());
sort(a,a+n);
int k=unique(a,a+n)-a;
for(int i=0;i<n;i++)
{
int qaq=lower_bound(a,a+k,e[i].second)-a;
e[i].second=qaq;
}
int c=0;
int res=INF;
int l=0,r=0;
while(r<n)
{
int id=e[r].second;
if(vis[id]==0)c++;
vis[id]++;
while(l<n&&vis[e[l].second]>1)
{
vis[e[l].second]--;
if(c==k)res=min(e[r].first-e[l].first,res);
l++;
}
if(c==k)res=min(e[r].first-e[l].first,res);
r++;
}
printf("%d",res);
return 0;
}
E Cow Beauty Pageant I
题意
求两个X连通块之间的最短距离。
Solution
将其中一个连通块的距离标记为0，其余点标记为INF，从距离为0的点出发，跑一遍bfs，求最短距离即可
代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int n,m;
char tu[55][55];
int dx[]={
0,0,1,-1},dy[]={
1,-1,0,0};
queue<P>q;
int vis[55][55];
void bfs1(int x,int y)
{
queue<P>qq;
qq.push(P(x,y));
tu[x][y]='.';
vis[x][y]=1;
while(!qq.empty())
{
P p=qq.front();qq.pop();
q.push(p);
for(int i=0;i<4;i++)
{
int x=dx[i]+p.first;
int y=dy[i]+p.second;
if(x<0||x>=n||y<0||y>=m)continue;
if(vis[x][y]==1||tu[x][y]=='.')continue;
tu[x][y]='.';
vis[x][y]=1;
qq.push(P(x,y));
}
}
}
int bfs2()
{
int res=INF;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(vis[i][j]==0)vis[i][j]=INF;
else vis[i][j]=0;
}
}
while(!q.empty())
{
P p =q.front();q.pop();
if(tu[p.first][p.second]=='X')res=min(res,vis[p.first][p.second]);
for(int i=0;i<4;i++)
{
int x=dx[i]+p.first;
int y=dy[i]+p.second;
if(x<0||x>=n||y<0||y>=m)continue;
if(vis[x][y]<=vis[p.first][p.second]+1)continue;
vis[x][y]=vis[p.first][p.second]+1;
q.push(P(x,y));
}
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%s",tu[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(tu[i][j]=='X')
{
bfs1(i,j);
}
if(!q.empty())break;
}
if(!q.empty())break;
}
int res=bfs2();
printf("%d",res-1);
return 0;
}
F Contest Timing
题意
给出结束时间的day、hour、minute，求这个时间距离11号11：11过了多久，如果结束时间在此之前，输出-1，在这个时间之后，输出过了多少分钟才结束
Solution
将时间转换为分钟，然后比较大小，输出
代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int d,h,m;
int main()
{
cin>>d>>h>>m;
ll x=(d-11)*24*60+(h-11)*60+m-11;
if(x<0)cout<<-1;
else cout<<x;
return 0;
}
G Paint by Letters
H Cow Beauty Pageant II
题意
给定三个X的联通块，求三个联通块最少需要添加几个X才能相连通
Solution
将图中的每个点（这里指’.’）都作为起点，跑一遍bfs，得到的距离分别为d1,d2,d3，那么d1+d2+d3-2即为答案，最终答案为所有的结果最小值，然后三个联通块分别以每一个连通块最为起点，跑一遍bfs
代码
// 以每一个点（‘.’）跑一遍bfs，三个连通块之间分别跑一次bfs
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int n,m;
char tu[505][505];
int dx[]={
0,0,1,-1},dy[]={
1,-1,0,0};
int d[10];
int vis[505][505];
int dd[505][505];
int res=INF;
void bfs(int x,int y,int id)
{
queue<P>q;
q.push(P(x,y));
while(!q.empty())
{
P p=q.front();q.pop();
tu[p.first][p.second]=(char)('0'+id);
for(int i=0;i<4;i++)
{
x=dx[i]+p.first;
y=dy[i]+p.second;
if(x<0||x>=n||y<0||y>=m)continue;
if(tu[x][y]!='X')continue;
q.push(P(x,y));
tu[x][y]=(char)('0'+id);
}
}
}
void bfs1(char ch)
{
queue<P>q;
memset(vis,INF,sizeof(vis));
memset(dd,-1,sizeof(dd));
memset(d,INF,sizeof(d));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(tu[i][j]==ch)
{
q.push(P(i,j));
vis[i][j]=0;
}
}
}
while(!q.empty())
{
P p = q.front(); q.pop();
if(dd[p.first][p.second]==1)continue;
dd[p.first][p.second]=1;
char tem=tu[p.first][p.second];
if((ch=='1'&&tem=='2')||(ch=='2'&&tem=='1'))
{
d[1]=min(vis[p.first][p.second],d[1]);
}
if((ch=='1'&&tem=='3')||(ch=='3'&&tem=='1'))
{
d[2]=min(vis[p.first][p.second],d[2]);
}
if((ch=='2'&&tem=='3')||(ch=='3'&&tem=='2'))
{
d[3]=min(vis[p.first][p.second],d[3]);
}
for(int i=0;i<4;i++)
{
int x=dx[i]+p.first;
int y=dy[i]+p.second;
if(x<0||x>=n||y<0||y>=m)continue;
if(vis[p.first][p.second]+1>=vis[x][y])continue;
q.push(P(x,y));
vis[x][y]=vis[p.first][p.second]+1;
}
}
sort(d+1,d+4);
res=min(res,d[1]+d[2]-2);
}
void bfs2(int x,int y)
{
queue<P>q;
memset(vis,INF,sizeof(vis));
memset(d,INF,sizeof(d));
vis[x][y]=0;
q.push(P(x,y));
while(!q.empty())
{
P p=q.front();q.pop();
if(tu[p.first][p.second]=='1')d[1]=min(d[1],vis[p.first][p.second]);
if(tu[p.first][p.second]=='2')d[2]=min(d[2],vis[p.first][p.second]);
if(tu[p.first][p.second]=='3')d[3]=min(d[3],vis[p.first][p.second]);
for(int i=0;i<4;i++)
{
x=p.first+dx[i];
y=p.second+dy[i];
if(x<0||x>=n||y<0||y>=m)continue;
if(vis[x][y]<=1+vis[p.first][p.second])continue;
vis[x][y]=1+vis[p.first][p.second];
q.push(P(x,y));
}
}
res=min(d[1]+d[2]+d[3]-2,res);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%s",tu[i]);
memset(d,INF,sizeof(d));
int c=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(tu[i][j]=='X')
{
++c;
bfs(i,j,c);
}
}
}
bfs1('1');
bfs1('2');
bfs1('3');
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(tu[i][j]=='.')
bfs2(i,j);
}
}
printf("%d",res);
return 0;
}
/* 9 9 ......... .....X... ......... ........X ......... .....X... ......... ......... ......... */
// 以每个点（'.','X'）跑一遍bfs
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int n,m;
char tu[505][505];
int dx[]={
0,0,1,-1},dy[]={
1,-1,0,0};
int d[10];
int vis[505][505];
int dd[505][505];
int res=INF;
void bfs(int x,int y,int id)
{
queue<P>q;
q.push(P(x,y));
while(!q.empty())
{
P p=q.front();q.pop();
tu[p.first][p.second]=(char)('0'+id);
for(int i=0;i<4;i++)
{
x=dx[i]+p.first;
y=dy[i]+p.second;
if(x<0||x>=n||y<0||y>=m)continue;
if(tu[x][y]!='X')continue;
q.push(P(x,y));
tu[x][y]=(char)('0'+id);
}
}
}
void bfs1(int x,int y)
{
char ch=tu[x][y];
queue<P>q;
memset(vis,INF,sizeof(vis));
memset(d,INF,sizeof(d));
vis[x][y]=0;
q.push(P(x,y));
while(!q.empty())
{
P p=q.front();q.pop();
if(tu[p.first][p.second]=='1')d[1]=min(d[1],vis[p.first][p.second]);
if(tu[p.first][p.second]=='2')d[2]=min(d[2],vis[p.first][p.second]);
if(tu[p.first][p.second]=='3')d[3]=min(d[3],vis[p.first][p.second]);
for(int i=0;i<4;i++)
{
x=p.first+dx[i];
y=p.second+dy[i];
if(x<0||x>=n||y<0||y>=m)continue;
if(vis[x][y]<=1+vis[p.first][p.second])continue;
if(ch==tu[x][y]&&ch!='.')
vis[x][y]=0;
else
vis[x][y]=1+vis[p.first][p.second];
q.push(P(x,y));
}
}
//cout<<d[1]<<' '<<d[2]<<' '<<d[3]<<endl;
res=min(d[1]+d[2]+d[3]-2,res);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%s",tu[i]);
memset(d,INF,sizeof(d));
int c=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(tu[i][j]=='X')
{
++c;
bfs(i,j,c);
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
bfs1(i,j);
}
}
printf("%d",res);
return 0;
}
/* 9 9 ......... .....X... ......... ........X ......... .....X... ......... ......... ......... */
I Cow Steeplechase
题意
给定n条水平线或竖直线的端点坐标，求最多能得到多少条不相交的线段
solution
两条线段有交点，就将线段看作点，有交点即代表两个点之间有一条边，任意两个点之间的连边不会相交，也就是说明要跑二分图的最大权独立子集。最大权独立子集=点数-二分图最大匹配。
代码
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
int n;
vector<P>s,t;
vector<int>e[300];
int used[300];
int vis[300];
bool found(int x)
{
for(int i=0;i<e[x].size();i++)
{
if(!used[e[x][i]])
{
used[e[x][i]]=1;
if(vis[e[x][i]]==-1||found(vis[e[x][i]]))
{
vis[e[x][i]]=x;
return 1;
}
}
}
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1>x2)swap(x1,x2);
if(y1>y2)swap(y1,y2);
s.push_back(P(x1,y1));
t.push_back(P(x2,y2));
}
for(int i=0;i<n;i++)
{
if(s[i].second!=t[i].second)continue;
for(int j=0;j<n;j++)
{
if(s[j].first!=t[j].first)continue;
if(s[i].second>=s[j].second&&s[i].second<=t[j].second&&s[i].first<=s[j].first&&t[i].first>=s[j].first)e[i].push_back(j);
}
}
int sum=0;
memset(vis,-1,sizeof(vis));
for(int i=0;i<n;i++)
{
memset(used,0,sizeof(used));
if(e[i].size()>0)
{
if(found(i))sum++;
}
}
printf("%d",n-sum);
return 0;
}
京公网安备 11010502036488号