2021牛客寒假算法基础集训营3
https://ac.nowcoder.com/acm/contest/9983#question
F-匹配串：字符串模拟
大意：题目给出n的模式串，模式串中有#字符，#字符可以是任意字符串或字符或空串，问有多少种匹配串和所有的模式串匹配。
思路：很明显只有两种答案，无穷多个和0个，其次可以发现两个模式串能够被同一匹配串匹配只会受到模式串第一个#字符前的字符串和最后一个#字符后的字符串的影响，假设n个模式串第一个#前的字符串分别为s1,s2...sn,其中sn最长，则其余都是sn的前缀，那就是无穷，否则就是0个。
别光看，多动笔画画就知道了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 5000005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
using namespace std;
string s,s1="",s2="";
bool check()
{
for(int i = 0; i < s.size(); i++){
if(s[i] == '#') break;
if(i >= s1.size()) s1 += s[i];
else if(s[i] != s1[i]) return false;
}
for(int i = s.size()-1,j = 0; i >= 0; i--,j++){
if(s[i] == '#') break;
if(j >= s2.size()) s2 += s[i];
else if(s[i] != s2[j]) return false;
}
return true;
}
void solve()
{
int n,flag = 0;
scanf("%d",&n);
for(int i = 1; i <= n; i++){
cin >> s;
if(i == 1){
for(int i = 0; i < s.size(); i++){
if(s[i] != '#') s1 += s[i];
else break;
}
for(int i = s.size()-1; i >= 0; i--){
if(s[i] != '#') s2 += s[i];
else break;
}
// cout << s1 << " " << s2 << endl;
}
else {
if(!check()){
flag = 1;
}
}
}
if(!flag) printf("-1");
else printf("0");
}
int main()
{
solve();
return 0;
} G-糖果：并查集
大意：有n个小朋友，m对关系，老师给n个小朋友发糖果，每个小朋友至少要ai个糖果，并且如果他的朋友有比他多的糖果，他就会不高兴，问老师至少要准备多少个糖果才会让所有的小朋友都不会不高兴。
思路：用并查集将m对关系连成块，取块能要糖果最多的作为这个块内分发给小朋友的糖果数。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 5000005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
using namespace std;
int n,m;
int a[N],f[N],size[N],cnt[N];
int find(int x)
{
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
void merge(int x,int y)
{
x = find(x);
y = find(y);
if(x != y){
size[x] += size[y];
cnt[x] = max(cnt[f[x]],cnt[f[y]]);
f[y] = x;
}
}
void solve()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) f[i] = i,size[i] = 1;
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
cnt[i] = a[i];
}
for(int i = 1; i<= m; i++){
int u,v;
scanf("%d%d",&u,&v);
merge(u,v);
}
ll ans = 0;
for(int i = 1; i <= n; i++){
if(f[i] == i){
ans += size[i]*cnt[i];
//cout << size[i] << " " << cnt[i] << endl;
}
}
printf("%lld\n",ans);
}
int main()
{
solve();
return 0;
} I-序列的美观度：动态规划
大意：给定一个长度为m的字符串s，定义序列的美观度为有多少个整数i，满足si=si+1。问字符串s的子序列中美观度最大是多少。
思路：问的是子序列，也就是对于每个字符可删可不删，两种选择，又是求最值，一定要往动态规划方面想。
找状态：dp[i] 表示前i个字符子序列构成的最大美观度。
状态转移：这道题有点不一样，我们考虑的不是第i个字符删不删，而是第i个字符和最靠近第i个字符并且和第i个字符直接的字符串删不删。
如果前面存在，dp[i] = max(dp[mp[x]]+1,dp[i-1])
不存在 dp[i] = dp[i-1]
赋初值：dp[1] = 0,长度最少为2才可能有美观度。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 5000005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
using namespace std;
map<int,int>mp;
int dp[N];
void solve()
{
int n,x;
cin >> n;
dp[1] = 0;
cin >> x;
mp[x] = 1;
for(int i = 2; i<= n; i++){
cin >> x;
dp[i] = dp[i-1];
if(mp[x]){
dp[i] = max(dp[i-1],dp[mp[x]]+1);
}
mp[x] = i;
}
cout << dp[n];
}
int main()
{
solve();
return 0;
} J-加法和乘法：博弈
https://ac.nowcoder.com/acm/contest/9983/J 大意：牛牛和牛妹做游戏，桌面上有n张牌，可以执行两个操作，1）如果桌面上只有一张牌，牌上的数字是奇数，牛牛赢，偶数则牛妹赢。2）桌面上有2张或以上牌，执行操作者取其中两张牌，操作者对着两张牌上的数字可以进行相加或相乘，把结果写在另外一张新牌上，并把这两张牌从剩下的牌中删去。牛牛先手，问最后谁会赢。
思路：首先要知道的，偶+偶=偶，偶*奇=偶，奇+奇=偶，所以如果最后只剩两张牌并且是牛妹执行操作，不管这两张牌的奇偶性如何，最后牛妹都能把结果能成偶数。
然后就是考虑牛牛最后执行操作结果如何。多列几组数据可以发现只要n个整数有至少两个偶数，牛妹一定能赢，否则牛牛赢。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <string.h>
#include <cmath>
#include <bitset>
#include <set>
#include <map>
#include <list>
#define ull unsigned long long
#define ll long long
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 5000005;
const ll ds = 1e15+7;
const double p1 = 3.141592653589793238462643383;
using namespace std;
int a[N];
void solve()
{
int n;
cin >> n;
int cnt = 0;
for(int i =1; i <= n; i++){
cin >> a[i];
if(!(a[i]&1)) cnt++;
}
if(n == 1){
if(a[1]&1) cout << "NiuNiu";
else cout <<"NiuMei";
}
else{
if(cnt == n) cout << "NiuMei" ;
else{
if(n&1) cout << "NiuMei";
else{
if(cnt >= 2){
cout << "NiuMei";
}
else cout << "NiuNiu";
}
}
}
}
int main()
{
solve();
return 0;
} 
