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

using namespace std;

int main () {
    string s;
    cin >> s;
    if (s[0] >= 'A' and s[0] <= 'Z')
        cout << s[0];
    else
        cout << (char)(s[0] - 32);
    for (int i = 1; i < s.size(); i ++ )
        cout << s[i];
}

//看到处理区间段基本就差分了
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int b[N];

int main()
{
    scanf("%d%d", &n, &m);

    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        b[l] ++, b[r + 1] -- ;
    }

    for (int i = 1; i <= n; i ++ )
    {
        b[i] += b[i - 1];
        if (b[i] != 1)
        {
            printf("%d %d\n", i, b[i]);
            return 0;
        }
    }

    puts("OK");

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int T;
int a[20];

int main() {
    cin >> T;

    while (T --) {
        int n; cin >> n;

        int ans = 0;
        while (n) { // 存储数位
            a[ans ++] = n % 10;
            n /= 10;
        }

        int res = 0;
        for (int i = 0; i < ans; i ++) 
            if (a[i] != 0) res ++, a[i] *= pow(10, i);

        cout << res << endl;
        for (int i = 0; i < ans; i ++) 
            if (a[i] != 0) cout << a[i] << ' ';
        cout << endl;
    }

    return 0;
}

给定两个数组 a1,a2,…,an 和 b1,b2,…,bn。

在一次操作中，你可以选择任意一个整数 i，其中 1≤i≤n，并交换 ai 和 bi。

确定在使用任意（可能为零）次操作后，是否可以同时满足以下两个条件：

an=max(a1,a2,…,an)，bn=max(b1,b2,…,bn)。
其中 max(c1,c2,…,ck) 表示 c1,c2,…,ck 中的最大数。例如，max(3,5,4)=5，max(1,7,7)=7，max(6,2)=6。

输入
每个测试包含多个测试用例。第一行包含测试用例的数量 t（1≤t≤200）。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 n（1≤n≤100）——数组的长度。

每个测试用例的第二行包含 n 个整数 a1,a2,…,an（1≤ai≤100）——第一个数组的元素。

每个测试用例的第三行包含 n 个整数 b1,b2,…,bn（1≤bi≤100）——第二个数组的元素。

输出
对于每个测试用例，如果使用任意（可能为零）次操作后满足上述条件，则打印“Yes”。否则，打印“No”。

你可以以任何形式输出答案（大写或小写）。例如，字符串“yEs”、“yes”、“Yes”和“YES”将被识别为正面回应。

先上代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;

bool check(vector<int> a, vector<int> b)
{
    int max_a = *max_element(a.begin(), a.end()); // a 中的最大值
    int max_b = *max_element(b.begin(), b.end()); // b 中的最大值

    return (a[n - 1] == max_a && b[n - 1] == max_b);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;

        vector<int> a(n), b(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) cin >> b[i];

        bool ok = false;
        for (int i = 0; i < n; ++i) {
            int t1 = a[i], t2 = b[i];
            a[i] = t2, b[i] = t1;
            if (check(a, b)) {
                ok = true;
                break;
            }
            if (a[i] > a[n - 1] || b[i] > b[n - 1]) a[i] = t1, b[i] = t2;
        }

        if (ok) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

不出意外WA了

改进代码，成功AC

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n;

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;

        vector<int> a(n), b(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) cin >> b[i];

        bool ok = false;
        for (int i = 0; i < n; ++i) {
            int t1 = a[i], t2 = b[i];
            if (a[i] > a[n - 1] || b[i] > b[n - 1]) 
            {
                a[i] = t2, b[i] = t1;
            }
            if (a[i] > a[n - 1] || b[i] > b[n - 1]) 
            {
                a[i] = t1, b[i] = t2;
            }
        }

        int max_a = *max_element(a.begin(), a.end()); // a 中的最大值
        int max_b = *max_element(b.begin(), b.end()); // b 中的最大值
        if (a[n - 1] == max_a && b[n - 1] == max_b) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

[USACO16DEC]Cities and States S

题目描述

To keep his cows intellectually stimulated, Farmer John has placed a large map of the USA on the wall of his barn. Since the cows spend many hours in the barn staring at this map, they start to notice several curious patterns. For example, the cities of Flint, MI and Miami, FL share a very special relationship: the first two letters of “Flint” give the state code (“FL”) for Miami, and the first two letters of “Miami” give the state code (“MI”) for Flint.

Let us say that two cities are a “special pair” if they satisfy this property and come from different states. The cows are wondering how many special pairs of cities exist. Please help them solve this amusing geographical puzzle!

为了训练奶牛们的智力，Farmer John 在谷仓的墙上放了一张美国地图。由于奶牛在谷仓里花了很多时间看这张地图，他们开始注意到一些奇怪的关系。例如，Flint 的前两个字母就是 Miami 所在的 FL 州，Miami 的前两个字母则是 Flint 所在的 MI 州。
确切地说，对于两个城市，它们的前两个字母互为对方所在州的名称。

我们称两个城市是一个一对“特殊的”城市，如果他们具有上面的特性，并且来自不同的省。奶牛想知道有多少对“特殊的”城市存在。请帮助他们解决这个有趣的地理难题！

输入格式

The first line of input contains $N$ ($1 \leq N \leq 200,000$), the number ofcities on the map.

The next $N$ lines each contain two strings: the name of a city (a string of at least 2 and at most 10 uppercase letters), and its two-letter state code (a string of 2 uppercase letters). Note that the state code may be something like ZQ, which is not an actual USA state. Multiple cities with the same name can exist, but they will be in different states.

第一行一个正整数 $N$，表示地图上的城市的个数。
接下来 $N$ 行，每行两个字符串，分别表示一个城市的名称（$2 \sim 10$个大写字母）和所在州的代码（$2$ 个大写字母）。可能出现类似 ZQ 的州代码，即并不真的是美国的一个州的代码。同一个州内不会有两个同名的城市。

输出格式

Please output the number of special pairs of cities.

输出特殊的城市对数。

样例 #1

样例输入 #1

6
MIAMI FL
DALLAS TX
FLINT MI
CLEMSON SC
BOSTON MA
ORLANDO FL

样例输出 #1

1

此使用两种方法，第一种照顾不熟悉map的

一，数组模拟

思路

因为题目可知我们只需要数组前两位即可，参考洛谷大佬思路，把字符串转化为26进制的数来储存，对于每个城市和省份我们让他的正序加一（因为我们要寻找配对，即该正序的倒序）每次让记录数加上倒序值（因为配对每个数只有一个倒序，所以保证了倒序即为该数的配对数）

AC代码

#include <iostream>

using namespace std;

int city[676][676], n, x, y, ans;//x表示城市前两个字母的26进制下的数，y是省份的。数相等则对应的省的两个字母和城市的前两个字母就相等。
int main() {
    string a, b;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        x = (a[0] - 'A') * 26 + a[1] - 'A';//不减的话数据太大，数组开不了那么大（map的优势） 
        y = (b[0] - 'A') * 26 + b[1] - 'A';
        if (x != y) {//x==y的话如果要配对的话只会配到自己省。题目说了不在同一省，所以要排除。
            city[x][y]++;
            ans += city[y][x];
        }
    }
    cout<<ans;
    return 0;
}

map写法

AC代码

#include <iostream>
#include <map>

using namespace std;

map<int,int>mmp[100005];

int n,ans;

int main()
{
    cin>>n;
    for(int i = 1; i <= n; i ++){
        string a,b;
        cin >> a >> b;
        int A = a[0] * 26 + a[1];
        int B = b[0] * 26 + b[1];
        if(A != B)
        mmp[A][B] ++;
        ans += mmp[B][A];
    }
    printf("%d",ans);
    return 0;
}

觉得还不错给个赞吧！！！！

HASH合集

1.进制哈希

进制哈希的核心便是给出一个固定进制base，将一个串的每一个元素看做一个进制位上的数字，所以这个串就可以看做一个
base进制的数，那么这个数就是这个串的哈希值；则我们通过比对每个串的的哈希值，即可判断两个串是否相同

村村通

题目描述

某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 “村村通工程” 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路？

输入格式

输入包含若干组测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目 $n$ 和道路数目 $m$ ；随后的 $m$ 行对应 $m$ 条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从 $1$ 到 $n$ 编号。

注意：两个城市间可以有多条道路相通。

在输入数据的最后，为一行一个整数 $0$，代表测试数据的结尾。

输出格式

对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。

样例 #1

样例输入 #1

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

样例输出 #1

1
0
2
998

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \le n < 1000$ 。

日常水题刷自信

思路

简单的并查集，题目要求输出还需要修建的路，所以用res记录一下已经修建的路即可，再输出(n - 1 - res),n-1根据抽屉原理，而输入数据中可能会有重复，特判即可

AC代码

#include <iostream>

using namespace std;

const int N = 5010;
int p[N];

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    while(true)
    {
        int res = 0;
        int n, m;
        cin >> n;
        if (!n) break;
        cin >> m;
        for(int i = 1; i <= n; i ++) p[i] = i;

        while(m-- )
        {
            int x, y;
            cin >> x >> y;
            int a = find(x), b = find(y);
            if (a != b) 
            {
                p[a] = b;
                res ++;
            }
        }
        cout << (n - 1 - res) << endl;
    }
    return 0;
}

// 枚举和A只有一位不同的数，减少计算量
// 用哈希表存数据，
// 进制转化采用秦九韶算法（该不仅仅包括进制转化，还有1元N次多项式求解等等）
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

int base(string s, int b)
{
    int res = 0;
    for (auto x: s)
        res = res * b + x - '0';
    return res;
}

int main()
{
    string x, y;
    cin >> x >> y;

    unordered_set<int> hash;
    for (int i = 0; i < x.size(); i ++ )
    {
        string s = x;
        s[i] ^= 1;
        if (s.size() > 1 && s[0] == '0') continue;
        hash.insert(base(s, 2));
    }

    for (int i = 0; i < y.size(); i ++ )
        for (int j = 0; j < 3; j ++ )
            if (y[i] - '0' != j)
            {
                string s = y;
                s[i] = j + '0';
                if (s.size() > 1 && s[0] == '0') continue;
                int n = base(s, 3);
                if (hash.count(n))
                    cout << n << endl;
            }

    return 0;
}

#include <iostream>

using namespace std;

const int N = 30010;
int d[N], p[N], sz[N];

int find(int x)
{
    if (x != p[x]) 
    {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}

int main()
{
    for(int i = 1; i <= N; i ++)
    {
        p[i] = i;
        sz[i] = 1;
    }
    int t;
    cin >> t;
    while(t --)
    {
        char op;
        int x, y;
        cin >> op >> x >> y;
        int a = find(x), b = find(y);
        if (op == 'M')
        {
            if (a != b)
            {
                d[a] = sz[b];
                sz[b] += sz[a];
                p[a] = b;
            }
        }
        else
        {
            if (a != b) puts("-1");
            else printf("%d\n", max(0, abs(d[x] - d[y]) - 1));
        }
    }
}

待补充题解

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

using namespace std;

const int N = 12, M = 1 << N;
long long f[N][M];
int st[M];
int n, m;

int main()
{
    while(cin >> n >> m, n || m)
    {
        for(int i = 0; i < 1 << n; i ++)//枚举状态, 1 << n == 2的n次方
        {
            int cnt = 0;
            st[i] = true;
            for(int j = 0; j < n; j ++)//判断空位偶数0，偶数为合法
            {
                if (i >> j & 1)
                {
                    if (cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else 
                {
                    cnt ++;
                }
            }
            if (cnt & 1) st[i] = false;
        }

        memset(f, 0, sizeof f);//初始化数组
        f[0][0] = 1;//默认第0列竖放为合法状态
        for(int i = 1; i <= m; i ++)//枚举每列
        {
            for(int j = 0; j < 1 << n; j ++)//枚举第i列的状态
            {
                for(int k = 0; k < 1 << n; k ++)//枚举第i - 1列的状态
                {
                    if ( (j & k) == 0 && st[j | k])
                    {
                        f[i][j] += f[i - 1][k];//判断是否重叠以及合并列的合法性
                    }
                }
            }
        }
        cout << f[m][0] << endl;
    }

    return 0;
}