Grakn Forces 2020 A-E

从前往后构造即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
#define ls (o<<1)
#define rs (o<<1|1)
//#define m (l+r)/2
#define pb push_back
const double PI= acos(-1.0);
const int M = 1e5+7;
/*
int head[M],cnt=1;
void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
*/
int a[110][3];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int T;cin>>T;while(T--){int n;cin>>n;for(int j=1;j<=3;j++)for(int i=1;i<=n;i++){cin>>a[i][j];}int lst=-1,st=-1;for(int i=1;i<=n;i++){for(int j=1;j<=3;j++){if(a[i][j]!=lst){if(i!=n || a[i][j]!=st){cout<<a[i][j]<<" ";lst=a[i][j];if(i==1)st=lst;break;}}}}cout<<endl;}return 0;
}

这应该是最难的B题了。。。

这样考虑：每个b数组最多能让k个不同的a变相同。

然后分情况讨论即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
#define ls (o<<1)
#define rs (o<<1|1)
//#define m (l+r)/2
#define pb push_back
const double PI= acos(-1.0);
const int M = 1e5+7;
/*
int head[M],cnt=1;
void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
*/
int a[110];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int T;cin>>T;while(T--){int n,k;cin>>n>>k;int nm=1;for(int i=1;i<=n;i++){cin>>a[i];if(i>1&&a[i]!=a[i-1])nm++;}if(nm>1&&k==1){cout<<-1<<endl;}else if(nm<=k)cout<<1<<endl;else{nm--;int tp = nm/(k-1)+(nm%(k-1) != 0);cout<<max(tp,1)<<endl;}}return 0;
}

简单的实数二分。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
#define ls (o<<1)
#define rs (o<<1|1)
//#define m (l+r)/2
#define pb push_back
const double PI= acos(-1.0);
const int M = 1e5+7;
typedef long double ld;
/*
int head[M],cnt=1;
void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
*/
ld a[M];
const ld eps=1e-7;
ld len;int n;
ld ck(ld t){//时间 ld tp=t,v=1,ans=0;int pos=0;while(pos<=n){ld tn = (a[pos+1]-a[pos])/v;if(tn + eps > tp){ans+=v*tp;break;}ans+=(a[pos+1]-a[pos]);tp-=tn; pos++;v++;}tp=t,v=1,pos=n;
//	cout<<ans<<"  - -  "<<t<<endl;while(pos>=0){ld tn = (a[pos+1]-a[pos])/v;if(tn + eps > tp){ans+=v*tp;break;}ans+=(a[pos+1]-a[pos]);tp-=tn; pos--;v++;}//cout<<" = =  "<<ans<<"  "<<t<<endl;if(ans +eps > len)return true;return false;
}
int main()
{int T;cin>>T;while(T--){scanf("%d%Lf",&n,&len);for(int i=1;i<=n;i++)scanf("%Lf",&a[i]);a[n+1]=len;a[0]=0;ld l=0,r=len,pr=0;while(l  + eps< r) {ld m=(l+r)/2;if(ck(m))r=m,pr=m;else l=m;}printf("%.10Lf\n",pr);}return 0;
}

比较经典的一维排序，然后枚举求结果。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
#define ls (o<<1)
#define rs (o<<1|1)
//#define m (l+r)/2
#define pb push_back
const double PI= acos(-1.0);
const int M = 1e7+7;
/*
int head[M],cnt=1;
void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
*/
int a[M],b[M],c[M],d[M];
struct node{int x,y;
}p[M];
bool cmp(node a,node b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,m;cin>>n>>m;	for(int i=1;i<=n;i++)cin>>a[i]>>b[i];for(int i=1;i<=m;i++)cin>>c[i]>>d[i];int sz=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(c[j]>=a[i]&&d[j]>=b[i]){p[++sz].x=max(0,c[j]-a[i]+1);p[sz].y=max(0,d[j]-b[i]+1);}}sort(p+1,p+1+sz,cmp);int mx=0,ans=1e9;for(int i=sz;i>=0;i--){//	cout<<p[i].x<<" "<<p[i].y<<endl;ans=min(ans,mx+p[i].x);mx=max(mx,p[i].y);}cout<<ans<<endl;return 0;
}

判断是否成环可用并查集判断。

但只能删点花费点权的代价，不好确定删除哪个点。

所以我们可以这样转化:

每个颜色集合i：里的每个点y，建立一条边权为a[i]+b[y]的边连接i，y。

这样每种颜色里的点就成了一个连通块(是一棵树)，若成环，说明一定是彩虹环。则删除边权最小的边。

我们可以按边权排序，从大往小插入，小的边权成环时直接删去补插入即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define re register
#define ls (o<<1)
#define rs (o<<1|1)
//#define m (l+r)/2
#define pb push_back
const double PI= acos(-1.0);
const int M = 4e5+7;
/*
int head[M],cnt=1;
void init(int n){cnt=1;for(int i=0;i<=n;i++)head[i]=0;}
struct EDGE{int to,nxt,w;}ee[M*2];
void add(int x,int y,int w){ee[++cnt].nxt=head[x],ee[cnt].w=w,ee[cnt].to=y,head[x]=cnt;}
*/
class node{//把点权转化为边权 public : int x,y,w;
}p[M];
int a[M],b[M];
int fa[M];
int get(int x){if(x==fa[x])return fa[x];return fa[x]=get(fa[x]);
}
bool cmp(node a,node b){return a.w<b.w;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);int m,n,sz=0;cin>>m>>n;for(int i=1;i<=n+m;i++)fa[i]=i;for(int i=1;i<=m;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];for(int i=1;i<=m;i++){int l;cin>>l;for(int j=1;j<=l;j++){int y;cin>>y;p[++sz]=node{i,y+m,a[i]+b[y]};//把点权转化为边权，用并查集做 }}sort(p+1,p+1+sz,cmp);ll ans=0;for(int i=sz;i>=1;i--){int x=p[i].x,y=p[i].y;int gx=get(x),gy=get(y);if(gx==gy){//已有路径，若仍然连接这条边，则会构成彩虹环 ans+=p[i].w;}else{fa[gx]=gy;}}cout<<ans<<endl;return 0;
}