http://acm.hdu.edu.cn/diy/contest_show.php?cid=36331
jxnu2020

03 并查集

Problem Description
从前有个老和尚对小和尚讲故事，他说他早上看到一个年轻男子赶着n头牛，在农田里耕种，突然下起了大雨，年轻男子怕牛着凉了，就打算把它们安排到几个各自分开的草棚下面避雨，他一共有q次操作，每次操作都将牛Xi与牛Yi所在的草棚合并在一起，对于n头牛，编号分别为1,2,3,...,n。
Input
多组输入。对于每组测试数据，第一行包含两个整数n,m，表示n头牛，m次操作，接下来m行，每行包括三个整数Zi,Xi,Yi,当Zi=1时，将牛Xi与牛Yi所在的草棚合并在一起，当Zi=2时，请输出牛Xi和牛Yi是否在一个草棚，是的输出"Yes",否则输出"No"（不包含双引号）。（1<=n<=10000,1<=m<=200000）
Output
对于Zi=2时，输出"Yes"或"No"（不包含双引号）。行末换行。
Sample Input
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
Sample Output
No
Yes
No
Yes

solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int vis[10005];
int find(int x) {
    return vis[x]==-1?x:(vis[x]=find(vis[x]));
}
int main() {
    int n,m;
    while(cin>>n>>m) {
        memset(vis,-1,sizeof(vis));
        while(m--) {
            int z,x,y,a,b;
            cin>>z>>a>>b;
            x=find(a),y=find(b);
            if(z==1) {
                if(x!=y) vis[y]=x;
            }
            else if(x!=y) cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
    }
    return 0;
}
#include <bits/stdc++.h>

using namespace std;

bool check(string a,string b){
    if(a.size()!=b.size())
    return a.size()>b.size();
    int p=0;
    while(p<(a.size())&&a[p]==b[p])
    p++;
    if(p==a.size()||a[p]>b[p])//a>=b为true 
    return true;
    else
    return false;
}
int ans[20010],len;
string a,b;
void work(){
    int jw=0,i,j;
    for(i=a.size()-1,j=b.size()-1;i>=0&&j>=0;i--,j--){
        if(a[i]-b[j]+jw<0)
        ans[len++]=10+jw+(a[i]-b[j]),jw=-1;
        else
        ans[len++]=a[i]-b[j]+jw,jw=0;
    }
    for(;i>=0;i--)
    if(a[i]-&#39;0&#39;+jw<0)
    ans[len++]=10+jw+a[i]-&#39;0&#39;,jw=-1;
    else
    ans[len++]=jw+a[i]-&#39;0&#39;,jw=0;
}
int main(){
    while(cin>>a>>b){
        int flag=0;
        if(!check(a,b))
        swap(a,b),flag=1;
        memset(ans,0,sizeof(ans));
        len=0;
        work();
        if(flag)
        cout<<"-";
        int flag2=0;
        for(int i=len-1;i>=0;i--){
            if(ans[i]!=0)
            flag2=1;
            if(flag2)
            cout<<ans[i];
        }
        if(!flag2)
        cout<<0;
        cout<<"\n";
    }
}

04 字符串尾0优化

Problem Description
CangLan学长最近在一个秘密研究部门，并需要打开一个大型保险箱,此时，CangLan学长接到了其他部门的电话，并得知打开保险柜的方法：保险柜代码由数字组成，并且没有前导零。还有一个特殊提示，可用于打开保险箱。提示是具有以下结构的字符串s：
如果si ='?'，则安全代码中排在第i位的数字可以是任何数字（0到9之间，包括0和9）。
如果si是一个数字（介于0到9之间，包括0和9之间），则表示代码中的位置i上存在数字si；
如果字符串包含从“A”到“J”的字母，则所有具有相同字母的位置必须包含相同的数字，而具有不同字母的位置必须包含不同的数字。
安全代码的长度与提示的长度一致。
例如，提示“?FF2”与之匹配的安全代码有:"1222","3552"等，而此时不匹配的:"5669","3232"
Input
多组输入，第一行包含字符串s表示安全代码的提示。 字符串s由以下字符组成：'?'，0-9，A-J。 确保字符串s的第一个字符不等于字符'0'。(1≤| s | ≤100000)，字符串中不包含逗号、单引号和冒号。
Output
打印与给定提示匹配的代码数。行末换行。
Sample Input
AJ
1?AA
Sample Output
81
100

solution

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
bool vis[12] = {0};
int cnt = 0,num0=0;
inline int deal(char x) {
    if (x == &#39;?&#39;) {
        ++num0;
        return 1;
    } else if (x >= &#39;0&#39; && x <= &#39;9&#39;)
        return 1;
    else if (x >= &#39;A&#39; && x <= &#39;J&#39;) {
        if (vis[x - &#39;A&#39;])
            return 1;
        else {
            ++cnt;
            vis[x - &#39;A&#39;] = 1;
            return (10 - cnt + 1);
        }
    }
}
int dealf(char x) {
    if (x == &#39;?&#39;)
        return 9;
    else if (x > &#39;0&#39; && x <= &#39;9&#39;)
        return 1;
    else if (x >= &#39;A&#39; && x <= &#39;J&#39;) {
        ++cnt;
        vis[x - &#39;A&#39;] = 1;
        return 9;
    }
}
int main() {
    string str;
    while (cin >> str) {
        cnt = 0;
        num0=0;
        int n = str.size();
        memset(vis, 0, sizeof(vis));
        LL ans = dealf(str[0]);
        for (int i = 1; i < n; i++) {
            ans *= deal(str[i]);
        }
        cout << ans ;
        for(int i=0; i<num0; i++) {
            printf("0");
        }
        cout<<endl;
    }
    return 0;
}

07 map的灵活使用

Problem Description
有一个跨时代的游戏定义了如下规则，当游戏结束后，只有一位得分最高的玩家时，那么他是赢家。在游戏过程中，每个回合，某一玩家会获得或失去特定分数，分数是在这一回合中获得或失去的分数并且是个整数。 如果游戏结束后，有多名玩家同时拥有最高分数，最先得到最高分数的玩家将获胜。起初，每个玩家都为0分。 确保在游戏结束时至少一名玩家的得分为正。
Input
多组输入，第一行包含一个整数n（1≤n≤1000），n是回合数。 然后跟随n行，按时间顺序包含名称name和得分score的回合信息，其中name保证小写，长度1到32，(-1000<=score<=1000)。
Output
打印获胜者的名字。行末换行。
Sample Input
3
tom 3
jerry 5
tom 2
3
tom 3
tom 2
jerry 5
Sample Output
jerry
tom

solution

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
typedef long long ll;
using namespace std;
struct node{
    string name;
    ll score;
} a[1005];
int main(){
    int n;
    while (cin >> n){
        map<string, ll> mp;
        for (int i = 0; i < n; i++){
            cin >> a[i].name >> a[i].score;
            mp[a[i].name] += a[i].score;
        }
        ll goal= -1000005;
        for(map<string,ll>::iterator it=mp.begin(); it!=mp.end(); ++it){
            if (it->second > goal)
                goal = it->second;
        }
        map<string, ll> t;
        for (int i = 0; i < n; i++){
            t[a[i].name] += a[i].score;
            if (t[a[i].name] >= goal&&mp[a[i].name]>=goal){
                cout << a[i].name << endl;
                break;
            }                                                                                               
        }
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(){
    string name[1001];
    int i,m,n,score[1001];
    map<string,int>p,t;
    while(cin>>n){
        p.clear();
        t.clear();
        m=0;
        for(i=0;i<n;i++)
        cin>>name[i]>>score[i],p[name[i]]+=score[i];
        for(i=0;i<n;i++)
        m=max(m,p[name[i]]);
        for(i=0;p[name[i]]<m||(t[name[i]]+=score[i])<m;i++);
        cout<<name[i]<<endl;
    }
    return 0;
}

```