test20190611

Posted on | Views:

$noip$ 模拟题?

$exam$

  • 贪心.
  • 显然是每 $k$ 题安排错一次能使得分最小.若能通过安排使得没有 $k$ 个连续正确,那么答案就是 $m$ .
  • 否则,一定会出现连续对 $k$ 次,我们尽量把它们安排在前面,错的题安排在后面.这样后面贡献就是做对的题目数,前面的贡献是连续做对 $x$ 道题目得分.这个得分单独算一下就可以了.
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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read()
{
	int x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{if(ch=='-') k=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')
		{x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return k*x;
}
const int P=1e9+9;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
int n,m,k;
int calc(int x)
{
	int t=x/k;
	int tmp=fpow(2,t+1);
	tmp=add(tmp,P-2-t);
	tmp=mul(tmp,k);
	return add(tmp,x);
}
int main()//use dp to check
{
	freopen("exam.in","r",stdin);
	freopen("exam.out","w",stdout);
	n=read(),m=read(),k=read();
	m=n-m;
	int tot=n/k;
	int ans=0;
	if(tot<=m)
	{
		ans=n-m;
		cout<<ans<<endl;
	}
	else
	{
		int x=n-m*k;
		ans=calc(x);
		ans=add(ans,mul(m,k-1));
		cout<<add(ans%P,P)<<endl;
	}
	return 0;
}

$genes$

  • 线段树.

  • 其实只有 $n$ 种情况,每次将第一个元素放到最后,并检验当前是否合法,做 $n$ 次即可.

  • 用线段树来维护每个元素当前对应的前缀和就好了.
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
114
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read()
{
	int x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		{if(ch=='-') k=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')
		{x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return k*x;
}
const int MAXN=1e6+10;
int n,a[MAXN],sum[MAXN],tot;
struct Segtree
{
	int val[MAXN<<2];
	int tag[MAXN<<2];
#define root val[o]
#define lson val[o<<1]
#define rson val[o<<1|1]
	void pushup(int o)
	{
		root=min(lson,rson);
	}
	void modifiy(int o,int c)
	{
		root+=c;
		tag[o]+=c;
	}
	void pushdown(int o)
	{
		if(tag[o])
		{
			modifiy(o<<1,tag[o]);
			modifiy(o<<1|1,tag[o]);
			tag[o]=0;
		}
	}
	void BuildTree(int o,int l,int r)
	{
		tag[o]=0;
		if(l==r)
		{
			root=sum[l];
			return;
		}
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
		pushup(o);
	}
	void upd(int o,int l,int r,int L,int R,int c)
	{
		if(L<=l && r<=R)
		{
			modifiy(o,c);
			return;
		}
		int mid=(l+r)>>1;
		pushdown(o);
		if(L<=mid)
			upd(o<<1,l,mid,L,R,c);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R,c);
		pushup(o);
	}
	int query(int o,int l,int r,int pos)
	{
		if(l==r)
			return root;
		int mid=(l+r)>>1;
		pushdown(o);
		if(pos<=mid)
			return query(o<<1,l,mid,pos);
		else
			return query(o<<1|1,mid+1,r,pos);
	}
	int check()
	{
		return val[1]>=0;
	}
}T;
int main()//use bf to check
{
	freopen("genes.in","r",stdin);
	freopen("genes.out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		sum[i]=sum[i-1]+a[i];
	}
	tot=sum[n];
	T.BuildTree(1,1,n);
	int ans=0;
	for(int i=1;i<=n;++i)
	{
		int tmp=T.query(1,1,n,i);
		T.upd(1,1,n,i,i,tot-tmp);
		if(i>1)
			T.upd(1,1,n,1,i-1,-tmp);
		if(i<n)
			T.upd(1,1,n,i+1,n,-tmp);
		ans+=T.check();
	}
	cout<<ans<<endl;
	return 0;
}

$paths$

  • $dp$ .
  • 其实就是要求两条不相交路径总长最小值.设 $f(i,j)$ 表示当前一条路径的最后一个点是 $i$ ,另一条路径的最后一个点是 $j$ 时的最短长度.
  • 每次用 $f(i,j)$ 去更新 $f(i,1+\max(i,j)),f(1+\max(i,j),j)$ 就可以保证每个点恰好被选一次了.
  • 特殊点和起点终点特判一下就可以了.
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
#include<bits/stdc++.h>
#define rg register
using namespace std;
inline int read()
{
	int x=0,k=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') k=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return k*x;
}
const int MAXN=1e3+10;
const double inf=1e18;
int n,x[MAXN],y[MAXN],b1,b2;
double dis[MAXN][MAXN],f[MAXN][MAXN];
double calcModulus(int i,int j)
{
	return sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+1.0*(y[i]-y[j])*(y[i]-y[j]));
}
int main()
{
	freopen("paths.in","r",stdin);
	freopen("paths.out","w",stdout);
	n=read(),b1=read()+1,b2=read()+1;
	for(int i=1; i<=n; ++i)
	{
		x[i]=read();
		y[i]=read();
		for(int j=1; j<i; ++j)
			dis[i][j]=dis[j][i]=calcModulus(i,j);
	}
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=n; ++j)
			f[i][j]=inf;
	f[1][1]=0;
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=n; ++j)
		{
			if(i==n && j==n)
				break;
			int k=max(i,j)+1;
			if(k>n)
				--k;
			if(k!=b2)
				f[k][j]=min(f[k][j],f[i][j]+dis[i][k]);
			if(k!=b1)
				f[i][k]=min(f[i][k],f[i][j]+dis[j][k]);
		}
	printf("%.2f\n",f[n][n]);
	return 0;
}