思维题整理

我会带着你远行 2022-10-15 09:56 153阅读 0赞

### 文章目录 ###

*  其它博客
 *   *  CodeForce Deltix Round, Summer 2021 C. Compressed Bracket Sequence 思维 序列 模拟
     *  Code Forces contest1550 C Manhattan Subarrays 思维
     *  Codeforces Round \#746 (Div. 2)
     *  ICPC南京 A Adrien and Austin博弈论
 *  整理
 *   *  CodeForces-888c K-Dominant Character 字符串
     *  codeforces 883E Field of Wonders 字符串处理
     *  CodeForces 893C Rumor 并查集

# 其它博客 #

## CodeForce Deltix Round, Summer 2021 C. Compressed Bracket Sequence 思维 序列 模拟 ##

博客地址[【题目记录】——CodeForce Deltix Round, Summer 2021][CodeForce Deltix Round_ Summer 2021]

## Code Forces contest1550 C Manhattan Subarrays 思维 ##

博客地址[C Manhattan Subarrays 思维][C Manhattan Subarrays]  
题目地址[C Manhattan Subarrays][C Manhattan Subarrays 1]

## Codeforces Round \#746 (Div. 2) ##

[Codeforces Round \#746 (Div. 2)][Codeforces Round _746 _Div. 2]

## ICPC南京 A Adrien and Austin博弈论 ##

[ICPC南京][ICPC]

# 整理 #

## CodeForces-888c K-Dominant Character 字符串 ##

[CodeForces - 888C K-Dominant Character][]  
题意：找到一个最小的k值，使得每次取k长度的子串总有某一个特定字符被取到

题解：找相同字符最大间距的最小值。  
（还要注意 每种字符的第一个与字符串左端点的的距离 和 每种字符的最后一个与右端点的距离）

我交了好几次没过主要是因为lastP的初始值设置成了0，导致字符串中的某一个字符到字符串左端的距离计算不正确。  
比如 字符串ab的计算结果是1 但应该是2。  
aaabbb的计算结果是3 但应该是4。

#include <iostream>
    using namespace std;
    int a[200] = {  0 };
    int search(string str, char c)
    { 
    	if (a[c] == 0)
    	{ 
    		a[c] = 1;
    		int t = 0;
    		int p = -1, lastP = -1;//就是这个lastP的值一开始设置成了0
    		int leng = str.length();
    		while ((p = str.find(c,p+1)) != string::npos)
    		{ 
    			if (t < p - lastP)
    			{ 
    				t = p-lastP;
    			}
    			lastP = p;	//记录最后一个p值
    		}
    		if (t < leng - lastP)
    		{ 
    			t = leng - lastP;
    		}
    		return t;
    	}
    	return 100010;
    }
    
    int main()
    { 
    	string str;
    	cin >> str;
    	int res = 100010;
    	int t;
    	for (int i = 0; i < (int)str.length(); i++)
    	{ 
    		t = search(str, str[i]);
    		if (res > t)
    		{ 
    			res = t;
    		}
    	}
    	cout << res << endl;
    
    	return 0;
    }

## codeforces 883E Field of Wonders 字符串处理 ##

[codeforces 883E Field of Wonders ][codeforces 883E Field of Wonders]  
题意：游戏最开始整个字符串都是未知的，另一个玩家会在前面的回合里说出1个字符，主持人会把字符串中所有的这个字符的位置公布，轮到你了，此时字符串还有部分未知字符，然后给你 m 个长度为 n 的字符串，未知处字符一定在这 m 个字符串里面。问存在多少个字符一定可以让一个未知字符变成已知字符。

思路：注意给出的 m 个串中已知的部分竟然可以和给定的 S 字符串处不同，未知的部分也可能出现已知的字符，这两种情况提示字符串算是无效的。  
所以先把错误的字符串去掉，然后遍历 a~z 26 个字符，如果字符未知并且在正确的字符串中都出现过，则答案 +1 。

#include<stdio.h>
    #include<string.h>
    #include<iostream>
    #include<set>
    using namespace std;
     
    int main() 
    { 
    	int i,j,n,m,len,vis[1010];
    	char c[3],s[55],t[1010][55];
    	set<char> st; //保存已知的字符 
    	while(~scanf("%d",&n))
    	{ 
    		scanf("%s",s);
    		st.clear();
    		for(i=0;i<strlen(s);i++)
    			if(s[i]!='*') st.insert(s[i]); //保存已知字符 
    		scanf("%d",&m);
    		memset(vis,0,sizeof(vis)); //判断字符串是否正确 
    		for(i=0;i<m;i++)
    		{ 
    			scanf("%s",t[i]);
    			int f=1;
    			for(j=0;j<strlen(t[i]);j++)
    				if(s[j]=='*')
    				{  //如果未知处出现已知字符 
    					if(st.count(t[i][j]))
    					{ 
    						f=0;
    						break;
    					}
    				}
    				else if(s[j]!=t[i][j])
    				{  //如果已知处和 S 不相同 
    					f=0;
    					break;
    				}
    			if(f) vis[i]=1; //是正确的字符 
    		}
    		int ans=0;
    		for(i=0;i<26;i++)
    		{  //遍历所有字符 
    			c[0]='a'+i;
    			c[1]='\0';
    			if(st.count(c[0])) continue; //如果在 s中出现过 
    			int f=1;
    			for(j=0;j<m;j++)
    				if(vis[j]&&strstr(t[j],c)==NULL)
    				{  //如果当前字符串是正确的且不包含当前字符 
    					f=0;
    					break;
    				}
    			if(f) ans++;
    		}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

## CodeForces 893C Rumor 并查集 ##

是一道比较简单的并查集类题目，初学并查集，记录一下。  
[CodeForces 893C][]

题目大意：  
有n个人，其中有m对朋友，现在你有一个秘密你想告诉所有人，第i个人愿意出价a\[i\]买你的秘密，获得秘密的人会免费告诉它的所有朋友（他朋友的朋友也会免费知道），你最少要花多少钱告诉所有人这个秘密？

思路：  
利用并查集，把是朋友的放在同一个集合中，然后遍历所有的集合，把每个集合中最少的价格找出来，求出他们的和就是答案

我在这里是用每个集合的代表元对应的价格作为一个集合里的最低价格，最后遍历整个数组，判断是不是代表元，将所有代表元对应的价格加到一起就是最终答案了。  
代码如下：

#include <iostream>
    #include <cstring>
    #define N (int)1e5+10
    using namespace std;
    
    long val[N];    //存储每个人要的价格
    int pre[N];     //每个元素的前驱结点
    void join(int,int);    //合并两个集合
    int find(int);  //找到每个元素的根节点
    long min(int a, int b);
    
    int main()
    { 
        long long sum = 0;
        int n, m;
        cin >> n >> m;
    
        for (int i = 1; i <= n; i++)    //读入价钱
        { 
            pre[i] = i;
            cin >> val[i];
        }
        while (m--)                     //读入朋友关系
        { 
            int a, b;
            cin >> a >> b;
            join(a, b);
        }
    
        for (int i = 1; i <= n; i++)    //求出每组的最小值
        { 
            int rt = find(i);
            val[rt] = min(val[rt], val[i]);
        }
        for (int i = 1; i <= n; i++)    //将每组的最小值相加
        { 
            if (i == find(i))
            { 
                sum += val[i];
            }
        }
        cout << sum << endl;
        return 0;
    }
    
    //int find(int x) //用循环会超时，
    //{ 
    // while (pre[x] != x)
    // { 
    // x = pre[x];
    // }
    // return x;
    //}
    int find(int x)		//用递归不会超时
    { 
        if (x == pre[x])
            return x;
        else
        { 
            pre[x] = find(pre[x]);
            return pre[x];
        }
    }
    void join(int a,int b)
    { 
        int fa = find(a);
        int fb = find(b);
        if (fa != fb)
        { 
            pre[fa] = fb;
        }
    }
    
    long min(int a, int b)
    { 
        if (a <= b)
        { 
            return a;
        }
        else
        { 
            return b;
        }
    }

[CodeForce Deltix Round_ Summer 2021]: https://blog.csdn.net/qq_45488453/article/details/120595137
[C Manhattan Subarrays]: https://blog.csdn.net/qq_45488453/article/details/120511662
[C Manhattan Subarrays 1]: https://codeforces.com/contest/1550/problem/D
[Codeforces Round _746 _Div. 2]: https://blog.csdn.net/qq_45488453/article/details/120649619
[ICPC]: https://blog.csdn.net/qq_45488453/article/details/120655351
[CodeForces - 888C K-Dominant Character]: https://codeforces.com/problemset/problem/888/C
[codeforces 883E Field of Wonders]: https://codeforces.com/problemset/problem/883/E
[CodeForces 893C]: https://codeforces.com/problemset/problem/893/C