2018年icpc徐州站 [Cloned]
A-Rikka with Minimum Spanning Trees
题意：
给了一段代码用于生成数据，并且讲解了了如何进行最小生成树计数的过程
solution：
我们队是用最小生成树计数过的，然鹅大佬说这个数据范围这么大，肯定只能生成一个最小生成树，直接用Kruscal过了
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
unsigned long long k1,k2;
unsigned long long xorShift128Plus(){
unsigned long long k3=k1,k4=k2;
k1=k4;
k3^=k3<<23;
k2=k3^k4^(k3>>17)^(k4>>26);
return k2+k4;
}
int n,m;
const int mod=1e9+7;
struct node
{
int u,v;
unsigned long long w;
bool operator<(const node x)const
{
return w<x.w;
}
}p[100001];
void gen(){
scanf("%d%d%llu%llu",&n,&m,&k1,&k2);
for(int i=1;i<=m;i++){
p[i].u=xorShift128Plus()%n+1;
p[i].v=xorShift128Plus()%n+1;
p[i].w=xorShift128Plus();
}
}
int t;
int f[100001];
int Find(int x)
{
return f[x]==x?x:f[x]=Find(f[x]);
}
void Union(int x,int y)
{
int u=Find(x),v=Find(y);
f[u]=v;
}
unsigned long long kruscal()
{
for(int i=1;i<=n;i++)f[i]=i;
unsigned long long res=0;
sort(p+1,p+1+m);
for(int i=1;i<=m;i++)
{
if(Find(p[i].u)!=Find(p [i].v))
{
res=(res+p[i].w%mod)%mod;
Union(p[i].u,p[i].v);
}
}
return res;
}
int main()
{
scanf("%d",&t);
while(t--)
{
gen();
bool flag=true;
unsigned long long res=kruscal();
for(int i=2;i<=n;i++)
if(Find(1)!=Find(i))
res=0;
cout<<res<<endl;
}
}
B-Rikka with Line Graphs
C-Rikka with Consistency
D-Rikka with Subsequences
E-Rikka with Data Structures
F-Rikka with Nice Counting Striking Back
G-Rikka with Intersections of Paths
H-Rikka with A Long Colour Palette
题意：
t组样例，给了n个区间，k中颜色，问有染色种数为k的长度有多长（不用连续的区间），区间重叠相当于染色重叠（如果染色数少于k，颜色数会有所增加）
solution：
把所给的区间分为左端点和右端点，左端点为1，右端点为-1，然后根据端点所在位置进行从小到大排序，贪心的选点即可
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int,int>P;
typedef long long ll;
int t,n,k;
int res[600005];
struct node
{
int pos,id,type;
bool operator <(const node x)const
{
if(pos!=x.pos)
return pos<x.pos;
return type<x.type;
}
}p[600005];
int tem[600005],l,r,maxn;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
int cnt=0;
res[n]=0;
for(int i=0;i<n;i++)
{
res[i]=0;
scanf("%d",&p[cnt].pos);
p[cnt].id=i;p[cnt].type=1;
cnt++;
scanf("%d",&p[cnt].pos);
p[cnt].id=i;p[cnt].type=-1;
cnt++;
}
sort(p,p+cnt);
ll ans=0;
l=0,r=0;
queue<int> q;
for(int i=1;i<=k;i++)q.push(i);
for(int i=0;i<cnt;i++)
{
if(q.empty()){
ans+=p[i].pos-p[i-1].pos;}
if(p[i].type==1)
{
if(!q.empty())
{
res[p[i].id]=q.front();q.pop();
}
else
tem[r++]=p[i].id;
}
else if(p[i].type==-1)
{
if(res[p[i].id]>0)
q.push(res[p[i].id]);
else
res[p[i].id]=1;
}
while(l<r&&!q.empty())
{
int x=tem[l++];
if(res[x]!=0)continue;
res[x]=q.front();
q.pop();
}
}
printf("%lld\n",ans);
printf("%d",res[0]);
for(int i=1;i<n;i++)
printf(" %d",res[i]);
printf("\n");
}
}
