大学康复训练

大学康复训练
进入清华第一次打codeforces，感觉自己又菜了好多好多呀，这几天回复手感，上传一些自己觉得做的好的题目。

波浪数P1112

看似是一个考进制转换的，但是一算发现暴力必定会t，所以换个欧拉筛的思路，先找出全部，之后按要求去输出。
即模拟波浪数的产生，找出所有波浪数并知道是几重，（注意，这里有个细节会在待会代码里提出）

#include
using namespace std;
int tag[10000007];

int main(){
    int l,r,ll,rr,k;
    cin>>l>>r>>ll>>rr>>k;
	memset(tag , 0 ,sizeof(tag));
    int pos;
    for(int i = l ; i <= r ; i++){
        for(int j = 1 ; j <= i - 1 ; j ++ ){
            for(int p = 0 ; p <= i - 1 ; p ++ ){
                if(j != p){
                    pos = 0;
                    int x = 0;
                    while(x <= rr){
                        if(pos % 2 == 0){
                            x = x * i + j;//这里一定是乘上i而不是10，几进制就乘几！！！！！！！！
                            pos ++;
                        }
                        
                        else {
                            x = x * i + p;
                            pos++;
                        }
                        if(x >= ll && x <= rr) tag[x] ++;
                    }
                }
            }
        }
        
    }for(int i = ll ; i <= rr ; i++){
            if( tag[i] == k )cout << i << endl;
        }
    return 0;
}

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

时态同步P1131

对于上一级的节点的维护会影响全部子节点，所以不可以贪心求解全部子节点的距离，之后求与最大值的和。
但我们发现无论如果，倒数第二个节点到子节点的距离一定全相等才可以，当这个分枝处理完后，该节点就可以视为最后一个节点（因为他的子节点不会再调整了），同理可以知道全部思路。
即dfs维护子节点最大时间，之后每一个节点自己去调整儿子的时间，最后向上回溯再去调整。
代码如下
要注意这是双向路，这个是图论易错的

#include 
const int oo = 1000005; 
#define ll long long
using namespace std;
int n , s , t[oo];
int num , head[oo] , nex[oo] , to[oo];

void add(int x , int y , int z){
	num ++;
	to[num] = y;
	nex[num] = head[x];
	head[x] = num;
	t[num] = z;
}
bool tag[oo];

ll  fin[oo] ,ans = 0 ;

void dfs(int x , int fa){
	tag[x] = 1;
	for(int i = head[x] ; i ; i = nex[i]){
		if(to[i] == fa)continue;
		if(tag[to[i]]  != 1) {
			//cout << to[i] <
			dfs(to[i] , x);
			fin[x] = max(fin[x] , fin[to[i]] + t[i]);
			//cout <
			
		}
	}
	for(int i = head[x] ; i  ; i = nex[i]){
		if(to[i] == fa) continue;
		ans += fin[x] - fin[to[i]] - t[i];
	}
}

int main(){
	cin >> n >> s;
	int a,b,c;
	for(int i = 1 ; i < n ;i ++){
		cin >> a >> b >> c;
		add(a,b,c);
		add(b,a,c);//注意这里是双向的/！！！！！！
	}
	dfs(s , 0);
	cout << ans << endl;
	return 0;
}
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

##火柴排队P1966
题面很simple，显然对于欧拉距离的计算是困难的，$（a-b{）}^2$拆开之后可以发现$a^2$+$b^2$是不变的，所以只用求max sum ab即可保证最小。
这种第一感觉都是贪心，最大乘最大，最小乘最小，数学知觉还是需要证明一下的。a>b，c>d，ac+bd>ad+bc证明显然。
最后就变成要换成大对大，小对小。这里显然不是将两个队列分别排序，我们固定a，移动b，只用将b的大小顺序搞成a的就OK。
经典操作先把ab排序，记着排序前一定要记录对应数据的下标，构造数组c，c［a［1］下标］=b［1］下标，最后c有序的过程数就是答案，求这个显然是经典的树状数组求逆序对。
代码不放了，这个常数写的太大了，丑陋至极。