腾讯3.31笔试，第一次ak纪念一下hh

//第一题 所有边都为红色

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int main() {
  int n, m, a, b;
  char ch;
  cin >> n >> m;

vector<vector<pii>>g(n + 1);
for (int i = 0; i < m; i++) {
    cin >> a >> b >> ch;
    if (ch == 'W') {
        g[a].push_back({b, 0});
        g[b].push_back({a, 0});
    } else {
        g[a].push_back({b, 1});
        g[b].push_back({a, 1});
    }
}

int c = 0, s;
for (int j = 1; j <= n; j++) {
    s = 0;
    for (auto [x, y] : g[j])s += y;

    if (s == g[j].size())c++;
}
cout << c << endl;
}

//第二题 可翻转一次变成升序的链表/**

class Solution {
public:
/*代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可@param lists ListNode类vector@return bool布尔型vector
*/

vector<bool> canSorted(vector<ListNode>& lists) {
// write code here
vector<bool>r;
for (ListNode* l : lists)r.push_back(f(l));
return r;
}
bool f(ListNode* node) {
  int x = 0;
  ListNode* p = node, *q = node->next;
  while (q) {if (p->val > q->val)x++;
  p = q;
  q = q->next;
   }
  
  if (x == 0)return true;
  else if (x == 1 && p->val < node->val)return true;
  return false;
 }
};

//第三题 加一条边使得图联通的方案数

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector<int>p;
int s;
int find(int x) {
  if (p[x] != x)p[x] = find(p[x]);
  return p[x];
}
void uite(int x, int y) {
  int px = find(x), py = find(y);
  if (px == py)return;
  else {
    p[px] = py;
    s--;}
}
int main() {int n, m;cin >> n >> m;
s = n;
p.resize(n);
iota(p.begin(), p.end(), 0);

int a, v;

for (int i = 0; i < m; i++) {
    cin >> a >> v;
    uite(a - 1, v - 1);
}

if (s != 2) {
    cout << 0 << endl;
    return 0;
}

vector<int>r;
for (int i = 0; i < n; i++)r.push_back(find(i));

int mi = *min_element(r.begin(), r.end());

long long c = 0;

for (int i : r) {

    if (i == mi)c++;

}
cout <<c*(n - c) << endl;
}// 64 位输出请用 printf("%lld")

//第四题 将数组分为k段 每段结果的最大和

#include <iostream>
#include<bits/stdc++.h>
#include <vector>
using namespace std;
int main() {int n, k;cin >> n >> k;

int a;
vector<long long>pre(n + 1);
for (int i = 0; i < n; i++) {
    cin >> a;
    pre[i + 1] = pre[i] ^ a;
}

//dp[i][k]代表截至i位置分为k段的最大和

vector<vector<long long>>dp(n, vector<long long>(k + 1, 0L));

for (int i = 0; i < n; i++) {
    dp[i][1] = pre[i + 1];
    dp[i][0] = INT_MIN;
}



for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
        for (int s = 1; s <= k; s++) {
            dp[i][s] = max(dp[i][s], dp[j][s - 1] + (pre[i + 1] ^ pre[j + 1]));
        }

    }
}
cout << dp[n - 1][k];
}// 64 位输出请用 printf("%lld")

//第五题 搜索字符串 "tencent" 的方案个数

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  string t = "tencent";
  vector<string>g(n);string s;
  for (int i = 0; i < n; i++) {cin >> s;g[i] = s;}

int ans = 0;

vector<int>dir = {1, 0, -1, 0, 1};
function<void(int, int, int)>dfs = [&](int i, int j, int step) {
    if (step == 6) {
        ans++;
        return;
    }
    for (int k = 0; k < 4; k++) {
        int ni = i + dir[k], nj = j + dir[k + 1];
        if (ni < 0 || ni >= n || nj < 0 || nj >= m || g[ni][nj] != t[step + 1])continue;
        dfs(ni, nj, step + 1);
    }
};

for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        if (g[i][j] == 't')dfs(i, j, 0);
    }

cout<<ans<<endl;
}// 64 位输出请用 printf("%lld")