layout: post
title: Codeforces Round 545 (Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
- 贪心
- 数学
- floyd判环
传送门
A - Sushi for Two(签到)
题意
在一个 01 序列中找出长为偶数的连续的一段使得它前一半和后一半内部分别相同，而前一半和后一半不同。
思路
纸上模拟了一下然后预处理 赛后发现太麻烦了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const int inf=1e9;
typedef unsigned long long ull;
int a[maxn];
int one[maxn];
int zero[maxn];
int num[maxn];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]==1)one[i]++;
else zero[i]++;
}
for(int i=1;i<=n;i++){
if(one[i])one[i]=one[i-1]+1;
if(zero[i])zero[i]=zero[i-1]+1;
// cout<<one[i]<<" "<<zero[i]<<endl;
}
for(int i=n;i>=1;i--){
if(one[i])one[i]=max(one[i],one[i+1]);
if(zero[i])zero[i]=max(zero[i],zero[i+1]);
}
// cout<<endl;
int ans=0;
for(int i=1;i<=n;i++){
// cout<<one[i]<<" "<<zero[i]<<endl;
ans=max(ans,min(one[i-1],zero[i]));
ans=max(ans,min(zero[i-1],one[i]));
}
cout<<ans*2<<endl;
return 0;
}B - Circus (数学，推公式)
题意
有 n个人，需要把它们分成两组，每组恰好 2/n 个人。每个人可能会技能 11或技能 2，一个人可能会其中一种、两种都会或什么都不会。
要求第一组中会技能 1的人数恰好等于第二组中会技能 2 的人数，输出方案
2<=n<=5000
思路
比赛在纸上写了两张纸都没写出来的题
参考https://www.cnblogs.com/wjyyy/p/cf1138.html
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
vector<int>v[5];
char s[maxn],t[maxn];
int main()
{
int n;
scanf("%d",&n);
scanf("%s%s",s+1,t+1);
for(int i=1;i<=n;i++){
v[s[i]-'0'+(t[i]-'0')*2].push_back(i);
}
int a=v[0].size(),b=v[1].size(),c=v[2].size(),d=v[3].size(),h=n/2;
for(int i=0;i<=d;i++){
if(d-i+c>h||i+b>h)continue;
if(i<d-i){
if(b<d-2*i)continue;
for(int j=0;j<i;j++)
printf("%d ",v[3][j]);
h-=i;
for(int j=0;j<d-2*i;j++)
printf("%d ",v[1][j]);
h-=d-2*i;
for(int j=0;j<c;j++)
printf("%d ",v[2][j]);
h-=c;
for(int j=0;j<h;j++)
printf("%d ",v[0][j]);
return 0;
}
else{
if(c<2*i-d)continue;
c-=2*i-d;
for(int j=0;j<i;++j)
printf("%d ",v[3][j]);
h-=i;
for(int j=0;j<c;++j)
printf("%d ",v[2][j]);
h-=c;
for(int j=0;j<h;++j)
printf("%d ",v[0][j]);
return 0;
}
}
printf("-1");
return 0;
}C - Skyscrapers (离散化+贪心)
题意
有一个 n×m的矩阵 aijaij。
对于每个 (i,j)1≤i≤n1≤i≤n），你把第 i行和第 j 列单独抽出，这样就有 n+m−1 个数被你抽出。
你可以对这些数重新标号为正整数，但是要满足第 i行所有数的大小关系不变，第 j列所有数的大小关系不变（两个限制相互独立）。
满足这个限制下，你希望最大的标号尽量小，对每个 (i,j) 求出这个最小的最大标号。
思路
因为行大小关系不变，列大小关系不变，我们考虑分别离散化每行每列，并统计每个数在行内和列内的排名。
然后贪心取个最大的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const int inf=1e9;
typedef unsigned long long ull;
vector<int>ve;
int a[1500][1500];
vector<int>h[1500];
vector<int>l[1500];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
h[i].push_back(a[i][j]);
l[j].push_back(a[i][j]);
}
}
for(int i=1;i<=n;i++){
sort(h[i].begin(),h[i].end());
h[i].erase(unique(h[i].begin(),h[i].end()),h[i].end());
}
for(int i=1;i<=m;i++){
sort(l[i].begin(),l[i].end());
l[i].erase(unique(l[i].begin(),l[i].end()),l[i].end());
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int A=h[i].size(),aa=lower_bound(h[i].begin(),h[i].end(),a[i][j])-h[i].begin()+1;
int B=l[j].size(),b=lower_bound(l[j].begin(),l[j].end(),a[i][j])-l[j].begin()+1;
cout<<(aa<b?max(B,b+A-aa):max(A,aa+B-b))<<" ";
}
cout<<endl;
}
return 0;
}D - Camp Schedule (KMP 贪心)
题意
有两个 01 串 s 和 t，要求重新排列 s 使得 t 在重新排列后的 s 中出现次数尽量多（位置相交的出现也算）。
思路
一眼KMP 求出T的next数组，然后贪心重叠匹配 关键是可以位置相交
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e6+50;
const int inf=1e9;
typedef unsigned long long ull;
char s[maxn];
char t[maxn];
void kmp_pre(char x[],int m,int next[]){
int i,j;
j=next[0]=-1;
i=0;
while(i<m){
while(-1!=j&&x[i]!=x[j])j=next[j];
next[++i]=++j;
}
}
int mynext[maxn];
int kmp(char x[],int m,char y[],int n){
int i,j;
int ans=0;
kmp_pre(x,m,mynext);
i=j=0;
while(i<n){
while(-1!=j&&y[i]!=y[j])j=mynext[j];
i++;j++;
if(j>=m){
ans++;
j=mynext[j];
}
}
return j;
}
string str;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>s;
cin>>t;
int lens=strlen(s);
int a0=0,a1=0;
for(int i=0;i<lens;i++)if(s[i]=='0')a0++;else a1++;
int lent=strlen(t);
kmp_pre(t,lent,mynext);
int num=mynext[lent];
//int num=kmp(t,lent,t,lent);
string p="";
int n1=0,n0=0;
for(int i=num;i<lent;i++){
p+=t[i];
if(t[i]=='0')n0++;
else n1++;
}
int b1=0,b0=0;
for(int i=0;i<lent;i++){
if(t[i]=='0')b0++;
else b1++;
}
if(a0<b0||a1<b1){
cout<<s<<endl;exit(0);
}
str+=t;
a1-=b1;a0-=b0;
while(a1>=n1&&a0>=n0){
str+=p;
a1-=n1,a0-=n0;
}
while(a1--){
str+="1";
}
while(a0--){
str+="0";
}
cout<<str<<endl;
return 0;
}E. Museums Tour
题意
给你一个国家，国家里面有n个城市 城市之间有单向边，国家一周有d天，每个城市有一个博物馆，会给你一个长度为d的字符串如果某个位置是‘1’代表这天这个城市的博物馆有开放
现在一个人再第1天从第一个城市出发，每天只能去往一个相邻城市，问这个人最多能见到多少个博物馆，假设天数无限
思路
首先我们把每个城市拆成d个城市。然后对于拆完的地图求强连通分量，再这个强连通分量中每个城市都可以互相到达，所以这个强连通分量的（不重复城市）的博物馆的数量就确定了。
然后就是把强连通分量缩点，变成一个新图，然后从第一个城市第一天开始dfs 跑DP这个新图
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=5e6+50;
const int inf=1e8;
typedef unsigned long long ull;
int n,m,d,dfn[maxn],low[maxn],st[maxn],vis[maxn];
int sz[maxn],dp[maxn],bel[maxn],Time,scc,top;
int Laxt[maxn],Next[maxn],To[maxn],cnt;
int Laxt2[maxn],Next2[maxn],To2[maxn],cnt2;
inline void add(int u,int v){
Next[++cnt]=Laxt[u],Laxt[u]=cnt,To[cnt]=v;
}
inline void add1(int u,int v){
Next2[++cnt2]=Laxt2[u],Laxt2[u]=cnt2,To2[cnt2]=v;
}
char s[100005][52];
inline int id(int a,int b){
return (a-1)*d+b+1;
}
void tarjan(int u){
dfn[u]=low[u]=++Time;
st[++top]=u;vis[u]=1;
for(int i=Laxt[u];i;i=Next[i]){
int v=To[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
}
int now;
if(dfn[u]==low[u]){
++scc;
do{
vis[st[top]]=0;
now=st[top--];
bel[now]=scc;
}while(now!=u);
}
}
int dfs(int u){
if(dp[u])return dp[u];
int ans=0;
for(int i=Laxt2[u];i;i=Next2[i]){
int v=To2[i];
ans=max(ans,dfs(v));
}
return dp[u]=ans+sz[u];
}
int main()
{
int u,v;
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
for(int j=0;j<d;j++)
add(id(u,j),id(v,(j+1)%d));
}
for(int i=1;i<=n;i++)scanf("%s",s[i]);
for(int i=1;i<=n*d;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++){
for(int j=0;j<d;j++){
int x=id(i,j);
if(s[i][j]=='1'&&vis[bel[x]]!=i)
vis[bel[x]]=i,sz[bel[x]]++;
for(int k=Laxt[x];k;k=Next[k]){
int v=To[k];
if(bel[x]!=bel[v])
add1(bel[x],bel[v]);
}
}
}
printf("%d\n",dfs(bel[1]));
return 0;
}
F - Cooperative Game (Floyd判环，龟兔赛跑算法)
题意
一个条路 连着一个环，路和环的连接点定义为终点
十个人 每次可以移动一些人向前单项移动（参考链表）
交互题，每次选择一个人的编号让他想前移动
之后系统会告诉你现在哪些点有人，分别是谁
把所有人移动到终点就输出“done”结束
思路
裸的Floyd算法 过程完全一模一样
首先让两个人一个一次移动一步，一个一次移动两步。
然后两人会在一个点相遇。次数假设慢的人经过的距离为\(s\) 那么快的人距离为\(2s\)
\(s=m+i*l+k\) 1式
\(2s=m+j*l+k\) 2式
两式相减
\(s=(j-i)l\) 3式
带入1式
\[ s=m+i*l+k\\(j-i)l=m+i*l+k\\(j-2i)l=m+k\\（j-2i）l-k=m \]
所以当一个点开始从m走到起点时，另一个点也走到了开始的地方
我的想法
假设出发起点到环起点的距离为m，已经确定有环，环的周长为n，（第一次）相遇点距离环的起点的距离是k。那么当两者相遇时，慢指针（t）移动的总距离i = m + a * n + k，快指针（h）的移动距离为2i，2i = m + b * n + k。其中，a和b分别为t和h在第一次相遇时转过的圈数。让两者相减（快减慢），那么有i = (b - a) * n。即i是圈长度的倍数。
将一个指针移到出发起点S，另一个指针仍呆在相遇节点M处两者同时移动，每次移动一步。当第一个指针前进了m，即到达环起点时，另一个指针距离链表起点为i + m。考虑到i为圈长度的倍数，可以理解为指针从链表起点出发，走到环起点，然后绕环转了几圈，所以第二个指针也必然在环的起点。即两者相遇点就是环的起点。#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
int t;
void get(){
fflush(stdout);
scanf("%d",&t);
for(int i=1;i<=t;i++)scanf("%*s");
}
int main()
{
do{
puts("next 0 1"),get();
puts("next 0"),get();
}while(t==3);
do{
puts("next 0 1 2 3 4 5 6 7 8 9"),get();
}while(t==2);
puts("done");
return 0;
}E - Train Car Selection (斜率)
题意
题意：维护一个数组，支持这些操作：
1、在前端塞入k个0。
2、在后端塞入k个0。
3、对于数组中每个数，假设它是数组的第i个，那么令它的值加上b+s(i−1)。
每次操作完后，询问数组中的最小值以及最左边的最小值的位置。
操作个数q≤300000。
思路
首先对于第一个操作之后肯定答案是1和0
对于第二个操作就需要判断，
对于第三个操作肯定不能直接加，那么如果不直接加那我们就可以把b和s存起来等到需要的时候加起来
发现这个最小值只和位置和现在的值有关。
所以我们可以用一个pair存储（位置，当前值） 然后对于操作三就相当于直接给这个加了一个函数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=5e5+50;
const int inf=1e8;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define mp make_pair
ll k,b;
pii p[maxn];
double slope(pii a,pii b){
return 1.0*(a.second-b.second)/(a.first-b.first);
}
ll cal(pii x){
return k*x.first+x.second+b;
}
int main()
{
int n,m,op,x,y,tail;
cin>>n>>m;
p[tail=1]=mp(0,0);
while(m--){
cin>>op;
if(op==1){
cin>>x;tail=1,k=b=0;
n+=x;
}
else if(op==2){
pii now=mp(n,-(n*k+b));
while(tail>1&&-slope(now,p[tail])>=-slope(p[tail],p[tail-1]))tail--;
p[++tail]=now;
cin>>x;
n+=x;
}
else
cin>>x>>y,b+=x,k+=y;
while(tail>1&&cal(p[tail])>=cal(p[tail-1]))tail--;
cout<<p[tail].first+1<<" "<<cal(p[tail])<<endl;
}
return 0;
}