Reku
0%

2013 Multi-University Training Contest 1

Posted on Edited on In Views: Valine:

4600 Harvest Moon 待补 4601 Letter Tree 待补

4602 Partition OEIS一波即可 交的时候错了两次，是因为没有判断\(N \le K\)的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const LL mod=1e9+7;
LL kpow(LL t,int x)
{
	if(x==0) return 1;
	LL o=kpow(t,x/2);
	o*=o;
	o%=mod;
	if(x&1) o*=t;
	o%=mod;
	return o;
}
LL ff(LL x)
{
	if(x==0) return 1;
	LL ans=x+2;
	ans*=kpow(2,x-1);
	ans%=mod;
	return ans;
}
void work()
{
	LL n,k;
	scanf("%lld%lld",&n,&k);
	n-=k;
	if(n==0)
	{
		printf("1\n");
		return;
	}
	if(n<0)
	{
		printf("0\n");
		return;
	}
	LL ans=ff(n-1)+kpow(2,n-1);
	ans%=mod;
	printf("%lld\n",ans);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}

4603 Color the Tree 待补

4604 Deque 可以看出是某个数字开头的最长不上升子序列和最长不下降子序列拼在一起形成的。 要注意判断两个序列重合的部分，要把重合的部分删去。 错了好多次，都是二分条件的问题...这个二分好难写啊...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n;
int a[100010];
vector<int> x;
vector<int> y;
int ans;
void work()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	x.clear(); y.clear();
	x.pb(a[n]); y.pb(-a[n]);
	ans=1;
	for(int i=n-1;i>=1;i--)
	{
		int l,r;
		l=0; r=x.size()-1;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(x[mid]>=a[i]) r=mid;
			else l=mid+1;
		}
		int zz=l;
		l=0; r=x.size()-1;
		while(l<r)
		{
			int mid=(l+r)/2+1;
			if(x[mid]<=a[i]) l=mid;
			else r=mid-1;
		}
		int yy=r; if(x[yy]<=a[i]) yy++;
		if(yy==x.size()) x.pb(a[i]);
		else x[yy]=a[i];
		int len1=yy+1;
		int sa=yy-zz+1;
		l=0; r=y.size()-1;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(y[mid]>=-a[i]) r=mid;
			else l=mid+1;
		}
		zz=l;
		l=0; r=y.size()-1;
		while(l<r)
		{
			int mid=(l+r)/2+1;
			if(y[mid]<=-a[i]) l=mid;
			else r=mid-1;
		}
		yy=r; if(y[yy]<=-a[i]) yy++;
		if(yy==y.size()) y.pb(-a[i]);
		else y[yy]=-a[i];
		int len2=yy+1;
		sa=min(sa,yy-zz+1);
		ans=max(ans,len1+len2-sa);
	}
	printf("%d\n",ans);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}

4605 Magic Ball Game 把所有的询问离线到固定的点上，然后用最简单的可持久化方法，在树上爬，然后用树状数组维护向左的边对应的值、向右的边对应的值，如果这个点上有询问，那就查询一下，计算出相对应的概率就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
class BITree{
public:
    static const int SIZE = 300010, BIAS = 5;
    long long u[SIZE];
    void clear(){
        memset(u,0,sizeof(u));
    }
    void modify(int x, long long v){
        for(x+=BIAS;x<SIZE;x+=x&-x) u[x]+=v;
    }
    long long getsum(int x){
        long long s=0;
        for(x+=BIAS;x;x-=x&-x) s+=u[x];
        return s;
    }
} trl,trr;  
int n,m;
int e[100010][2];
int w[100010];
int Q;
vector<int> q[100010];
vector<int> id[100010];
int ans1[100010];
int ans2[100010];
vector<int> t;
map<int,int> ha;
void dfs(int x,int fa,int wi)
{
	for(int i=0;i<q[x].size();i++)
	{
		int p=ha[q[x][i]];
		int u=id[x][i];
		int bj=trl.getsum(p)-trl.getsum(p-1)+trr.getsum(p)-trr.getsum(p-1);
		if(bj!=0) ans1[u]=0,ans2[u]=-1;
		else
		{
			ans2[u]+=trl.getsum(p)*3;
			ans2[u]+=(trl.getsum(200001)-trl.getsum(p));
			ans2[u]+=trr.getsum(p)*3;
			ans2[u]+=(trr.getsum(200001)-trr.getsum(p));
			ans1[u]+=trr.getsum(p);
		}
	}
	if(e[x][0]!=0)
	{
		trl.modify(ha[w[x]],1);
		dfs(e[x][0],x,0);
		trr.modify(ha[w[x]],1);
		dfs(e[x][1],x,1);
	}
	if(fa!=0)
	{
		if(wi==0) trl.modify(ha[w[fa]],-1);
		if(wi==1) trr.modify(ha[w[fa]],-1);
	}
	return;
}
void work()
{
	ha.clear();
	t.clear();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
		t.pb(w[i]); e[i][0]=e[i][1]=0;
		q[i].clear();
		id[i].clear();
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int u,a,b;
		scanf("%d%d%d",&u,&a,&b);
		e[u][0]=a; e[u][1]=b;
	}
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		ans1[i]=0;
		ans2[i]=0;
		int v,x;
		scanf("%d%d",&v,&x);
		q[v].pb(x);
		t.pb(x);
		id[v].pb(i);
	}
	sort(t.begin(),t.end());
	int num=0;
	for(auto &i:t)
	{
		num++;
		ha[i]=num;
	}
	trl.clear();
	trr.clear();
	dfs(1,0,-1);
	for(int i=1;i<=Q;i++)
	{
		if(ans2[i]==-1) printf("%d\n",ans1[i]);
		else printf("%d %d\n",ans1[i],ans2[i]);
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}

4606 Occupy Cities 几何题...不想做...

4607 Park Visit 求出树的直径，然后如果要访问的点的个数\(\le\)直径上的点个数的话，那对应的边走一次就行。如果要访问的点的个数\(\ge\)直径上的点的个数，那多出的点每个点要走两条边才能走到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define N 100010
#define pb push_back
using namespace std;
vector<int> e[N];
int d[N];
int n,m;
void ff(int x,int fa)
{
	d[x]=d[fa]+1;
	for(auto &i:e[x])
	{
		if(i!=fa) ff(i,x);
	}
}
void work()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) e[i].clear(),d[i]=0;
	int a,b;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&a,&b);
		e[a].pb(b);
		e[b].pb(a);
	}
	ff(1,0);
	int s=0;
	for(int i=1;i<=n;i++) if(d[i]>d[s]) s=i;
	for(int i=1;i<=n;i++) d[i]=0;
	ff(s,0);
	for(int i=1;i<=n;i++) if(d[i]>d[s]) s=i;
	int ans=d[s];
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&a);
		if(a<=ans) printf("%d\n",a-1);
		else printf("%d\n",ans-1+(a-ans)*2);
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}

4608 I-number 简单题，暴力爬一爬就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
char c[100010];
void work()
{
	scanf("%s",c+1);
	int n=strlen(c+1);
	c[0]='0';
	int u=1;
	while(u%10!=0)
	{
		u=0;
		c[n]++;
		int p=n;
		while(c[p]>'9')
		{
			c[p]='0';
			p--;
			c[p]++;
		}
		for(int i=0;i<=n;i++)
		{
			u+=c[i]-'0';
		}
	}
	if(c[0]=='0') printf("%s\n",c+1);
	else printf("%s\n",c);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}

4609 3-idiots 通过快速傅里叶变换求出所有可能的两条边构成的和的情况，然后排列组合枚举就好了 错误两次 第一次：数组开小了 第二次：有一个地方类型转换写错了，直接套的模板，模板是int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
#include<complex>
#define N 540000
#define pi acos(-1)
using namespace std;
typedef complex<double> E;
typedef long long LL;
int n,m,L;
LL R[N],c[N],sum[N];
E a[N],b[N];
int p[N];
int u[N];
void fft(E *a,int f)
{
    for(int i=0;i<n;i++)
    {
        if(i<R[i]) swap(a[i],a[R[i]]);
    }
    for(int i=1;i<n;i<<=1)
    {
        E wn(cos(pi/i),f*sin(pi/i));
        for(int j=0;j<n;j+=(i<<1))
        {
            E w(1,0);
            for(int k=0;k<i;k++,w*=wn)
            {
                E x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y;
                a[j+k+i]=x-y;
            }
        }
    }
    if(f==-1) for(int i=0;i<n;i++) a[i]/=n;
}
void work()
{
	int q;
	scanf("%d",&q);
	q--;
	memset(c,0,sizeof(c));
	memset(p,0,sizeof(p));
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(R,0,sizeof(R));
	n=0;
	for(int i=0;i<=q;i++) {scanf("%d",&u[i]);p[u[i]]++;n=max(n,u[i]);}
        for(int i=0;i<=n;i++) {a[i]=p[i];b[i]=p[i];}
	m=2*n;
	L=0;
	for(n=1;n<=m;n<<=1) L++;
	for(int i=0;i<n;i++)
	{
		R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	}
	fft(a,1);
	fft(b,1);
	for(int i=0;i<=n;i++)
	{
		a[i]*=b[i];
	}
	fft(a,-1);
	 for(int i=0;i<=m;i++)
	{
		c[i]=(long long)(a[i].real()+0.1);
	}
	sort(u,u+q+1);
	for(int i=0;i<=q;i++)
	{
		c[u[i]+u[i]]--;
	}
	for(int i=0;i<=m;i++) c[i]/=2;
	long long res=0;
	long long fz=(long long)(q+1)*q*(q-1)/6;
	sum[0]=c[0];
	for(int i=1;i<=m;i++)
	{
		sum[i]=sum[i-1]+c[i];
	}
	for(int i=0;i<=q;i++)
	{
		res+=sum[m]-sum[u[i]];
		res-=(long long)(q-i)*i;
		res-=q;
		res-=(long long)(q-i)*(q-i-1)/2;
	}
	double ans=res*1.0/fz;
	printf("%.7lf\n",ans);
	return;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--) work();
}

4610 Cards 待补