杭电多校 2 补题

1010 女神的睿智

按顺序合并 8 块碎片，如果两片相同，合成后仍相同，如不同，取左侧的，最后合成大碎片时，如果两片相同，不变，如果不同，取出现次数最多的，如果不确定，输出 $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


#include <bits/stdc++.h>
using namespace std;

void solve(){
    string t,s;
    cin>>s;
    map<char,int>vis;
    for(int i=0;i<8;i++){
        if(i%2!=1)t+=s[i];
        vis[s[i]]++;
    }
    s=t;
    t="";
    for(int i=0;i<4;i++){
        if(i%2!=1)t+=s[i];
    }
    if(vis[t[0]]==vis[t[1]])cout<<"N";
    else if(vis[t[0]]>vis[t[1]])cout<<t[0];
    else cout<<t[1];
    cout<<"\n";
}

int main(){
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

1007 URL 划分

输入: 1 s3://hdu-oj-bucket/problem=1/type=data/ 输出： s3 hdu-oj-bucket problem=1 type=data

签到，按题意拆分字符串即可

 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


#include <bits/stdc++.h>
using namespace std;

void solve(){
    string s;
    cin>>s;
    int pos = s.find("://");
    cout<<s.substr(0,pos)<<"\n";
    pos+=3;
    int now = s.find("/",pos);
    cout<<s.substr(pos,now-pos)<<"\n";
    while(1){
        pos=now+1;
        if(pos>=s.size())break;
        now = s.find("/",pos);
        string t = s.substr(pos,now-pos);
        int flag = t.find("=");
        if(flag!=-1)cout<<t<<"\n";
    }
}

int main(){
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

1001 鸡爪

给 $n$ 条边，任意顶点，构造数量最多的鸡爪，同时保证输出每条边的两个顶点时，保证行优先遍历，字典序最小。

鸡爪的定义：1 个顶点，和它所连的 3 条边，不包括其他顶点，不可重复利用。

构造，易想出 $n$ 条边，最多构造出 $n/3$ 个鸡爪，多出的 1 或 2 个边，补到顶点1上即可。
因为字典序最小，所以顶点 1 上连的边肯定最多，我们就让 1 连到所有的顶点上，这样其他所有构造鸡爪的顶点 $n$ 都能用上 $1-n$ 这条边。因此 1 自己用的边肯定是入度最小的几个顶点，即编号最大的顶点，类推到之后的顶点，都是先采用与其之前的顶点的边，再从最后面选。到顶点 4 开始，不再需要往后采用，因为前面有 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


#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin>>n;
    if(n>=3){
        int now=0,cnt=n/3+3;
        for(int i=1;i<=min(n/3,3);i++){
            for(int j=i+1;j<=cnt-i+1;j++){
                cout<<i<<" "<<j<<"\n";
                if(i==1&&j==cnt-i+1){
                    int now=j;
                    while(n%3!=0){
                        cout<<i<<" "<<++now<<"\n";
                        n--;

                    }
                }
            }
        }
    }
    else{
        for(int i=2;i<=n+1;i++)cout<<"1 "<<i<<"\n";
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

1006 传奇勇士小凯

有一个 $n$ 个结点的有根树，你需要从 1 号结点走到任意一个叶子节点，每天你有 $p[i]/15$ 的可能性可以向任意一个儿子节点走一步（ $i$ 为你当前所在的节点编号），询问你期望最多可以在这颗树上走多久

期望计算，在某一节点停留的步数应该为 $15/p[i]$ 。

 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


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+7;

ll ans=0, LCM=360360;
vector<int> nxt[N];
vector<int> p(N);

ll gcd(int x,int y){
    if(!x||!y)return x+y;
    return gcd(y,x%y);
}

void dfs(int u,int fa, ll sum) {
    sum += (LCM / p[u]);
    if(sum>ans)ans=sum;
    for (auto x : nxt[u]) {
        if(x==fa)continue;
        dfs(x, u, sum);
    }
}

void solve() {
    int n;
    cin >> n;
    ans=0;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        nxt[u].push_back(v);
        nxt[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) cin >> p[i];
    dfs(1, 0, 0);
    ll d=gcd(15*ans,LCM);
    printf("%lld/%lld\n",15*ans/d,LCM/d);
    for (int i = 1; i <= n; i++) nxt[i].clear();
}

int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

1003 绝对不模拟的简单魔方

1)暴力，从初始状态开始模拟，每次对比当前状态和给出状态，若相同或不同点仅两个，即得到答案
2)将魔方视为 2 阶的，预处理得到 24 种可能状态，与给出状态对比，至多有一个角不同，即为答案。

1

之后补...

1011 在 A 里面找有 C 的 B

AC自动机（还不会，之后补….