Pluto_Rabbit's Blog

蒟蒻妹纸一枚,轻拍

【Training Contest】2016.04.22 CQOI2016 DAY1

Jacinth posted @ 2016年4月22日 22:59 in ZHOJ with tags Contest 2016 bzoj , 501 阅读

为什么都说这个水呢

T2标算KD树什么鬼都不知道的啊

一脸懵逼

T1. 不同的最小割

Description
学过图论的同学都知道最小割的概念:对于一个图,某个对图中结点的划分将图中所有结点分成两个部分,如果结点s,t不在同一个部分中,则称这个划分是关于s,t的割。对于带权图来说,将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量,而s,t的最小割指的是在关于s,t的割中容量最小的割。而对冲刺NOI竞赛的选手而言,求带权图中两点的最小割已经不是什么难事了。我们可以把视野放宽,考虑有N个点的无向连通图中所有点对的最小割的容量,共能得到N(N−1)2个数值。
这些数值中互不相同的有多少个呢?这似乎是个有趣的问题。
Input 输入文件第一行包含两个数N,M,表示点数和边数。接下来M行,每行三个数u,v,w,表示点u和点v(从1开始标号)之间有条边权值是w。
Output 输出文件第一行为一个整数,表示个数。
Sample Input
4 4
1 2 3
1 3 6
2 4 5
3 4 4
Sample Output
3
Data Range
对于50%的数据,N≤200,M≤2000
对于100%的数据,1≤N≤850,1≤M≤8500,1≤w≤100000

传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=4519

网络流+分治

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#define NN 900
#define MM 9000
using namespace std;
set<int> se;
int S,T,n,m,a[NN],head[NN],tot=1,h[NN],tmp[NN],flag[NN];
struct E
{
	int ne,v,w;
}e[MM<<1];
#define INF 0x3f3f3f3f
void Build(int xx,int yy,int zz)
{
	e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;
}
queue<int>que;
bool BFS()
{
	while (!que.empty()) que.pop();
	memset(h,-1,sizeof(h));
	que.push(S), h[S]=0;
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
			if (e[i].w && h[e[i].v]==-1)
				h[e[i].v]=h[now]+1, que.push(e[i].v);
	}
	return h[T]!=-1;
}
int DFS(int xx,int ff)
{
	if (xx==T) return ff;
	int vis=0;
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].w && h[e[i].v]==h[xx]+1)
	{
		int tmp=DFS(e[i].v,min(e[i].w,ff-vis));
		e[i].w-=tmp; e[i^1].w+=tmp; vis+=tmp;
		if (vis==ff) return ff;
	}
	if (!vis) h[xx]=-1;
	return vis;
}
void DFSS(int xx)
{
	flag[xx]=1;
	for (int i=head[xx];i;i=e[i].ne)
		if (!flag[e[i].v] && e[i].w) DFSS(e[i].v);
}
void Clear()
{
	for (int i=2;i<=tot;i+=2) e[i].w=e[i^1].w=((e[i].w+e[i^1].w)>>1);
}
void Solve(int l,int r)
{
	if (l==r) return;
	Clear();
	S=a[l], T=a[r];
	int res=0;
	while (BFS())	res+=DFS(S,INF);
	se.insert(res);
	memset(flag,0,sizeof(flag));
	DFSS(S);
	int ll=l,rr=r;
	for (int i=l;i<=r;++i)
		if (flag[a[i]]) tmp[ll++]=a[i]; else tmp[rr--]=a[i];
	for (int i=l;i<=r;++i) a[i]=tmp[i];
	Solve(l,ll-1), Solve(rr+1,r);
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z); Build(x,y,z), Build(y,x,z);
	}
	for (int i=1;i<=n;++i) a[i]=i;
	Solve(1,n);
	printf("%d",se.size());
	return 0;
}

T2. K远点对

已知平面内 N 个点的坐标,求欧氏距离下的第 K 远点对。

传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=4520

听说KD树裸题

宝宝不会

T3. 手机号码

Description
人们选择手机号码时都希望号码好记、吉利。比如号码中含有几位相邻的相同数字、不含谐音不吉利的数字等。手机运营商在发行新号码时也会考虑这些因素,从号段中选取含有某些特征的号码单独出售。为了便于前期规划,运营商希望开发一个工具来自动统计号段中满足特征的号码数量。
工具需要检测的号码特征有两个:号码中要出现至少3个相邻的相同数字,号码中不能同时出现8和4。号码必须同时包含两个特征才满足条件。满足条件的号码例如:13000988721、23333333333、14444101000。而不满足条件的号码例如:1015400080、10010012022。
手机号码一定是11位数,前不含前导的0。工具接收两个数L和R,自动统计出[L,R]区间内所有满足条件的号码数量。L和R也是11位的手机号码。
Input 输入文件内容只有一行,为空格分隔的2个正整数L,R。
Output 输出文件内容只有一行,为1个整数,表示满足条件的手机号数量。
Sample Input 12121284000 12121285550
Sample Output 5
Hint 满足条件的号码: 12121285000、 12121285111、 12121285222、 12121285333、 12121285550
Data Range 10^10 < =  L < =  R < 10^11

传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=4521

数位DP, 还是比较好想的吧QAQ

#include <iostream> 
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define LL long long
using namespace std;
LL l,r,ans,f[15][11][5][5][3];
int a[20],tmp[20];
//f[][][][][] len, µ±Ç°ÊýÖµ, Öظ´, 4/8, ==a[len]
int Xun(int xx,int yy)
{
	if (xx+yy>=3) return 3;
	else if (xx) return yy+1;
	else return 1;
}
int P(int xx,int yy)
{
	if (xx==4) return yy|1;
	else if (xx==8) return yy|2;
	else return yy;
}
LL solve(LL xx)
{
	int len=0;
	memset(a,0,sizeof(a)); memset(tmp,0,sizeof(tmp));
	memset(f,0,sizeof(f));
	while (xx) { tmp[++len]=xx%10; xx=xx/10;}
	for (int i=1;i<=len;++i) a[i]=tmp[len-i+1];
	for (int i=1;i<=a[1];++i) f[1][i][1][P(i,0)][i==a[1]]++;
	for (int i=2;i<=len;++i)
	{
		for (int j=0;j<=9;++j)
			for (int k=1;k<=3;++k)
				for (int w=0;w<3;++w)
				{
					if (f[i-1][j][k][w][0])
						for (int t=0;t<=9;++t)
							f[i][t][Xun(t==j,k)][P(t,w)][0]+=f[i-1][j][k][w][0];
					if (f[i-1][j][k][w][1])
						for (int t=0;t<=a[i];++t)
							f[i][t][Xun(t==j,k)][P(t,w)][t==a[i]]+=f[i-1][j][k][w][1];
				}
	}
	ans=0;
	for (int i=0;i<=9;++i)
		for (int j=0;j<3;++j) ans+=f[len][i][3][j][0]+f[len][i][3][j][1];
	return ans;
}
int main()
{
	scanf("%lld%lld",&l,&r);
	if (l==10000000000ll) printf("%lld",solve(r));
		else printf("%lld",solve(r)-solve(l-1));
	return 0;
}
Avatar_small
BSNL Fiber 说:
2022年8月08日 18:30

BSNL is installing Bharat Net a country-wide fiber optic cable for internet connectivity in many of the panchayats, and on the other hand, ISP brought the same fibernet technology to your doorstep directly and through TIPs. BSNL Fiber Telecom Infrastructure Providers (TIPs) with new Fiber plans covering many isolated pockets in all BSNL circles of the country for 50Mbps to 300 Mbps internet speed on providing with BSNL FTTH Plans along with FREE ONT as per the possibility.BSNL is installing Bharat Net a country-wide fiber optic cable for internet connectivity in many of the panchayats, and on the other hand, ISP brought the same fibernet technology to your doorstep directly and through TIPs.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter