lemonoil

OI__nothing is impossible

ACN_v_first

• 标签: ACM

CDQZ 高新2016级ACM模拟赛第一套

result

这里写图片描述

结果如上，因为人数问题，我们队只有两人但规则上允许每人都拥有一台电脑。 这次比赛还是蛮有意思的，在过程中能看见其他人的进度对自己也是一种鼓励（特别是看了自己A了四块深绿）。 深绿胜者可获得笔记本。。。。（没有电脑）一个。

一共九道题，难度（对于自己来说）F>J>I>C>G>B>A>D>E>H。 于是乎我还是按照字典序发题解吧。

A

这里写图片描述 A - QSC and Master HDU - 5900

dp题，用dp[[i][j]表示从i到j之间的最优解，转移方程可以这样写 当i>=j的时，dp[i][j]=0; 当i+1==j且key[i]和key[j]互质时，dp[i][j]=0; 当i+1==j且key[i]和key[j]不互质时，dp[i][j]=val[i]+val[j] 其他情况为，枚举k从i到j-1, dp[i][j]=max(dp[i][k]+dp[k+1][j]). 上面还遗漏了一种情况，就是i+1到j-1之间都可以取，且i和j不互质，这种情况i到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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=302;
long long key[maxn],val[maxn],sum[maxn],dp[maxn][maxn];//sum为前缀和
bool ok[maxn][maxn];
template<class T>inline void readin(T &res) {
	static char ch;
	while ((ch=getchar())>'9'||ch<'0');
	res=ch-48;
	while ((ch=getchar())<='9'&&ch>='0')
	res=ch-48+res*10;
}
long long gcd(long long a,long long b) {
	return b==0?a:gcd(b,a%b);
}
int main() {
	int n,cas;
	readin(cas);
	while (cas--) {
		readin(n);
		sum[0]=0;
		memset(ok,false,sizeof(ok));
		memset(dp,0,sizeof(dp));
		for (register int i=1;i<=n;i++) 
			readin(key[i]);
		for (register int i=1;i<=n;i++) {
			readin(val[i]);
			sum[i]=sum[i-1]+val[i];
		}		
/*		for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++) {
			if (j<=i) ok[i][j]=false;
			else if (gcd(key[i],key[j])==1) ok[i][j]=false;
			else ok[i][j]=true;
		}*/
		for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++) {
			if (gcd(key[i],key[j])!=1) ok[i][j]=true;
		}					
  		for (register int i=1;i<n;i++) 
		if (ok[i][i+1])	dp[i][i+1]=val[i]+val[i+1]; 
/*		for(int i=1;i<=n;i++)  
        {  
            for(int j=1;j<=n;j++)  
            {  
                if(j==i+1&&ok[i][j]) dp[i][j]=val[i]+val[j];  
                else dp[i][j]=0;  
            }  
        }*/
/*		for (register int i=1;i<n;i++)
		for (register int j=i+1;j<=n;j++)
		for (register int k=i;k<=j;k++) {*/
        for(int l=1;l<=n;l++)  
        {  
            for(int i=1;i+l<=n;i++)  
            {  
                int j=i+l;  
                for(int k=i;k<=j;k++)  
                {  
			if (ok[i][k]&&dp[i+1][k-1]==sum[k-1]-sum[i])
				dp[i][j]=max(dp[i][j],dp[i+1][k-1]+val[i]+dp[k+1][j]+val[k]);
			//
			if (ok[k][j]&&dp[k+1][j-1]==sum[j]-sum[k+1])
				dp[i][j]=max(dp[i][j],dp[i][k-1]+val[k]+dp[k+1][j-1]+val[j]);
			//
			dp[i][j]=max(dp[i][j],dp[i+1][j-1]);
			dp[i][j]=max(dp[i][j],dp[i+1][j]);
			dp[i][j]=max(dp[i][j],dp[i][j-1]);
//		}
		}}}
		cout<<dp[1][n]<<endl;
	}
	return 0;
}

B

这里写图片描述 B - Anton and Tree CodeForces - 734E 这题考察了树的直径的作用。题意中的paint(v)就是把所有的与v同色的并从这个点到v不经过其他颜色的点都涂成一种颜色，包括v; 这样缩点是必然的，用dfs缩点后重构树（可证：重构图必然是树） 然后因为paint（v）对所有点有效，我们很容易看出树的直径/2就是答案。 

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<stack>
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define res(i,x,y) for(int i=x;i<=y;i++)
#define INF 2100000000
#define LL long long
#define clr(x)  memset(x,0,sizeof(x))
using namespace std;
template<class T>inline void readin(T &res){
	static char ch;
	while((ch=getchar())>'9'||ch<'0');
	res=ch-48;
	while((ch=getchar())<='9'&&ch>='0')
	res=ch-48+res*10;
}
const int maxn = 1e5+7;  
int c[maxn<<1],d[maxn<<1];  
vector<int>e[maxn<<1]; 
void dfs(int u,int fa){  
    for(register int i=0;i<e[u].size();i++){  
        int v=e[u][i];
        if(v==fa)continue;  
        d[v]=d[u]+(c[u]^c[v]);  
        dfs(v,u);  
    }  
}  
int main(){
    int n;  
    readin(n);  
    for(register int i = 1;i<=n;i++) readin(c[i]);  
    for(register int i = 1;i<=n-1;i++){  
        int u,v;
        readin(u),readin(v);
        e[u].push_back(v);  
        e[v].push_back(u);  
    }
    int u=1;  
    dfs(u,-1);
    int maxlen=d[u];
    for(register int i = 1;i<=n;i++)  
        if(d[i]>maxlen)  
            maxlen=d[i],u=i;
    memset(d,0,sizeof(d));  
    dfs(u,-1);
    maxlen = d[u];
    for(register int i=1;i<=n;i++){
        if(d[i]>maxlen){ 
            maxlen = d[i];  
            u=i;  
        }  
    }  
    printf("%d\n",(d[u]+1)/2);  
}

C

这里写图片描述 C - Road to Cinema CodeForces - 729C

题意：首先给出N，K，S，T分别代表汽车类型数量，加油站数量，路程全程，最大耗时。 接着N行，每行给出一种汽车的价格和邮箱容积，最后一行给出K个加油站的位置。 汽车每到一个加油站都可以瞬间加满油，汽车有两种行驶方式，高速：一公里一分钟一升油，低速：一公里两分钟一升油。可以在任意时间选择任意一种行驶方式。 在小于最大耗时的前提下，选择价格最小的汽车跑完全程。输出最小价格，如果找不到就输出-1.

思路：根据最大耗时可以二分查找出最小油量，根据最小油量去汽车类型中找到最小价格。 对于二分过程，设出x1和x2代表高低速所走的路程，解个二元一次方程组即可。这时要处理好边界情况，比如就算全程慢速油料也不够用或者全程高速也用不完油料。实现时我直接忽略掉了x1,x2的中间结果，直接累加的时间 注意点一：二分出的结果并不一定合法。需要设置标记变量记录二分过程中是否真的找到过合法的油量，只要找到过一次，就可以拿这个合法的油量去汽车类型中求最小价格，如果一次都找不到，那么二分出的答案本身就不合法，也没必要去汽车类型中找答案了，直接输出-1吧。 注意点二：给出的油站位置是乱序的，记得排个序，把起点和终点都当作一个油站会方便运算。

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
#include<stdio.h>
#include<stdlib.h>
int cmp(const void* a,const void* b)
{
	return (*(int*)a-*(int*)b);
}
int c[262144],v[262144],g[262144],px[262144],px2[262144];
int cmp2(const void* a,const void* b)
{
	int cc=*(int*)a,dd=*(int*)b;
	return c[cc]-c[dd];
}
int main()
{
	int n,k,s,t;
	scanf("%d%d%d%d",&n,&k,&s,&t);
	for(int i=0;i<n;i++)
	{
		scanf("%d%d",&c[i],&v[i]);
		px[i]=i;
	}
	for(int i=0;i<k;i++)
	{
		scanf("%d",&g[i]);
	}
	qsort(g,k,4,&cmp);
	qsort(px,n,4,&cmp2);
	g[k]=s;
	c[n]=-1;
	px[n]=n;
	int max=0;
	int j=0;
	for(int i=0;i<n;i++)
	{
		if(v[px[i]]>max)
		{
			max=v[px[i]];
			px2[j++]=px[i];
		}
	}
	px2[j]=n;
	int left=0,right=j;
	while(left<right)
	{
		int i=(left+right)>>1;
		int oil=v[px2[i]];
		int j=0;
		int wz=0;
		int tim=0;
		while(1)
		{
			if(tim>t)
			{
				break;
			}
			if(oil<g[j]-wz)
			{
				tim=t+1;
				break;
			}
			int spd=oil-(g[j]-wz);
			oil-=spd<<1;
			if(oil>0)
			{
				wz+=spd;
				tim+=spd;
			}
			else
			{
				tim+=g[j]-wz;
				wz=g[j];
			}
			tim+=(g[j]-wz)<<1;
			wz=g[j];
			oil=v[px2[i]];
			j++;
			if(j>k)
			{
				break;
			}
		}
		if(tim<=t)
		{
			right=i;
		}
		else
		{
			left=i+1;
		}
	}
	printf("%d",c[px2[left]]);
	return 0;
}

D

这里写图片描述 D - Taxes CodeForces - 735D 吐槽一下，答案只有1,2,3真的没问题吗？（原因你可以把哥德巴赫猜想给证明一遍。。。。。。） 题意： 某人要交税，交的税钱是收入n的最大因子（!=n，若该数是质数则是1），但是这人作弊，把钱拆成几份，使交税最少，输出税钱。 解法： 如果n为质数不拆， 如果n是偶数可以拆成两个质数的和。 如果n可以拆成2+一个质数输出2 剩下的只能成3份。

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
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
template<class T>inline void readin(T &res) {
	static char ch;
	while ((ch=getchar())>'9'||ch<'0');
	res=ch-48;
	while ((ch=getchar())<='9'&&ch>='0')
	res=ch-48+res*10;
}
long long n;
int prime[60002],sum=0;
void init() {
	int j,vis[60002];
	vis[2]=0,vis[3]=0,sum=1;
	
	for (int i=2;i<=60002;i++) {
		if (!vis[i]) {
			vis[i]=1;
			prime[sum++]=i;
			j=2*i;
			while (j<60001) {
				vis[j]=1;
				j+=i;
			}
		}
	}
}
int main() {
	readin(n);
	int flag1=0,flag2=0;
	if (n==2) {
		printf("%d\n",1);
		return 0;
	}
	if (n%2==0) {
		printf("%d\n",2);
		return 0;
	}
	else {
		init();		
		for (int i=1;prime[i]*prime[i]<=n;i++) {
			if (n%prime[i]==0) {
				flag1=1;
				break;
			}
		}
		if (flag1) {
			n-=2;
			for (int i=1;prime[i]*prime[i]<=n;i++) {
				if (n%prime[i]==0) {
					flag2=1;
					break;
				}
			}
			if (flag2) printf("%d\n",3);
			else printf("%d\n",2); 
		}
		else printf("%d\n",1);
	}
	return 0;
}

E

这里写图片描述 E - Easy Math SCU - 4436 一句话：无理数+任意整数数都为无理数。

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
#include<stdio.h>
#include<math.h>
int a[131072];
int main()
{
	int n;
	while(scanf("%d",&n)>0)
	{
		int r=1;
		for(int i=0;i<n;i++)
		{
			
			scanf("%d",&a[i]);
			int m=(int)sqrt(1.0*a[i]+0.5)+1;
			while(r)
			{
				if((long long)m*m==a[i])
				{
					break;
				}
				if((long long)m*m<a[i])
				{
					r=0;
				}
				m--;
			}
			
		}
		if(r)
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
		
	}
	return 0;
}

F

这里写图片描述 F - Treasure HDU - 5770 令subtree(i)表示以i为根节点的子树，对于某个宝箱a,b,v，令c=lca(a,b) 1.若a!=c且b!=c，那么要想得到这个宝箱的权值，起点必须在subtree(a)中，终点必须在subtree(b)中 2.若a=c，说明b是a的祖先，要想拿到此宝箱，起点不能在subtree(a)中，终点必须在subtree(b)中 3.若b=c，与a=c类似，起点不能在subtree(b)中，终点必须在subtree(b)中 4.若a=b，说明宝箱和其对应的钥匙在同一点，那么起点和终点只要不同的subtree(son)中即可（son为a的儿子节点） 考虑到每种情况起点终点都在某棵子树中任意选取，故首先求出每个节点的dfs序，用dfs序将一棵子树subtree(i)映射成一个连续的区间[l[i],r[i]]，进而上面四种情况中起点和终点的选则就对应二维平面的一个矩阵，平面上点(x,y)的实际意义是走以x为起点y为终点的简单路径能够得到的权值，通过对每个宝箱的讨论可以在平面上扔若干个矩阵，最后从整个平面上找一个点权最大的点即为答案，后者用扫描线加线段树即可（即将一个矩阵看作两条横线，扫到下方横线就权值加v，扫到上方横线就权值减v表示消除影响） 注意前三种情况每种情况最多加两个矩阵，但是第四种情况由于起点终点可以在a的若干儿子子树中选取，故最多会出现n^2个矩阵，这显然不行，故可以采取总体累加，局部消除的方法，即先给加一个全平面矩阵，权值为v，然后加所有的不合法矩阵，权值为-v，不非法矩阵有四种情况： 1.起点终点都在a的某个subtree(son)中，son为a的儿子节点（累加至多n个） 2.起点终点都在suntree(left_brother)中，left_brother为a的左兄弟节点（即dfs序比l[a]小的点)（至多一个） 2.起点终点都在suntree(right_brother)中，right_brother为a的右兄弟节点（即dfs序比r[a]大的点)（至多一个） 3.起点和终点，一个在suntree(left_brother)中一个在suntree(right_brother)中（至多两个） 不合法矩阵累加不超过4*n个，这样就可以保证复杂度是O(nlogn)的了 对于上面第一种情况所加矩阵至多n个的解释：虽然每个节点的儿子节点数可以达到n-1个，但是如果将位于同一个节点处的宝箱看作一个来考虑的话，那么每个节点作为其父亲节点的儿子节点在这种情况下被加进去至多一次，故累加不超过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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<stack>
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define res(i,x,y) for(int i=x;i<=y;i++)
#define INF 0x3f3f3f3f
#define maxn 111111
#define ll long long
#define ls (t<<1)
#define rs (t<<1|1)
#define clr(x)  memset(x,0,sizeof(x))
using namespace std;
template<class T>inline void readin(T &res){
	static char ch;
	while((ch=getchar())>'9'||ch<'0');
	res=ch-48;
	while((ch=getchar())<='9'&&ch>='0')
	res=ch-48+res*10;
}
struct node{
    int y,l,r,v;
    node(){};
    node(int _y,int _l,int _r,int _v){
        y=_y,l=_l,r=_r,v=_v;
    } 
    bool operator <(const node &b)const{
        return y<b.y;
    }
}a[maxn*10];
vector<int>g[maxn];
int p[maxn][20],deep[maxn],vis[maxn];
int index,l[maxn],r[maxn];
int T,n,m,res,Case=1;
void dfs(int u){
    l[u]=++index;
    vis[u]=1;
    for(register int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(vis[v])continue;
        deep[v]=deep[u]+1;
        p[v][0]=u;
        dfs(v);
    }
    r[u]=index;
}
int lca(int a,int b){
    if(deep[a]<deep[b])swap(a,b);
    register int i,j;
    for(i=0;(1<<i)<=deep[a];i++);
    i--;
    for(j=i;j>=0;j--)
        if(deep[a]-(1<<j)>=deep[b])
            a=p[a][j];
    if(a==b) return a;
    for(j=i;j>=0;j--)
        if(p[a][j]!=-1&&p[a][j]!=p[b][j])
            a=p[a][j],b=p[b][j];
    return p[a][0];
}
int find(int x,int step){
    for(register int i=0;i<20;i++)
        if(step&(1<<i))x=p[x][i];
    return x;
}
void init(int n){
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i<=n;i++)
            if(~p[i][j-1])p[i][j]=p[p[i][j-1]][j-1];
}
void deal(int y1,int y2,int x1,int x2,int v){
    a[res++]=node(y1,x1,x2,v);
    if(y2<n)a[res++]=node(y2+1,x1,x2,-v);
}
struct Tree{
    int Max,lazy;
}tree[maxn<<2];
void push_up(int t){
    tree[t].Max=max(tree[ls].Max,tree[rs].Max);
}
void push_down(int t){
    int lazy=tree[t].lazy;
    if(!lazy)return ;
    tree[ls].Max+=lazy,tree[ls].lazy+=lazy;
    tree[rs].Max+=lazy,tree[rs].lazy+=lazy;
    tree[t].lazy=0;
}
void build(int l,int r,int t){
    tree[t].Max=tree[t].lazy=0;
    if(l==r)return ;
    int mid=(l+r)>>1;
    build(l,mid,ls),build(mid+1,r,rs);
}
void update(int l,int r,int L,int R,int t,int v){
    if(l==L&&r==R){
        tree[t].Max+=v,tree[t].lazy+=v;
        return ;
    }
    push_down(t);
    int mid=(l+r)>>1;
    if(R<=mid)update(l,mid,L,R,ls,v);
    else if(L>mid)update(mid+1,r,L,R,rs,v);
    else {
        update(l,mid,L,mid,ls,v);
        update(mid+1,r,mid+1,R,rs,v);
    }
    push_up(t);
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)g[i].clear();
        for(int i=1;i<n;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v),g[v].push_back(u);
        }
        memset(p,-1,sizeof(p));
        memset(vis,0,sizeof(vis));
        deep[1]=1;index=0;
        dfs(1);
        init(n);
        res=0;
        while(m--){
            int a,b,v;
            scanf("%d%d%d",&a,&b,&v);
            int c=lca(a,b);
            if(a==b){
                deal(1,n,1,n,v);
                for(int i=0;i<g[a].size();i++){
                    int d=g[a][i];
                    if(deep[d]<deep[a])continue;
                    deal(l[d],r[d],l[d],r[d],-v);
                }
                if(l[a]>1)deal(1,l[a]-1,1,l[a]-1,-v);
                if(r[a]<n)deal(r[a]+1,n,r[a]+1,n,-v);
                if(l[a]>1&&r[a]<n){
                    deal(1,l[a]-1,r[a]+1,n,-v);
                    deal(r[a]+1,n,1,l[a]-1,-v);
                }
            }
            else if(a!=c&&b!=c){
                deal(l[a],r[a],l[b],r[b],v);
            }
            else if(a==c){
                int d=find(b,deep[b]-deep[a]-1);
                if(l[d]>1)deal(1,l[d]-1,l[b],r[b],v);
                if(r[d]<n)deal(r[d]+1,n,l[b],r[b],v);
            }
            else if(b==c){
                int d=find(a,deep[a]-deep[b]-1);
                if(l[d]>1)deal(l[a],r[a],1,l[d]-1,v);
                if(r[d]<n)deal(l[a],r[a],r[d]+1,n,v);
            }
        }
        sort(a,a+res);
        int ans=-INF;
        build(1,n,1);
        for(int i=1,j=0;i<=n;i++){
            for(;j<res&&a[j].y==i;j++)
                update(1,n,a[j].l,a[j].r,1,a[j].v);
            ans=max(ans,tree[1].Max);
        }
        printf("Case #%d: %d\n",Case++,ans);
    }
    return 0;
}

G

这里写图片描述 G - Mr. Kitayuta, the Treasure Hunter CodeForces - 506A

一共有30001个岛屿，下标为0~30000，有些岛屿藏有宝藏。你从0往下标大的方向跳，第一步跳的距离为d。如果上一步跳的距离为l，这一步就可以跳l-1或l或l+1（距离必须大于0）。问最多拿到多少宝藏。 设dp[i][j]表示到达第i个岛屿，跳了j步得到的最大宝藏数，那么动态转移方程： dp[to][j]=max(dp[to][j],dp[i][j]+treasure[to]) dp[to+1][j+1]=max(dp[to+1][j+1],dp[i][j]+treasure[to+1]) dp[to-1][j-1]=max(dp[to-1][j-1],dp[i][j]+treasure[to-1]) 如果开一个dp[30000][30000]的数组的话会MLE，那么在到达30000之前，最大步长是1+2+3+...+250>30000。所以第二维开到500就够了。

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cctype>
#include <algorithm>
#define clr(x) memset(x,0,sizeof(x))
#define ms(a,x) memset(x,a,sizeof(x))
#define LL long long
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std; 
const int maxn = 30005;
const int stp = 505;
int n,d,x,ans,maxx;
int num[maxn],sum[maxn];
int dp[maxn][stp];
int sp[] = {-1, 0, 1};
int dfs(int pos, int l) {
    int sit = pos+l+d;
    if(l+d < 1 || sit > maxx) return 0;
    if(dp[sit][l+250] != -1) return dp[sit][l+250];
    if(l+d <= 2) {
        dp[sit][l+250] = sum[sit];
        return dp[sit][l+250];
    }
    if(l+d == 3) {
        dp[sit][l+250] = sum[sit+2]+num[sit];
        return dp[sit][l+250];
    }
    int he = 0;
    for(int i = 0; i < 3; i++) {
        int xl = l+sp[i];
        he = max(he, dfs(sit, xl));
    }
    he += num[sit];
    return dp[sit][l+250] = he;
}
void init() {
	ms(-1, dp);
    scanf("%d%d",&n,&d);
    for(int i = 0; i < n; i++) scanf("%d",&x), maxx = max(x, maxx), num[x]++;
	for(int i = maxx; i >= 1; i--) sum[i] = sum[i+1]+num[i];
}
int main() {
	init();
    ans = dfs(0, 0);
    printf("%d\n",ans);
    return 0;
}

H

这里写图片描述

H - Case of Matryoshkas CodeForces - 555A

规定两种操作： 1、拆下编号最大的娃娃。 2、将一条链上的娃娃套在一个没有套在任何其他链子上的娃娃上（有点绕）。意思就是比如有一条链1→2→4→5，你可以拆下5，然后变成两条链1→2→4和5，或者将这条链套在6上，但是6不能已经套在任何其他链子上（即6必须是单独一个），变成1→2→4→5→6。题目要求用最少的操作步数将所有的娃娃套在一个链子上。 思 路： 编号为1的娃娃所在的那条链子上，1是不需要拆下来的。也就是不用进行任何操作。如果1套在2上，那么2也不用拆下来，再接着如果2套在3上，那么3也不用拆 ...... 以此类推，这条链上从1开始连续的数字都是不用拆的。直到某个地方不连续，比如1→2→3→4→6→7→8，其中4套在6上，那么5肯定在别的链子上，需要把6（包括6）以后的所有娃娃都拆下来，然后把5接上去，再把6 7 8接上去。由此看来，这条链上从1开始连续的数字不用拆。一旦遇到不连续，则从这个不连续的娃娃开始后面的全部都要拆。 然后依据要输入几组数据来计算要拆的次数，在计算要套的次数。例如输入n个，m组数据，从一开始连续的用k个，则： 需要次数= 要拆的次数 ( n - k - m + 1 ) + 要套的次数( n - 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
49
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stack>
using namespace std;
int a[100005];
int n,m;
int k;
int cnt;
int main() {
    while(scanf("%d%d",&n,&m)!=EOF) {
        int t = 0;
        cnt = 0;
        for(int i=0; i<m; i++) {
            scanf("%d",&k);
            int flag = 0;
            int minn = 999999;
            for(int j=0; j<k; j++) {
                scanf("%d",&a[j]);
                if(j == 0 && a[0] == 1) {
                    flag = 1;
                } else if(flag == 1) {
                    if(a[j] - 1 != a[j-1]) {
                        flag = 2;
                        t = a[j-1];
                        cnt += k - j;
                    }
                } else if(flag == 0) {
                    if(a[j]>minn) {
                        cnt++;
                    } else {
                        minn = a[j];
                    }
                }
            }
            if(flag == 1) {
                t = a[k-1];
            }
        }
        cnt += n - t;
        printf("%d\n",cnt);
    }
    return 0;
}

I

这里写图片描述 I - Bubble Sort HDU - 5775

题意：给出一个序列，求每一个数字在冒泡排序中出现的最大最小下标差。 从小到大考虑每一个数组，一个数字右边有多少个比他大的数字就是他右移的数量。用树状数组维护下就好了。

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#define maxn 100010
#define maxm 1000010
using namespace std;
int T,n,cas=0;
int num[maxn<<1],f[maxn<<1],ans[maxn<<1];
int lowbit(int x){return x&(-x);}
void update(int x){
    while(x<=n){
        f[x]++;
        x+=lowbit(x);
    }
}
int Sum(int x){
    int t=0;
    while(x!=0){
        t+=f[x];
        x-=lowbit(x);
    }
    return t;
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(f,0,sizeof(f));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&num[i]);
        int cnt=0,l=0,r=0,nx=0,minn=0;
		for(int i=1;i<=n;i++){
            update(num[i]);
            nx=i-Sum(num[i]);
            minn=num[i]+nx-i;
            l=min(i,num[i]);
            r=max(i,i+minn);
            ans[num[i]]=abs(r-l);
        }
        printf("Case #%d:",++cas);
        for(int i=1;i<=n;i++)printf(" %d",ans[i]);
        cout<<endl;
    }
    return 0;
}

J

这里写图片描述

J - Countries HihoCoder - 1391

题目大意： 　　A和B两个国家互射导弹，每个国家都有一个防御系统，在防御系统开启的时间内可以将到达本国的导弹反弹回去(掉头，防御系统不能开开关关)。 　　现在已知：Ta、Tb为A、B两国导弹防御能开启的持续时间，X为B国开启导弹防御系统的时刻(持续时间为[X,Tb+X]，包含端点) 　　A向B发射N枚导弹，B向A发射M枚导弹。每枚导弹有3个值：发射时间，从A到B或从B到A的飞行时间，伤害值。 　　现在A可以在任意时刻开启防御系统，求A所受到的最小伤害值。 题目思路： 　　【预处理+排序+堆】 　　首先预处理，求出每枚导弹不会打到A需要A国防御系统开启的时间段[st,et]，只有A开启防御的时间段[Y,Y+Ta]包含[st,et]那么这枚导弹不会打到A。 　　预处理之后将每枚导弹按照et从小到大排序。 　　从1到n+m枚导弹，对于当前这枚导弹，如果需要被防御，那么A防御系统的结束时间就为et，那么开启时间就为et-Ta 　　那么将之前已经被防御的导弹中st<et-Ta的移除出去，表示这些导弹不能在当前决策中被防御。 　　可以开个STL的优先队列或者堆记录之前被防御的导弹序号，按照st从小到大存，每次比较最小的st和开启时间et-Ta。并在过程中增减伤害值，并记录最小伤害。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<stack>
#define rez(i,x,y) for(int i=x;i>=y;i--)
#define res(i,x,y) for(int i=x;i<=y;i++)
#define INF 2100000000
#define LL long long
#define clr(x)  memset(x,0,sizeof(x))
#define MAX 0x3f3f3f3f
#define N 20004
using namespace std;
template<class T>inline void readin(T &res){
	static char ch;
	while((ch=getchar())>'9'||ch<'0');
	res=ch-48;
	while((ch=getchar())<='9'&&ch>='0')
	res=ch-48+res*10;
}
int n,m,cnt,ans;
int Ta,Tb,X,sum;
struct node{
    LL t,c,e,d;
}a[N],b[N];
struct cmpf{
    bool operator ()(const int &lhs,const int &rhs){
        return a[lhs].t>a[rhs].t;
    }
};
bool cmp(node lhs,node rhs){
    return lhs.e<rhs.e;
}
int main(){
    int x,y,i,j;
    while(scanf("%d%d",&Ta,&Tb)!=EOF){
        cnt=0,ans=MAX,sum=0;
        readin(X),readin(n),readin(m);
        for(i=1;i<=n;i++){
            readin(b[i].t),readin(b[i].c),readin(b[i].d);
            b[i].e=b[i].t+b[i].c;
            if(b[i].e>=X&&b[i].e<=X+Tb){
                sum+=b[i].d;
                a[++cnt].t=b[i].e+b[i].c;
                j=Tb+X-a[cnt].t;
                j=j%(2*b[i].c);
                a[cnt].e=Tb+X-j;
                a[cnt].d=b[i].d;
                if(j>=b[i].c)a[cnt].e+=b[i].c+b[i].c;
                if(a[cnt].t+b[i].c<X||a[cnt].t>Tb+X)a[cnt].e=a[cnt].t;
            }
        }
        for(i=1;i<=m;i++){
            readin(b[i].t),readin(b[i].c),readin(b[i].d);
            b[i].e=b[i].t+b[i].c;
            sum+=b[i].d;
            a[++cnt].t=b[i].e;
            j=Tb+X-a[cnt].t;
            j=j%(2*b[i].c);
            a[cnt].e=Tb+X-j;
            a[cnt].d=b[i].d;
            if(j>=b[i].c)a[cnt].e+=b[i].c+b[i].c;
            if(a[cnt].t+b[i].c<X||a[cnt].t>Tb+X)a[cnt].e=a[cnt].t;
        }
        sort(a+1,a+cnt+1,cmp);
        priority_queue<int,vector<int>,cmpf>q;
        for(i=1;i<=cnt;i++){
            q.push(i);y=a[i].e;
            sum-=a[i].d;
            x=q.top();
            while(y-a[x].t>Ta&&!q.empty()){
                sum+=a[x].d;
                q.pop();x=q.top();
            }
            ans=min(ans,sum);
        }
        printf("%d\n",ans);
    }
    return 0;
}

click it and link me

Launch CodeCogs Equation Editor