coci2015-2016填坑

cwy posted @ 2016年9月21日 21:35 with tags COCI , 128 阅读

contest1_RELATIVNOST

暴力线段树。。

 

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
__attribute__((optimize("-O3"))) inline void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
__attribute__((optimize("-O3"))) inline void putint(int n)
{
     char a[10];
     int size=0;
     if (n==0)
        putchar('0');
     while (n)
     {
           a[size++]=n%10+48;
           n/=10;
     }
     for (int i=size-1;i>=0;i--)
         putchar(a[i]);
     putchar('\n');
}
const int MO=10007;
int n,c,a[100010],b[100010],seg[400010][22],p,q,ap,bp,ans;
__attribute__((optimize("-O3"))) inline void pushup(int rt)
{
	FOR(i,0,20) seg[rt][i]=0;
	FOR(i,0,19)
		FOR(j,0,i)
			(seg[rt][i]+=seg[rt<<1][j]*seg[rt<<1|1][i-j])%=MO;
	FOR(i,0,20)
		FOR(j,20-i,20)
			(seg[rt][20]+=seg[rt<<1][i]*seg[rt<<1|1][j])%=MO;
}
__attribute__((optimize("-O3"))) inline void build(int l,int r,int rt)
{
	if (l==r)
	{
		seg[rt][1]=a[l]%MO;
		seg[rt][0]=b[l]%MO;
		return;
	}
	int m=(l+r)>>1;
	build(l,m,rt<<1);
	build(m+1,r,rt<<1|1);
	pushup(rt);
}
__attribute__((optimize("-O3"))) inline void updata(int l,int r,int rt,int x,int y,int z)
{
	if (l==r)
	{
		seg[rt][1]=y%MO;
		seg[rt][0]=z%MO;
		return;
	}
	int m=(l+r)>>1;
	if (x<=m) updata(l,m,rt<<1,x,y,z); else updata(m+1,r,rt<<1|1,x,y,z);
	pushup(rt);
}
__attribute__((optimize("-O3"))) int main()
{
	scanf("%d%d",&n,&c);
	FOR(i,1,n) getint(a[i]);
	FOR(i,1,n) getint(b[i]);
	build(1,n,1);
	scanf("%d",&q);
	while (q--)
	{
		getint(p),getint(ap),getint(bp);
		updata(1,n,1,p,ap,bp);
		ans=0;
		FOR(i,c,20) (ans+=seg[1][i])%=MO;
		putint(ans);
	}
	return 0;
}

 

contest1_UZASTOPNI

树型背包DP

%%%zhan8855

#include <cstdio>
#include <algorithm>

using namespace std;

int c[12000][120],d[12000][120],f[120][120][120],h[120][120][120],g[12000],l[12000],r[12000];
int edge[12000],next[12000],first[12000];
bool b[12000];
int i,j,m,n,s,sum_edge;

struct edges
{
	int x,y;
	inline bool operator < (const edges t) const
	{
		return g[y]<g[t.y];
	}
};

edges e[12000];

inline void addedge(int x,int y)
{
	sum_edge++,edge[sum_edge]=y,next[sum_edge]=first[x],first[x]=sum_edge;
	return;
}

inline void dfs1(int x)
{
	if (d[x][g[x]])
	{
		b[x]=true;
		return;
	}
	for (int i=first[x];i!=0;i=next[i])
	{
		for (int j=1;j<=m;j++)
			d[edge[i]][j]=d[x][j];
		d[edge[i]][g[x]]=1;
		dfs1(edge[i]);
		if (! b[edge[i]])
			for (int j=l[edge[i]];j<=r[edge[i]];j++)
				c[x][j]=1;
	}
	c[x][g[x]]=1;
	for (int i=0;i<g[x];i++)
		if (! c[x][i])
			l[x]=i+1;
	for (int i=m+1;i>g[x];i--)
		if (! c[x][i])
			r[x]=i-1;
	for (int i=1;i<l[x];i++)
		c[x][i]=0;
	for (int i=r[x]+1;i<=m;i++)
		c[x][i]=0;
	return;
}

inline void dfs2(int x,int y)
{
	if (l[y]==r[y])
	{
		f[x][g[y]][g[y]]=1;
		return;
	}
	for (int i=l[y];i<=r[y];i++)
		for (int j=i;j<=r[y];j++)
			f[x][i][j]=0,h[x][i][j]=0;
	for (int o=first[y];o!=0;o=next[o])
	{
		if (b[edge[o]])
			continue;
		l[edge[o]]=max(l[edge[o]],l[y]);
		r[edge[o]]=min(r[edge[o]],r[y]);
		if (l[edge[o]]>r[edge[o]])
			continue;
		dfs2(x+1,edge[o]);
		for (int i=l[y];i<=r[y];i++)
			for (int j=i;j<=r[y];j++)
				h[x][i][j]=f[x][i][j];
		for (int i=l[edge[o]];i<=r[edge[o]];i++)
		{
			if (i<g[y])
			{
				for (int j=l[edge[o]];j<=i;j++)
					if (f[x+1][j][i])
						for (int k=i+1;k<g[y];k++)
							f[x][j][k]=f[x][j][k]+f[x+1][j][i]*h[x][i+1][k];
				for (int j=i;j<g[y];j++)
					if (f[x+1][i][j])
						for (int k=l[y];k<i;k++)
							f[x][k][j]=f[x][k][j]+f[x+1][i][j]*h[x][k][i-1];
			}
			if (i>g[y])
			{
				for (int j=i;j<=r[edge[o]];j++)
					if (f[x+1][i][j])
						for (int k=g[y]+1;k<i;k++)
							f[x][k][j]=f[x][k][j]+f[x+1][i][j]*h[x][k][i-1];
				for (int j=g[y]+1;j<=i;j++)
					if (f[x+1][j][i])
						for (int k=i+1;k<=r[y];k++)
							f[x][j][k]=f[x][j][k]+f[x+1][j][i]*h[x][i+1][k];
			}
		}
		for (int i=l[edge[o]];i<=r[edge[o]];i++)
			for (int j=i;j<=r[edge[o]];j++)
				f[x][i][j]=f[x][i][j]+f[x+1][i][j];
	}
	for (int i=l[y];i<=r[y];i++)
		for (int j=i;j<=r[y];j++)
			h[x][i][j]=f[x][i][j],f[x][i][j]=0;
	f[x][g[y]][g[y]]=1/*++*/;
	for (int i=l[y];i<g[y];i++)
		if (h[x][i][g[y]-1])
			f[x][i][g[y]]=1/*h[i][g[y]-1]*/;
	for (int i=g[y]+1;i<=r[y];i++)
		if (h[x][g[y]+1][i])
			f[x][g[y]][i]=1/*h[g[y]+1][i]*/;
	for (int i=l[y];i<g[y];i++)
		if (h[x][i][g[y]-1])
			for (int j=g[y]+1;j<=r[y];j++)
				if (h[x][g[y]+1][j])
					f[x][i][j]=1/*f[x][i][j]+h[i][g[y]-1]*h[g[y]+1][j]*/;
	return;
}

int main()
{
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d",&g[i]),m=max(g[i],m);
	for (i=1;i<n;i++)
		scanf("%d%d",&e[i].x,&e[i].y);
	sort(e+1,e+n);
	for (i=1;i<n;i++)
		addedge(e[i].x,e[i].y);
	dfs1(1);
	dfs2(1,1);
	for (i=l[1];i<=g[1];i++)
		for (j=g[1];j<=r[1];j++)
			s=s+f[1][i][j];
	printf("%d",s);
	return 0;
}

 

contest2_vudu

二分以后树状数组check一下。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
void getint(LL &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int n,p,bit[1000010];
LL ans,a[1000010],b[1000010];
inline int lowbit(int x){
	return x&-x;
}
int sum(int x){
	int s=0;
	for (;x;x-=lowbit(x)) s+=bit[x];
	return s;
}
void add(int x){
	for (;x<=n+1;x+=lowbit(x)) bit[x]++;
}
int main(){
	scanf("%d",&n);
	FOR(i,1,n) getint(a[i]);
	scanf("%d",&p);
	FOR(i,1,n) a[i]-=p;
	FOR(i,1,n) a[i]+=a[i-1];
	FOR(i,1,n) b[i]=a[i];
	b[n+1]=0;
	sort(b+1,b+n+2);
	FOR(i,0,n) a[i]=lower_bound(b+1,b+n+2,a[i])-b;
	add(a[0]);
	FOR(i,1,n){
		ans+=sum(a[i]);
		add(a[i]);
	}
	cout<<ans<<endl;
	return 0;
}

 

contest4_Galaksija

离线倒着处理,用并查集,启发式合并。

我就说怎么这么难写呢,,原来标程是map套vector。。

 

contest4_ENDOR

可以把方向改变看成蚂蚁改变然后再处理。

之后大概就是每只蚂蚁与一些蚂蚁相遇问题,可以DP了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
void getint(LL &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
vector<int> r;
int n,k,l,s,d[100010],b[100010];
char c[100010];
double ans[44],dp[44],dp_[44];
int main(){
	scanf("%d%d%d",&n,&k,&l);
	FOR(i,1,n){
		scanf("%d%d %c",&d[i],&b[i],&c[i]);
		if (c[i]=='D'){
			ans[b[i]]+=l-d[i];
			(s+=b[i])%=k;
			if (!r.empty()){
				FOR(j,0,k-1) dp_[(j+b[i])%k]=dp[j];
				dp_[b[i]]+=0.5*(d[i]-r.back());
				FOR(j,0,k-1) dp[j]=dp_[j];
			}
			r.pb(d[i]);
		}
		else{
			if (r.empty()){
				ans[b[i]]+=d[i];
				continue;
			}
			ans[b[i]]+=0.5*(d[i]-r.back());
			FOR(j,0,k-1) ans[(b[i]+j)%k]+=dp[j];
			ans[(b[i]+s)%k]+=0.5*(d[i]+r[0]);
		}
	}
	FOR(i,0,k-1) printf("%.1f\n",ans[i]);
	return 0;
}

contest3_nekameleoni

刚开始不会,标程是比较奇怪的线段树。

对于线段树的每个节点,要维护前缀和后缀中的数字种类不同的。

比如11122223

前缀只有111,111222,1112223有用

后缀只有3,22223,11122223有用

然后合并区间的时候求区间内的

ans时候,左右两个指针都单调。

contest6_KRUMPIRKO

我们假定第一家店选其中的若干堆,总价格c1,总土豆数w1。同理第二家店价格c2,数量w2,答案就是c1*c2/w1/w2,也就是c1*(c-c1)/(w1*(w-w1))。如果w1确定的话,我们只需c1尽可能小。那对于每个w1都求出最小的c1。F(n,w,l)表示前n包中取l包,土豆数为w的最小价格c1,最后统计最小值。时间复杂度是O(wn^2)。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int INF=1e9;
int n,l,sa,sc,a[110],c[110],dp[510][110];
double ans;
int main(){
	scanf("%d%d",&n,&l);
	FOR(i,1,n) getint(a[i]),sa+=a[i];
	FOR(i,1,n) getint(c[i]),sc+=c[i];
	FOR(i,0,sa) FOR(j,0,l) dp[i][j]=INF;
	dp[0][0]=0;
	FOR(i,1,n)
		FORD(j,sa,a[i])
			FOR(k,1,l)
				dp[j][k]=min(dp[j][k],dp[j-a[i]][k-1]+c[i]);
	ans=1e18;
	FOR(w,0,sa)
		if (dp[w][l]<INF) ans=min(ans,(double)dp[w][l]/w*(sc-dp[w][l])/(sa-w));
	l=n-l;
	FOR(i,0,sa) FOR(j,0,l) dp[i][j]=INF;
	dp[0][0]=0;
	FOR(i,1,n)
		FORD(j,sa,a[i])
			FOR(k,1,l)
				dp[j][k]=min(dp[j][k],dp[j-a[i]][k-1]+c[i]);
	FOR(w,0,sa)
		if (dp[w][l]<INF) ans=min(ans,(double)dp[w][l]/w*(sc-dp[w][l])/(sa-w));
	printf("%.3f\n",ans);
	return 0;
}

contest7_Prosti

令f(i)为{i,i+1…i+k-1}集合中happy数的个数,不难发现|f(i)-f(i+1)|<=1

若有f(a)<=L<=f(b),则必存在x∈[a,b]或者[b,a],f(x)=L。

预处理f(1),二分答案mid,计算f(mid),若f(mid)=L则输出。

若f(mid)<=L<=f(1)则找左边,否则找右边。

时间复杂度O(Qlogv)

 

Avatar_small
spactim 说:
2017年2月13日 14:00

为蛤泥喜欢开O3 QAQ(其实这只是用来测测wordpress的力量的QAQ)


登录 *


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