Codeforces 每日一练 495B+55C+1280C

495B Modular Equations

传送门
题意：求有多少个x满足a mod x=b
如果满足题意，则有k*x=a-b，而且那就变成了分解因子，而且x必定大于b，从1到$\sqrt{a-b}$枚举即可，根号时间可以解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
#define ll long long
#define maxn 10005

int main() {
    ll a,b;
    cin>>a>>b;
    a-=b;
    if(a<0)cout<<0;
    else if(a==0)cout<<"infinity";
    else{
        ll ans=0;
        for (ll i = 1; i <=sqrt(a+b) ; ++i) {
            if(a%i==0){
                if(i>b)ans++;
                if(a/i!=i&&a/i>b)ans++;
            }
        }
        cout<<ans;
    }
    return 0;
}

55C Pie or die

传送门
题意：每次你可以把一个棋子移动一步，同时对手可以在边界上加上一块长为1的挡板，询问能否将某个棋子移到棋盘外。
画个图就可以看出来规律了，首先定义：
在这里插入图片描述
图中红点为当前棋子并向左移动，红线为挡板，此时挡板领先棋子1个单位，不难发现如果棋子移动方向上存在没有挡板的拐角，那么棋子就会追上一个单位，但是如果有两个挡板，就会落后一个，那么一种合理的挡板摆放就是在某条边两端各放两个，中间和棋子一条直线上放一个挡板，此时需要棋子到达四个方向边界所需步数都大于等于5
挡板如图：
在这里插入图片描述

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
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
#define ll long long
#define maxn 105
struct node{
    int x,y;
}p[maxn];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    int fl=0;
    for (int i = 1; i <=k ; ++i) {
        cin>>p[i].x>>p[i].y;
        int r=m-p[i].y,d=n-p[i].x;
        if(r<=4||p[i].y-1<=4||d<=4||p[i].x-1<=4){
            fl=1;
        }
    }
    if(fl)cout<<"YES";
    else cout<<"NO";
    return 0;
}

1280C Jeremy Bearimy

传送门
牛客有一道弱化版的：
传送门
题意：一棵有2k个节点的边权树，分成k个点对，求出每个点对中两点距离之和的最大值和最小值。
先说说最大值，首先对于每棵子树，最理想的情况就是把其中的结点去和该子树外的结点相匹配，假设子树节点数为num[i],根节点的父节点为fa[i]，那么想要尽量多的实现这种理想配对，那么i和fa[i]之间的边应该选择min(num[i],n-num[i])次，dfs处理子树就好了。
然后是最小值，考虑到最大值的写法，不难想出最小值就是尽量内部配对，但是如果节点数是奇数，就会多一个不能配对，这时候就应该选择根节点和父亲结点之间的边，即从子树外找一点参与匹配。

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
#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
#define ll long long
#define maxn 200005
map<pair<int,int>,ll>mp;
vector<int> g[maxn];
int num[maxn];
void calc(int x,int fa){
    num[x]=1;
    for(auto i:g[x]){
        if(i!=fa){
            calc(i,x);
            num[x]+=num[i];
        }
    }
}
int n;
ll ans=0,ans2=0;
void dfs(int x,int fa){
    if(mp[pair<int,int>(x,fa)]!=0){
        ans2+=mp[pair<int,int>(x,fa)]*min(num[x],2*n-num[x]);
    }
    else ans2+=mp[pair<int,int>(fa,x)]*min(num[x],2*n-num[x]);
    if(num[x]%2==1){
        if(mp[pair<int,int>(x,fa)]!=0)ans+=mp[pair<int,int>(x,fa)];
        else ans+=mp[pair<int,int>(fa,x)];
    }
    for(auto i:g[x]){
        if(i!=fa){
            dfs(i,x);
        }
    }
}
int main() {
    int t;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        ans2=0;
        ans=0;
        memset(num,0, sizeof(num));
        mp.clear();

        cin>>n;
        for (int j = 1; j <=2*n ; ++j) {
            g[j].clear();
        }
        for (int i = 1; i <2*n ; ++i) {
            int u,v;
            ll w;
            cin>>u>>v>>w;
            mp[pair<int,int>(u,v)]=w;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        calc(1,0);
        dfs(1,0);
        cout<<ans<<" "<<ans2<<endl;
    }
    return 0;
}

（大晚上写的，可能有点乱