重生之我在黑润心有错当蒟蒻

· · 个人记录

我觉得我的代码还是比较美观的

8.1 枚举和模拟

NOIP2001-J-2-最大公约数和最小公倍数问题

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y,ans;
signed main(){
    scanf("%lld%lld",&x,&y);
    for(int i=1;i<=sqrt(x*y);i++){
        if(x*y%i) continue;
        if(__gcd(i,x*y/i)==x){
            ans+=2;//两数可以交换顺序
        } 
    }
    printf("%lld",ans);
    return 0;
}
- 这道题一开始我以为是把这个数加上1，然后处理进位，把所有0变成1,但老师给了大样例，才发现是遇到第一个0就把后面的数全变成1，还有文件读写
### [修剪灌木](https://xinyoudui.com/ac/contest/745008679000811054CCA86/problem/12701)
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,k,a[2000050],ans,mn=0x7ffffff;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    map <int,pair<int,int> > m;//当前数的个数，共经过几次操作 
    for(int i=1;i<=n;i++){
        int u=a[i];
        int j=0;//经过j次操作 
        while(u){
            m[u].second+=j;
            m[u].first++;
            if(m[u].first>=k){
                mn=min(mn,m[u].second);
            }
            u/=2;
            j++;
        }
    } 
    printf("%d",mn);
    return 0;
}
- 这道题最暴力的就是枚举出发点，时间复杂度 $O(n^2)$
- [st表](https://oi-wiki.org/ds/sparse-table/)是非常好的东西，基于倍增的思想
 - $f_{i,j}$表示的是从第 $i$ 个点开始，分成 $2^j$ 个区间的下一个，那么我们用双指针写出 $f_{i,0}$ 的值，然后先枚举 $j$ 再枚举起点，就可以推出状态转移公式，$f_{i,j}=f_{f_{i,j-1},j-1}$，但是如果 $f_{i,j-1}$ 已经超出范围了我们就要也把 $f_{i,j}$ 标记成超范围
 - 答案的话就要枚举起点，枚举 $j$ （从大到小会快），这里需要一个 $now$ 来维护当前走到了哪个点，$step$ 维护步数，判断如果 $f_{now,j}>=i+n$，即走完了一圈就要记录答案($2^j+step$)；否则就要把 $now$ 更新成 $f_{now,j}$ ，$step$ 加上 $2^j$。最后输出即可
## [8.9模考](https://xinyoudui.com/ac/contest/745008686000811054CC8B6)
### [田忌赛马](https://xinyoudui.com/ac/contest/745008686000811054CC8B6/problem/12692)
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[5];
int b[5];
int win,lose;
int main(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
    scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&b[1],&b[2],&b[3]);
    sort(a+1,a+4);
    sort(b+1,b+4);
    int l=1,r=3;
    int x=1,y=3;
    while(l<=r&&x<=y){
        if(b[l]>a[x]){
            l++;
            x++;
            win++;
        }
        else if(b[r]>a[y]){
            r--;
            y--;
            win++;
        }
        else{
            l++;
            y--;
            lose++;
        }
    } 
    if(win>lose){
        printf("Yes");
    }
    else{
        printf("No");
    }
    return 0;
}

}

- 这道题考试的时候脑子抽抽了，把```sort```的复杂度想成 $O( \log n)$ 了
- 这道题劳氏讲了之后说其实这道题本质就是给 $[l,r]$ 这个区间加一，求最大值，然后我茅厕顿开，注意范围很大，要用```map```
### [小信的su7](https://xinyoudui.com/ac/contest/745008684000811054CD6F6/problem/12686)
```cpp
#include<bits/stdc++.h>
#define int long long//好习惯
#define pii pair<int,int>//不要太长 
using namespace std;
const int N=1e5+5;
int n,m,a[N],t[N],x[N],b[N];
int ed[N],last[N],ans,k=1;
queue <int> qu[N];
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        b[i]=a[i];
    }
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&x[i],&t[i]);
        qu[t[i]].push(x[i]);
    }
    priority_queue<pii,vector<pii>,greater<pii> > q;
    for(int i=1;i<=n;i++){
        qu[i].push(0x7fffffff);
        q.push({qu[i].front(),i});
        qu[i].pop();
    } 
    while(!q.empty()){
        auto u=q.top();
        int id=u.second;
        q.pop();
        if(k<=m&&ans+b[id]>=x[k]){
            int d=x[k]-ans;
            b[id]-=d;
            ans+=d;
            b[t[k]]=a[t[k]];
            q.push({qu[t[k]].front(),t[k]}); 
            qu[t[k]].pop();
            if(id!=t[k])
                q.push({u.first,u.second});
            k++;
        }
        else{

            ans+=b[id];
            b[id]=0; 
        }
    }
    printf("%lld",ans);
    return 0;
}

这表明，有价值的x必须是某个完全平方数减去集合中的元素，无需考虑无关的x值。

2. 生成候选x值的策略

为避免遗漏可能的最优解，需从多个维度生成候选x：

（1）基于单个元素的候选x

对于集合中的每个元素(a_i)：

（2）基于元素对的候选x

对于集合中任意两个元素 a_i \ 和 \ a_j(i > j） ： 

- 非常简单的差分，没啥好说的
## [8.19依旧模考](https://xinyoudui.com/ac/contest/745008678000811054CD126)
- **赛时总结**，第一题还是一如既往地稳定，不到30min就做完了；第二题感觉很像AT的题，是个思维题，但真想不出来，还得多练
- **赛后总结**
### [小信玩乐高](https://xinyoudui.com/ac/contest/745008678000811054CD126/problem/12658)
```cpp
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
//#include<cmath>
#define pb push_back
using namespace std;
int l,s;
int a,b,n;
int main(){
    //freopen("grq.in","r",stdin);
    //freopen("grq.out","w",stdout);
    scanf("%d%d%d",&b,&a,&n);
    l=a;//长滑块的右
    s=b;//短右
    int i=1;
    for(i=1;l!=n&&s!=n;i++){
        if(l==s){
            l=min(n,l+a-b);
        }
        else{
            s=l;
        } 
    } 
    printf("%d",i); 
    return 0;
}