day4下午

清北学堂--刷题班

t1

更相减损

t2

最大生成树，
求出最大生成树，

kruskal重构树

例子:bzoj3551,3545

每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。

t3

正解
首先，
f[i],取到了第i个 由 f[i] f[i-m]+a[i]，

解题报告及总结

预计100+30+？
实际100+30+0

连续两天了，t1用了太长时间。。

t1

一上来不会做啊，于是写了好几组数据，还不会，于是在本子上从1开始写，，
没找到规律，于是，打表找规律。。。。
找and不断的试接近半个多小时，发现了性质，开始写，直到1个小时半小时过去，才写完，调试出几个错误。

性质：任意两个数交换不会影响答案(试出来的。。)
所以让小的在前，然后发现对于x,y(x<=y)的答案work(x,y)
有work(y%x,y)+(y-1)/a，递归求解，边界
if (x==1) return y+1;
if (x==b) return 2;
if (x==0) return 2;

非常感谢一份代码——我的暴力代码：（它是我正解的基础！）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>

using namespace std;

int a[100010];
bool vis[300200];

inline long long read() {
    long long x = 0,f = 1;char ch = getchar();
    for (; ch<'0'||ch>'9'; ch = getchar())
        if (ch=='-') f = -1;
    for (; ch>='0'&&ch<='9'; ch = getchar())
        x = x*10+ch-'0';
    return x*f;
}

int main() {

//  a[1] = read(),a[2] = read();
//  while (scanf("%d%d",&a[1],&a[2])) //测试时使用这个
    {
        scanf("%d%d",&a[1],&a[2]);//对拍时使用这个
        memset(vis,0,sizeof(vis));
        vis[a[1]] = vis[a[2]] = true;
    //  printf("%d %d ",a[1],a[2]);
        for (int i=3; ; ++i) {
            a[i] = abs(a[i-1]-a[i-2]);
            vis[a[i]] = true;
    //      printf("%d ",a[i]);
            if (a[i]==a[i-1]) break;
        }
        int ans = 1;
        for (int i=1; i<=100000; ++i) 
            if (vis[i]) ans ++;
        printf("%d\n",ans);
    }
    return 0;
}

正解：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>

using namespace std;

inline long long read() {
    long long x = 0,f = 1;char ch = getchar();
    for (; ch<'0'||ch>'9'; ch = getchar())
        if (ch=='-') f = -1;
    for (; ch>='0'&&ch<='9'; ch = getchar())
        x = x*10+ch-'0';
    return x*f;
}/*
long long gcd(long long a,long long b) {
    return b==0?a:gcd(b,a%b);
}*/

long long work(long long a,long long b) {
    if (a > b) swap(a,b);
    if (a==1) return b+1;
    if (a==b) return 2;
    if (a==0) return 2;
    long long c = b%a,t = (b-1)/a;
    long long ret = 0;
    ret = work(a,c)+t;
    return ret;
}

int main() {

    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);

    long long a = read(),b = read();
    if (a > b) swap(a,b);
    if (a==1) {
        cout<<b+1;
        return 0;
    }
    //long long d = gcd(a,b);
    /*if (d>1) {
        long long ans = (b/d)+1;
        cout<<ans;
        return 0;
    }*/
    cout<<work(a,b);

    return 0;
}

还有写完对拍时，在dev上的对拍拍到8000多组数据时，把dev弄炸了，以后注意

t2

写了一个大暴力

t3

讲课

启发式合并，

并查集，合并时做一些事情，遍历size小的集合