1519

yxc的小迷妹

TralSun

LD_64

lscll
NLER

fighting_HZ

#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;
}


an=max(a1,a2,…,an)，bn=max(b1,b2,…,bn)。

# 先上代码

#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;
}


# 改进代码，成功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!

## 输入格式

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.

## 输出格式

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


# 思路

### 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;
}


# 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进制的数，那么这个数就是这个串的哈希值；则我们通过比对每个串的的哈希值，即可判断两个串是否相同

# 村村通

## 样例 #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


# 思路

## 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;
}